pseudo-random generator + improvement idea

[ced_ne]

@ Glass Pearl Player:
Sorry to disagree, but I have used exactly the Wesnoth's RNG code during my test (over 1.000.000 of time), and in the test I displayed here, it was exactly an unit with 4 strike at 70% chance to hit. So no, there isn't more chance to miss all the 4 strikes, in my test, it happened 8250 times => 0.825%, very close to the real statistic chance of 0.81% (at least under Linux).
Sure everyone have had a rough experience, where a computer unit just don't want to die, even attacked by 4 level 4 Grand Mage. The opposite happened too, but human have a tendency to memorize bad event more than good one.

I just think that exceptional case (like a no hit with an archimage) are too 'grouped'.

And it remains the case of WML random, where requested random number range could be 2,4,8,16,etc... using exclusively lower bit of the RNG, that have less randomness.



I will not bother you anymore with the RNG, I have patched the source using linux /dev/urandom one week ago, and I'm very confident with this one, and it does not require a lot of work to patch successive Wesnoth version I will get in the future.

So... Good luck to everyone :O)

[JW]

I will not bother you anymore with the RNG, I have patched the source using linux /dev/urandom one week ago, and I'm very confident with this one, and it does not require a lot of work to patch successive Wesnoth version I will get in the future.

So... Good luck to everyone :O)

I was hoping you would run some tests on Windows.

[Glass Pearl Player]

@ Glass Pearl Player:
Sorry to disagree, but I have used exactly the Wesnoth's RNG code during my test (over 1.000.000 of time), and in the test I displayed here, it was exactly an unit with 4 strike at 70% chance to hit. So no, there isn't more chance to miss all the 4 strikes, in my test, it happened 8250 times => 0.825%, very close to the real statistic chance of 0.81% (at least under Linux).

Perhaps my english was too unclear, I have to apologize.
I never doubted the probability of 0.81% which is about one in 123. I merely wanted to show that even such an unlikely event happens very frequently - even more frequently than intuition would lead one to believe. To be precise, it happens about once every 123 tries. Given that a lot of people play Wesnoth, this almost equates to "It happens all the time".
Regarding your test results, did you compute any significance thresholds or run some statistical test on them? Maybe, maybe I could do that myself on monday...

I just think that exceptional case (like a no hit with an archimage) are too 'grouped'.

Define "too grouped". Obviously this case cannot happen with perfect regularity, otherwise the RNG would be considered broken.

[Dave]

using exclusively lower bit of the RNG, that have less randomness.

From the Linux man page on my system:

The versions of rand() and srand() in the Linux C Library use the same
random number generator as random(3) and srandom(3), so the lower-order
bits should be as random as the higher-order bits. However, on older
rand() implementations, and on current implementations on different
systems, the lower-order bits are much less random than the higher-
order bits.

This is clearly no longer an issue on modern Linux distributions. I also doubt any other operating systems have a serious problem with it.

However, even in older versions of rand(), I doubt the difference in randomness is perceptible or important for a game like Wesnoth. I think it would be important for, for instance, a cryptographic application.

David

[silene]

However, even in older versions of rand(), I doubt the difference in randomness is perceptible or important for a game like Wesnoth.

That I disagree with. As I explained above, predictable second bit of the random values can lead to doing up to +50% average damage, which is quite noticeable. And in earlier rand implementations (linear-modulo generators), the period of the second bit was at most 4, so it was completely predictable, even if you were an external observer that could only guess based on the outcome of the first few fights. But anyways, that's completely irrelevant nowadays, I hope.

[dragontamer]

Wait... I'm not a source-diver but I do know a little bit of C++... and also... I'm new to the forums and Wesnoth in general so excuse me if I say something ignorant or whatnot.

Why is the Wesnoth code using the obsolete "rand()" function? Why is it not using the TR1 Random Number Generators? Both Visual Studio and G++ support std::TR1 now, and std::TR1 includes an implementation of the rigorously tested Mersenne Twister. TR1 also includes the rigorous functions necessary for dice rolling. (ie: the uniform_distribution generator, which is a little more subtle than programmers tend to think). TR1 generators are more object oriented: their state is stored in an explicit generator object instead of inside of a static variable in some random standard-library C file. Finally, all compilers that support TR1 will have the same implementation of the Mersenne Twister (and other standard random number generators), as well as the uniform_distribution generator.

Therefore, all of the original poster's concerns can simply be addressed by upgrading from stdlib.h rand() into std::tr1 random number generators. If TR1 is too new for some systems, then Boost's random number facilities (of which TR1 was based on...) should work. Oh, and if you google TR1 random numbers, be sure that the tutorial you read mentions variate generators, which converts the outputs of a raw engine into the inputs of a distribution.

[silene]

Why is the Wesnoth code using the obsolete "rand()" function?

I'm not sure how you got the idea this function was the obsolete. Even the next C++ Standard that will be released in a few years doesn't go that far. Its draft only says "Note: The random number generation (26.4) facilities in this standard are often preferable to rand." Notice that it doesn't say "shall", it doesn't even say "should", it purposely uses the "note" and "preferable" words that don't have any normative meaning. The only issue the C++ committee has with rand is that it doesn't provide any race-free facility (that is, two threads feeding on the random generator at the same time could possibly get correlated values). But for a monothreaded usage of random numbers, as Wesnoth does, rand is considered to be just fine.

As a side note, do you really think that library writers that are able to write and ship the <random> header would purposely ship a crappy implementation of rand?

[dragontamer]

In hindsight, I think I was a bit too forward with my question. I respect the developers here, and should have not posed a pointed question like that. I apologize.

Just maybe... if I had the time, maybe it could be an acceptable patch for this game. I believe a switch to the more rigorously tested Mersenne Twister and careful design of the RNG code ought to quell any claims about "unfair luck" in this game. IMO, the tradeoffs are reasonable, but it probably is not my job to decide something like that. As you've stated: even if the rand() function was bad, it probably wouldn't matter for a game.

EDIT: To answer some of your questions directly: I don't expect crappy versions of rand. I expect however, inconsistent versions of rand and therefore different performance of the RNG on different systems. Using Boost's or TR1's MT19937 would guarantee a high standard across all systems. Currently, it appears that, tests that prove randomness on Linux does not transfer over to Windows. I'm specifically talking about this user's response here.

[Max]

hope i'm not telling nonsense, but it looks like wesnoth pretty much has it's own (simple and straight forward) RNG implementation (see src/random.cpp and here), using rand() only for the initial seed.

i don't really see what could be possibly wrong with this approach - maybe besides that it's predictable (although that's only a MP issue - not sure how this is handled).

[Dave]

I believe a switch to the more rigorously tested Mersenne Twister

rand() has been standardized since at least 1989. The Mersenne Twister is only now being standardized. Why would you think it is more rigorously tested?

David

[Boucman]

Just maybe... if I had the time, maybe it could be an acceptable patch for this game. I believe a switch to the more rigorously tested Mersenne Twister and careful design of the RNG code ought to quell any claims about "unfair luck" in this game.

hmm

let me guess

no

it's not a no about the patch itself (I don't really care what RNG we use, I leave that to coders with more insight about it)

what I guarentee is that no, changing the RNG will not quell any claims at all. It wont even lower the voices complaining. Our RNG is good enough that any unfairness is totally irrelevant to the game.

The problem is that random numbers are not born equal. If you have bad luck at the bad moment, you will claim the RNG is unfair despite any statistics/mathematical proof/RNG testing prooving the contrary

this plus the biased perception of the human mind means that I'm pretty confident that trying to reduce the claims of unfairness by changing the RNG are bound to fail

the problem is not the unfairness of the RNG, it's players refusing to admit that luck is a part of the game, sometime you're lucky and sometime you're not.

luck might play an important role between good players, but I observe that "usually" the best player wins.

And good players are usuallly honest enough to recognise when they won/lost because of a mistake and when the won/lost because of luck.

There are talks about reducing the overall importance of luck in gameplay, but that's a totally different matter. It's a change in the game philosophy.

[dragontamer]

I believe a switch to the more rigorously tested Mersenne Twister

rand() has been standardized since at least 1989. The Mersenne Twister is only now being standardized. Why would you think it is more rigorously tested?

David

First: rand() is only a specification of the C Standard Library. There is no guarantee that rand() uses a rigorously tested algorithm. The only guarantee that I know of is that rand() returns a number between 0 and RAND_MAX. Hypothetically, even Dilbert's and xkcd's RNGs fit the C89 specification. This isn't too far off either: as others have pointed out in this thread, there are deficiencies in early rand() implementations. Nonetheless, these deficient rand() implementations fit the C89 standard. Basically, rand() itself cannot be subjected to a randomization test. Specific implementations can, but certainly not "standard rand()".

Second: The Mersenne Twister is a specific algorithm... and the specific mt19937 has parameters that make it fit the classical sense of a random number generator. True, it is a relatively new algorithm but at least it can be tested. And tested it was. The Mersenne Twister passes equidistribution tests up to 600+ dimensions (typical LCG generators fail at ~5 dimensions). The cycle length is proven to be (2^19937) -1 (typical LCG generators have cycle lengths of only 2^64). For more information, you can read the original paper published in ACM here.

There is a reason that the Mersenne Twister is entering standard C++: it is fast and memory efficient, and is provably "more random" than typical LCG generators. (well, if you can agree that cycle length and high-dimensions of equidistribution is more random). Empirically, it passes "random-enough" based studies such as the Diehard test (claimed in paper referenced above). Finally, by utilizing the std::tr1::mt19937 or boost::random::mt19937, you can guarantee the implementation of the Mersenne Twister; as opposed to relying on the compiler-specific rand() implementation.

hope i'm not telling nonsense, but it looks like wesnoth pretty much has it's own (simple and straight forward) RNG implementation (see src/random.cpp and here), using rand() only for the initial seed.

Looking at the source... LCG Generators are simple and effective generators, and do pass the standard randomization tests. Nonetheless, there is quite a bit of raw rand() usage in the source code. (grep "rand()" src/*). From a quick glance, it doesn't look like anything critical like damage however.

[hiro hito]

Despite the fact that I am not a coder/developper, I don't think that the the code for the RNG is bad.... Even if I play more matches with negative stats than positive, I trust the developpers when they say that the RNG is fair enough!

The problem, for almost all RNG complainers, is that the RNG doen't fit the fighting system... Even if 1 000 000 test have been made to test the "precision" of the code, is this RNG really fit one match between two good players? I don't think so, because only +/-20% difference (gap) of luck , for more than 2 turns, just screw one game!.... RNG code can be fair a thousand turns for other application/game, but it has to be fair on 5 turns (max) to fit Wesnoth*.

*when I say fair for Wesnoth: the EV stats should be near to 0% all every 5 turns (max) for both players. Then we should have a real strategic game with some randomness!

[Max]

Looking at the source... LCG Generators are simple and effective generators, and do pass the standard randomization tests. Nonetheless, there is quite a bit of raw rand() usage in the source code. (grep "rand()" src/*). It doesn't look like anything critical like damage however.

i think this could be easily dealt with by using a second instance of the random class to replace these calls.

but as you said - these calls aren't used for anything critical - has there ever been a point to this discussion?

[Sauron]

Long time ago (in 2006) I proposed unification of random number generator - and adding some test for incoming random numbers if they're coming from the sequence indicated by the seed. Why is that necessary? Because if you can change the function responsible for generating random numbers, anyone can do it.
I played some time ago with fenix at ladder - and observed his other games. Watching it I could not resist feeling he was more lucky than he should be. If you have some of his games logged on server - I would be glad to get to know if his numbers matched the sequence from reported seed. I no longer have interest in digging in wesnoth code (mabye if there was some guide into coding it I would - some programmers' guide WIKI might be the right way) and playing with saves - but some developers mabye should?
Mabye that's a good answer why unification of RNG makes sense?