Computer dealt hands - with a hiccup

[aguahombre]

2. You will remonstrate with the player if he announced it in such a way as to poison the board for others (but not if he told you quietly)

3. You will direct that the boards continue to be played because you have no evidence that this is other than a correct deal (although I agree probability is on the side of suspicion).

I do hope this is tongue-in-cheek.

[pran]

And what does it take to test a card dealing program? A set of 8000 deals run through my testing procedure will give an initial answer within seconds. More such sets created independently over some time and tested will usually be sufficient to provide a definite answer, but preferably the basic random generator algorithm should also be available for a separate test as this is the kernel of any such system.

Seriously, how hard is it to write a random board generating algorithm. Every programming language has a library for getting good (secure) random numbers, plug that into a Knuth shuffle and you're done... Seeding it isn't a problem either, the platform should have a way of randomly initializing the seed each time.

 

Out of interest what's your testing procedure?

1: Good random number generators are not common although they have certainly become better over the years. I don't know if Microsoft Excel still uses a 16 bits generator or if they at last have advanced to 32 bits.

The size of the generator is directly limiting the number of deals that can safely be generated with that generator. A 16 bits generator is "safe" for only about 12 deals in a run.

 

Delphi (the language I use) includes a good 32 bits generator, but I have implemented my own 64 bits generator based on the recommendation by Knuth.

(At present I am testing out a generator where I can select the size to any number of bits I want.)

 

2: For seeding the only really important issue is to guarantee that two different runs can never start with the same seed. In addition all the seed bits should be created randomly. This is not usually secured by any platform that I know of.

 

3: My test procedure is to apply Chi-square analysis on hand distributions, suit distributions, High card point distributions and individual card distributions over series of (typically) 800 deals. Each Chi-Sq value is transformed into the probability that a true random set would be closer to the theoretical average than the observed distribution.

 

The most "expected" result is of course 50% indicating that a closer to average result is just as probable as a less close result.

 

But the really important test is that over ten such test series (each with 800 deals) the probabilities should spread fairly evenly between 0 and 100%

 

A consistently low probability is a danger signal, it is like a dice which when thrown many times will yield exactly one each of the numbers from 1 thru 6 for each 6 throws, or six dice when thrown will show a straight on (nearly) each throw, a very unlikely event.

 

A consistently high probability is another danger signal. Last time I observed that was with a card dealing program that gave the ♣2 to the same hand in almost every deal.

 

I have selected the size of a test set 800 deals rather arbitrarily, but it should not be less, or the Chi-Sq tests will be significant for only the most common distributions.

[nige1]

On what legal grounds do you issue such a warning, Nigel? Did he do something wrong?

Under what law, can you object to consecutive identical hands? :P

 

Obviously, from the point of view of the player, who calls the director, this deal might be similar to but not the same as the previous deal. The unseen cards may be quite differently distributed. His claim that his hand is similar to his previous hand is gratuitous unauthorised information. He can wait until the play is over.

[nige1]

I believe that Thomas Andrews' dealing program will generate all possible hands (eventually). Richard Pavlicek's dealer is similarly excellent and fast. They both have all kinds of fascinating stuff!

[aguahombre]

On what legal grounds do you issue such a warning, Nigel? Did he do something wrong?

Under what law, can you object to consecutive identical hands? :P

 

Obviously, from the point of view of the player, who calls the director, this deal might be similar to but not the same as the previous deal. The unseen cards may be quite differently distributed. His claim that his hand is similar to his previous hand is gratuitous unauthorised information. He can wait until the play is over.

Why do you keep going there? The same hand was rotated counter-clockwise. that is a "given". How else should the OP say it, and in what different ways, before the fact is established?

 

Keeping both boards in play is not bridge as I know it. People with the appropriate skill set will know the hand, especially RHO's hand while attempting to bid, play, defend or whatever. Others will not.

 

Get over the fact that one astute player drew attention to the problem. That player is not the problem. My partner and I were the first to report that two different boards were identical at the start of the fifth round of a top flight regional scored across multi sections ---resulting in a chinese fire drill of scoring that you would not believe. But not once did anyone suggest we should have kept our mouths shut so both boards could continue to be played. And no one was silly enough to suggest it was just a miracle of random number selection.

[mjj29]

1: Good random number generators are not common although they have certainly become better over the years. I don't know if Microsoft Excel still uses a 16 bits generator or if they at last have advanced to 32 bits.

The size of the generator is directly limiting the number of deals that can safely be generated with that generator. A 16 bits generator is "safe" for only about 12 deals in a run.

 

Well, that suggests using a LFSR or similar, which will, obviously, loop after it's width. However, that won't actually give you completely independent deals, since it _can't_ repeat until the end. Surely you want to re-seed each board (this is, infact, what I do). There are a number of good ways to generate a cryptographically secure bitstream from a seed, AES256 in CTR mode with a random key being quite a good one.

 

Delphi (the language I use) includes a good 32 bits generator, but I have implemented my own 64 bits generator based on the recommendation by Knuth.

(At present I am testing out a generator where I can select the size to any number of bits I want.)

 

A use Java's SecureRandom class re-seeded from the host's entropy pool each board, using just the low-order 6 bits as the input of a Knuth shuffle. I believe this to be both statistically flat and cryptographically secure.

 

2: For seeding the only really important issue is to guarantee that two different runs can never start with the same seed. In addition all the seed bits should be created randomly. This is not usually secured by any platform that I know of.

 

/dev/urandom on anything other than windows for a start.

 

Anyway, I think we've probably side-tracked this thread enough

[helene_t]

Last time I observed that was with a card dealing program that gave the ♣2 to the same hand in almost every deal.

I think I know that program. Not sure how it manages to get that wrong. One of the first computer programs I wrote when my dad took an office compute home for me and my brother to play with was a dealing prgram that would usually give ♠AK to the same player, as it allocated each card randomly among the non-filled hands, instead of weighting them by their numbers of empty slots.

[blackshoe]

Under what law, can you object to consecutive identical hands? ;)

Under what law can you not?

Obviously, from the point of view of the player, who calls the director, this deal might be similar to but not the same as the previous deal. The unseen cards may be quite differently distributed. His claim that his hand is similar to his previous hand is gratuitous unauthorised information. He can wait until the play is over.

 

I disagree. It might be "better", for some values of "better", if he had waited, but there is no law requiring him to do so.

 

The relevant law is 9A1. Gtanted, 9A1 refers to unnamed other laws which may prohibit the director call. Fair enough. Find one. :P

[nige1]

Hans van Staveren's Big deal uses 96 bits to ensure that his random number generator can produce enough numbers and uses Thomas Andrews' algorithm to map each number to a deal (ensuring every possible deal is accessible).

[pran]

Last time I observed that was with a card dealing program that gave the ♣2 to the same hand in almost every deal.

I think I know that program. Not sure how it manages to get that wrong. One of the first computer programs I wrote when my dad took an office compute home for me and my brother to play with was a dealing prgram that would usually give ♠AK to the same player, as it allocated each card randomly among the non-filled hands, instead of weighting them by their numbers of empty slots.

Classic and well known mistake.

 

So in your program you started with placing the ♣2 and ended with placing the ♠A? :P

[pran]

Hans van Staveren's Big deal documentation shows you why you need 96 bits to ensure that no deal is inaccessible and uses Thomas Andews' algorithm to identify each deal.

I know about BigDeal and the fallacy in showing how you need a 96 bits random generator. (Yes, there is a fallacy there!)

[nige1]

Obviously, from the point of view of the player, who calls the director, this deal might be similar to but not the same as the previous deal. The unseen cards may be quite differently distributed. His claim that his hand is similar to his previous hand is gratuitous unauthorised information. He can wait until the play is over.

Why do you keep going there? The same hand was rotated counter-clockwise.  that is a "given".  How else should the OP say it, and in what different ways, before the fact is established?  Keeping both boards in play is not bridge as I know it.  People with the appropriate skill set will know the hand, especially RHO's hand while attempting to bid, play, defend or whatever.  Others will not. Get over the fact that one astute player drew attention to the problem.  That player is not the problem. My partner and I were the first to report that two different boards were identical at the start of the fifth round of a top flight regional scored across multi sections ---resulting in a chinese fire drill of scoring that you would not believe.  But not once did anyone suggest we should have kept our mouths shut so both boards could continue to be played.  And no one was silly enough to suggest it was just a miracle of random number selection.

I disagree (with nigel). It might be "better", for some values of "better", if he had waited, but there is no law requiring him to do so.

The relevant law is 9A1. Gtanted, 9A1 refers to unnamed other laws which may prohibit the director call. Fair enough. Find one.

Its no big deal Blackshoe and Aquahombre :P

 

I imagined that, in the middle of a hand, saying that you hold the same cards as on the previous deal, might be construed as unauthorised information to partner. I'm not a director and bow to your superior knowledge ;)

[nige1]

I think I know that program. Not sure how it manages to get that wrong. One of the first computer programs I wrote when my dad took an office compute home for me and my brother to play with was a dealing prgram that would usually give ♠AK to the same player, as it allocated each card randomly among the non-filled hands, instead of weighting them by their numbers of empty slots.

Computer Weekly challenged readers to deal hands in the early 70's. I wrote a simple program like Helen_t's that Ian Morrison used to deal hands for Scottish national competitions. A colleague published my sampling algorithm in CACM :). but modern programs (eg Thomas Andrews, Richard Pavlicek, and Hans van Staveren) are much better.

[suprgrover]

I know about BigDeal and the fallacy in showing how you need a 96 bits random generator. (Yes, there is a fallacy there!)

Could you explain what you mean here? There are between 2^95 and 2^96 possible bridge deals, so what is wrong with using 96 bits?

[suokko]

And what does it take to test a card dealing program? A set of 8000 deals run through my testing procedure will give an initial answer within seconds. More such sets created independently over some time and tested will usually be sufficient to provide a definite answer, but preferably the basic random generator algorithm should also be available for a separate test as this is the kernel of any such system.

Seriously, how hard is it to write a random board generating algorithm. Every programming language has a library for getting good (secure) random numbers, plug that into a Knuth shuffle and you're done... Seeding it isn't a problem either, the platform should have a way of randomly initializing the seed each time.

 

Out of interest what's your testing procedure?

Too bad secure random number generator is often hidden so I would suspect normal bridge dealer use simple rand() call. Quality of rand is platform depend but often it is optimized for speed instead of quality of bit stream. Luckily new c++ standard will provide better random number library that provides multiple random number generators with different qualities and speeds. (But none that is cryptographically)

 

In windows secure random number api is hidden in crypto api which is probably not know to many programmers except when writing some crypto programs. You already mentioned the unix world /dev/random that would provide really independent bit stream.

 

Problem for using non-windows platform is that wireless bridge scoring systems are only supported in windows so directors are using windows for everything.

[suokko]

I know about BigDeal and the fallacy in showing how you need a 96 bits random generator. (Yes, there is a fallacy there!)

Could you explain what you mean here? There are between 2^95 and 2^96 possible bridge deals, so what is wrong with using 96 bits?

Because you don't need to use if your generator has long enough period to generate enough random bits for the set of deals. I don't know what sizes generator is good enough but at least pran is claiming that 32bit PRNG is enough.

[suprgrover]

Because you don't need to use if your generator has long enough period to generate enough random bits for the set of deals. I don't know what sizes generator is good enough but at least pran is claiming that 32bit PRNG is enough.

But the period of a generator tells us how long until the sequence repeats. The idea behind having 96 bits is to ensure that every deal could be generated; with fewer bits I do not see how you can include all possible deals in the set of deals that the program could produce.

[suokko]

But the period of a generator tells us how long until the sequence repeats. The idea behind having 96 bits is to ensure that every deal could be generated; with fewer bits I do not see how you can include all possible deals in the set of deals that the program could produce.

I can take 3 (32bit) random numbers and append them to each other to produce 96 bits of information.

 

Better of course would be only using the most random part of that 32 bit and append more numbers to each other to produce the full 96 bits.

[Echognome]

I was the person who noticed this problem.

 

I simply don't understand all the discussion about the possibility or impossibility of the boards being the same. They were the same. I believe the problem was when the deals were made and I'm pretty sure it was human error, rather than computer error. The boards were pre-dealt, so there was no issue of a player making the error.

 

I called when dummy came down, because I remembered my hand from the previous board, which was now dummy's, to the pip. I had less of a recollection of the hand I held from the previous board as it was an opponent's, but it seemed like it was the exact hand. I called the director and went away from the table to tell him to check. He did and confirmed there was an error.

 

Those are the facts. The question is what is the ruling? Should the cancelled boards be scored as is? Should they be given average plus (no players at fault)? Or should they be scored as average or average minus (as no one else noticed)?

 

Those seem to be the salient questions to me.

[pran]

I was the person who noticed this problem.

 

I simply don't understand all the discussion about the possibility or impossibility of the boards being the same. They were the same. I believe the problem was when the deals were made and I'm pretty sure it was human error, rather than computer error. The boards were pre-dealt, so there was no issue of a player making the error.

 

I called when dummy came down, because I remembered my hand from the previous board, which was now dummy's, to the pip. I had less of a recollection of the hand I held from the previous board as it was an opponent's, but it seemed like it was the exact hand. I called the director and went away from the table to tell him to check. He did and confirmed there was an error.

 

Those are the facts. The question is what is the ruling? Should the cancelled boards be scored as is? Should they be given average plus (no players at fault)? Or should they be scored as average or average minus (as no one else noticed)?

 

Those seem to be the salient questions to me.

This completes the story with important information.

 

You informed the Director about your suspicion without giving away any indication on the problem to the other players at the table, that was very good and in fact the correct procedure.

 

Now we are in Law 6D2 territory, and at your table the correct ruling would be to replace the board with a correct one if possible or award A+ to both sides. (As I understand you there was no "correct" board.)

 

The rest of this thread has gone into a discussion on computerized card dealing.

 

regards Sven

[pran]

I know about BigDeal and the fallacy in showing how you need a 96 bits random generator. (Yes, there is a fallacy there!)

Could you explain what you mean here? There are between 2^95 and 2^96 possible bridge deals, so what is wrong with using 96 bits?

It is nothing wrong (provided it is shown that each possible result will occur with the correct probability), but it is not neccessary.

 

Traditional shuffling routines use 51 (separate) random numbers to determine the transformation of one shuffled card deck into the next. So even after for instance 2^32 random numbers have been used and a new full cycle is started upon in the generator there will not be any apparent repetition of already created deals.

 

There is even more to this question, but I shall try not to "overflow" the thread.

 

regards Sven

[helene_t]

I can take 3 (32bit) random numbers and append them to each other to produce 96 bits of information.

But if the random number generator only uses 32 bits to represent its state, then you can never get more than 32 bits of entropy out of it. A sequence of 3x32 bits will contain only the first 32 bits of entropy - the remaining 64 bits are determined by the first 32 and therefore contain 0 (conditional) entropy. So if there are really 2^95 hands, you can only generate a small subset of them.

 

Practically speaking, it would probably work to create three different initial seeds (for example by reading the user's keystroke tempo 3 times) and then initiate three different random number generators and run them in parallel, generating each hand from the concatenation of the current states of the three generators. This procedure will repeat itself after 2^32 boards rather than 2^96, but the user is likely to have rebooted the system before you come that far :(. (I would then use 4x32 rather than 3x32 to make sure that it wouldn't be possible to guess the next deal if you recognize one deal).

[axman]

I was the person who noticed this problem.

 

I simply don't understand all the discussion about the possibility or impossibility of the boards being the same.  They were the same.  I believe the problem was when the deals were made and I'm pretty sure it was human error, rather than computer error.  The boards were pre-dealt, so there was no issue of a player making the error.

 

I called when dummy came down, because I remembered my hand from the previous board, which was now dummy's, to the pip.  I had less of a recollection of the hand I held from the previous board as it was an opponent's, but it seemed like it was the exact hand.  I called the director and went away from the table to tell him to check.  He did and confirmed there was an error.

 

Those are the facts.  The question is what is the ruling?  Should the cancelled boards be scored as is?  Should they be given average plus (no players at fault)? Or should they be scored as average or average minus (as no one else noticed)?

 

Those seem to be the salient questions to me.

This completes the story with important information.

 

You informed the Director about your suspicion without giving away any indication on the problem to the other players at the table, that was very good and in fact the correct procedure.

 

Now we are in Law 6D2 territory, and at your table the correct ruling would be to replace the board with a correct one if possible or award A+ to both sides. (As I understand you there was no "correct" board.)

 

The rest of this thread has gone into a discussion on computerized card dealing.

 

regards Sven

We were informed subsequently that the hand records matched the cards for boards 9 & 10. This suggests that the computer generated the hands legitimately as played.

 

And merely because such an occurence is improbable, this player by not holding his tongue has destroyed probably the one opportunity in this solar system to experience the anomaly [legitimately].

[aguahombre]

LOL. Echo, I think you should give up trying to get an answer. Nobody wants to accept that there was a human error and fouled board(s). The presence (if true) of a hand record showing both hands as they were only means the human error occurred at a different point.

 

Even if it was a computer malfunction, to allow continued play of hands where the other players' hands are known or knowable cannot be right. Continued shooting of the messenger cannot be helpful, either.

[gordontd]

I think you should give up trying to get an answer.

I'll give what I think is a practical answer, using L6D1 and L16C as my legal basis, but fully accepting that it's not water-tight.

 

Boards 9 & 10 are materially different, because of the rotation, dealer & vulnerability. Those who have already played them have valid comparisons that can be made with each other, and so I would score them as they were played.

 

Now we have a player who has recognised the hands in Board 10 and who is therefore in receipt of extraneous information and who will need to be awarded an artificial score (A+/A+) under L16C. Since we know that there may be others who will be in that position, we should now redeal Board 10 to avoid having to issue further artificial scores, and then at the end of the game we can score it as a fouled board, with those who played it in one form compared with each other, and those after the redeal scored separately. Board 9 can continue to be played and scored as normal (assuming they are playing 2-board rounds and the two boards are in the same board-set).

Edited December 7, 2009 by gordontd