[April Fool's] Wesnoth Random Number Generator Changes

General feedback and discussion of the game.

Moderator: Forum Moderators

Dave
Founding Developer
Posts: 7071
Joined: August 17th, 2003, 5:07 am
Location: Seattle
Contact:

[April Fool's] Wesnoth Random Number Generator Changes

Post by Dave »

Over the course of time, a large number of complaints have been made about Wesnoth's random number generator (RNG). While I have often dismissed these complaints due to cognitive bias or for other reasons, I have come to realize that I must acknowledge my own cognitive bias in the face of such overwhelming anecdotal evidence.

As such, I have worked with several of the best programmers, mathematicians, and statisticians I have known over my career, and am coming up with a new, comprehensive RNG system for Wesnoth that will hopefully solve all the problems we have had with inaccurate random numbers ruining otherwise pleasant games.

Currently I think our random number generator is at least 87% accurate [1]. I would have thought this would be good enough, but it seems like it's not. So, now I want to strive for a RNG that is absolutely 100% accurate. So far we have got it to around 99.99% accuracy, which I think is ready for testing, but we really want 100% accurate random numbers by the 1.8 release.

In doing so, I have worked with some engineers from my days at Google. They were especially excited by this project because it gives yet another application for Google's computing resources. The way this new random number generator works is by taking a huge sample of the pages on the web, and does a massive checksum of these pages. After all, the web is huge and ever changing, so the checksum of a sufficiently large number of web pages will be indistinguishable from random noise. To give a comparison, we are basically shaving the dice to be an exact perfect cube with no biases or weights, like they do in all serious casinos.

There are still several issues with this, of course. For one thing, summing those web pages does take a substantial amount of time, and ultimately computing resources. In fact, we're not sure if we'll have the computing resources to compute random numbers for everyone playing Wesnoth. We might have to institute a program where some players who want the most accurate numbers of all can pay for a premium random number service, to cover the cost of all the resources.

Anyhow, I would love some feedback on all this. I've put a page up which will generate a stream of random numbers. Of course, it's computing the checksum from millions of sites in real time, so it'll take a while to load -- it's a simple perl script which connects to our upstream farm of machines that are crunching the numbers and then prints out the numbers it generates. I'd love people to look at them and tell me if they think the numbers look random.

Here's the site: http://www.wesnoth.org/cgi-bin/dave/rand-test.pl

For comparison purposes, I've put up a similar script which uses Wesnoth's current RNG, for users using Linux (Windows and OSX users will have slightly different results). Wesnoth's current RNG is here: http://www.wesnoth.org/cgi-bin/dave/rand-old.pl (it'll run much faster of course). I'd love for people to look at both sets of numbers and make any comments on what seems most random.

Of course the speed is very slow, so we're working on ways to speed it up before putting it in-game. People may still have to wait a few seconds on every combat, though.

Also, people have complained a lot about the AI perhaps cheating, or skewing the random numbers. At first, of course, I dismissed these complaints too. But, I have realized that our pluggable AI framework allows for sophisticated AI's which are programmed to dynamically respond to changing conditions to adaptively develop a winning strategy. I think it's impossible to rule out the possibility of the AI somehow touching the memory pages where the RNG data is stored in order to manipulate the RNG in its favor.

As such, I've decided that something has to be done about this. In order to thwart any AI attempt at subverting the RNG, we are going to insert code into Wesnoth that will call mprotect() on the memory regions where the RNG seed and other data is stored while AI algorithms are run. The memory will be set to PROT_NONE -- i.e. the AI will not be able to either read or write the memory where the RNG is stored. This will make sure the AI can't possibly interfere with the RNG or skew it in its favor. Additionally, we will be tracking calls to mprotect() using strace to ensure that the AI can't possibly call mprotect() itself to unprotect the page and read or write to it.

With this feature in place, we can be fairly sure the AI won't be able to cheat. Of course, it's possible the AI will make an illegal access to the memory page with the random number generator, so we will catch SIGSEGV and detect if that is the illegal page being accessed. Then we will print a message telling the user of the segmentation fault but mentioning that it's possible the AI was trying to cheat.

Any comments or feedback on these changes is valued and welcome!

David

[1] This is on Linux, and based on Die Hard test results coupled with the incidence of anecdotal evidence.
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
User avatar
NarajinX
Posts: 18
Joined: March 26th, 2009, 11:10 pm
Location: Calgary,Alberta

Re: Wesnoth Random Number Generator Changes

Post by NarajinX »

Quickly tried both random number generators.

Wesnoth RNG provided mostly 50 and above while the webpage checksum gave more even spread (0-99).

Seems the Wesnoth RNG is skewed but will try couple times.


Update:
Tried 7 times. Wesnoth RNG didn't give me any number below 50.
5dPZ
Posts: 211
Joined: July 11th, 2006, 7:20 pm
Location: Vancouver, Canada

Re: Wesnoth Random Number Generator Changes

Post by 5dPZ »

I think today is a good time to declare that RNG will be removed and all units will have 1 attack with x dmg that always hits.
User avatar
thespaceinvader
Retired Art Director
Posts: 8414
Joined: August 25th, 2007, 10:12 am
Location: Oxford, UK
Contact:

Re: Wesnoth Random Number Generator Changes

Post by thespaceinvader »

5dPZ wrote:I think today is a good time to declare that RNG will be removed and all units will have 1 attack with x dmg that always hits.
I agree with this assessment.
http://thespaceinvader.co.uk | http://thespaceinvader.deviantart.com
Back to work. Current projects: Catching up on commits. Picking Meridia back up. Sprite animations, many and varied.
Yogibear
Retired Developer
Posts: 1086
Joined: September 16th, 2005, 5:44 am
Location: Hamburg, Germany

Re: Wesnoth Random Number Generator Changes

Post by Yogibear »

Dave wrote:As such, I've decided that something has to be done about this. In order to thwart any AI attempt at subverting the RNG, we are going to insert code into Wesnoth that will call mprotect() on the memory regions where the RNG seed and other data is stored while AI algorithms are run. The memory will be set to PROT_NONE -- i.e. the AI will not be able to either read or write the memory where the RNG is stored.
:lol2:

As a dev not too familiar with the C libraries i actually googled mprotect - and was quite surprised it actually exists :o . I didn't expect that because PROT_NONE sounds like a bad name to me - i would expect it to read as "no protection" :wink: .
Smart persons learn out of their mistakes, wise persons learn out of others mistakes!
HomerJ
Posts: 812
Joined: April 25th, 2008, 1:22 pm
Location: Hannover, Germany

Re: Wesnoth Random Number Generator Changes

Post by HomerJ »

:lol2:
The timing is just perfect!

Greetz
HomerJ
Six years without a signature!
Blarumyrran
Art Contributor
Posts: 1700
Joined: December 7th, 2006, 8:08 pm

Re: Wesnoth Random Number Generator Changes

Post by Blarumyrran »

Code: Select all

[code]
[/code]
Last edited by Blarumyrran on August 30th, 2014, 11:43 am, edited 1 time in total.
User avatar
ivanovic
Lord of Translations
Posts: 1149
Joined: September 28th, 2004, 10:10 pm
Location: Germany

Re: Wesnoth Random Number Generator Changes

Post by ivanovic »

Since some of you might be surprised that 1.8 is announced now:

Yes, Dave has spent some serious efforts into this subproject. But so far this new random number generator is not used everywhere in the game. We started this project before ubisoft announced their game launcher project. The general plan was that you have to be connected to the wesnoth servers from where you would be getting the random numbers. Yes, even for singleplayer campaign gameplay. The problem would be that without contact to our server you would not be able to play. After seeing the fiasco ubisoft went into we decided to introduce this change in two steps:

1) From 1.8 onwards you get your random numbers from the multiplayer server. As you might have seen in the changelogs from sometime last summer, this was already the case for several 1.7.x versions. What has changed is the algorithm we are now using to generate those random numbers. So for multiplayer games, once you updated to 1.8, you will already see the new RNG working.

2) So far we are having problems to make things work in a reliable way for singleplayer gameplay. Currently we are working on having this feature activated for singleplayer mode, too, but we are not sure if we will manage to do so with 1.8.1. The problem is that currently you have to get the random numbers right from our server. We want to talk google into allowing everyone making use of the new googleRNG, but this might still take some time.

Short version: if you want to experience these great new random numbers ingame you have to play multiplayer on the official 1.8 multiplayer server!
Velensk
Multiplayer Contributor
Posts: 4002
Joined: January 24th, 2007, 12:56 am

Re: Wesnoth Random Number Generator Changes

Post by Velensk »

I read this and was trying to figure out how to respond, then I caught on.
"There are two kinds of old men in the world. The kind who didn't go to war and who say that they should have lived fast died young and left a handsome corpse and the old men who did go to war and who say that there is no such thing as a handsome corpse."
User avatar
artisticdude
Moderator Emeritus
Posts: 2424
Joined: December 15th, 2009, 12:37 pm
Location: Somewhere in the middle of everything

Re: Wesnoth Random Number Generator Changes

Post by artisticdude »

ivanovic wrote:2) So far we are having problems to make things work in a reliable way for singleplayer gameplay. Currently we are working on having this feature activated for singleplayer mode, too, but we are not sure if we will manage to do so with 1.8.1. The problem is that currently you have to get the random numbers right from our server. We want to talk google into allowing everyone making use of the new googleRNG, but this might still take some time.
So does this mean, should this feature ever get implemented, that you will have to be connected to the internet whenever you want to play single-player campaigns in wesnoth? That could be problematic for those of us with a usage limit...
"I'm never wrong. One time I thought I was wrong, but I was mistaken."
Mabuse
Posts: 2239
Joined: November 6th, 2007, 1:38 pm

Re: Wesnoth Random Number Generator Changes

Post by Mabuse »

umm, reading this thread - i cant belive the current wesnoth RNG is really that bad.
(and that noone has never rcognized it before - i remember several threads where it was stated that the RNG is good and nothing is wrong with it)

i tried the old rng (linked here) several times now and the results are really not good.
they are, to be honest, disastrous. i cant believe that this is really the wesnoth rng


imo, i dont think its good to connect to the internet for getting random numbers, is there no other way ?
The best bet is your own, good Taste.
User avatar
ivanovic
Lord of Translations
Posts: 1149
Joined: September 28th, 2004, 10:10 pm
Location: Germany

Re: Wesnoth Random Number Generator Changes

Post by ivanovic »

If you want to rely on the randomness the internet gives you via a checksum over website:
No, it is not possible to obtain this random seed regulary without connection to the internet. We could of course make sure that the fallback to the old RNG is still around, but then the complaints we get would be really strange. Eg some people saying that the RNG is perfectly fine and all mistakes are just part of the way human being perceive things and the others saying that it is clearly wrong, suddenly a case where both might be right. Like I said, a hard decision for us and not easy to find a good solution. At least for the moment you will have good random numbers when using the official 1.8.x multiplayer server. Hey, this is at least a start, right?
ilor
Inactive Developer
Posts: 129
Joined: March 24th, 2008, 9:05 pm

Re: Wesnoth Random Number Generator Changes

Post by ilor »

artisticdude wrote:So does this mean, should this feature ever get implemented, that you will have to be connected to the internet whenever you want to play single-player campaigns in wesnoth? That could be problematic for those of us with a usage limit...
Keep in mind that the server will be downloading and checksumming the webpages, and will only send you the resulting random numbers. It's not a ot of data, shouldn't be more than several megabytes per month even if you play a lot.
User avatar
alda
Posts: 49
Joined: December 2nd, 2009, 4:06 pm

Re: Wesnoth Random Number Generator Changes

Post by alda »

Of course the speed is very slow, so we're working on ways to speed it up before putting it in-game. People may still have to wait a few seconds on every combat, though.
This could also be quite a problem. But anyway, what are these minor problems compared to the beauty of having a RNG based on browsing internet pages ?


Also, I'd really want to thank Dave and the devs team for finding ways to protect us against the evil AI. Keep on the good work, someday we will defeat it ! :P
User avatar
King_Elendil
Posts: 250
Joined: February 26th, 2010, 4:54 am

Re: Wesnoth Random Number Generator Changes

Post by King_Elendil »

My brother is a huge fan of Wesnoth, but he doesn't have an internet connection. Does this mean that he wouldn't have any noticeable changes with the RNG, because he would still be using the old one?
I'm finally admitting that this will be a very long (if not permanent) Wesbreak. Thank y'all for the great times, and may Wesnoth rise to become one of the most popular games on the planet.
Post Reply