03 September 2006

The Random Number Generator

I am writting this entry offline, because my sweet, beautiful DSL is down. It's been down pretty much the whole day, which is really annoying. Not only that I can't do my normal surfing, but I can't give people the stuff they ordered.

The good thing is that since I can't go online and waste my time, I can do other things, such as actually working at the game :)
I did a lot of stuff today, but the most important is that I finally decided to test the random number generator.
After implementing a new 'feature', where some items break during the manufacturing (items such as the hammer, the molds, needle, etc.), I wanted to test and see if it works, so I set the chance of the ring mold to 5000 out of 10000 (so 50%), and starting making rings. To my surprise, it appeared that the chance of the items to break was aparently much higher than 50%. In my estimates, it was something like 60-70%.
The code was pretty simple, even trivial. There couldn't have been a mistake in the code:
if(required_to_have_1!=-1)
{
rand_no=my_rand(10000);
if(rand_no<items[required_to_have_1].damage_when_hit)
{
//secret code, but basically break the item
}
}
As you can see, there is little room for error.

The function my_rand() is OS specific. Under Windows, it uses rand(), while under Linux and BSD it uses random()
Here is the code:

int my_rand(int max)
{
#ifdef WINDOWS
return rand()%(max+1);
#else
return random()%(max+1);
#endif
}

Yes, I know, there are better ways to do it than using %.

So I decided to write a test function:

void test_random_generator()
{
FILE *f = NULL;
int treshold=80;
int count=10000;
int rand_no;
int i;
int zero_count=0;
int one_count=0;
char str[200];

for(i=0;i<count;i++)
{
rand_no=my_rand(10000);
if(rand_no<treshold)zero_count+=1;
else one_count+=1;
}
sprintf(str,"\nCounting to %i, treshold of %i, we got zero: %i and one: %i",count,treshold, zero_count, one_count);

f=fopen("debug.txt", "a");
fwrite(str, strlen(str), 1, f);
fclose(f);
}

The results were:
Counting to 10000, treshold of 5000, we got zero: 5420 and one: 4580
Counting to 10000, treshold of 5, we got zero: 5 and one: 9995
Counting to 10000, treshold of 5: 6 and one: 9994
Counting to 10000, treshold of 80, we got zero: 92 and one: 9908
Counting to 10000, treshold of 80, we got zero: 89 and one: 9911

This means that the higher the treshold is, the higher the bias towards the end. However, in EL, most of the random tests are compared towards the 0 range. In addition, I heard that random() is somewhat more reliable than rand(), but at home I only have Windows, so I will have to test it on our BSD machine as well, when Mr. DSL will decide to work.

If the BSD machine will show a similar bias as well, I guess we will eventually have to use something better than %.
Nevertheless, the result of my tests are encouraging, and the multiple reports from the players on how stuff breaks more than it should are most likely due to bad luck, not due to errors in the code.

5 Comments:

Blogger Brendan said...

Mersenne Twister, perhaps? The overhead is minimal (624 words of working area), and it's about the same speed, or faster than rand(). Given that it's one of the best for Monte-Carlo simulations, it should satisfy almost every need as-is except cryptography.
Just as a note - though random() beats rand(), random()'s period is only 16*((2**31)-1), while MT's is (2**19937)-1.

4/9/06 11:58  
Blogger Donny said...

Looks like fairly simple code I don't see how there could be any problems with it at all. The windows random functions are much worse then those on BSD or atleast that is what I have heard. I could be wrong. I know they deal with time and some other random things to calculate the randomness so they may be very similar never really tested them myself.

Hope things work well.

Also sucks that you DSL has been acting up I'm actually surprised my cable has been working fine the past few days but I think this is becasue Time Warner is taking over Adelphia so Time Warner may have control of the ISP at this point.

4/9/06 14:23  
Anonymous csiga said...

Maybe you can try to generate the random numbers using chaotic sequences (not same as random, but mathematically gives better results in computer related applications).

4/9/06 21:36  
Anonymous Mihaim said...

Ethernal problem ... I told many times to use uniform random generators. Take a look here. Both code and theory :
http://www.agner.org/random/randoma.htm

Regards
mihai

5/9/06 02:50  
Blogger Radu said...

Thanks everyone for the comments.
It turns out that there won't be any need for 'fancier' stuff.
The new tests on the real server show that random() is very good at generating random numbers, unlike rand()

As for the period, that's not a problem, since this is a MMO and there is also the human entropy source (that is, between two actions by the same player, there will be other actions by different players), and since each action reseeds the random generator, in practice the period can be pretty infinite, from the point of view of one player.

6/9/06 12:52  

Post a Comment

<< Home