Currently Online

Latest Posts

Topic: Random Number Generator Fairness Testing

Forums » International Player Forums » [English] - Player Forum » Random Number Generator Fairness Testing
Nordfriese
Avatar
Topic Opener
Joined: 2017-01-17, 17:07
Posts: 2006
OS: Debian Testing
Version: Latest master
Ranking
One Elder of Players
Location: 0x55555d3a34c0
Posted at: 2022-10-08, 21:44

There are occasional complaints about fights between soldiers going unusually badly for one side and unusually well for the other. For example, a supersoldier may sometimes be killed by a much weaker soldier, or in a fight between equals one may remain completely unharmed.

I ran some tests on the random number generator to see whether there is some inherent unfairness that allows such possible but unlikely situations to arise more often than they should.

Result

It is fair!

The deviations are negligible. The frequencies of all possible values are all in the same order of magnitude.

Bad luck is simply that – bad luck, it does happen occasionally, and is very noticeable for humans; but the randomness in Widelands is not biased for or against anyone or anything.

Method

Program source code attached.

I generated 100 Million random numbers each in the intervals 0..5 (used for movement decisions), 0..99 (used in soldier fights), and 0..2^16-1 (generic case). The distributions are shown in the following plot:

[00:00:00.000 real] INFO: ****************************************************************************
[00:00:00.000 real] INFO:            N = 6
[00:00:00.000 real] INFO:     mean_val = 2.500063
[00:00:00.000 real] INFO:         mean = 16666666.666667
[00:00:00.000 real] INFO:        sigma = 2252.924297
[00:00:00.000 real] INFO: [         0] =   16662938 #################################################
[00:00:00.000 real] INFO: [         1] =   16669017 ##################################################
[00:00:00.000 real] INFO: [         2] =   16665862 #################################################
[00:00:00.000 real] INFO: [         3] =   16668158 #################################################
[00:00:00.000 real] INFO: [         4] =   16669002 #################################################
[00:00:00.000 real] INFO: [         5] =   16665023 #################################################
[00:00:05.878 real] INFO: ****************************************************************************
[00:00:05.878 real] INFO:            N = 100
[00:00:05.878 real] INFO:     mean_val = 49.498911
[00:00:05.878 real] INFO:         mean = 1000000.000000
[00:00:05.878 real] INFO:        sigma = 938.768651
[00:00:05.878 real] INFO: [         0] =    1001640 #################################################
[00:00:05.878 real] INFO: [         1] =     999915 #################################################
[00:00:05.878 real] INFO: [         2] =     999251 #################################################
[00:00:05.878 real] INFO: [         3] =     999008 #################################################
[00:00:05.878 real] INFO: [         4] =    1000165 #################################################
[00:00:05.878 real] INFO: [         5] =    1000719 #################################################
[00:00:05.878 real] INFO: [         6] =     999670 #################################################
[00:00:05.879 real] INFO: [         7] =    1000576 #################################################
[00:00:05.879 real] INFO: [         8] =    1000156 #################################################
[00:00:05.879 real] INFO: [         9] =    1000023 #################################################
[00:00:05.879 real] INFO: [        10] =    1000751 #################################################
[00:00:05.879 real] INFO: [        11] =     999024 #################################################
[00:00:05.879 real] INFO: [        12] =     998878 #################################################
[00:00:05.879 real] INFO: [        13] =    1000936 #################################################
[00:00:05.879 real] INFO: [        14] =    1000352 #################################################
[00:00:05.879 real] INFO: [        15] =    1000702 #################################################
[00:00:05.879 real] INFO: [        16] =     999098 #################################################
[00:00:05.879 real] INFO: [        17] =    1001073 #################################################
[00:00:05.879 real] INFO: [        18] =    1000571 #################################################
[00:00:05.879 real] INFO: [        19] =     999857 #################################################
[00:00:05.879 real] INFO: [        20] =    1001125 #################################################
[00:00:05.879 real] INFO: [        21] =    1000079 #################################################
[00:00:05.879 real] INFO: [        22] =     997886 #################################################
[00:00:05.879 real] INFO: [        23] =     998411 #################################################
[00:00:05.879 real] INFO: [        24] =     999532 #################################################
[00:00:05.879 real] INFO: [        25] =     998810 #################################################
[00:00:05.879 real] INFO: [        26] =     999444 #################################################
[00:00:05.879 real] INFO: [        27] =    1001108 #################################################
[00:00:05.879 real] INFO: [        28] =    1000703 #################################################
[00:00:05.879 real] INFO: [        29] =    1001770 #################################################
[00:00:05.880 real] INFO: [        30] =     999134 #################################################
[00:00:05.880 real] INFO: [        31] =     999209 #################################################
[00:00:05.880 real] INFO: [        32] =    1001400 #################################################
[00:00:05.880 real] INFO: [        33] =     999484 #################################################
[00:00:05.880 real] INFO: [        34] =     999435 #################################################
[00:00:05.880 real] INFO: [        35] =     999539 #################################################
[00:00:05.880 real] INFO: [        36] =    1000454 #################################################
[00:00:05.880 real] INFO: [        37] =    1000578 #################################################
[00:00:05.880 real] INFO: [        38] =     998881 #################################################
[00:00:05.880 real] INFO: [        39] =    1001528 #################################################
[00:00:05.880 real] INFO: [        40] =    1000499 #################################################
[00:00:05.880 real] INFO: [        41] =    1000366 #################################################
[00:00:05.880 real] INFO: [        42] =     999074 #################################################
[00:00:05.880 real] INFO: [        43] =     998789 #################################################
[00:00:05.880 real] INFO: [        44] =    1000699 #################################################
[00:00:05.880 real] INFO: [        45] =     999274 #################################################
[00:00:05.880 real] INFO: [        46] =    1000313 #################################################
[00:00:05.880 real] INFO: [        47] =    1001873 ##################################################
[00:00:05.880 real] INFO: [        48] =     999351 #################################################
[00:00:05.880 real] INFO: [        49] =    1001135 #################################################
[00:00:05.880 real] INFO: [        50] =    1000661 #################################################
[00:00:05.880 real] INFO: [        51] =     999377 #################################################
[00:00:05.880 real] INFO: [        52] =     999457 #################################################
[00:00:05.881 real] INFO: [        53] =     999433 #################################################
[00:00:05.881 real] INFO: [        54] =    1000806 #################################################
[00:00:05.881 real] INFO: [        55] =     998885 #################################################
[00:00:05.881 real] INFO: [        56] =     998061 #################################################
[00:00:05.881 real] INFO: [        57] =     999147 #################################################
[00:00:05.881 real] INFO: [        58] =     998116 #################################################
[00:00:05.881 real] INFO: [        59] =     999724 #################################################
[00:00:05.881 real] INFO: [        60] =    1000710 #################################################
[00:00:05.881 real] INFO: [        61] =    1000863 #################################################
[00:00:05.881 real] INFO: [        62] =     999810 #################################################
[00:00:05.881 real] INFO: [        63] =    1001021 #################################################
[00:00:05.881 real] INFO: [        64] =    1000945 #################################################
[00:00:05.881 real] INFO: [        65] =     999687 #################################################
[00:00:05.881 real] INFO: [        66] =    1000487 #################################################
[00:00:05.881 real] INFO: [        67] =    1000415 #################################################
[00:00:05.881 real] INFO: [        68] =    1000407 #################################################
[00:00:05.881 real] INFO: [        69] =    1001046 #################################################
[00:00:05.881 real] INFO: [        70] =    1001196 #################################################
[00:00:05.881 real] INFO: [        71] =    1000661 #################################################
[00:00:05.881 real] INFO: [        72] =    1000803 #################################################
[00:00:05.881 real] INFO: [        73] =     999566 #################################################
[00:00:05.881 real] INFO: [        74] =     998317 #################################################
[00:00:05.881 real] INFO: [        75] =     999770 #################################################
[00:00:05.882 real] INFO: [        76] =    1001212 #################################################
[00:00:05.882 real] INFO: [        77] =     999974 #################################################
[00:00:05.882 real] INFO: [        78] =    1000453 #################################################
[00:00:05.882 real] INFO: [        79] =     999181 #################################################
[00:00:05.882 real] INFO: [        80] =    1000160 #################################################
[00:00:05.882 real] INFO: [        81] =    1000865 #################################################
[00:00:05.882 real] INFO: [        82] =    1000852 #################################################
[00:00:05.882 real] INFO: [        83] =    1000371 #################################################
[00:00:05.882 real] INFO: [        84] =    1000622 #################################################
[00:00:05.882 real] INFO: [        85] =     998651 #################################################
[00:00:05.882 real] INFO: [        86] =     999705 #################################################
[00:00:05.882 real] INFO: [        87] =     999819 #################################################
[00:00:05.882 real] INFO: [        88] =     998662 #################################################
[00:00:05.882 real] INFO: [        89] =    1000095 #################################################
[00:00:05.882 real] INFO: [        90] =    1001032 #################################################
[00:00:05.882 real] INFO: [        91] =    1000017 #################################################
[00:00:05.882 real] INFO: [        92] =    1000489 #################################################
[00:00:05.882 real] INFO: [        93] =    1001205 #################################################
[00:00:05.882 real] INFO: [        94] =     996991 #################################################
[00:00:05.882 real] INFO: [        95] =     999795 #################################################
[00:00:05.882 real] INFO: [        96] =    1000119 #################################################
[00:00:05.882 real] INFO: [        97] =     998817 #################################################
[00:00:05.883 real] INFO: [        98] =     999267 #################################################
[00:00:05.883 real] INFO: [        99] =    1000027 #################################################
[00:00:11.648 real] INFO: ****************************************************************************
[00:00:11.649 real] INFO:            N = 65536
[00:00:11.649 real] INFO:     mean_val = 32766.050191
[00:00:11.649 real] INFO:         mean = 1525.878906
[00:00:11.649 real] INFO:        sigma = 39.227010

>65000 lines of details omitted. Run the patch yourself to view the full distribution – the RNG is deterministic so you can reproduce my results exactly.
Attachment:
patch.txt (2.6 KB)
Top Quote
RichHolton
Avatar
Joined: 2022-09-08, 19:44
Posts: 23
Ranking
Pry about Widelands
Location: Rockford, Illinois, USA
Posted at: 2022-10-18, 04:51

It can be hard to please people when it comes to truly random (or pseudo-random) numbers. Their expectations are often different from what is truly random.

I remember reading about some video game (turn-based strategy, I think) where before a battle the approximate odds were displayed to the user. And there were loud complaints if, say, the odds were 3 to 1, and they tried the attack three times and didn't win. Eventually, the game designers changed the algorithm so that, on the third try, a win was guaranteed.

I wish I could find the story, but I can't.

Meanwhile, I did find something about dota2 that you might find interesting: random distribution

I've sometimes wondered if a normal distribution (like a bell curve) would work better than a uniform random distribution. There are ways to use an RNG to create normally distributed values. The python random library has a gauss function that does just that.

If you're at all interested, I could try to find a similar c/c++ function, or roll my own if necessary.

Rich Holton

Top Quote
tothxa
Avatar
Joined: 2021-03-24, 11:44
Posts: 453
OS: antix / Debian
Version: some new PR I'm testing
Ranking
Tribe Member
 Posted at: 2022-10-18, 13:48

RichHolton wrote:

I've sometimes wondered if a normal distribution (like a bell curve) would work better than a uniform random distribution. There are ways to use an RNG to create normally distributed values. The python random library has a gauss function that does just that.

If you're at all interested, I could try to find a similar c/c++ function, or roll my own if necessary.

I believe the main user visible event determined by some randomness in Widelands is the fight between soldiers. This has 2 random parameters:

  1. damage dealt: while some tribes have a wider range than others, the percentage of the random range to the mean value decreases with attack training, which AFAIK increases the damage by a constant value over the random base
  2. evade: this is a binary decision where you cannot use a normal distribution anyway

However each fight between 2 soldiers is a series of alternating strikes, each of which get the above values randomised. Even a level 0 soldier needs at least 3 hits from a max attack level soldier. Adjusting with evade, the mean number of strikes needed is around 4. For equal rated soldiers it's above 10. So in practice a defeat is the sum of this many independent random events. Summing evenly distributed independent variables gives you a random distribution. So I don't think it would make much sense to change the damage to follow a normal distribution.

Re Nordfriese's analysis: I think some form of frequency analysis is also needed to evaluate randomness.

Top Quote