  |
|
| View previous topic - View next topic |
| Author |
Message |
Hajo
Demon Hunter
Joined: 30 Sep 2003
Posts: 779
Location: Between chair and keyboard.
|
 Posted: Fri Nov 02, 2007 4:45 pm Post subject: Abusing random number generation |
[quote] |
|
Just a simple question. In most languages random number generators can be seeded with a value.
If I try something like this:
| Code: | long n = current_time();
generator.seed(n);
int value = generator.next();
|
how well will the first values after seeding be distributed?
Would it be better to use:
| Code: | long n = current_time();
generator.seed(n);
for(int i=0; i<10; i++) {
generator.next();
}
int value = generator.next();
|
And not use the first value but the tenth, if I want evenly distributed values?
For some design reason I cannot use the same generator for a longer sequence, but will have to use newly seeded generators all over ... a quick test implementation gave a "reasonable" distribution, but I didn't run any statistics really. Does someone know anything about such issues?
In particular the answer to the question if the first value has a worse distribution than a n-th value for fixed n would be interesting.
|
|
| Back to top |
|
 |
Rainer Deyke
Demon Hunter
Joined: 05 Jun 2002
Posts: 672
|
| Posted: Fri Nov 02, 2007 5:54 pm Post subject: |
[quote] |
|
If skipping the first ten values after seeding gave you a better distribution, then generator.seed would already be skipping the first ten values. Don't do that.
Side note: having a good random number generator helps a lot. I recommend Mersenne Twister (available from Boost for C++).
|
|
| Back to top |
|
|
Scrim
Mandrake's Little Slap Bitch
Joined: 05 Apr 2007
Posts: 69
Location: Canada
|
| Posted: Fri Nov 02, 2007 7:28 pm Post subject: |
[quote] |
|
Yeah, as I understand it, essentially, the "seed" value selects the position to start in a long (pseudo) random sequence of numbers. If the sequence has good properties, it shouldn't matter where you start.
An alternative to using the built in number generator is to "roll your own" using a little cryptography. A stream cipher, such as RC4, is designed to to produce a sequence of seemingly random bits that you XOR with some message to encrypt it. Essentially, it's a small, fast, pseudo-random number generator with good properties. All you do is use something (the date?) to "seed" the key schedule algorithm, and then run the algorithm. You don't have to encrypt anything, just use the output as your "random" number.
Hmm. You're probably better off going with just going with the built-in pseudo-random number generator or the one Rainer suggested anyway, but the crypto solution just sort of appeals to the geek in me.
|
|
| Back to top |
|
|
Verious
Mage
Joined: 06 Jan 2004
Posts: 409
Location: Online
|
| Posted: Sat Nov 03, 2007 2:33 pm Post subject: |
[quote] |
|
I found using the server's Timer in combination with game client supplied data provided a strong random seed.
Simplified example (for illustration purposes only, do not use in production):
| Code: | | Seed = ([Timer] + [Timer Value of Last Connected User]) / 2 |
While using an average will decrease the effective range of values, the random values will be more uniformly distributed over the reduced range.
This approach can be extended to factor in other data such as:
- Mouse coordinates from game client(s)
- Free memory of client(s) or server
- Last packet size
- Cumulative packet size
Game client data which affects random seeds should never come from the game client that issues the request, unless used in aggregate form. Data sources that are continually changing tend to work best.
|
|
| Back to top |
|
|
Hajo
Demon Hunter
Joined: 30 Sep 2003
Posts: 779
Location: Between chair and keyboard.
|
| Posted: Mon Nov 05, 2007 10:17 am Post subject: |
[quote] |
|
Mersenne Twister is good indeed. I have used it with H-World, one of my former projects.
The hint that generator.seed() would internally roll ten numbers if that helps to make a better first "official" number implies that the developers there had time to think and actually thought about it ;)
But I agree, one should at first expect a good implementation and look for workarounds only if there are hints that the library implementation is bad. I think Java's java.util.random() class is a fairly well-designed RNG. Some tests with time-based seed and rolling a short sequence of numbers gave results which I think are good enough, but since this is meant to be used to decide magic item properties in a multiplayer online game, people _will_ complain if they ever find out the implementation tends to be unfair in a way. I want to be sure that it items rolled on certain times (time = seed) aren't better than others.
Using more "random" bits for the seed but only time makes sense. Thank you for the suggestions, there, Verious. I'll try to add some more unpredicatble sources to the seed. If we consider that time changes mostly on the low bits, and the seed is a 64 bit value, would it help to shift the other sources to the higher bits, which would be the same for days and months if only time is used?
|
|
| Back to top |
|
|
| |
Page 1 of 1 |
All times are GMT
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
