[CarlRitner]

So, despite the hands dealt being statistically appropriate for hand patterns and HCP, can BBO deal every possible deal, or only 2^32 (4 billion or so)?
I thought one needed 96 bits of entropy to cover all 53,644,737,765,488,792,839,237,440,000 possibilities.

[barmar]

Probably not. Let me know when you notice us repeating and we'll think about "fixing" it.

[CarlRitner]

barmar, on 2012-October-11, 18:59, said:

Probably not. Let me know when you notice us repeating and we'll think about "fixing" it.

The reason I mentioned this is because for years, Bridge Baron (and most other bridge playing programs) stated "4 billion random deals" etc... but about two years ago, Bridge Baron upgraded the internal dealer to cover all possible deals. I can't tell you why they did this, but it was implemented without any issues (I am a beta tester for them).

I would never "notice it" repeating (heck, I can replay my deals from a year ago and not notice it, and I did not mean to imply it was "broken". I was expressing curiosity, perhaps on the wrong thread?

[barmar]

The general point I'm making is while there may be ways to improve it, what we've got is good enough for our needs and we have more important things to fix.

To tell the truth, I'm not sure how to calculate how many possible hands this algorithm can deal. If someone else knows, help me out. The period of rand() is about 2^35, but we also reseed it from time to time (whenever the BBO server is restarted). But this isn't the only thing we're calling rand() for -- it's also used in some movements.

[Antrax]

The "fix" would be pasting a piece of code with no licensing issues into the existing code and recompiling. You can piggyback it on whatever update you have planned next. Even just using the algorithm to generate a random permutation (Which I learned from this thread is called a "Knuth Shuffle") would mean you consume less randomness per deal so you get more possible hands.

[CarlRitner]

barmar, on 2012-October-11, 20:11, said:

The general point I'm making is while there may be ways to improve it, what we've got is good enough for our needs and we have more important things to fix.

Gotcha. Didn't mean to stir things up, it's just anytime I can combine bridge and computer stuff, I enjoy it.
4 trillion boards ought to cover my needs.

[Siegmund]

Quote

So, despite the hands dealt being statistically appropriate for hand patterns and HCP, can BBO deal every possible deal, or only 2^32 (4 billion or so)?
I thought one needed 96 bits of entropy to cover all 53,644,737,765,488,792,839,237,440,000 possibilities.

Without addressing BBO specifically...

Whether you can deal every possible deal is a separate question from how much entropy you have per deal. You can reach every possible deal completely deterministically just by enumerating them -- and if you did something like choosing the (30,000,000,000,000,000,000,000,000,001*n mod 53,644,737,765,488,792,839,237,440,000) th hand from the list to be your nth deal, it would be quite a long time before someone noticed the determinism.

There are many possible shuffling routines which can reach all possible deals, but can only "start from" 2^32 places as they work their way through the list.

There is a whole subdiscipline of "quasirandom number generators", guaranteed to eventually cover all possibilities and to scatter the first n points as uniformly around the sample space as possible. It's not much talked about now, but once upon a time it was used to do Monte Carlo integration faster and with tighter error bounds than by using pseudorandom numbers.


How many bits of entropy are used for each new hand addresses a separate question -- how well can the next deal be predicted, given the hands which have been dealt before it?

For humans, almost none are needed, if the pattern in which the hands are presented doesn't show any too-obvious trend. To defeat computer prediction of next boards, several bits per hand are desirable, but you can get away with quite a bit less than 96 per hand.

[barmar]

It just occurred to me that the fact that the same RNG is being used for a variety of things in the program effectively ADDS entropy.

If the RNG were just being used for dealing hands, and you saw a sequence of several hands, you might be able to calculate where it is in the random sequence, and predict the next set. But if hand dealing can alternate with an unpredictable number of other activities that also use the RNG, you lose your place. You might be able to estimate a range of other random activities that took place between deals, but that will give you a variety of possible deal sequences.

To get around this, you would need to somehow eavesdrop on ALL the activities that use the RNG, and know exactly how it's being used, to have a decent chance at predicting sequences.

[Antrax]

That sounds about right. Assuming these unpredictable events are driven by interrupts or user input, that's actually another source of randomness

[woefuwabit]

There was a pretty good paper about fair generation of bridge deals written 12 years ago:
http://sater.home.xs4all.nl/doc.html

There are two issues with the implementation barmar posted
1. c1=rand()%13; This will be biased towards certain values. A simple way of unbiasing it would be to modify the line to:
do {
c1=rand() & 0xF;
}
while (c1 >= 13);

2. Not sure what implementation of rand() the bbo compiler is using but AFAIK most implementations (e.g. GCC, VC) use a LCG with a period of 2^32, which is far below the minimum 2^96 that is required, meaning that it will only be able to deal a very small subset (1 in 2^64) of all the possible bridge hands. You should probably use something like a Mersenne Twister instead which has a period of 2^19937


Ideally, you would really want to implement something like that Big Deal has done.
1. Generate 512 bits of entropy, which can be reused forever
2. Start counter at 0
3. Hash(Entropy + Counter), I'd recommend using SHA256
4. Map the result to a bridge deal, e.g. using http://bridge.thomas...com/impossible/
5. Increment counter, go to 3 for next hand

[jandrew]

I sometimes wonder how many angels can REALLY dance on a pin head.



jandrew

[jandrew]

... ... and if one fell off, would we REALLY notice.

jandrew

[barmar]

woefuwabit, on 2012-October-15, 11:49, said:

2. Not sure what implementation of rand() the bbo compiler is using but AFAIK most implementations (e.g. GCC, VC) use a LCG with a period of 2^32

We're using whatever you get with Debian Linux.

[woefuwabit]

barmar, on 2012-October-15, 15:48, said:

We're using whatever you get with Debian Linux.

That would be glibc, which uses a LCG with period of 2^31
Since you are on Linux, you have easy access to a strong PRNG in /dev/urandom and should probably just use that. Just add this and replace your calls to rand() with urand():

int urand() {
   static FILE* file = fopen("/dev/urandom", "r");
   int random;
   fread(&random, sizeof(random), 1, file);
   return random;
}

[barmar]

The fixes are all pretty obvious, I don't need programming lessons.

It's the need to fix it that I'm not so sure of. I think folks are overstating the inadequacies of the current implementation.

[Antrax]

No disrespect intended, I'm sure. It just seems like low-hanging fruit.

[woefuwabit]

No disrespect intended, just showing that the fix is trivial compared to potential issues.
Just remember that because of the birthday paradox, there will be a 50% probability of a deal being repeated after 2^15.5 = 46341 deals. Personally, I'm not comfortable with that, but the prerogative is yours.

[woefuwabit]

I thought about it further and the problem is actually far more serious than I thought.
I can build a database containing all 2^31 possible hands that BBO can deal.

After seeing 13 cards (my own), there will be an average ~296 possible distributions for the remaining 3 hands.

After seeing 26 cards (mine + dummy's), the exact distribution of the remaining 2 hands can almost always be determined. Occasionally there will be 2 possibilities but that will be very rare. the exact distribution of the remaining 3 hands can be determine ~99.7% of the time.

[Antrax]

I'm not sure that's accurate, because of the existing deal algorithm. If the algorithm were "pick a random number; take that hand from the index of all possible hands" then that would've made sense, but because each card consumes a different amount of randomness, it ends up creating smaller cycles in the larger cycle. I have no clue how to deal with it, and assuming the PRNG is reseeded from time to time, the added randomness from rand() being used for other things makes this attack unlikely.

[woefuwabit]

Antrax, on 2012-October-18, 00:26, said:

I'm not sure that's accurate, because of the existing deal algorithm. If the algorithm were "pick a random number; take that hand from the index of all possible hands" then that would've made sense, but because each card consumes a different amount of randomness, it ends up creating smaller cycles in the larger cycle. I have no clue how to deal with it, and assuming the PRNG is reseeded from time to time, the added randomness from rand() being used for other things makes this attack unlikely.

It doesn't matter. Because the LCG has 2^31 possible states when you start the generation, there can only be a maximum of 2^31 possible hands generated. Reseeding the LCG will only change the state from one of the 2^31 possible states to another of the 2^31 possible states. The maximum number of different hands that BBO can generate is 2^31, no matter how much entropy you try to introduce to it.

I actually underestimated the seriousness of the attack in my previous calculation:

There are 52c13 = 52!/(13! * 39!) = 6.35e11 possible 13 card hands
BBO can deal 2^31 = 2.15e9 possible hands

That means your 13 card starting hand is enough to determine the distribution of all the remaining 3 hands, 295 out of 296 times. (Not determine ~296 possible distributions as I previously miscalculated)


Of course, if rand() is called by another thread while we are in the middle of generating a hand, this will throw off the attack. I don't expect this to happen a lot though unless rand() is called by another thread very frequently. Also not certain if the other rand() calls happen in a different thread.