Sign in to follow this  
Numsgil

Deterministic Random Number Generator

Recommended Posts

Numsgil    501
I'm programming in C#. What I'd like is a random number generator that has these two properties: 1. I can save the state information of the random number generator as part of the save game file. A loaded save should behave exactly as if it had never been saved at all. 2. Eventually I want to implement some worker threads to update the different agents in my world (there are thousands of agents). Obviously the order that the different agents get executed isn't deterministic. Is there a method someone can think of to generate random numbers for the different agents that is deterministic? Maybe use unique random number generators for each agent, seeded somehow using a global seed and an agent's hash code? Primarily I'm interested in making bugs easy to reproduce. If a user provides me with a save file that happens before a crash or abberant behavior, at the moment the problem doesn't always reappear. Some of this has to do with other things, but alot of it has to do with the random number generator generating a different sequence after a save/load.

Share this post


Link to post
Share on other sites
Palidine    1315
rand() is deterministic if given the same seed value.

most (all?) pseudo-random number generators are deterministic as they typically operate like so:

initialize with a seed value
random1 = function(seed);
random2 = function(random1);
random3 = function(random2);

i.e. the last number created is, in some form, used as the "seed" to generate the next number.

so all you need to do is remember the last number generated and you're good to go. You can find algorithms for a bunch of RNGs that operate like this with your best bud google.

-me

Share this post


Link to post
Share on other sites
Different types of random number generators have different operational properties though. For example, the Mersenne Twister is a fast, high quality generator, but it needs 624 words to store the state for the 32 bit version. A couple thousand of these states is not that cheap.

On the other hand, a multiple recurrence generator with appropriate coefficients can perform reasonably well and the only state it requires are the coefficients in the recurrence. For example, mrg32k3a (this particular algorithm is tuned for double precision floats) requires only 6 words of state. That's not too hefty.

I honestly don't know enough to give you the ideal generator, and it wouldn't be possible to figure out unless you gave more details about the use. But if you are interested in multiple recurrence generators, check out this paper: http://www.iro.umontreal.ca/~lecuyer/myftp/papers/combmrg2.ps

It has source in the back for 3 generators, and you might also learn something :)

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by Palidine
rand() is deterministic if given the same seed value.


Yes, but you can't get the "current" seed *back* from std::rand, which he would need to do.

TR1 is correcting this stuff, IIRC, but for now, you can use - well, almost anything that is published by reputable people and isn't std::rand(). :) (I recommend investigating Boost::random.)

Edit: I'm skeptical of this thread-per-agent idea. Threading on a large scale does impose a fair amount of overhead, even when locking isn't required. And when it is - whoo boy. (You'll also need some serious planning to figure out any inter-thread communication issues. Often a message queue is the sanest way to handle things.)

Share this post


Link to post
Share on other sites
intrest86    742
Quote:
Original post by Numsgil
I'm programming in C#.

Seems everyone lost track of this point.

Use the System.Random class to get your random numbers. I would create a seperate generator for each object that will be requesting a lot of random numbers.

Now, .Net is going to help us in the saving phase. A good chunk of the classes in the framework, including the random class, are "Serializable". That means that the ability to save the state of these classes is built into the class and the framework.

Lookup the class "System.Runtime.Serialization.Formatters.Binary.BinaryFormatter". If you create an instance of this class, you can pass a Random class and a stream and the formatter will write all of the information needed to restore the generator to the stream. You can then read from the same stream and recreate the random generator from the stream.

In other words, .Net has the details handled here. All you have to do is set it up.

Share this post


Link to post
Share on other sites
Numsgil    501
Quote:
Original post by Palidine
rand() is deterministic if given the same seed value.

most (all?) pseudo-random number generators are deterministic as they typically operate like so:

initialize with a seed value
random1 = function(seed);
random2 = function(random1);
random3 = function(random2);

i.e. the last number created is, in some form, used as the "seed" to generate the next number.

so all you need to do is remember the last number generated and you're good to go. You can find algorithms for a bunch of RNGs that operate like this with your best bud google.


Yes, simplistically. However, any number generator worth its salt is going to be doing some bit shuffling, etc. that also depends on more numbers prior in the sequence. It's this state data that I would want to save between sessions.

I've implemented some random number generators before, so I'm not totally in the dark when it comes to this. I could implement my own again in C#, but I'm not all that certain it would be a great idea.

Quote:

Edit: I'm skeptical of this thread-per-agent idea. Threading on a large scale does impose a fair amount of overhead, even when locking isn't required. And when it is - whoo boy. (You'll also need some serious planning to figure out any inter-thread communication issues. Often a message queue is the sanest way to handle things.)


Most of the concurrency issues have already been resolved, since I don't want the order that the agents are executed to effect the end result. It wouldn't really be a thread per agent. It would probably be like 3 or 4 threads that execute the various agents. I'm primarily trying to tap into multiple core PCs.

Quote:

I honestly don't know enough to give you the ideal generator, and it wouldn't be possible to figure out unless you gave more details about the use.


The random number generator primarily is used for mutations that change the operating program of the agents. It comes up fairly infrequently, but it's the primary purpose for the program, and the primary source for finding bugs.

Share this post


Link to post
Share on other sites
Numsgil    501
Quote:
Original post by intrest86
In other words, .Net has the details handled here. All you have to do is set it up.


That's good. One problem solved ;)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Quote:
Original post by The Reindeer Effect
Different types of random number generators have different operational properties though. For example, the Mersenne Twister is a fast, high quality generator, but it needs 624 words to store the state for the 32 bit version. A couple thousand of these states is not that cheap.


(624 words/generator)*(32 bits/word)*(1 byte/8 bits) = 2496 bytes/generator

(2496 bytes/generator)*(2048 generators) = 5111808 bytes = 4.875 MB

Maybe not cheap, but not that expensive even for such a large number of generators (or am I behind the times and games these days tend to use more than 2048 separate PRNG's?).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this