Random number generator code improvement

[mistersheik]

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]

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.

[MDG]

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

[Zarel]

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:

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.

[Yogibear]

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.

[Dave]

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

[Zarel]

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.

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.

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.

[lmelior]

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.

[Zarel]

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.

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.

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.

[mistersheik]

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.

[Sapient]

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?

[lmelior]

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.

[Zarel]

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.

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

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

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.

[mistersheik]

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]

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.