On 9/12/07, Austin Nichols <[EMAIL PROTECTED]> wrote: > but I guess the issue is how often an 8-bit PRNG that produces 256 > distinct *initial* letter orderings can produce e.g. identical first > rack draws. 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?
Let's assume a hypothetical implementation of rand() and srand() which had 32-bit internal state and 32bit input parameters and results. If you only seed the PRNG once at the start of the run with a hardware-produced truly random number which had only 8 bits of entropy (ie could only have 256 different values, even if the actual values were widely dispersed over the 32 bit range), then you would only every get 256 different tile orderings, assuming rand() was not called at other times and no more entropy was injected. You could make 10,000 calls to rand() in a row, and you would get that same sequence of 10,000 random numbers the next time you ran the code with the same seed. Your assumption that "it shuffles on every draw" is where the problem lies. Successive calls to rand() are predicable. Only srand() enables what you'd consider shuffling in this context. In practice you probably do change the state *a little* because of the randomness of human players, making different selections for their play and therefore having a knock-on effect that causes the AI player to select different tiles even though the PRNG might have returned the expected next value in the sequence, because the game state has changed even if the PRNG state is predictable. Resetting the seed to an 8-bit value before running each sim would be disasterous, for example. You'ld only ever simulate 256 games. That doesn't happen in practise because you don't ever reset the seed. As with the poker example in my last post, if you have a rough idea of when quackle was started up, and assuming quackles initial randomness comes only from the date/time of day clock, then by running quackle's tile sorting algorithm multiple times, guessing the clock tick number that it started at (say by iterating from the value it would have had 5 minutes before invocation to the value from 5 minutes after) you will eventually deal yourself an initial hand that exactly matches the one quackle gave you, and from that point on you could exactly track quackle's tiles and the ones still to be chosen. This can be mitigated if quackle called rand() every clock tick while it was idle, in order to insert some more true randomness from the timing of the player making his move, but it wouldn't alleviate the potential of working out at least the opponents initial rack. This sort of timing attack is common in cryptography, and you need a little care to avoid being succeptible to it. (For example some linuxes generate SSL keys during the boot process. This is before *any* user interaction, and presumably the entire machine state is predictable and reproducible, with the only variable being again the clock, even though the programmer thinks he's getting lot of entropy because he's calling for data from the system entropy pool which works well enough once the system has been running long enough to actually gather some true random inputs) However from the point of view of bias, all this is irrelevant. It only would matter if quackle were playing against a human for something valuable (money or reputation) and someone went to the bother of mounting a cryptographic timing attack against it. Graham
