srand() troubles

[Gordon Burditt]

Now my suggestion is to use the (normally pitiful) built in rand

and srand functions to produce one random value, and use the
result to seed the Mersenne Twister (with seedMT()). You could

The number of possible shuffles of a deck of cards is 52 factorial.
Any seed less than 200 bits long is pitifully inadequate, especially
if you're playing for real money.

By using the built in rand() to generate a seed, you are potentially
crippling the Mersenne Twister (which only has 31 bits of seed,
still horribly inadequate, but probably generates much better random
numbers than rand()) with something which may only generate 2**15
possible seeds.

then use another value from rand to clock the twister through a
semi-random number of initial values, and continue from there.
Something like:

unsigned long count;

srand(time(NULL));
seedMT((unsigned long)rand() & ~1UL);
count = rand();
while (count--) randMT();

This only need to happen once, at program initialization, and can
be bypassed for a deterministic sequence for testing. After that
the shuffle can depend only on randMT. If initialization takes
too long limit the size of count.

This approach does nothing to increase the number of possible shuffle
results beyond the number of seeds that srand() accepts.

Notice that the period of the Mersenne Twister is much longer than
the maximum return value, which is ULONG_MAX. Thus duplicate
values CAN and will occur.

This would increase the number of possible shuffles *IF* you don't
start the program over again each time, but just continue from
the previous state of the Twister.

Gordon L. Burditt

 

[Merrill & Michele]

Thanks all. I'll go with the Twister. Just seeing the word Mersenne in it
and having it associated with Knuth is sufficient for me to invest my faith
in it. I'm worried about design already, but that is not germane to this
thread.

Can you imagine having been in the room when Frank Coles wordlessly
approached the board and wrote:
2^67-1=193707721*761838257287 ? MPJ

 

[CBFalconer]

The number of possible shuffles of a deck of cards is 52 factorial.
Any seed less than 200 bits long is pitifully inadequate, especially
if you're playing for real money.

By using the built in rand() to generate a seed, you are potentially
crippling the Mersenne Twister (which only has 31 bits of seed,
still horribly inadequate, but probably generates much better random
numbers than rand()) with something which may only generate 2**15
possible seeds.


This approach does nothing to increase the number of possible shuffle
results beyond the number of seeds that srand() accepts.


This would increase the number of possible shuffles *IF* you don't
start the program over again each time, but just continue from
the previous state of the Twister.

That is assumed. Note that shuffling a deck requires only 52
successive random values (assuming no rejections by the shuffling
code). Once the system has been seeded the future shuffles are
deterministic, but I challenge anybody to create a practical way
of detecting the seed from a reasonable deal. The period of
2^19937 -1 makes indexing this impracticable. The seed of the
built in rand probably cannot be detected, because its values are
only used twice.

 

[Gordon Burditt]

That is assumed. Note that shuffling a deck requires only 52

successive random values (assuming no rejections by the shuffling
code). Once the system has been seeded the future shuffles are
deterministic, but I challenge anybody to create a practical way
of detecting the seed from a reasonable deal. The period of
2^19937 -1 makes indexing this impracticable. The seed of the
built in rand probably cannot be detected, because its values are
only used twice.

I only need to determine
(a) the initial seed to srand(), and
(b) which shuffle we are on since the program restarted.
everything is determined from that.

Given those two items, I just need to run the algorithm forward,
which should be trivial if the machine is playing against a human
(with a hidden computer, or talking to someone with a computer) who
is expected to take time for his decisions.

Now, how do I determine (a) and (b)? Run the algorithm forward for
all possible combinations of seeds and maybe the first dozen or so
shuffles from any start of the program. (Note: it really helps
here if I can force the program to restart, as in cause a power
failure, say overnight, to go back to deal 1, so when I get to the
machine the deal number is "small"). Make an index of things I can
observe (cards I get dealt) to look up (a) and (b). This I only
have to do once, and store it.

Then I feed in observed items for this deal, and see how many
possibilities there are. Once I know that the seed is X and the
shuffle is N, the next deal is either seed X and shuffle N+1 or
unknown seed and shuffle 1.

If the initial seed only has 15 bits and you compute 30 deals, the
precomputed index is probably feasable with only about 1 million
entries. (and possibly could be done with a handheld). The index
perhaps includes my 5 cards (6 bits each), in order, the seed (16
bits), and the deal number (8 bits) - about 7MB total. The 5 cards
you see have 300 million possible combinations (including the order,
which you should use if it's available), so most of the time ( 316
out of 317) you should be able to identify a unique seed and deal
from just your own cards. There's also a substantial chance that
you will be able to tell that your combination is not in the index
(the machine has been running longer than 30 deals) if that's the
case. I believe this is a practical way to determine the seed from
part of the dealt cards (for the 15-bit seed case).

If the initial seed has 31 bits (and you do 30 deals), the index
is now getting large enough that it takes lots of storage and it
may be hard to get answers fast enough. Further, you almost certainly
will not be able to identify a unique seed and deal from your own
5 cards (you'll probably end up with about 200 possibilities). You
still might be able to determine the seed and deal AFTER the hand
is played and then determine the next hand. You also won't be able
to tell if your combination is not in the index. Given, say, 5
possible shuffles, equally likely, quick, determine how you should
bet. Unless you get really serious about this, and are able to do
it unobserved (say, over the internet or at an unattended poker
machine in a store (not casino)) and observe several hands first,
this isn't a practical way to determine the seed.

The huge state kept by the Twister (period of 2**19937 -1) is
sabotaged by the limited seed and practical limits on the run time
of the program.

Gordon L. Burditt

 

[CBFalconer]

I only need to determine
(a) the initial seed to srand(), and
(b) which shuffle we are on since the program restarted.
everything is determined from that.

Given those two items, I just need to run the algorithm forward,
which should be trivial if the machine is playing against a human
(with a hidden computer, or talking to someone with a computer) who
is expected to take time for his decisions.

Now, how do I determine (a) and (b)? Run the algorithm forward for
all possible combinations of seeds and maybe the first dozen or so
shuffles from any start of the program. (Note: it really helps
here if I can force the program to restart, as in cause a power
failure, say overnight, to go back to deal 1, so when I get to the
machine the deal number is "small"). Make an index of things I can
observe (cards I get dealt) to look up (a) and (b). This I only
have to do once, and store it.

Then I feed in observed items for this deal, and see how many
possibilities there are. Once I know that the seed is X and the
shuffle is N, the next deal is either seed X and shuffle N+1 or
unknown seed and shuffle 1.
.... snip ...

The huge state kept by the Twister (period of 2**19937 -1) is
sabotaged by the limited seed and practical limits on the run time
of the program.

Not being any sort of cryptographer, I guess you are right in that
it can be beaten. After all, there is no such thing as an
unbeatable system, given enough time. Another thought that occurs
to me is to permute the bit order of the randoms generated.
However, all this is getting OT here, where the original idea was
to generate a suitable simile of a shuffle, not to protect it
against the world.

 

[Mike Wahler]

doubled;

All in favor, say aye.

int i;

-Mike