pseudo-random generator + improvement idea

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

Moderators: Forum Moderators, Developers

ced_ne
Posts: 46
Joined: September 18th, 2006, 2:38 am
Location: France

pseudo-random generator + improvement idea

Post by ced_ne » January 31st, 2009, 12:15 pm

Hi!

I know you don't like random generator thread, however, my purpose is not only complaining again it: I found why it is not really good random, and I have some idea about how to improve it. So please, don't lock it too early...


But now, let's start to complain ;)
Like many people, I have experienced many time bad random generator series. I have studied maths and statistic, so I know that some series should not happen so often. For example, having a Magi failing all his 4 attacks is something that has only (3/10)^4=0.81% of chance to happen, and I'm pretty sure it happens a lot more. Same for elves who have marksman, failing their 5 attacks has (4/10)^5=1.024% of chance to happen, but it happens more. Of course, the opposite situation happens too, I mean a unit that have little chance to hit, but success all his attacks.
And I have a strange feeling: it looks like when you have a bad series, your opponent have a tendency to have a quite good.
Another strange feeling: I play this game on both Linux and Windows (since Wesnoth 1.0 series), and (maybe I'm parannoid lol) I've got more strange series while playing under Windows.


So I search the Wesnoth's code to see why.


First, I see that you are using the libc rand(). That could explain why I have different feeling while playing Linux or Windows. Did you know that all OS has its own implentation of rand() ? Some OS have a very weird rand(). However, using rand() is probably boring for syncing network game.

Second, I see that you have a very bad habit, everytime you use random generator, you apply a modulo to scale it. Example in action.cpp taken from the SVN (updated today):

Code: Select all

                        const int ran_num = get_random();
                        bool hits = (ran_num%100) < attacker_cth_;

In this code, get_random() just perform a libc rand() & 0x7FFFFFFF.
I must warn you that lower bits in the rand() function (and in most of random generator) are far less random than higher bits.
That's why the linux manpage of srand() explain that you should replace:
random_num = (rand() % 100);
by:
random_num = (int) (100 * (rand() / (RAND_MAX + 1.0)));
because this last form use higher bits that have more randomness.
You can use the ">>" operator too. For example the previous code will be:

Code: Select all

                        const int ran_num = get_random();
                        bool hits = ((ran_num>>16)%100) < attacker_cth_;


And I found at the end of random.cpp:

Code: Select all

void simple_rng::random_next()
{
        // Use the simple random generator as shown in man rand(3).
        // The division is done separately since we also want to
        // quickly go the the wanted index in the random list.
        random_pool_ = random_pool_ * 1103515245 + 12345;
}

This is the code of the old UNIX random generator (without the division), that is famous for being one of the worst generator ever. It has parity problem (tendency to be stuck on either even or odd numbers), and really bad lower bits randomness.
This code, just like the libc rand() use what is called a "Lehmer pseudo-random generator". They all consist in:
next_seed = ( current_seed * MULTIPLY_CONSTANT + ADDITIVE_CONSTANT ) % MODULO_CONSTANT
However, depending on which constant you use, you have a more or less good generator. One of the best Lehmer generator is the one found by Park and Miller, it is called the "minimal standard" (cause it pass successfully many statistic test), and it uses:
MULTIPLY_CONSTANT : 16807
ADDITIVE_CONSTANT : 0
MODULO_CONSTANT : 2147483647



Another think to know, is that sometime, some generator can have series of this kind : high value - low value - high value - low value - high value - low value - and so on... That is really a big trouble for Wesnoth, because during a fight, the attacker strike first, then the defender strike, then the attacker strike again, then the defender strike again, and so on... Do you see what I mean ? If the generator fall in a short series of hi-lo value, one of the fighter will be particularly lucky while the other one will have bad luck... That's something I have experienced, like I was saying at the begining, I feel that most of time, when I have incredible bad luck, my opponent is incredibly lucky at the same time.


So here what could be done to improve the random generator in Wesnoth:
1/ never ever use lower bits, use higher bits when scaling the random number (either using the example of the manpage of srand(), or by using a ">>16" to throw away the 16 lower bits)
2/ if possible, try to have your own code for random number generator, to be sure that they will be the same on all OS/compiler
3/ it could be a good idea if every unit would have its own random seed (to prevent the hi-lo series trouble), always using the striker's seed in a fight, so if A attack B, A strike B using A's next_seed against its Chance To Hit, B strike A using B's next_seed against its Chance To Hit, etc...


That's not really difficult to code his own random generator, only constant used are important and have to be chosen carefully. I have already made one few years ago for a friend. If you don't want to code it, I can eventually give you my code (I need to turn all comment in english, cause they are in french for instance ;) ).

(EDITED)
Last edited by ced_ne on January 31st, 2009, 2:59 pm, edited 1 time in total.
-- please don't blame me about my bad english spoken ! --

silene
Posts: 1109
Joined: August 28th, 2004, 10:02 pm

Re: pseudo-random generator + improvement idea

Post by silene » January 31st, 2009, 1:30 pm

ced_ne wrote:I have studied maths and statistic, so I know that some series should not happen so often. For example, having a Magi failing all his 4 attacks is something that has only (3/10)^4=0.81% of chance to happen, and I'm pretty sure it happens a lot more. Same for elves who have marksman, failing their 5 attacks has (4/10)^5=1.024% of chance to happen, but it happens more.
Are you sure it really happens more? The "statistics" part of the save files is there for a reason, so that you can check that it is not just your feeling.
ced_ne wrote:I must warn you that lower bits in the rand() function (and in most of random generator) are far less random than higher bits.
That's why the linux manpage of srand() explain that you should replace:
random_num = (rand() % 100);
by:
random_num = (int) (100 * (rand() / (RAND_MAX + 1.0)));
because this last form use higher bits that have more randomness.
Careful with what you write: Doing an operation modulo 100 does use the higher bits!!! It's not the best, but it's definitely not as bad as you think it is. Especially as the game doesn't really make a decision on the last two bits (granularity in Wesnoth is about 10). As a matter of fact, one of the issues with this modulo is that numbers below 48 are slightly favored.
ced_ne wrote:That's something I have experienced, like I was saying at the begining, I feel that most of time, when I have incredible bad luck, my opponent is incredibly lucky at the same time.
Do you have a savegame that shows this issue?

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

Re: pseudo-random generator + improvement idea

Post by hiro hito » January 31st, 2009, 2:28 pm

silene wrote:
ced_ne wrote:I have studied maths and statistic, so I know that some series should not happen so often. For example, having a Magi failing all his 4 attacks is something that has only (3/10)^4=0.81% of chance to happen, and I'm pretty sure it happens a lot more. Same for elves who have marksman, failing their 5 attacks has (4/10)^5=1.024% of chance to happen, but it happens more.
Are you sure it really happens more? The "statistics" part of the save files is there for a reason, so that you can check that it is not just your feeling.

Badly i didn't keep all my replays since 0.9.x, but i have the same "feeling" of ced_ne: 80% of my match (victorious or not) have negative stats.... I am very surprising when my stats are positive, and when it's happen, my opponent (even the best player :wink: ) often blame my luck... and i am agree with him because that "rule of bad series" happen frequently and kill the game ....

I don't think that so many people will blame the RNG if that bad (or good) series don't happen so frequently...
"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

ced_ne
Posts: 46
Joined: September 18th, 2006, 2:38 am
Location: France

Re: pseudo-random generator + improvement idea

Post by ced_ne » January 31st, 2009, 2:58 pm

Are you sure it really happens more? The "statistics" part of the save files is there for a reason, so that you can check that it is not just your feeling.
Unfortunately checking wesnoth statistic doesn't help. Imagine I attack with 2 units that have 50% chance to hit and 4 attacks. In the first case I hit 2 times and miss 2 times with each units. In the second case I hit 4 times this one unit, and don't hit anything with the second unit. For Wesnoth's statictic point of view, it will be the same, but you should agree that the second case is more rare.
Careful with what you write: Doing an operation modulo 100 does use the higher bits!!! It's not the best, but it's definitely not as bad as you think it is. Especially as the game doesn't really make a decision on the last two bits (granularity in Wesnoth is about 10). As a matter of fact, one of the issues with this modulo is that numbers below 48 are slightly favored.
If the modulo was a power of 2,only lower bits would be really used. However 100 = 64+32+4 (64, 32 and 4 are power of 2 numbers, so 100 is a sum of only 3 power of 2 numbers), so lower bits remains more important than higher (i don't want to explain why, but it is ;) ). And BTW, there is randomness everywhere in Wesnoth (like trait, or in WML), it would be a true miracle if no random number were scaled with a power of 2 modulo.
However, it cost nothing to add a ">>16" everytime you use random numbers (it could be inserted directly into the get_random() function in random.cpp), and it's what everyone recommand (or using the formula found in linux manpage of srand() ).


@ Hiro Hito : Of course, I'm not saying that the RNG is in favor of computer rather than human ;) In my example, I spoke about bad series, but good series happen as well. My point is just that there are too many series. I used to play role playing game with dice (not video game), and this kind of series doesn't happend too much in real life.


(Oh and sorry, I have made a stupid error "bool hits = ((ran_num%100) >> 16) < attacker_cth_;" should be "bool hits = ((ran_num>>16)%100) < attacker_cth_;", I will edit my first post :S )
-- please don't blame me about my bad english spoken ! --

silene
Posts: 1109
Joined: August 28th, 2004, 10:02 pm

Re: pseudo-random generator + improvement idea

Post by silene » January 31st, 2009, 4:39 pm

ced_ne wrote:However 100 = 64+32+4 (64, 32 and 4 are power of 2 numbers, so 100 is a sum of only 3 power of 2 numbers), so lower bits remains more important than higher (i don't want to explain why, but it is ;) ).
Right, and Fermat explained the margin was too small for his proof.

Let me explain what the issue actually is, since you don't want to. So Wesnoth is doing a modulo 100, and then it compares the result with a multiple of 10. Let us assume that the x upper bits are perfectly random and the (31 - x) lower bits are equal to zero (that's not the worse one can do, but it's already quite bad). Due to the prime factors of 10 and 100, you will get 12% chance to be between 0 and 9, 8% between 10 and 19, 12% between 20 and 29, and so on.

Funnily enough, these percentages do not depend on the amount of bits you choose or their positions. This means that, even with a perfect generator, you have 14% more chance to get a value smaller than 30 than a value bigger than 70, and 8% more chance to get a value smaller than 50 than bigger than 50.

Now, let's assume that the constant part is no longer zero. The repartition will now depend on the constant part. More precisely, we will get a period 2:4 (not really surprising since 10=2*5 and 100=4*25). Concretely, when the second bit is 0, you are in the case above; and when the second bit is 1, you are in the opposite case.

So assuming the second bit is flipping 01010101, you would indeed get in a situation where it would seem like the other player is more lucky than you. How does simple_rng behave with respect to that? The second bit does 00110011, which is not the flipping above.

So yes, the Wesnoth RNG is badly skewed, and the skew depends on the value of the second bit (and only this one!) of the random generator, but I have yet to seen a situation where it actually matters. (But perhaps it only happens with the random generator of Windows, which would explain I never noticed it.) So I don't mind people complaining about the RNG, but please get your explanations right.

Note also that it means your suggestion of scaling down by 2^16 won't change anything to this issue. As a matter of fact, it would skew the RNG even worse since it would remove the pseudo-randomness brought by the second bit.

ced_ne
Posts: 46
Joined: September 18th, 2006, 2:38 am
Location: France

Re: pseudo-random generator + improvement idea

Post by ced_ne » January 31st, 2009, 8:05 pm

So I wonder why conceptor of Lehmer pseudo-random generator actually recommand to not use directly modulo to scale numbers... :roll:

Few years ago, I have made some test to simulate a 4d6 (4 dices of 6 faces), using 1+rand()%6, 1+(rand()>>8)%6, 1+(rand()>>16)%6.
By the way 1+rand()%6 was the worst. So yes, 6 is not 100, but 6 is not a power of 2. There is no doubt in my mind, it will be more or less the same.

Is there something I haven't understand or you are really thinking that a bit that does 001100110011 is random ??

And there is a fact you miss, all your calcul are based upon the predicat that some higher bits are pure random: that's not the case.
You speak about average chance of doing over or below some value (and to be honest, I never realize that average chance was not equal), but I speak about series. Your demonstration can't be done unless you know exactly which constant are used for the rand(), and it cannot be so easy (there are tons of book fully dedicated to random generator). This is precisely because it's not pure random, that "artifact" appear.
Those generators are very sensitive, a slight variation of one of their constant cause dramatic change on their behaviour. If you don't use them the way they was designed for, you have good chance to disrupt the balance of generated numbers.


Finally, I should say it again, that the RNG is not only used for combat. User's made campaign can use random in WML. If someone want an event to have 1/4 chance to happen at each turn, only the 2 last bits of the RNG will be used...



I can't force anyone to trust me, but if you don't trust me, trust the scientists that have created and studied those generator. ;)
-- please don't blame me about my bad english spoken ! --

silene
Posts: 1109
Joined: August 28th, 2004, 10:02 pm

Re: pseudo-random generator + improvement idea

Post by silene » January 31st, 2009, 8:44 pm

ced_ne wrote:And there is a fact you miss, all your calcul are based upon the predicat that some higher bits are pure random: that's not the case.
So what? The goal of my post was to explain the real reason why Wesnoth's RNG is bad (that is, a 4x modulo). I did so by assuming that the higher bits were random. If they aren't, then it can only make the RNG worse.

Anyway, that's not why Ipost; I just want to put a correction to my previous post. I was mistaken when I said that ">> 16" would make the issue worse. It does not make the issue worse, it just moves the dependency on the 17th bit. So assuming the 17th bit has a longer period than the 2nd one, it may indeed hide the issue.

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

Re: pseudo-random generator + improvement idea

Post by Max » January 31st, 2009, 8:48 pm

ced_ne wrote:For example, having a Magi failing all his 4 attacks is something that has only (3/10)^4=0.81% of chance to happen, and I'm pretty sure it happens a lot more. Same for elves who have marksman, failing their 5 attacks has (4/10)^5=1.024% of chance to happen, but it happens more.

Another think to know, is that sometime, some generator can have series of this kind : high value - low value - high value - low value - high value - low value - and so on... That is really a big trouble for Wesnoth, because during a fight, the attacker strike first, then the defender strike, then the attacker strike again, then the defender strike again, and so on... Do you see what I mean?
ced_ne wrote:I can't force anyone to trust me, but if you don't trust me, trust the scientists that have created and studied those generator. ;)
i'm not trying to argue if you're wrong or right. but the point is that you make assertions that can be backup up statistically. run a large series of such calculations. i think everything can be automated to some degree (either directly using the source) or "just" with a appropriately configured wml scenario.

if you come back here with hard facts, e.g. data with a CI of e.g. 99.99% that would change a lot.

ced_ne
Posts: 46
Joined: September 18th, 2006, 2:38 am
Location: France

Re: pseudo-random generator + improvement idea

Post by ced_ne » February 2nd, 2009, 10:42 am

So assuming the 17th bit has a longer period than the 2nd one, it may indeed hide the issue.
The longer the period is, the better it is ;)
If the period is longer, there is more randomness. True randomness have no period (infinite period if you prefer).

I have written a little program to test the RNG. Because I'm an honest person, I will give you its result despite the fact they disagree with some of my feelings.

Before reading those result, please remember that this test were running on Linux (so only test the linux rand() ), and that this program DOESN'T analyse series (which is my major annoyance). Analysing series needs a much more complicated work than my one-hour-program.
However it demonstrate I was wrong about hi-lo series (see cross hit section), and my feeling that all-hit or no-hit was over-represented was wrong too, at least on linux. It demonstrate that you (Silene), was wrong too (when you said "Due to the prime factors of 10 and 100, you will get 12% chance to be between 0 and 9, 8% between 10 and 19, 12% between 20 and 29, and so on.").

Performed with the wesnoth RNG (simulating 1.000.000 fight):

Code: Select all

  ++ Elf ++
Number of Strike: 4
Chance To Hit: 70 %

  ++ Orc ++
Number of Strike: 3
Chance To Hit: 50 %



  ** Hit of the Elf **
Hit 0 time: 8250/1000000 => 0.825 % , should be 0.810 %
Hit 1 time: 75019/1000000 => 7.502 % , should be 7.560 %
Hit 2 time: 264827/1000000 => 26.483 % , should be 26.460 %
Hit 3 time: 411265/1000000 => 41.127 % , should be 41.160 %
Hit 4 time: 240639/1000000 => 24.064 % , should be 24.010 %




  ** Hit of the Orc **
Hit 0 time: 125766/1000000 => 12.577 % , should be 12.500 %
Hit 1 time: 374731/1000000 => 37.473 % , should be 37.500 %
Hit 2 time: 374684/1000000 => 37.468 % , should be 37.500 %
Hit 3 time: 124819/1000000 => 12.482 % , should be 12.500 %




  ** Cross hit **
Hit 0 x 0 : 1042/1000000 => 0.104 % , should be 0.101 %
Hit 0 x 1 : 3071/1000000 => 0.307 % , should be 0.304 %
Hit 0 x 2 : 3144/1000000 => 0.314 % , should be 0.304 %
Hit 0 x 3 : 993/1000000 => 0.099 % , should be 0.101 %
Hit 1 x 0 : 9334/1000000 => 0.933 % , should be 0.945 %
Hit 1 x 1 : 28087/1000000 => 2.809 % , should be 2.835 %
Hit 1 x 2 : 28315/1000000 => 2.832 % , should be 2.835 %
Hit 1 x 3 : 9283/1000000 => 0.928 % , should be 0.945 %
Hit 2 x 0 : 33147/1000000 => 3.315 % , should be 3.307 %
Hit 2 x 1 : 99380/1000000 => 9.938 % , should be 9.923 %
Hit 2 x 2 : 99253/1000000 => 9.925 % , should be 9.923 %
Hit 2 x 3 : 33047/1000000 => 3.305 % , should be 3.307 %
Hit 3 x 0 : 51917/1000000 => 5.192 % , should be 5.145 %
Hit 3 x 1 : 153881/1000000 => 15.388 % , should be 15.435 %
Hit 3 x 2 : 153864/1000000 => 15.386 % , should be 15.435 %
Hit 3 x 3 : 51603/1000000 => 5.160 % , should be 5.145 %
Hit 4 x 0 : 30326/1000000 => 3.033 % , should be 3.001 %
Hit 4 x 1 : 90312/1000000 => 9.031 % , should be 9.004 %
Hit 4 x 2 : 90108/1000000 => 9.011 % , should be 9.004 %
Hit 4 x 3 : 29893/1000000 => 2.989 % , should be 3.001 %
In this test, I have used /dev/urandom instead of rand() :

Code: Select all

  ++ Elf ++
Number of Strike: 4
Chance To Hit: 70 %

  ++ Orc ++
Number of Strike: 3
Chance To Hit: 50 %



  ** Hit of the Elf **
Hit 0 time: 8035/1000000 => 0.803 % , should be 0.810 %
Hit 1 time: 75519/1000000 => 7.552 % , should be 7.560 %
Hit 2 time: 263848/1000000 => 26.385 % , should be 26.460 %
Hit 3 time: 412059/1000000 => 41.206 % , should be 41.160 %
Hit 4 time: 240539/1000000 => 24.054 % , should be 24.010 %




  ** Hit of the Orc **
Hit 0 time: 124784/1000000 => 12.478 % , should be 12.500 %
Hit 1 time: 375337/1000000 => 37.534 % , should be 37.500 %
Hit 2 time: 375131/1000000 => 37.513 % , should be 37.500 %
Hit 3 time: 124748/1000000 => 12.475 % , should be 12.500 %




  ** Cross hit **
Hit 0 x 0 : 1006/1000000 => 0.101 % , should be 0.101 %
Hit 0 x 1 : 3061/1000000 => 0.306 % , should be 0.304 %
Hit 0 x 2 : 2981/1000000 => 0.298 % , should be 0.304 %
Hit 0 x 3 : 987/1000000 => 0.099 % , should be 0.101 %
Hit 1 x 0 : 9400/1000000 => 0.940 % , should be 0.945 %
Hit 1 x 1 : 28297/1000000 => 2.830 % , should be 2.835 %
Hit 1 x 2 : 28507/1000000 => 2.851 % , should be 2.835 %
Hit 1 x 3 : 9315/1000000 => 0.931 % , should be 0.945 %
Hit 2 x 0 : 32901/1000000 => 3.290 % , should be 3.307 %
Hit 2 x 1 : 99103/1000000 => 9.910 % , should be 9.923 %
Hit 2 x 2 : 98862/1000000 => 9.886 % , should be 9.923 %
Hit 2 x 3 : 32982/1000000 => 3.298 % , should be 3.307 %
Hit 3 x 0 : 51479/1000000 => 5.148 % , should be 5.145 %
Hit 3 x 1 : 154771/1000000 => 15.477 % , should be 15.435 %
Hit 3 x 2 : 154417/1000000 => 15.442 % , should be 15.435 %
Hit 3 x 3 : 51392/1000000 => 5.139 % , should be 5.145 %
Hit 4 x 0 : 29998/1000000 => 3.000 % , should be 3.001 %
Hit 4 x 1 : 90105/1000000 => 9.011 % , should be 9.004 %
Hit 4 x 2 : 90364/1000000 => 9.036 % , should be 9.004 %
Hit 4 x 3 : 30072/1000000 => 3.007 % , should be 3.001 %
About cross hit, for example "hit 3 x 2" is a fight were our "Elf" hit 3 times while our "Orc" hit 2 times.


We see that /dev/urandom is slightly better, but linux's rand() pass this test successfully too.
There is much more difference between rand() and /dev/urandom if I run my program for only 100 fight, but this is statisticly pointless to put here one of the output of those test.

And it will be really a too big work to write a program that study series (something that take care of the context).

However, I have played Wesnoth this week-end using /dev/urandom instead of rand(), I have had a real feeling of randomness. I don't remember what is used for /dev/urandom (maybe Mersenne Twister??) but it is definitively more human-friendly than rand().
-- please don't blame me about my bad english spoken ! --

silene
Posts: 1109
Joined: August 28th, 2004, 10:02 pm

Re: pseudo-random generator + improvement idea

Post by silene » February 2nd, 2009, 9:35 pm

ced_ne wrote:It demonstrate that you (Silene), was wrong too (when you said "Due to the prime factors of 10 and 100, you will get 12% chance to be between 0 and 9, 8% between 10 and 19, 12% between 20 and 29, and so on.").
Just to be sure you are not getting this sentence out of context, let me explain again.

I said that you get 12% 8% 12%... when the lower bits of the random value are zero (and more precisely the second bit). That's easy to see: The multiples of 4 are 0 4 8 12 16 20 24 28, etc. So you have three of them between 0 and 9, but only two between 10 and 19, three again between 20 and 29, and so on. That's really 12% 8% 12%, etc. But if you set the second bit to one, then you get 2 6 10 14 18 and so on. So once the second bit is one, the chances become 8% 12% 8% and so on.

Did you really test by zeroing or setting to one the second bit of the random value? That's the only way to see whether the second bit is as important as I say it is.

Now, in order to test how good or bad the randomness of the second bit is, we can do as follows. Just get a sequence of 8 random values; Once concatened, their second bits give you a value between 0 and 255. Repeat enough times. Then look how bad the deviation is with expected chances of 1/256. The following is obtained for 1.000.000 values with linux rand(). (I only display values with more than 3.5% deviation.)

Code: Select all

11111000 104%
01000110 96%
01001110 96%
11100101 96%
11111111 107%
Can we deduce anything? The generator seems to like long sequences of 1. But that's not even true, since testing with more values make these deviations disappear. Testing for other periods than 8 doesn't change the result: No particular pattern appear. So linux random generator is quite good, even for lower bits.
ced_ne wrote:And it will be really a too big work to write a program that study series (something that take care of the context).
That may not be that hard. In your test program, instead of counting the cross sequences as hits x hits pairs, really count them as sequences.

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

Re: pseudo-random generator + improvement idea

Post by Dave » February 3rd, 2009, 12:47 am

ced_ne wrote: Like many people, I have experienced many time bad random generator series.
All depends on perceptions...
ced_ne wrote: First, I see that you are using the libc rand(). That could explain why I have different feeling while playing Linux or Windows. Did you know that all OS has its own implentation of rand() ?
Yes, we know C pretty well and have a pretty good understanding of what is and isn't specified about rand() in the C Standard. :-)

ced_ne wrote:That's why the linux manpage of srand() explain that you should replace:
The Linux man page you're referring to is quite old, and I think all rand() implementations are much more sophisticated now.

But that is really irrelevant. The man page refers to cryptographic randomness. The randomness required for cryptography is much more sophisticated than what is required for a game.

I don't think anyone can perceive any difference between randomness in Wesnoth and real randomness.

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

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

Re: pseudo-random generator + improvement idea

Post by zookeeper » February 3rd, 2009, 7:40 am

Let's have a test: post the results of a thousand (or a million, whatever) rolls of the Wesnoth RNG and a thousand rolls of the best other kind of RNG you can find (I'm sure there are some available online, no?) without telling which one is which. Then we can see who can really spot the difference.

User avatar
Glass Pearl Player
Posts: 19
Joined: February 4th, 2008, 9:19 pm

Re: pseudo-random generator + improvement idea

Post by Glass Pearl Player » February 4th, 2009, 12:21 am

Ladies and Gentlemen, allow me to make an outrageous claim, one in stark contrast to the opinion of the esteemed ced_ne, who claims that, while the computed chance for a mage to miss four strikes in a row is 0.81%, or roughly one in onehundredtwentythree, such an unfortunate event happened far more frequently than a fair random number generator could possibly admit.
You may, by now, already have a fairly accurate idea about the nature of my claim. I claim - admittedly in no small part for the sake of the argument - that such an event should be expected to happen about once every game; such a claim must of course be assumed to be about averages.
Now, you may ask: Has this gentleman actually lost his faculties? How can it be that an event with such a miniscule probability should be expected that often - in fact, that its very absence from a game should be considered unusual?
Well, my argument is quite simple, altough it requires quite a few assumptions that are barely justified. The first being that in every game, on average, three such units happen to emerge. The second, that these units manage to persist for another 30 round before they are slain or the game reaches a conclusion. The third, that each such unit attacks every round henceforth, and is forced to defend itself in ranged combat once every three rounds.
With these assumptions, one quickly calculates that there will be 120 opportunities per game, and on average, about one of them will be ruined in such a way as to question the fairness of the random number generator, as I previously dared to claim.

For those who said "wtf tl;dr":
Define a random variable F to count how often in a game of BfW a mage manages to miss with 4 strikes in a single attack. I claim that E(F) equals one, well within an order of magnitude. Is there a better estimate?

This post ist not meant as an offense to anybody. It is meant, however, to provoke tought. For example, I think that we are not really asking the right questions, and therefore the answers we get are actually misleading.
"Say 'Disintegrate' one more time, Vaarsuvius. For me." - OotS 626

User avatar
JW
Posts: 5046
Joined: November 10th, 2005, 7:06 am
Location: Chicago-ish, Illinois

Re: pseudo-random generator + improvement idea

Post by JW » February 4th, 2009, 1:00 am

Glass Pearl Player wrote:Well, my argument is quite simple, altough it requires quite a few assumptions that are barely justified. The first being that in every game, on average, three such units happen to emerge. The second, that these units manage to persist for another 30 round before they are slain or the game reaches a conclusion. The third, that each such unit attacks every round henceforth, and is forced to defend itself in ranged combat once every three rounds.
With these assumptions, one quickly calculates that there will be 120 opportunities per game, and on average, about one of them will be ruined in such a way as to question the fairness of the random number generator, as I previously dared to claim.
Those assumptions are a little shaky. For example, Knalgans and Northerners have no magic units, and all lvl 1 recruitable mages have 3 strikes or less. They are recruited in varying numbers depending on opponents faction and user's playstyle, with adepts (2 strikes) being the most commonly recruited magic unit. Assuming that the magic unit attacks every round for 30 rounds is highly unlikely do to their low hp and the fact that all have unfavorable times of day, and it is perhaps most unlikely that an opponent would attack a magic unit in range twice in a day rotation. The average rounds in a game is not something I'm as famailiar with, so I can't comment there.

Even assuming your numbers to be off, the point is still valid in its purpose. You used a 4 strike mage, meaning its occurrence to miss all is less likely than a 3 strike mage, who has a 2.7% chance to miss all 3 strikes. In just 25 mage attacks you would have a 50% chance to have 1 or more of them miss all 3 strikes. Adepts would obviously miss all of their strikes even more frequently (7 attacks gives you about 50% for 1 or more adepts to miss both strikes).

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

Re: pseudo-random generator + improvement idea

Post by Dave » February 4th, 2009, 2:38 am

The game already does record the sequences of attack hits and misses for each different hit%. Just look in the [attacks] and [defends] sections in a save file.

Anyone with some decent scripting skills should be able to write a script that shows from one's saved games exactly how lucky or unlucky they are or how streaky they are, or whatever else it is that the random number supposedly does to people to keep them from winning or having a satisfying experience.

Note that sequences of four hits will probably be underrepresented compared to sequences of four misses, since the fight is more likely to end early with a unit perishing if hits are occurring.

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

Post Reply