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! ≈ 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 <[EMAIL PROTECTED]>
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
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
