--- In [email protected], "Austin Nichols" <[EMAIL PROTECTED]> wrote: > > The best PRNG I know of that is not restricted in export due to crypto > applications is the Mersenne Twister and here is a fast version with > period up to 2^216091:
Mersenne Twister is a good RNG, but has the downside of requiring more computation than KISS, and it requires a lot more state bits. This is quibbling, though. Mersenne Twister is better than rand(). > Unless I am misunderstanding the code Jason quotes, it > shuffles on every tile draw, so even a period 2^8 PRNG would produce > O(2^(8)(14)) initial rack draws, no? Two problems: 1) Jason said that srand() is called when Quackle starts up. 2) The alternative of calling srand() on each tile draw (or move) does not work! (On most OS/hardware combinations.) If you call srand() on every turn, initializing with the current system time, then when Quackle makes two moves in a row on the same clock tick then the RNG will be initialized the same way each time. The normal OS clock available in standard C has millisecond precision, so if Quackle can make two moves in the same millisecond then it would lose randomness. But the situation is actually worse than that, because many operating systems (e.g., Windows) do not have clocks with millisecond resolution! For example, on Windows the normal clock increments in 1/18 of a second. This would leave Quackle using the same random seeds for many, many moves in a row. It is true that any modern OS will have a real-time clock that has better timing characteristics. But these are not portable code. Better algorithm: seed using a millisecond timer, so that Quackle does not start up in the same state. Use an RNG that passes all tests of randomness (e.g., KISS). Optionally, you can reseed by adding clock() to the RNG state. The algorithm given above eliminates the benefit of shuffling, so you don't need to take that measure. If the random state has more than 32 bits then you eliminate the issue of having some numbers fractionally more likely than others because the period isn't a multiple of 100 factorial. Final point: you actually have to test your randomness. Do not imagine that if it looks right then it must be OK. Do a chi-squared test of the pairs of numbers drawn sequentially for each possible bag size. You sometimes cannot tell randomness apart from uniformity just by eyeballing the data.
