RNG produces proper distribution. But that isn't everything

[adhesv]

I did a quick search and noticed the large amount of threads of whine concerning the nature of the "randomness" in Wesnoth. It has been tested that the math works correctly

ok, how about this: i just had two units (unit A and unit B) with 1-1 attack do 100,000 rounds of combat. they were both on 40% dodge. unit A hit unit B 60,011 times. unit B hit unit A 60,026 times.

So is the randomness in Wesnoth is just attribution error? (a perception problem)

When I came across this link it seems that it may not be the case. http://maradns.blogspot.com/2010/07/wes ... esses.html
According to this site, wesnoth uses a RNG method called a "Linear Congruential RNG" and in turn fails some RNG quality tests. After reading some supplemental information about this type of RNG http://www1.i2r.a-star.edu.sg/~knandaku ... erator.htm some important aspects stood out.

Linear congruential RNGs were once considered to be a good method of generating pseudo-random numbers (1960�s) but are now obsolete. As the example above suggests, they did tend to produce (after division by m+2) a series of numbers that took on values in the unit interval that were remarkably uniformly-distributed. They tended to fail in other important respects, notably in the distribution of sequences of numbers.

The point of this example is that we can characterize any pseudo-random number generator in terms of the tests of randomness that it can pass. The linear congruential generator did produce a very uniform distribution but it flunked a simple sequential test. Note that in the sequence we computed, that ODD and EVEN alternate! The tests that a pseudo-random generator can pass determine what it is good for. If, for example, your application requires only a source of uniformly-distributed number, a linear-congruential generator wouldn�t be so bad. But if you were simulating a coin toss sequence by generating random integers and choosing H (heads) when the integer is odd, T (tails) when it is even, you might be very surprised to get HTHTHTHTHTH�..

The RNG does produce correct distributions (70% hits to 30% miss given a 70% claimed hit chance as sample sizes increases). But not necessarily a random sequence (Strings of hits and misses possibly over-represented).
So I'm wondering if wesnoth uses this RNG method as the website claims, and if it does should it be changed?

[lipk]

The high mathematics don't really count here since Wesnoth's random generator doesn't rely solely on the algorithm in question, many semi-random variables are also involved in the computation (units' location on the map and such). Also, a random seed isn't used in more than one attack, so the sequences don't even get a chance to repeat themselves.

[Kymille]

I'd like to caution everyone that the second quote above is out of context. It is possible to make terrible choices for the parameters of the RNG which do things like produce alternating Heads and Tails, and repeat the entire sequence after only eight numbers. No one distributes RNG generators that are that bad, and you will see from the first link that Wesnoth is not using such parameter choices.

No doubt though it's true that you could improve the RNG, but this is about very subtle correlations in 4-dimensional space. It would be bad news for modeling the Higgs boson, but humans can't detect such things.

[ancestral]

Eventually, you have to ask “what is random?” Computers cannot choose a true random number like in many real-life ways, such as rolling a die or picking a letter out of a bag. So judging how effective a random number generator is really judging how even its distribution is, at which point, it’s not truly so random anymore.

For the OP: There are a few mods and builds of Wesnoth which alter the RNG. This is a very oft discussed topic, though largely from people coming from games where the RNG is tweaked to be more forgiving in the short-run.

[alluton]

Random thing occurs when you take alot of drugs. It might be abit difficult for computer tought. So I suggest sticking in already used one to generate randomness.

[Iris]

Random thing occurs when you take alot of drugs. It might be abit difficult for computer tought. So I suggest sticking in already used one to generate randomness.

And this is the kind of comment we don’t want in this kind of topic.

[alluton]

From my opinion that would really be only way to produce randomness. Since unable to be done whit computers. True randomness cannot be achieved and so forth I see no need to change the current system.

[JaMiT]

When I came across this link it seems that it may not be the case. http://maradns.blogspot.com/2010/07/wes ... esses.html
According to this site, wesnoth uses a RNG method called a "Linear Congruential RNG" and in turn fails some RNG quality tests.

That blog is in error. Wesnoth uses a modified linear congruential RNG. The difference is that Wesnoth discards the lowest 16 bits of the state before returning a result. This simple modification greatly ameliorates at least one of the shortcomings of strictly linear congruential RNGs.

Interestingly, that blog does contain an accurate portrayal of the Wesnoth RNG, yet the blog still calls it a linear congruential generator with no acknowledgment of the modification from the strict definition of "linear congruential". I could descend into argumentum ad hominem here (I suspect a bias towards newer, flashier RNGs because they are newer and oh-so-glittery), but instead I will just suggest that conclusions in that blog maybe should be questioned instead of accepted at face value.

After reading some supplemental information about this type of RNG http://www1.i2r.a-star.edu.sg/~knandaku ... erator.htm some important aspects stood out.

Do you have any idea who wrote that? (I don't.) While the basic facts look generally correct, some of the conclusions look questionable to me. (For example, there is an appeal to "As the example above suggests" and a conclusion that there is too much uniformity. Sure, there is a lot of uniformity when you look at a dozen or so results. That is because the "example above" only permitted 8 possible results. If you instead permit tens of thousands of results, the uniformity does not appear even after hundreds of results are obtained.) This is another web page I would take with a grain of salt.

One conclusion I find rather questionable is calling linear congruential RNGs "obsolete". They are not suitable for all purposes, and there are more sophisticated RNGs around. Furthermore, a linear congruential RNG can be configured to give rather bad results. However, that does not make them obsolete. They can be configured to give reasonably good results. There are circumstances in which they are adequate. (I suppose the question is whether or not a board game fits this category.) Plus, they are very simple and efficient, much more so than some of the more sophisticated RNGs.

What that article does get right is describing what is possibly the biggest shortcoming of linear congruential RNGs. Even when configured to give the largest possible cycle before the pseudo-random sequence repeats itself, there tends to be smaller cycles present. In particular, a linear congruential RNG may indeed produce alternating odd and even numbers; a simulated coin toss might alternate heads and tails. This is where the modification I mentioned earlier comes into play. By eliminating the lowest bit, this odd-even alternation is eliminated. But Wesnoth does more than that. Wesnoth discards the lowest 16 bits, which should eliminate all cycles shorter than 2^16 = 65,536 (which is rather good considering that the RNG returns only 32,768 distinct numbers).

Are there problems with linear congruential RNGs? Yes. Are the problems insurmountable? No. Might a test show that there are shortcomings even with the modification used by BfW? Yes, but I would not accept a conclusion to that effect unless the test results are available for independent analysis. In fact, having such results available might be interesting to see how far -- or how close -- Wesnoth's RNG is from the more sophisticated RNGs available.

Linear congruential RNGs are not perfect, but I still see no hard evidence that Wesnoth's RNG is inadequate for the job it does.


Disclaimer: Disregard the color of my name. I am a fairly new developer for Wesnoth, and the above is my personal view, not something from the Wesnoth development team.

[Sapient]

Also, a random seed isn't used in more than one attack, so the sequences don't even get a chance to repeat themselves.

Funny how the blogger failed to notice that, isn't it?
But maybe rand() isn't good enough either, like that Mersenne Twister guy tried to warn us.
Good times, good times...

[pyrophorus]

Hi !
Would the RNG be changed to another one, I bet no one would notice it. (BTW, I can be wrong, but I thought Wesnoth was using the stdlib rand() function. If so, it still uses different RNGs on Windows, Linux and MacOSX, and no one ever noticed it).
IMHO, people complains about RNG, but the problem is elsewhere. Given an unit having 5% chances to remain unscathed under attack and one single hitpoint less, it has still 5% to survive, no matter how much attacks it already survived in this turn. Common sense would tell it has less and less chances to survive successive attacks. Game logic, not RNG problem.
Friendly,

[AxalaraFlame]

I concur. I believe I have read another topic which explained how to pervent the RNG result in the consequence far out of our expection. Its principle is to add one more fake step, makes the RNG select whether it is to be hit or dodged randomly more times, and use this way to nerf down the uncertainty. For instance, a thunderer has 1 strike, while elv archer has 4. It is like that the dwarf will also shot four times and according to this result, the computer picks the most probable result of hit or miss. Someone told me this postor has even made an add-on to elaborate how different it is, but i did not see. Who knows this man and his RNG? I believe it might be useful.

[JaMiT]

(BTW, I can be wrong, but I thought Wesnoth was using the stdlib rand() function. If so, it still uses different RNGs on Windows, Linux and MacOSX, and no one ever noticed it).

No, the game uses an algorithm from stdlib, but that is coded directly without a call to rand(). (This might have been done to avoid using different RNGs on Windows, Linux and MacOSX. I think someone would have noticed it.) If you want to check the implementation for yourself, go to the bottom of random.cpp (the last function in that file). A few functions up from that -- get_next_random() -- is where the modification is made to prevent small cycles.

[Sapient]

But it does use rand() to generate a new seed whenever the seed is invalidated. So if you are playing a standard campaign, there won't be a unit with more than a handful of strikes before the seed gets invalidated. The longest sequence would when an ulfserker attacks a dark adept on high defense. Considering that the outcome of that attack is a foregone conclusion, there's no point in analyzing the hit/miss sequence for repeating patterns. Even then it wouldn't be a long enough sequence to do any meaningful analysis.

Disclaimer: I did not write the random number generation code, nor have I extensively analyzed it

[pyrophorus]

But it does use rand() to generate a new seed whenever the seed is invalidated.

Yes, so results are actually different on each platform, but the user experience is the same. Users complains have nothing to do with random generation IMO.

Friendly,

[Xudo]

Problem with "user-unfriendly RNG" already solved.

Is there any chance to get option in MP lobby "RNG mode" with options: "Modified linear congruential", "Hyperheometric"?