Random number generator code improvement

Discussion of all aspects of the game engine, including development of new and existing features.

Moderators: Forum Moderators, Developers

Random number generator code improvement

Postby mistersheik » April 27th, 2010, 9:44 pm

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.
mistersheik
 
Posts: 10
Joined: April 27th, 2010, 9:29 pm

Re: Random number generator code improvement

Postby mistersheik » April 27th, 2010, 10:02 pm

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.
mistersheik
 
Posts: 10
Joined: April 27th, 2010, 9:29 pm

Re: Random number generator code improvement

Postby MDG » April 28th, 2010, 2:18 am

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).
MDG
 
Posts: 378
Joined: June 7th, 2007, 11:18 am
Location: UK

Re: Random number generator code improvement

Postby Zarel » April 28th, 2010, 7:24 am

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:

Dave 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.

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-unsafe 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.
User avatar
Zarel
 
Posts: 700
Joined: July 15th, 2009, 8:24 am
Location: Minnesota, USA

Re: Random number generator code improvement

Postby Yogibear » April 28th, 2010, 7:47 am

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.


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.

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!
Yogibear
Retired Developer
 
Posts: 1086
Joined: September 16th, 2005, 5:44 am
Location: Hamburg, Germany

Re: Random number generator code improvement

Postby Dave » April 28th, 2010, 7:38 pm

Zarel wrote:
Dave 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.

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-unsafe 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++).


Nonsense. Firstly rand() is a commonly used C function. It doesn't have any analogue or replacement in C++98.

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
Dave
Founding Developer
 
Posts: 7064
Joined: August 17th, 2003, 5:07 am
Location: Seattle

Re: Random number generator code improvement

Postby Zarel » April 28th, 2010, 8:44 pm

Dave wrote:Nonsense. Firstly rand() is a commonly used C function. It doesn't have any analogue or replacement in C++98.

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.

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.

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.

"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)

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.

Dave wrote:Not using rand() because there exist functions such as strcpy() is a bizarre argument.

Anything can be made to seem bizarre if you skip all the steps in between.
Proud creator of the :whistle: smiley | I prefer the CC-0 license.
User avatar
Zarel
 
Posts: 700
Joined: July 15th, 2009, 8:24 am
Location: Minnesota, USA

Re: Random number generator code improvement

Postby lmelior » April 29th, 2010, 8:39 pm

Zarel wrote:
Dave wrote:Nonsense. Firstly rand() is a commonly used C function. It doesn't have any analogue or replacement in C++98.

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.

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.

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.

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.
lmelior
 
Posts: 116
Joined: June 16th, 2009, 3:30 am

Re: Random number generator code improvement

Postby Zarel » April 29th, 2010, 9:49 pm

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.

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: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.

afaict, those all seem inferior to a true PRNG like Mersenne Twister.

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.

True. I never said MT was a good RNG. ;) Just sayin' it can't be worse than libc rand.
Proud creator of the :whistle: smiley | I prefer the CC-0 license.
User avatar
Zarel
 
Posts: 700
Joined: July 15th, 2009, 8:24 am
Location: Minnesota, USA

Re: Random number generator code improvement

Postby mistersheik » April 29th, 2010, 10:27 pm

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.
mistersheik
 
Posts: 10
Joined: April 27th, 2010, 9:29 pm

Re: Random number generator code improvement

Postby Sapient » April 29th, 2010, 11:30 pm

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.


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?
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."
User avatar
Sapient
Developer
 
Posts: 4363
Joined: November 26th, 2005, 7:41 am

Re: Random number generator code improvement

Postby lmelior » April 30th, 2010, 12:32 am

Zarel wrote:
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.

afaict, those all seem inferior to a true PRNG like Mersenne Twister.

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).

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.
lmelior
 
Posts: 116
Joined: June 16th, 2009, 3:30 am

Re: Random number generator code improvement

Postby Zarel » April 30th, 2010, 12:49 am

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?

Those are indeed useful questions. My guesses for the answers are probably no, no, not significantly, and possibly, respectively.

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).

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: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.

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:Also, more dependencies = more compilation headaches. Libraries make developers' lives a whole lot easier in general, but adding unnecessary dependencies is always bad.

The dependency problem can be solved simply by including the (fairly small) library. Then again, Debian tends to get annoyed at you. ;)
Proud creator of the :whistle: smiley | I prefer the CC-0 license.
User avatar
Zarel
 
Posts: 700
Joined: July 15th, 2009, 8:24 am
Location: Minnesota, USA

Re: Random number generator code improvement

Postby mistersheik » April 30th, 2010, 1:56 am

Sapient wrote:
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.


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?


I offered to submit a patch for this if someone can help me with the linker errors that I'm getting.
mistersheik
 
Posts: 10
Joined: April 27th, 2010, 9:29 pm

Re: Random number generator code improvement

Postby mistersheik » April 30th, 2010, 2:03 am

Zarel wrote:
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).

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".


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.
mistersheik
 
Posts: 10
Joined: April 27th, 2010, 9:29 pm

Next

Return to Coder’s Corner

Who is online

Users browsing this forum: No registered users and 2 guests