pseudo-random generator + improvement idea

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

Moderators: Forum Moderators, Developers

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

Re: pseudo-random generator + improvement idea

Post by Max » August 20th, 2009, 1:43 pm

from the 1.7.3 changelog:

* Multiplayer:
* Server-side generation of random numbers for MP (combats)

User avatar
Saphy
Posts: 31
Joined: December 28th, 2006, 2:07 am

Re: pseudo-random generator + improvement idea

Post by Saphy » August 20th, 2009, 1:58 pm

The best random generator rely not on computation, but on external entropy. Since must of the Unix system support /dev/urandom, why not use that instead?

Sauron
Posts: 221
Joined: January 11th, 2006, 8:51 am
Location: Barad-Dur, Mordor
Contact:

Re: pseudo-random generator + improvement idea

Post by Sauron » August 20th, 2009, 3:05 pm

Random numbers are generated on the Wesnoth server during MP combats,
making 1.7.3 require a supporting wesnothd version and unable to play
a game with earlier versions.
Does that mean you need to run also a server during game? :shock:
Sauron
Customize yourself random factor in game:
GET my mod [available as C++ sourcecode and compiled Windows executable] for wesnoth 1.6.4
at http://saurons-mod.zor.org/
Mod thread
http://www.wesnoth.org/forum/viewtopic.php?t=26803

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

Re: pseudo-random generator + improvement idea

Post by Max » August 20th, 2009, 3:28 pm

no, both clients need to be 1.7.3 and connect to the official (1.7) server.

Sauron
Posts: 221
Joined: January 11th, 2006, 8:51 am
Location: Barad-Dur, Mordor
Contact:

Re: pseudo-random generator + improvement idea

Post by Sauron » August 20th, 2009, 4:11 pm

Well, good idea - no 'tweaking' of random numbers will be possible. Other than that - Mersenne Twister is the best computationally effective RNG at the moment and really worth consideration alternative to rand.
Sauron
Customize yourself random factor in game:
GET my mod [available as C++ sourcecode and compiled Windows executable] for wesnoth 1.6.4
at http://saurons-mod.zor.org/
Mod thread
http://www.wesnoth.org/forum/viewtopic.php?t=26803

wbr
Posts: 12
Joined: September 14th, 2008, 3:06 pm

Re: pseudo-random generator + improvement idea

Post by wbr » September 28th, 2009, 8:01 am

i agree with all request for changing the random... you tell us that statistic is good and bla bla mumbo numbo after 5 rounds its ok ... first of all there is 3 kinds of lies
lie, filthily lie and statistic :).

so what your statistic do put the all strikes in same group and tell see statistic is near + - 0. if u play game you can clearly see that units who attack somebody on 70 or 60% chance to hit fail in their attacks then unit with 30 chance to hit strikes 2 or 3 times... after that statistic is better and u say that its ok... its not ok this is strategy STRATEGY what type strategy is that if i capture the better terrain and i get better defence and thats not realy important becouse it anyway fall on some random generator who say u got number this its greater or smaller than that and ofcourse u hit or miss :(
that is low point of the game

User avatar
zookeeper
WML Wizard
Posts: 9739
Joined: September 11th, 2004, 10:40 pm
Location: Finland

Re: pseudo-random generator + improvement idea

Post by zookeeper » September 28th, 2009, 9:10 am

wbr wrote:i agree with all request for changing the random... you tell us that statistic is good and bla bla mumbo numbo after 5 rounds its ok ... first of all there is 3 kinds of lies
lie, filthily lie and statistic :).

so what your statistic do put the all strikes in same group and tell see statistic is near + - 0. if u play game you can clearly see that units who attack somebody on 70 or 60% chance to hit fail in their attacks then unit with 30 chance to hit strikes 2 or 3 times... after that statistic is better and u say that its ok... its not ok this is strategy STRATEGY what type strategy is that if i capture the better terrain and i get better defence and thats not realy important becouse it anyway fall on some random generator who say u got number this its greater or smaller than that and ofcourse u hit or miss :(
that is low point of the game
Ain't true.

hiro hito
Posts: 201
Joined: November 23rd, 2006, 8:00 am

Re: pseudo-random generator + improvement idea

Post by hiro hito » September 28th, 2009, 4:53 pm

Can I troll this last RNG thread? :P
"Of course His Majesty is a pacifist. When I told him that to initiate war was a mistake, he agreed.Thus, gradually, he began to lead toward war."-Emperor Shòwa (Enlightened Peace)'s chief cabinet secretary

User avatar
Zarel
Posts: 700
Joined: July 15th, 2009, 8:24 am
Location: Minnesota, USA
Contact:

Re: pseudo-random generator + improvement idea

Post by Zarel » September 28th, 2009, 5:32 pm

Saphy wrote:The best random generator rely not on computation, but on external entropy. Since must of the Unix system support /dev/urandom, why not use that instead?
Depends on the purpose. If you want verifiable random numbers without having to send each one, a number pseudorandomly generated from a seed is indistinguishable from true randomness for the purpose of a game like Wesnoth, requires less bandwidth.

Also, /dev/urandom relies on computation. ;) You're thinking of /dev/random, which you shouldn't be reading unless you're writing a crypto program or something. It's way overkill for a game.
Proud creator of the :whistle: smiley | I prefer the CC-0 license.

Noy
Inactive Developer
Posts: 1321
Joined: March 13th, 2005, 3:59 pm

Re: pseudo-random generator + improvement idea

Post by Noy » September 28th, 2009, 10:12 pm

hiro hito wrote:Can I troll this last RNG thread? :P
The mere fact you're posting in here with nothing to say except to point out your obsession with this topic just underlines our annoyance with you. Others with the same concerns actually do something constructive with their time on here. You just repeat the same simplistic arguments in every thread with a tangental relationship with RNG without regard of any previous arguments. With a few exceptions that basically sums up your contribution on the forum.
I suspect having one foot in the past is the best way to understand the present.

Don Hewitt.

Yoyobuae
Posts: 408
Joined: July 24th, 2009, 8:38 pm

Re: pseudo-random generator + improvement idea

Post by Yoyobuae » September 28th, 2009, 11:00 pm

I ran an experiment. The problem is not the RNG.

First I got a control. HERE is a hardware random number generator that someone else built. In that page there is some sample output that can be downloaded.

So I processed that output and produced the same kind of random sequence Wesnoth would. Since most of the complaining is about long sequences of misses/hits, I counted how many occurrances of these sequences happen on the output.

This is what I got for 500 events at a simulated 70% defense (or 30% conversely):
*** CONTROL ***
*** 70% / 30% ***
one hit / miss in a row: 63
two hits / misses in a row: 16
three hits / misses in a row: 6
four hits / misses in a row: 1
---
one miss / hit in a row: 23
two misses / hits in a row: 17
three misses / hits in a row: 10
four misses / hits in a row: 11
five misses / hits in a row: 7
six misses / hits in a row: 8
seven misses / hits in a row: 4
eight misses / hits in a row: 3
nine misses / hits in a row: 1
ten misses / hits in a row: 3
eleven misses / hits in a row: 1
twelve misses / hits in a row: 1
thirteen misses / hits in a row: 1
fourteen misses / hits in a row: 0
fifteen misses / hits in a row: 1

At first I was surprised that such long sequences of misses do occasionally happen. Sure a single wesnoth battle probably has fewer events, which means these would be more rare (but after many battles, it can probably happen).

Now this is what happened on wesnoth. The test was done with elvish archers on forests, with lots of thunderers attacking them with their ranged attack. I only took into account whether thunderer hit or miss (a single attack was easier to track, "bang!" = hit, *silence* = miss :D ). I wrote that down on a text file and counted the sequences:
*** WESNOTH ***
*** 70% / 30% ***
one hit / miss in a row: 57
two hits / misses in a row: 29
three hits / misses in a row: 6
four hits / misses in a row: 0
---
one miss / hit in a row: 17
two misses / hits in a row: 19
three misses / hits in a row: 23
four misses / hits in a row: 10
five misses / hits in a row: 3
six misses / hits in a row: 4
seven misses / hits in a row: 2
eight misses / hits in a row: 5
nine misses / hits in a row: 5
ten misses / hits in a row: 0
eleven misses / hits in a row: 0
twelve misses / hits in a row: 1
thirteen misses / hits in a row: 1
fourteen misses / hits in a row: 1

It follows the same pattern. There are some variations (trying to measure random stuff, its unavoidable) but both cases are quite similar. The max sequence of hits/misses are pretty similar.

If anything, this just shows that even true randomness is not as well behaved as wesnoth players would like to. Those long sequences of misses would be devastating for an attacker that's expecting average luck. And the short sequences of hits could also mean a dead archer, thief, fencer, etc vs just two attackers.

So that's randomness for you, either accept the good/bad luck you'll get, or go play some other deterministic game. As long as wesnoth keeps a pure random system for hits/misses, there probably will be long sequences of bad/good luck.

NOTE: Just for completeness, to simulate 70% defense with the random data downloaded I did these steps:
  • Convert the binary data to hexadecimal
  • Discard the [a-f] digits, delete them
  • Replace [0-6] with 0 (miss)
  • Replace [7-9] with 1 (hit)
If I'm not mistaken, none of these introduce an undesired bias.

CMaster
Posts: 55
Joined: December 7th, 2008, 2:25 pm

Re: pseudo-random generator + improvement idea

Post by CMaster » September 29th, 2009, 9:32 pm

You've talked a lot about achieving good (and probably proven) randomness with Wesnoth. And everytime someone tries to prove that the RNG is somehow screwed, he seems to fail. And then he wonders why that is so, the RNG feels screwed after all!

I think, you're simply not asking the right question:
What kind of RNG is desireable(!) for Wesnoth?

Is randomness desireable?
Of course it is, it is the basis for the strike system - Wesnoth simply wouldn't be Wesnoth without it!

Are long streaks of good/bad luck desireable?
I think not, since they do screw games.

So, are true random numbers desireable?
No, cause they do create long streaks of good/bad luck!

How then, can we achieve an RNG that is random, but not random enough to produce the long streaks of good/bad luck?
We need to introduce some limited amount of correlation!

What I suggest, is to introduce a variable for each side, that accumulates the deviation from the expected number of hits. Each time a strike is calculated, the accumulated deviation is multiplied by a small constant and subtracted from the chance to hit. Thus the constant value controlls the amount of (negative) correlation between successive strikes.

Code: Select all

actualChanceToHit = chanceToHit - deviationAccu*correlationConstant;
bool hit = some RNG call with probability of actualChanceToHit;
if(hit) {
	deviationAccu += 1-chanceToHit;
} else {
	defiationAccu -= chanceToHit;
}
I believe this would add to the overall gameplay experience. It would certainly reduce safeloading, simply because the effect of safeloading on the statistics wouldn't be so large or even nonexistant, if the deviation accumulators got saved with the game.

It is important to have an accumulator variable for each side: If it were global, a hit of the attacker would reduce the chance of the defender to hit and vice versa. This would be worse than pure random. If it were per unit, several units could have bad luck at the same time, screwing games again.

And it's also been done before: It is good practice to do it in diffusion dither algorithms to make the overall impression of the output image more smooth. And, after all, Wesnoth RNG is all about user impression too, isn't it?
I'm a reciever!

ilor
Inactive Developer
Posts: 129
Joined: March 24th, 2008, 9:05 pm

Re: pseudo-random generator + improvement idea

Post by ilor » September 29th, 2009, 9:51 pm

CMaster wrote:Yet another "let's make the RNG not so random and more <<fair>>" idea
No. A lot of people are very happy when a 40% hit chance for some unit on grass is always the same forty percent, two out of five chance. Any form of maiknig the RNG "fair" will screw this up.

Soliton
Site Administrator
Posts: 1539
Joined: April 5th, 2005, 3:25 pm
Location: #wesnoth-mp

Re: pseudo-random generator + improvement idea

Post by Soliton » September 29th, 2009, 10:34 pm

Many kinds of karma systems have been discussed before. Ultimately they will all just make people game the karma system instead which is not something we want.

You're welcome to implement one in WML like the lessluck era does though.
"If gameplay requires it, they can be made to live on Venus." -- scott

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

Re: pseudo-random generator + improvement idea

Post by Dave » October 2nd, 2009, 6:17 pm

@ Yoyobuae: you must be commended for posting the results of your experiment even though it didn't line up with your expected outcome.

Random number behavior is counter-intuitive for most people.

However there is something beautiful about random numbers too: how they reflect the turbulence of life, the unpredictability of a raging storm, how dealing with their uncertainty plays such an important role in Wesnoth, just as dealing with uncertainty plays such an important role in life.

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

Post Reply