Random number generator code improvement
Moderator: Forum Moderators
-
- Posts: 10
- Joined: April 27th, 2010, 9:29 pm
Random number generator code improvement
Two questions about random number generation:
Why does the random number generator store call_count instead of the seed?
Why doesn't it use a decent random number generator, like the mersenne twister. It's available in boost, and is also standard C++0x.
Why does the random number generator store call_count instead of the seed?
Why doesn't it use a decent random number generator, like the mersenne twister. It's available in boost, and is also standard C++0x.
-
- Posts: 10
- Joined: April 27th, 2010, 9:29 pm
Re: Random number generator code improvement
On closer inspection, both simple_rng.hpp:: random_seed_, and random_calls_ can be safely removed. Only random_pool_ has to be saved/stored/etc.
I noticed that boost is not included. Is there an aversion to using boost.random? It would be a drop-in replacement for simple_rng.hpp.
If there's interest, I could submit a patch.
I noticed that boost is not included. Is there an aversion to using boost.random? It would be a drop-in replacement for simple_rng.hpp.
If there's interest, I could submit a patch.
Re: Random number generator code improvement
If you scroll down the page you'll find a (locked) topic about mersenne twister. Here's a link to make it even easier. In future, please use the forum search functionality...
If you want to talk to the coder's on the project, you are probably better off hanging out on the main IRC channel (some details here).
If you want to talk to the coder's on the project, you are probably better off hanging out on the main IRC channel (some details here).
Re: Random number generator code improvement
Last time, I didn't weigh in much, because I didn't know much about the rand() libc function.
Now that I do, I do think that using a Mersenne twister would be an improvement over libc rand(), simply because you know what its properties are.
From the other thread:
Regardless, even if modern C implementations have a passable version of
Of course, while I think the Mersenne Twister would be an improvement, I do not think it will matter in any noticeable way - for the most part,
Now that I do, I do think that using a Mersenne twister would be an improvement over libc rand(), simply because you know what its properties are.
From the other thread:
This is only partially true. C implementers aren't really known for high quality standard library functions - they're usually optimized for compatibility more than anything else. For instance, no one actually expects you to use libc's buffer-unsafeDave wrote:rand() is not an algorithm. rand() is a standard C function that is implemented using an algorithm. There was a time when some C implementors used fairly poor algorithms to implement rand(), but these days all the C implementations that I'm aware of use sophisticated implementations that work very well.
I'm not sure why anyone would think that C platform vendors would intentionally choose a very poor algorithm to implement rand(), but it appears to be a common misconception. By contrast, most vendors try to make the quality of their C implementation as good as possible, and so implement a RNG that works as well as possible on their target hardware.
strcpy
or even strncpy
; you're supposed to use strlcpy
. It's only a bit of an exaggeration to say the only libc functions you're actually expected to use are malloc
and free
(and only if you're actually writing C and not a C-based language like C++).Regardless, even if modern C implementations have a passable version of
rand
, it's easier to guarantee that the PRNG you're using has the right properties (combination of speed, memory usage, quality) that you want. And plus, it ensures that no matter what compiler a user is using, the resulting PRNG will still work well.Of course, while I think the Mersenne Twister would be an improvement, I do not think it will matter in any noticeable way - for the most part,
rand
is enough, and if you think you can feel the difference without using statistical analysis tools, you're wrong and a true random number generator won't feel any different.Proud creator of the :whistle: smiley | I prefer the CC-0 license.
-
- Retired Developer
- Posts: 1086
- Joined: September 16th, 2005, 5:44 am
- Location: Hamburg, Germany
Re: Random number generator code improvement
Not sure about the first question. I am right now refactoring the rng mechanics for the experimental corner wesnoth (see the corresponding subforum). I will take a look at that shortly.mistersheik wrote:Two questions about random number generation:
Why does the random number generator store call_count instead of the seed?
Why doesn't it use a decent random number generator, like the mersenne twister. It's available in boost, and is also standard C++0x.
About mersenne twister and boost: Wesnoth using boost is relatively new, so it's not like we don't want to replace it but rather that noone thought it urgent enough to do it. Also, from a statistical point of view, for a game like wesnoth a standard rng is more than good enough. People have issues about its influence on gameplay, but that's a completely different story and switching to mersenne twister wouldn't change anything regarding that.
Smart persons learn out of their mistakes, wise persons learn out of others mistakes!
Re: Random number generator code improvement
Nonsense. Firstly rand() is a commonly used C function. It doesn't have any analogue or replacement in C++98.Zarel wrote:This is only partially true. C implementers aren't really known for high quality standard library functions - they're usually optimized for compatibility more than anything else. For instance, no one actually expects you to use libc's buffer-unsafeDave wrote:rand() is not an algorithm. rand() is a standard C function that is implemented using an algorithm. There was a time when some C implementors used fairly poor algorithms to implement rand(), but these days all the C implementations that I'm aware of use sophisticated implementations that work very well.
I'm not sure why anyone would think that C platform vendors would intentionally choose a very poor algorithm to implement rand(), but it appears to be a common misconception. By contrast, most vendors try to make the quality of their C implementation as good as possible, and so implement a RNG that works as well as possible on their target hardware.strcpy
or evenstrncpy
; you're supposed to usestrlcpy
. It's only a bit of an exaggeration to say the only libc functions you're actually expected to use aremalloc
andfree
(and only if you're actually writing C and not a C-based language like C++).
Also, implementations such as glibc rather heavily optimize the string functions. Try benchmarking, say, strlen() against your own implementation and you'll likely see your standard library implementation is much faster.
Not using rand() because there exist functions such as strcpy() is a bizarre argument.
David
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
Re: Random number generator code improvement
From what I hear, most people use mt_rand or some more sophisticated RNG if they're looking for really random numbers. rand is only used when the randomness isn't all that important. Sure, in most applications, randomness isn't all that important, so rand is "good enough", but there's no denying that using a more suitable PRNG is better.Dave wrote:Nonsense. Firstly rand() is a commonly used C function. It doesn't have any analogue or replacement in C++98.
For as good as rand supposedly is, I've still seen situations where people get the same "random" numbers each time they run a program because rand didn't seed itself. Most people recommend seeding with the time. If rand were as good an RNG as you claim, it wouldn't be seeded by anything so cryptographically insecure as the time rounded to the nearest second.
"No optimization can make strlen fast for significantly large inputs, so storing the length of strings is generally the recommended fix. It is also possible to merge the length measurement into another O(n) function such as copying the string, strlcpy is an example." (Wikipedia)Dave wrote:Also, implementations such as glibc rather heavily optimize the string functions. Try benchmarking, say, strlen() against your own implementation and you'll likely see your standard library implementation is much faster.
strlen may be fast, but it's not as fast as rewriting your code not to need strlen in the first place. Pascal strings work decently in that regard. I admit I haven't tried benchmarking it, but I'd still wager that my O(1) implementations at least as fast as libc strlen.
Anything can be made to seem bizarre if you skip all the steps in between.Dave wrote:Not using rand() because there exist functions such as strcpy() is a bizarre argument.
Proud creator of the :whistle: smiley | I prefer the CC-0 license.
Re: Random number generator code improvement
Well the thing is, randomness really isn't all that important in Wesnoth, comparatively speaking. Implementing Mersenne Twister won't make the arguments go away, though it may make a few people happy for a time. Personally I think the approach more likely to make people happy will be the implementation of a quasi-random number generator, or a shuffle bag as I described in this other post.Zarel wrote:From what I hear, most people use mt_rand or some more sophisticated RNG if they're looking for really random numbers. rand is only used when the randomness isn't all that important. Sure, in most applications, randomness isn't all that important, so rand is "good enough", but there's no denying that using a more suitable PRNG is better.Dave wrote:Nonsense. Firstly rand() is a commonly used C function. It doesn't have any analogue or replacement in C++98.
For as good as rand supposedly is, I've still seen situations where people get the same "random" numbers each time they run a program because rand didn't seed itself. Most people recommend seeding with the time. If rand were as good an RNG as you claim, it wouldn't be seeded by anything so cryptographically insecure as the time rounded to the nearest second.
I'm sure you are already aware that Mersenne Twister is also very poor for cryptography purposes by default, so being cryptographically insecure doesn't have much to do with being a "good" PRNG.
Re: Random number generator code improvement
It will make the Mersenne Twister threads go away, though, which I think is worth it. It's not like there's anything wrong with it.lmelior wrote:Well the thing is, randomness really isn't all that important in Wesnoth, comparatively speaking. Implementing Mersenne Twister won't make the arguments go away, though it may make a few people happy for a time.
afaict, those all seem inferior to a true PRNG like Mersenne Twister.lmelior wrote:Personally I think the approach more likely to make people happy will be the implementation of a quasi-random number generator, or a shuffle bag as I described in this other post.
True. I never said MT was a good RNG. Just sayin' it can't be worse than libc rand.lmelior wrote:I'm sure you are already aware that Mersenne Twister is also very poor for cryptography purposes by default, so being cryptographically insecure doesn't have much to do with being a "good" PRNG.
Proud creator of the :whistle: smiley | I prefer the CC-0 license.
-
- Posts: 10
- Joined: April 27th, 2010, 9:29 pm
Re: Random number generator code improvement
I don't know where wikipedia got the table, but under C++0x, they have:
Class template: Quality, Speed
linear_congruential: Medium, Medium
subtract_with_carry: Medium, Fast
mersenne_twister: Good, Fast
Someone at the standards committee thinks that mersenne twister gives higher quality random numbers than the default linear congruential generator. I always took that for granted.
Anyway, if someone is rewriting the random number stuff, the file simple_rng.h should really just be replaced with an include to boost's random number library and a typedef to any one of the random number generators. Storage of the state, which is right now done by storing the original seed and the number of times the rng has been sampled (which is crazy since you can just store the running state) can be replaced with boosts stream operators (serialize to strstream, and store the resulting string.)
Also, there is essentially a global random number generator stack being implemented by a class set_rng or something like that... It probably makes more sense to just pass the random number generator object by const reference instead of using global variables.
Class template: Quality, Speed
linear_congruential: Medium, Medium
subtract_with_carry: Medium, Fast
mersenne_twister: Good, Fast
Someone at the standards committee thinks that mersenne twister gives higher quality random numbers than the default linear congruential generator. I always took that for granted.
Anyway, if someone is rewriting the random number stuff, the file simple_rng.h should really just be replaced with an include to boost's random number library and a typedef to any one of the random number generators. Storage of the state, which is right now done by storing the original seed and the number of times the rng has been sampled (which is crazy since you can just store the running state) can be replaced with boosts stream operators (serialize to strstream, and store the resulting string.)
Also, there is essentially a global random number generator stack being implemented by a class set_rng or something like that... It probably makes more sense to just pass the random number generator object by const reference instead of using global variables.
Re: Random number generator code improvement
Making 2 or 3 threads go away is very easy and requires no coding experience. Development decisions should be driven by logic, not by forum annoyances. Logical questions are those such as: is anyone really going to submit a patch for this? if so, are they really going to take the time to test for multiplayer OOS and/or savegame corruption? Finally, will it increase the size of the binary or increase build times? Do the potential benefits even outweigh the time it takes to properly review and commit such a change?Zarel wrote: It will make the Mersenne Twister threads go away, though, which I think is worth it. It's not like there's anything wrong with it.
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."
Re: Random number generator code improvement
Inferior in terms of true randomness, yes, but if you follow the shuffle bag link I posted you'll see that the author argues that a less random approach will "feel right" to most people. True random means you can miss a unit with 20% defense 100 times in a row. With the shuffle bag approach, you'll miss him exactly twenty times out of a hundred (if you put 100 numbers in there).Zarel wrote:afaict, those all seem inferior to a true PRNG like Mersenne Twister.lmelior wrote:Personally I think the approach more likely to make people happy will be the implementation of a quasi-random number generator, or a shuffle bag as I described in this other post.
Like I said before, even though that says MT provides "better" random numbers, Wesnoth doesn't require enough of them to make a difference. How many per battle, a thousand at most? Nobody will notice the slightly higher uniformity and higher period there. MT is for the researchers that run thousands of Monte Carlo simulations with thousands of uncertainty parameters.
Also, more dependencies = more compilation headaches. Libraries make developers' lives a whole lot easier in general, but adding unnecessary dependencies is always bad.
Re: Random number generator code improvement
Those are indeed useful questions. My guesses for the answers are probably no, no, not significantly, and possibly, respectively.Sapient wrote:Making 2 or 3 threads go away is very easy and requires no coding experience. Development decisions should be driven by logic, not by forum annoyances. Logical questions are those such as: is anyone really going to submit a patch for this? if so, are they really going to take the time to test for multiplayer OOS and/or savegame corruption? Finally, will it increase the size of the binary or increase build times? Do the potential benefits even outweigh the time it takes to properly review and commit such a change?
Shuffle bags don't work very well when you have a bunch of units with varying defense probabilities, though. It's a good direction, of course, though they do have the "karma system" flaw of being able to predict probabilities by "card counting".lmelior wrote:Inferior in terms of true randomness, yes, but if you follow the shuffle bag link I posted you'll see that the author argues that a less random approach will "feel right" to most people. True random means you can miss a unit with 20% defense 100 times in a row. With the shuffle bag approach, you'll miss him exactly twenty times out of a hundred (if you put 100 numbers in there).
Perhaps not, but it does hold more weight to say "Wesnoth uses this standard PRNG with these useful properties" than to say "Wesnoth uses whatever PRNG your C compiler uses, which probably has these useful properties." Perception means a lot, and even though, as I've mentioned, it won't actually affect anything, it's a lot more authoritative to say "this is random enough" than to say "this is probably random enough".lmelior wrote:Like I said before, even though that says MT provides "better" random numbers, Wesnoth doesn't require enough of them to make a difference. How many per battle, a thousand at most? Nobody will notice the slightly higher uniformity and higher period there. MT is for the researchers that run thousands of Monte Carlo simulations with thousands of uncertainty parameters.
The dependency problem can be solved simply by including the (fairly small) library. Then again, Debian tends to get annoyed at you.lmelior wrote:Also, more dependencies = more compilation headaches. Libraries make developers' lives a whole lot easier in general, but adding unnecessary dependencies is always bad.
Proud creator of the :whistle: smiley | I prefer the CC-0 license.
-
- Posts: 10
- Joined: April 27th, 2010, 9:29 pm
Re: Random number generator code improvement
I offered to submit a patch for this if someone can help me with the linker errors that I'm getting.Sapient wrote:Making 2 or 3 threads go away is very easy and requires no coding experience. Development decisions should be driven by logic, not by forum annoyances. Logical questions are those such as: is anyone really going to submit a patch for this? if so, are they really going to take the time to test for multiplayer OOS and/or savegame corruption? Finally, will it increase the size of the binary or increase build times? Do the potential benefits even outweigh the time it takes to properly review and commit such a change?Zarel wrote: It will make the Mersenne Twister threads go away, though, which I think is worth it. It's not like there's anything wrong with it.
-
- Posts: 10
- Joined: April 27th, 2010, 9:29 pm
Re: Random number generator code improvement
I think shuffle bags are a terrible idea because of the "karma system" flaw you describe. If the game is too random for you, double the number of attacks for all units, as well as their hitpoints. Or triple it, etc. Attacking with 40-1 is a lottery; attacking with 1-40 has a much smaller variance.Zarel wrote:Shuffle bags don't work very well when you have a bunch of units with varying defense probabilities, though. It's a good direction, of course, though they do have the "karma system" flaw of being able to predict probabilities by "card counting".lmelior wrote:Inferior in terms of true randomness, yes, but if you follow the shuffle bag link I posted you'll see that the author argues that a less random approach will "feel right" to most people. True random means you can miss a unit with 20% defense 100 times in a row. With the shuffle bag approach, you'll miss him exactly twenty times out of a hundred (if you put 100 numbers in there).