Random or Pseudorandom?

General feedback and discussion of the game.

Moderators: Forum Moderators, Developers

Tryptic
Posts: 8
Joined: August 19th, 2009, 4:14 pm

Random or Pseudorandom?

Post by Tryptic » June 20th, 2011, 2:47 am

Now hopefully I can start talking about Wesnoth's randomness without causing a massive threadnought of opinions. I'm concerned about the randomness of Wesnoth but NOT the way you're thinking.

I played Wesnoth in the past, after lamenting to a friend that Fire Emblem needed a multiplayer aspect. We had a good time, but as college got busy we put it down for other things. Now I'm returning just to see what's new (drakes have some awesome new attack animations :D ) and I just felt like going through my favorite campaign again, Descent into Darkness.

At first I told myself, "I won't load when things go bad" and stuck to it for several levels. I lost my first wraith...and my second, but eventually I managed to steamroll the orcs and come out with some living (sort of) rank-2 units. However every once in a while the game made me cringe. A battle where 2 units with 50% and 60% miss chance together launched 7 attacks and missed every one (chances of this happening = 0.32%) When I played Wesnoth before I hadn't taken a ProbStats class yet and didn't have the rock-solid understanding of probability I do now :wink: but things like that usually struck me as odd.

As the games wore on and my units became increasingly harder to replace, I found myself getting more and more upset. My Skeleton warrior died when the damage calculation said it was a 5% chance. But what surprised me was when I reloaded the game, tried again and it happened again. (chances of this happening = 0.25%)

Now, I understand that it's impossible to prove a random number generator bad simply because an unusual pattern has appeared, but this is not the first time this has happened! In this game events with less than a 5% probability seem to happen much more often than 5% of the time. I don't mean to whine (in fact if this project takes part in Google's Summer of Code program next year I will definitely apply) but I wonder if somebody could take a look at the random number generator, maybe run it through the DIEHARD test or something? I believe there's a good probability (no pun intended) that it isn't handling small probabilities correctly, or that it tends to not vary properly from one number to the next resulting in strings of similar results.

I know that random chance is a core part of Wesnoth, but at least the campaign part of it is built on ranking units up! In multiplayer it's fine, in campaigns it's heartbreaking to set up the best defensive line possible that will still advance to the objective fast enough, and have to do it a second time because the RNG sniped your best unit.

It sounds a bit odd to suggest that something so basic to the game has a flaw, but I can see how it could be missed. Some people whine because it's different from Fire Emblem without saying anything important. Anybody mature enough to be polite and work with the community to study the problem is also mature enough to think that they're only upset because they had to load, and decides to stay silent. If there WERE a problem with the RNG, no single player or developer would be able to tell. This is why I think there IS a problem and it hasn't been looked at yet.

User avatar
Jetrel
Art Director
Posts: 7241
Joined: February 23rd, 2004, 3:36 am
Location: Midwest US

Re: Random or Pseudorandom?

Post by Jetrel » June 20th, 2011, 3:32 am

This person is coming to us with foreknowledge of the usual RNG debates, and is not trying to participate in them. He is not questioning our intent, only the nitty-gritty mathematical details of our execution. Because he's aware of the status quo, please refrain from any comments about the purpose or appropriateness of our RNG, whether for or against. I especially direct this as our forum regulars and MP experts/devs - do not hammer him with the usual sermon on why we have a RNG. He knows that, and your posts will only drown out a worthwhile signal in noise.

Any such posts will be promptly deleted.
Play Frogatto & Friends - a finished, open-source adventure game!

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

Re: Random or Pseudorandom?

Post by Dave » June 20th, 2011, 3:37 am

Tryptic wrote:A battle where 2 units with 50% and 60% miss chance together launched 7 attacks and missed every one (chances of this happening = 0.32%)
Actually, assuming there was a 50% miss chance, there would be a 0.78% chance of this happening. With some of the attacks having 60% miss chance, it'd be higher.

Considering the number of units that attack each other in a typical battle in Wesnoth, and considering the number of Wesnoth battles that take place, it is unsurprising that this happens from time to time.
Tryptic wrote: My Skeleton warrior died when the damage calculation said it was a 5% chance. But what surprised me was when I reloaded the game, tried again and it happened again. (chances of this happening = 0.25%)
Do you perhaps have the game configured to save random seeds when you save the game, so the same thing would have been guaranteed to occur?
Tryptic wrote: In this game events with less than a 5% probability seem to happen much more often than 5% of the time.
So the problem is that people come along making a claim like this from time to time, but when asked to provide any kind of solid evidence, these people inevitably evaporate.

I put it down to cognitive bias. Though I'm always happy to be proved otherwise. It shouldn't be that hard to do.
Tryptic wrote: I don't mean to whine (in fact if this project takes part in Google's Summer of Code program next year I will definitely apply) but I wonder if somebody could take a look at the random number generator, maybe run it through the DIEHARD test or something?
Maybe you should take it upon yourself to do this? After all, if you showed a problem with the RNG, then that'd give you a huge leg up in consideration for GSoC! ;)

David
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming

Tryptic
Posts: 8
Joined: August 19th, 2009, 4:14 pm

Re: Random or Pseudorandom?

Post by Tryptic » June 20th, 2011, 4:08 am

Haha now I feel like whining. You mean I need to go load the binaries and check it myself...

that's an interesting point though, now I want to figure out exactly how many attacks I've done this afternoon. I had assumed around 1000 which puts the aforementioned events at around 1% probability, but of course it could be much higher than that.

While I'm at it, I should mention that the reason I'm trusting my gut with this thread is because my dad and I are working on publishing a board game sometime in the next few years, a game similar to Risk. I've been playtesting for weeks, and sometimes a 6% chance succeeds when a 60% chance fails but Wesnoth just feels like it gets more consecutive rolls than the dice I use.

As for looking at the code itself, I'm not familiar with the system you guys use. Would I be able to unpack the zip file from this site and open it in Eclipse or is there more I'm going to need? If you can point me in the right direction I'll see what I can do.

User avatar
Pentarctagon
Forum Administrator
Posts: 3981
Joined: March 22nd, 2009, 10:50 pm
Location: Earth (occasionally)

Re: Random or Pseudorandom?

Post by Pentarctagon » June 20th, 2011, 4:35 am

Perhaps relevant to this thread: In response to someone in a different thread, I had two units attack each other. Each was on 40% dodge and they attacked each other with a 1-100,000 attack. After that was all done (it took a few hours :lol2: ), unit A had hit unit B 60,011 times and unit B had hit unit A 60,026 times.
99 little bugs in the code, 99 little bugs
take one down, patch it around
-2,147,483,648 little bugs in the code

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

Re: Random or Pseudorandom?

Post by Dave » June 20th, 2011, 4:55 am

Tryptic wrote: While I'm at it, I should mention that the reason I'm trusting my gut with this thread is because my dad and I are working on publishing a board game sometime in the next few years, a game similar to Risk. I've been playtesting for weeks, and sometimes a 6% chance succeeds when a 60% chance fails but Wesnoth just feels like it gets more consecutive rolls than the dice I use.
I think you should remember that Wesnoth has lots of dice rolls in it. If you were to roll each one of them with physical dice, it'd take quite a long time.

In its saves, by the way, Wesnoth records how often different events occurred. For instance, there might be a section like this:

Code: Select all

				[sequence]
					s1010="1"
					s111="1"
					_num="60"
				[/sequence]
This indicates that twice in the scenario the indicated side attacked with a 60% chance to hit. Once they hit, missed, hit, missed. Once they hit, hit, hit.

It is quite easy to, after playing a while, extract all saves you have and analyze how often unusual events occur.
As for looking at the code itself, I'm not familiar with the system you guys use. Would I be able to unpack the zip file from this site and open it in Eclipse or is there more I'm going to need? If you can point me in the right direction I'll see what I can do.
http://wiki.wesnoth.org/WesnothSVN

Note that to generate random numbers, Wesnoth basically just uses rand().

David
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming

Tryptic
Posts: 8
Joined: August 19th, 2009, 4:14 pm

Re: Random or Pseudorandom?

Post by Tryptic » June 20th, 2011, 5:25 am

Ah, thanks a lot. Right after I read this I went back and saw the SVN link on the compiling page. The next free time I get I'll go look and start figuring things out.

I figured that in the end it would be the rand() function, and I know it generates numbers across the spectrum properly. In response to pentarctagon's comment, the problem I think I see (If I didn't imagine it) is either too much or too little variation between individual results. I know it's just an example, but Dave's attack log shows what I mean: either hit-hit-hit-miss-miss-miss-miss or hit-miss-hit-miss-hit-miss patterns occurring too often. When designing a pseudorandom number generator I know it's incredibly difficult to avoid this kind of tendency.

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

Re: Random or Pseudorandom?

Post by Dave » June 20th, 2011, 1:41 pm

Tryptic wrote:Dave's attack log shows what I mean: either hit-hit-hit-miss-miss-miss-miss or hit-miss-hit-miss-hit-miss patterns occurring too often.
However, if you sum up all of the attack patterns after a sufficiently long time playing, you'll see that they each occur in amounts close to what one would statistically expect.
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming

User avatar
Limabean
Posts: 350
Joined: August 26th, 2008, 2:14 pm
Location: New Hampshire, USA

Re: Random or Pseudorandom?

Post by Limabean » June 20th, 2011, 3:30 pm

Dave wrote:
Tryptic wrote:Dave's attack log shows what I mean: either hit-hit-hit-miss-miss-miss-miss or hit-miss-hit-miss-hit-miss patterns occurring too often.
However, if you sum up all of the attack patterns after a sufficiently long time playing, you'll see that they each occur in amounts close to what one would statistically expect.
I think Tryptic has a very good point with the patterns. Imagine a very common situation in wesnoth campaign. You've set up a defensive line and the only unit at any risk of death is a lvl 2 Troll. You've put it on a hills with a reasonable 50% defense and left the enemy only 1 slot to attack. He will need 3 hits with his pikeman to get the kill. He gets all three hits Anyway, what seems to happen often is that those concentrated hits by one unit, resulting in a frustrating loss, will be followed by an unusual number of misses from the rest of the enemy force.

As dave said, the overall "sum of the attack patterns" would be statistically reasonable. However that doesn't change the fact, at least in the eyes of the casual player, that a valuable unit died when it shouldn't have. It's also not much of a consolation that the non-critical units escaped with less damage than expected.

Anyway, just my humble observations. I'm not sure there needs to be any change, and i'm happy with the way things are, but I can understand why some people get frustrated.
When a scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong.
-Arthur C. Clarke-

bjhartin
Posts: 10
Joined: October 19th, 2009, 7:08 pm

Re: Random or Pseudorandom?

Post by bjhartin » June 20th, 2011, 8:14 pm

I wonder if this is just a matter of how you are thinking about the problem. I'll assume you do have a good understanding of probability, as you've said.

Let's think about a typical campaign, using very generalized figures as a basis:

* 15 scenarios
* A typical scenario length of 15 turns
* A typical 'confrontations per turn' of six, e.g. you attack with three units and the computer does the same. Obviously this is over simplified, but it's a starting point.

This gives us the following number of unit-vs-unit confrontations per campaign:

15 * 15 * 6 = 1350

So, for an event that has a 1% chance of occurring, you would expect to see that happen about 13.5 times in a given campaign. In your initial post you say:
However every once in a while the game made me cringe. A battle where 2 units with 50% and 60% miss chance together launched 7 attacks and missed every one (chances of this happening = 0.32%)
By my calculation, you would expect to see such a scenario 4.32 times per campaign. Does that square with your thinking? Do you think you are seeing it much more than that?

Insinuator
Posts: 706
Joined: January 6th, 2004, 10:42 pm
Location: Portland, OR

Re: Random or Pseudorandom?

Post by Insinuator » June 21st, 2011, 12:02 am

Limabean wrote:As dave said, the overall "sum of the attack patterns" would be statistically reasonable. However that doesn't change the fact, at least in the eyes of the casual player, that a valuable unit died when it shouldn't have. It's also not much of a consolation that the non-critical units escaped with less damage than expected.
But the sum over attacks is what it's really all about. To a RNG, it doesn't matter what the situation is. So, your Dwarvish Fighter may miss 20 retaliatory strikes against an Orcish Grunt on grass but then hit all three times to kill an Assassin on castle. Just because the situation doesn't line up doesn't mean the RNG is broken. In fact, to me, it illustrates how well it works. It's merely our perspective and the damage done that is different.

Penctarctagon's test really seems to be the best way to test the RNG and it seems to be working.

Making it "more accurate" situationally would really reduce the randomness, making a more deterministic game. (Which personally I would love. :wink: )

Tryptic
Posts: 8
Joined: August 19th, 2009, 4:14 pm

Re: Random or Pseudorandom?

Post by Tryptic » June 21st, 2011, 2:29 am

bjhartin wrote:I wonder if this is just a matter of how you are thinking about the problem. I'll assume you do have a good understanding of probability, as you've said.

Let's think about a typical campaign, using very generalized figures as a basis:

* 15 scenarios
* A typical scenario length of 15 turns
* A typical 'confrontations per turn' of six, e.g. you attack with three units and the computer does the same. Obviously this is over simplified, but it's a starting point.

This gives us the following number of unit-vs-unit confrontations per campaign:

15 * 15 * 6 = 1350

So, for an event that has a 1% chance of occurring, you would expect to see that happen about 13.5 times in a given campaign. In your initial post you say:
However every once in a while the game made me cringe. A battle where 2 units with 50% and 60% miss chance together launched 7 attacks and missed every one (chances of this happening = 0.32%)
By my calculation, you would expect to see such a scenario 4.32 times per campaign. Does that square with your thinking? Do you think you are seeing it much more than that?
Yeah, I understand there is a good chance that my brain is picking out patterns that SHOULD happen that often. I feel like I saw those situations more often than that (given that I only played 4-5 scenarios) but I know that, for example, 7 misses in a row and 6 hits in a row do not "stack" together when counting.

However the study and (maybe) correction of this problem isn't nearly as complicated as the problem itself. If there IS a problem with the RNG, however miniscule, it stems from the use of rand(), a basic pseudorandom number generator built into the language for simplicity. Just from a quick browse around the internet, I'm certain that more than one cryptography group has released better RNGs for public use.

So the practical question is, if a fancier RNG can be found in the Cryptography community or someplace, would the devs be willing to use it? If it runs slower, how much slower would be tolerable? The code conversion would be easy enough if a good replacement is found.

Atz
Art Contributor
Posts: 313
Joined: August 21st, 2008, 2:22 am

Re: Random or Pseudorandom?

Post by Atz » June 21st, 2011, 4:56 am

Limabean wrote:However that doesn't change the fact, at least in the eyes of the casual player, that a valuable unit died when it shouldn't have. It's also not much of a consolation that the non-critical units escaped with less damage than expected.
The vast majority of players have a terrible understanding of probability and a chronic case of cognitive bias. Conforming to player expectations would meaning making the interface outright lie about the probabilities, while secretly fudging numbers to protect the bias of the player. It would also mean that human players should get better "random" numbers than AIs, since humans are prone to complaining that the computer is cheating if it ever gets lucky. Some games do actually do this, which probably isn't helping on the "understanding of probability" front. I suppose it comes down to the choice of whether you think it's more important to have probability mechanics which work the way they claim to and which can't be gamed, or to keep people from complaining.

It's also worth noting that sometimes people complain because computer RNGs tend to produce a more "random" distribution than than real-world randomisation methods. Card games are particularly prone to this, since shuffling takes some time and many people don't take enough time or use the right technique to fully randomise the deck.

User avatar
Viliam
Translator
Posts: 1341
Joined: January 30th, 2004, 11:07 am
Location: Bratislava, Slovakia
Contact:

Re: Random or Pseudorandom?

Post by Viliam » June 21st, 2011, 8:55 am

Tryptic wrote:I know it's just an example, but Dave's attack log shows what I mean: either hit-hit-hit-miss-miss-miss-miss or hit-miss-hit-miss-hit-miss patterns occurring too often.
Perhaps could you post a real log from your game, so we can speak about those numbers -- whether they are random or not.

Max
Posts: 1449
Joined: April 13th, 2008, 12:41 am

Re: Random or Pseudorandom?

Post by Max » June 21st, 2011, 12:00 pm

Insinuator wrote:However the study and (maybe) correction of this problem isn't nearly as complicated as the problem itself. If there IS a problem with the RNG, however miniscule, it stems from the use of rand(), a basic pseudorandom number generator built into the language for simplicity.
wesnoth doesn't use rand().

Locked