[computer-go] Random

[Don Dailey]

That's very interesting and I believe it explains everything perfectly. 
If I understand this correctly, my 4 billion possible seeds (I used a 32 
bit seed) cannot produce 32 billion different games (against the same 
deterministic opponent.) In my implementation there were also issues 
with the lower ordered bits which of course are less random.

- Don



terry mcintyre wrote:
> An interesting note from 
> http://en.wikipedia.org/wiki/Knuth_shuffle which
> appears to be pertinent to Don's remarks about a
> limited number of games: 
>
> <quote>
> Limited PRNG state space
>
> An additional problem occurs when the Fisher-Yates
> shuffle is used with a pseudorandom number generator:
> as the sequence of numbers output by such a generator
> is entirely determined by its internal state at the
> start of a sequence, a shuffle driven by such a
> generator cannot possibly produce more distinct
> permutations than the generator has distinct possible
> states. Even when the number of possible states
> exceeds the number of permutations, the irregular
> nature of the mapping from sequences of numbers to
> permutations means that some permutations will occur
> more often than others. Thus, to minimize bias, the
> number of states of the PRNG should exceed the number
> of permutations by at least several orders of
> magnitude.
>
> For example, the built-in pseudorandom number
> generator provided by many programming languages
> and/or libraries may often have only 32 bits of
> internal state, which means it can only produce 232
> different sequences of numbers. If such a generator is
> used to shuffle a deck of 52 playing cards, it can
> only ever produce a vanishingly small fraction of the
> 52! &#8776; 2225.6 possible permutations. Thus, it's
> impossible for a generator with less than 226 bits of
> internal state to produce all the possible
> permutations of a 52-card deck, and for a (reasonably)
> unbiased shuffle, the generator must have at least
> about 250 bits of state.
>
> A further problem occurs when a simple linear
> congruential PRNG is used with the
> divide-and-take-remainder method of range reduction
> described above. The problem here is that the
> low-order bits of a linear congruential PRNG are less
> random than the high-order ones: the low n bits of the
> generator themselves have a period of at most 2n. When
> the divisor is a power of two, taking the remainder
> essentially means throwing away the high-order bits,
> such that one ends up with a significantly less random
> value.
>
> Also, of course, no pseudorandom number generator can
> produce more distinct sequences than there are
> distinct seed values it may be initialized with. Thus,
> it doesn't matter much if a generator has 1024 bits of
> internal state if it is only ever initialized with a
> 32-bit seed.
> </quote>
>
> The page also describes several other sources of bias
> which may be pertinent to the development of MC
> programs.
>
>
> Terry McIntyre &lt;terrymcintyre at yahoo.com&gt;
>
> “Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery.”
>
> Benjamin Disraeli, Speech in the House of Commons [June 15, 1874]
>
>
>       
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
>