Very interesting talk on Random Number Generators

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

Moderators: Forum Moderators, Developers

Very interesting talk on Random Number Generators

Postby Simons Mith » April 12th, 2015, 6:25 pm

YouTube: https://youtu.be/45Oet5qjlms
FixYT: http://fixyt.com/watch?v=45Oet5qjlms

This video is an hour long plus a 15 min Q+A session at the end. It is likely to be of interest to anyone dealing with random number generators - quite possibly of professional interest. People complaining about the Wesnoth RNG being flawed has been a long-standing problem (though I haven't seen much recently, so maybe it's finally died down), but this video explains very clearly how to make a really good RNG, and how to spot bad ones.

Broad summary:
1. Gather approximately a hundred of the best tests for statistical randomness into a test suite.
2. Put most of the used pseudo-random number generators through the test suite. (Most fail).
3. Select a couple of the easiest pseudo-random number generators to reason about.
4. Try an easy extension of their state to see if and when (or if ever), they can pass.
5. Knowing that some state bits are more random than others, and that less random bits are usually dropped, use the most random state bits to (invertably) permute and select the bits returned.
6. Achieve PRNG nirvanna!

It's a long video, but time well spent for many programmers.

via G+.

I've put it in Coder's Corner even though it's not directly Wesnoth-related, because it's so educational. My apologies if the mods think it should have gone to Off-topic right from the outset.

See also: http://www.pcg-random.org

Enjoy
 
User avatar
Simons Mith
 
Posts: 784
Joined: January 27th, 2005, 10:46 pm
Location: Twickenham

Re: Very interesting talk on Random Number Generators

Postby pauxlo » April 19th, 2015, 8:56 pm

I just spent several hours on browsing the web site, reading the paper, and viewing the video.

It looks almost too good to be true, so I would wait for the paper to be reviewed and published before starting to actually use those generators productively.
(Though I guess they can't be worse than using rand().)
User avatar
pauxlo
 
Posts: 1006
Joined: September 19th, 2006, 8:54 pm

Re: Very interesting talk on Random Number Generators

Postby Crow_T » April 19th, 2015, 9:10 pm

i recall iceiceice looking into the RNG a while back, for similar reasons- the current RNG model being flawed in some manner. I wonder if he has seen this thread yet :whistle:
User avatar
Crow_T
 
Posts: 835
Joined: February 24th, 2011, 4:20 am

Re: Very interesting talk on Random Number Generators

Postby iceiceice » April 20th, 2015, 2:47 am

So my opinion is that any of these RNGs is probably fine for wesnoth. The only one that is really bad is the C rand function from 1980, because that one will actually cause detectable problems and probably result in various exploits related to unit traits (don't know this for a fact but I would expect it. The exploits would be based on known patterns in the low order bits of rand's output which determines the units traits). Even rand was basically good enough that no one found actual evidence from gameplay that it was bad, after years and years. And afaik no user has actually reported that they know such exploits -- it's just my prediction that they probably exist.

When the PCG authors write that Mersenne Twister has "easy prediction" I think this is only related to cryptographic attacks. If you don't have direct access to the output of the generator, and you only have the info visible from attack / trait outcomes in a game of wesnoth, I seriously doubt that it is predictable at all. When they talk about "failures of the statistical properties" because it obeys some F2 linear recurrences (that being its definition, a very complex linear recurrence)... I don't think this is likely to be important to how we are using it. I believe that the 624-dimensional equidistributed property essentially means that you would have to recruit hundreds of units in a single game before you could observe any patterns in how the traits are being generated. When you consider attacks, where we are taking the generator output and mapping it to an integer 0-100, and comparing with some defense value... the fact that it obeys linear congruences might mean that, if you observe many different attacks then there will be some nontrivial F_2 linear relations in the bit patterns generated. But there no patterns like that that are going to survive a % 100 operation and not be relatively uniformly distributed among 'high' numbers and 'low' numbers. So I don't think that this information, even if you managed to obtain it, would allow you to actually predict any attacks, unless you essentially cracked the entire state and were predicting the entire output of the generator. Note also that in MP the server reseeds the game very frequently, like after every attack I believe.

The PCG thing sounds nice but I think it's probably more significant for Scientific applications or crypto. The efficiency of the RNG is not a major selling point for us either, imo.
User avatar
iceiceice
Developer
 
Posts: 1056
Joined: August 23rd, 2013, 2:10 am

Re: Very interesting talk on Random Number Generators

Postby midberry » January 23rd, 2016, 1:18 am

Greatings Travellers - I have some experience in programming random numbers and
I have played and loved Wesnoth and was a bit frustrated by the level of unpredictability
in the game.

The reason why I am telling this, is I have just penned and tested a 'loaded distribution'
generator designed specifically to provide the sought after capability to smoothly alter
the level of combat unpredictability in Battle of Wesnoth.

Below are charts of the random variates generated by a small function which can drop in
replace the basic random number generator used in Wesnoths combat calculations.
The function takes a parameter value 0 to 1 which biases the results (randomly) to
produce combat conditions like this:

0.0 infuriatingly unreliable
0.2 less infuriating
0.4 somewhat more combat surprises than present game
0.5 exact same combat setting as present game (frustrates me)
0.6 somewhat fewer combat suprises
0.8 probably too predictable
1.0 many fights very hopeless (but never completely)

These descriptions are guestimate, testing can find best settings they might be 0.55 or 0.7
to see a significant difference, only testing can tell but the parameter range is smooth and balanced,
the effect can be arranged to be very subtle.
I dont expect anyone would want to play with more combat suprises (?) but its is possible with (p<0.5)

A new option to choose game chanciness setting could be given separately, or this could be hidden in the
existing easy, medium, hard, nightmare settings. I believe easy and medium settings at least should be more
comfortable to play with fewer surprises.

Charts of the functions follow, If these are over complex it is because i use them to examine my javascript prng
project on github 'fdrandom.js'
(The 2d scatterchart and linecharts are extraneous, the red graph
shows the 1d distribution of the prng for a given parameter eg 0.4, 0.5... )

Image

Some Random Explainations:
The playing qualities of the randomness used in Wesnoth are almost certainly not
perceptably affected by any statistical imperfections present in the standard libs
PRNG employed in the code. Replacing the standard libraries prng with mersenne twister
for example would not have any perceptable effects on the game.


The numbers generated by a standard random number generator are known as 'variates'
Each generated variate should have an almost completely unbiased chance of being any value
between 0 and 1 (the stnd lib's prng actualy does this well enough for most purposes)

The effective resulting 'fairness' of these numbers in the game, is their average value
which is 0.5 to be fair. What determines how often these numbers overwhelm the combat
modifiers (the +10 skill, -20 terrain details etc) is not their average but how often they stray
far from the average (and how far they tend to 'stray'). These things are qualities of the distribution.

Imagine if playing with a dice loaded so that it more often produces very high or very
low rolls - that would make modifiers less often sway the outcome, so underdogs would
be able to win more often.
If playing with a dice loaded so that it more often produces middle value rolls - that
would make modifiers more significant and flukes will happen less often.

So basically this is just a function for fairly loading the virtual dice which the combat system uses.

I will have a look at the source over the next few days and see if I can see where best to put the function
and substitute it in the existing combat simulations and possibly AI's API and/or scripts to make sure that
is in synch, and I will need to see about settings dialogue.
Help and pointers on were to put it etc appreciated, but Ill just push it to the repo and see, if no one has spare.

Thanks to all for this magical game! Hopefuly this will make it in :)
midberry
 
Posts: 8
Joined: January 22nd, 2016, 9:15 pm

Re: Very interesting talk on Random Number Generators

Postby Cackfiend » January 23rd, 2016, 8:41 am

so are you saying the RNG in wesnoth is flawed in some way?
"There's no love in fear." - Maynard James Keenan

I'm the guy who's responsible for 40% Gliders in all hexes... I can now die a happy man. =D
User avatar
Cackfiend
 
Posts: 400
Joined: January 28th, 2007, 7:36 am
Location: Florida, USA

Re: Very interesting talk on Random Number Generators

Postby midberry » January 23rd, 2016, 1:37 pm

Thanks for reply Cackfiend - I am sure the rngs quality is fine.

The playing qualities of the randomness used in Wesnoth are almost certainly not
perceptably affected by any statistical imperfections present in the standard libs
PRNG employed in the code.


This feature will actually use the present rng. It just allows the standard rngs flat variates to
be transformed into variates which are loaded in a settable way which can increase or decrease
the importance which combat modifiers have on the outcome of fights.
( Its similar effect to simply scaling the modifiers by a factor but better because the possibility of all
outcomes are preserved, the probability of rare outcomes is descreased or increased according
to the option parameters value)
midberry
 
Posts: 8
Joined: January 22nd, 2016, 9:15 pm

Re: Very interesting talk on Random Number Generators

Postby Pentarctagon » January 23rd, 2016, 3:51 pm

So it would allow people to choose how likely it is to get particularly good or bad results?
99 little bugs in the code, 99 little bugs
take one down, patch it around
-2,147,483,648 little bugs in the code
User avatar
Pentarctagon
Forum Administrator
 
Posts: 2888
Joined: March 22nd, 2009, 10:50 pm
Location: Earth (occasionally)

Re: Very interesting talk on Random Number Generators

Postby zookeeper » January 23rd, 2016, 4:05 pm

I'm not proficient to tell whether your method makes sense or not (mostly meaning that it's not easily exploitable), but assuming that it does and you do all the related work:

midberry wrote:A new option to choose game chanciness setting could be given separately, or this could be hidden in the
existing easy, medium, hard, nightmare settings. I believe easy and medium settings at least should be more
comfortable to play with fewer surprises.

Considering that the official position on RNG is and will continue to be that the current true (pseudo)randomness is "Wesnoth as intended", it would definitely have to be an off-by-default option somewhere in the preferences dialog, separate from difficulty levels.

On a related note, the preferences dialog is currently being re-worked and you might want to discuss it on #wesnoth-dev before beginning work on that.

Some additional things that you'd need to take into account: replays and multiplayer.
User avatar
zookeeper
WML Wizard
 
Posts: 9598
Joined: September 11th, 2004, 10:40 pm
Location: Finland

Re: Very interesting talk on Random Number Generators

Postby midberry » January 24th, 2016, 12:54 am

it would allow people to choose how likely it is to get particularly good or bad results?

Basically yes - it could be described as a setting to make combat more or less 'chaotic' :hmm:

it would definitely have to be an off-by-default option somewhere in the preferences dialog, separate from difficulty levels.

Right. If I dont find compiling Wesnoth too difficult I will send a patch soon with this feature and a setting.
If it is found not to be much use then I wont spend much time campaigning for it.

It 'should' be nice though :P . . . .
midberry
 
Posts: 8
Joined: January 22nd, 2016, 9:15 pm

Re: Very interesting talk on Random Number Generators

Postby Freem » May 22nd, 2016, 1:57 am

Simons Mith wrote:YouTube: https://youtu.be/45Oet5qjlms
FixYT: http://fixyt.com/watch?v=45Oet5qjlms

This video is an hour long plus a 15 min Q+A session at the end. It is likely to be of interest to anyone dealing with random number generators - quite possibly of professional interest.
[...]

See also: http://www.pcg-random.org


I will be honest, I was not able to understand what that person was saying. Probably because it's harder to understand english in videos than on a text.
For the text, it just seems like a document not targeted to people like me. Either I lack technical skills (which would not be that surprising), either I am just allergic to bad ads.

Anyway, I don't think it would be smart to add a dependency to wesnoth for the RNG. But I also have read/listened stuff before about "rand() considered harmful". And what resulted from my own experiments is that the C++11 standard functions (so no more dependency) are harder to use badly than rand, plus their behavior is actually defined by standard, unlike rand() again.
So, if people decided to remove rand(), it could be a good idea, not only to have a better Random Number God, but also to ease codebase's maintenance (who knows on what OS wesnoth might be ported, and how those OS will implement rand?), which is in my mind more important.
The only "negative" thing is that C++11 support would be needed.
Freem
 
Posts: 16
Joined: July 12th, 2009, 7:58 pm

Re: Very interesting talk on Random Number Generators

Postby galneon » July 28th, 2016, 6:52 pm

midberry wrote:
it would allow people to choose how likely it is to get particularly good or bad results?

Basically yes - it could be described as a setting to make combat more or less 'chaotic' :hmm:

it would definitely have to be an off-by-default option somewhere in the preferences dialog, separate from difficulty levels.

Right. If I dont find compiling Wesnoth too difficult I will send a patch soon with this feature and a setting.
If it is found not to be much use then I wont spend much time campaigning for it.

It 'should' be nice though :P . . . .


I think this is a great idea for the many who consider Wesnoth just too random--a sort of weighting in favor of a midpoint roll. I see midberry hasn't visited since January. Did anything ever come of this as an option?

P.S. Did anyone wear out their Genesis hitting the reset button to always land that first attack in Master of Monsters? :P
galneon
 
Posts: 8
Joined: August 22nd, 2014, 7:08 pm

Re: Very interesting talk on Random Number Generators

Postby Yomar » July 29th, 2016, 12:38 pm

I had the same idea time ago, so yes I would like this new settings.
Yomar
 
Posts: 231
Joined: October 27th, 2011, 5:14 am

Re: Very interesting talk on Random Number Generators

Postby LittleHandle » July 4th, 2017, 1:37 pm

This is an old thread, but I feel that it needs commenting on just in case someone thinks these are good ideas to use in Wesnoth.

First off, the field of RNGs at the advanced level is very interesting and has applications to cryptography and simulations where a very high level of precision would be useful. Wesnoth is not one of these. When people in this field talk about lack of randomness for RNGs, and failed statistical tests, they are talking about failure rates of less than 1% on large batches (if it even makes sense to re-run statistical tests). Imperceptible in a game like Wesnoth unless you're carefully tracking hundreds of thousands of attack rolls. Built in random methods will do just fine.

Secondly, midberry's proposal for shifting the distribution would not work as intended. Instead, it would change the existing balance of the game. If you make rolls of 0.5 more common (ie: loaded rng 0.6), then that would mean that it would be harder to hit units with evasion of 70%, and less likely to miss units with an evasion of 30%. If you make rolls of 0.5 less common (ie: loaded rng 0.4), it would make misses of 30% evasion and hits of 70% evasion more common. In effect, this would change the evasion rates for all units in the game, shifting them up or down depending if they are above or below 50%. Doing so would change the unit balance across the game, and have no effect on the rates of serial misses or hits beyond this change in balance (see below).

The main problem with RNGs if psychological. In fact, the more random you make things, the more some people think it isn't really random!

Consider for instance the statistics that track your damage dealt and received and how much these differ from expected. Suppose for instance, you've been very lucky in the first scenario of a campaign (or even in a series of attacks on a unit). Many people would think that this should balance out later, and that they will be less lucky in the next scenario (or attack on a unit). This is not how randomness works, as each roll of the dice is independent. While it is true that for most large games that the advantages or disadvantages should be close to zero (barring save scumming), if you've had a good string of luck (or lack of it) early on, your stats will more likely continue to show a lucky (unlucky) streak throughout the campaign. This is because the average for each scenario will likely be close to zero, and has just as much chance of being 'lucky' or 'unlucky'. Therefore, your earlier luck will carry through. (If you want to learn more about this phenomenon, look up random walks.)

You would get into trouble though if you wanted to make the RNG less random and conform to people's expectations. If you forced the RNG to average out (a more appropriate way to do this), first you'd have to track this for each side (otherwise the other side might get the benefit/loss of an unlucky/lucky streak for you). Even then, it would change the balance of the game at times (like midberry's proposal would do all the time), and give an advantage to the player that carefully tracks his 'luck' and therefore plans for a lucky or unlucky streak each turn. This would add an additional level of complexity and change the nature of the game, as the same unit encounters could play out very differently based on your current 'luck' level. Even then, the odds would most likely balance out later on, and unless you limit the memory (and enhance the predictable lucky/unlucky streaks), the randomness would eventually behave just as it does now.

Another example where our intuition gets random wrong is when considering rare events, and that counter-intuitively, it is actually fairly common for _some_ very rare event to occur given enough time. For instance, the case where your 4 attacks at 60% chance all miss. This has a chance of (0.4)**4 or 2.56% chance of happening in any given encounter. However, this could happen in any encounter. So, if you attack say 100 times in a scenario, the chance for something like this NOT happening at least once is (1 - 0.0256)**100 or only about 7.5%. In fact, something like this NOT happening in any given scenario should be pretty rare. Campaign wide (say 1000 battles), you would expect even an extremely rare event to be possible. Consider the case where 3 units all miss their 4 attacks at 60%. The likelihood of that (in any given sequence of attacks) is only about 0.0017 percent! However, something that rare should happen in about 1.7% (1 - (1-0.000017)**1000) of 1000-battle campaigns, so it is not impossible, especially with enough people playing. Further, when you consider all the possible ways that something rare could happen (extreme misses/hits, one-sided misses/hits, unexpected misses/hits, lucky/unlucky units) the chances of _something_ very rare happening in any campaign is actually not as low as you might think. This is not a flaw of the RNG, rather it is an indication that it is working very well. In fact, the best thing about RNGs, is that you can expect that for every encounter there is some chance of something unexpected happening, but that most often the most expected thing will happen, and the chances will always be the same in the same circumstance.

Long and the short, the RNG works well the way it is, and behaves exactly as expected.
LittleHandle
 
Posts: 13
Joined: December 6th, 2012, 4:38 am

Re: Very interesting talk on Random Number Generators

Postby Tad_Carlucci » July 4th, 2017, 2:55 pm

Yeah!

Someone who understands.

I get so tired of explaining to people that just because the odds are 1-in-10000, and we just saw it happen twice in a row, does not prove there is a flaw in the RNG but does, in fact, lend credence to the claim it is actually random; and that if were could never see it happen twice in a row, it would be clear proof it was not truly random.

For single-player, the RNG is meaningless. Simply reload and replay until you get the result you want.

For MP, it is critical the RNG be fair.

This thread is about making it not-fair.
I forked real life and now I'm getting merge conflicts.
Tad_Carlucci
Developer
 
Posts: 168
Joined: April 24th, 2016, 4:18 pm


Return to Coder’s Corner

Who is online

Users browsing this forum: No registered users and 1 guest