BBO random generator

[bluecalm]

Intuively I feel that hands on BBO are flatter than hands I play live (also generated by computer but i don't know which program).

Is there any resource about BBO random generator ? I am just curios, I am aware that probably my intuition is just wrong about it but I would like to see what kind of generator BBO is using and if it is good.

[cloa513]

Intuively I feel that hands on BBO are flatter than hands I play live (also generated by computer but i don't know which program).

Is there any resource about BBO random generator ? I am just curios, I am aware that probably my intuition is just wrong about it but I would like to see what kind of generator BBO is using and if it is good.

This probably a better question for the BBO Support Forum- there you might get an answer.

[Antrax]

What you're describing sounds reasonable, as hand-dealing is "less random" than a well-implemented PRNG, and it's more likely BBO uses correct practices than dealing programs (just because BBO is more high profile).

[dwar0123]

What you're describing sounds reasonable, as hand-dealing is "less random" than a well-implemented PRNG, and it's more likely BBO uses correct practices than dealing programs (just because BBO is more high profile).

My understanding was that hand-dealing actually results in flatter hands. Regardless he was comparing BBO dealt hands to other computer dealt hands and in both cases while computer pseudo random number generation is not truly random(hence the pseudo) the difference is utterly indistinguishable to humans*. Pseudo random number generation has been a solved problem for over a decade and it is very unlikely either bbo or another computer dealing program is screwing it up. Possible, but here I would wager pretty heavily on your intuition being wrong.

 

 

*without taking a lot of actual unbiased samples and pouring over them with some math.

[Antrax]

Formally, the difference between pseudo and truly random is such that a computationally bounded adversary cannot detect it. In simple terms, it means that assuming no implementation flaws, a team of NSA experts using all the computing resources in the world won't be able to distinguish between a PRNG's output and God himself giving them random numbers, in time to make it for the heat death of the universe.

 

Intuitively, hand-dealing depends on the algorithm used, but from my experience, people usually just do a couple of riffle shuffles. Those tend to leave clumps intact, especially as the cards age. That would result in hands with wilder shape and an uneven distribution of HCP, as people tend to do things like clear suits and cash out, which cause HCPs and suits to bunch together at the end of play.

 

But there's an awful lot of speculation here from my part, so if anyone has contrary notions, feel free to correct me.

[barmar]

The BBO dealer is very simple:

 

    for ( w=1; w<4; w++ )
   {
     for ( c=0; c<13; c++ )
     {
       do
       {
         s=rand()%4;
         c1=rand()%13;
       } while ( PLAYARRAY[s][c1]!=0 );
       PLAYARRAY[s][c1]=w;
     }
   }

The Linux rand() function isn't random enough for cryptographic use, but it seems to be good enough for dealing bridge hands. Uday told me that we get the expected statistics of hand distributions.

[TylerE]

Wow, that seems like a bit of an archaic way to do it. Why not use a Knuth shuffle, which will always complete in exactly 52 steps?

[Antrax]

That's a bit weird. rand() % is a well-known bad practice. It's true you're not running a bank, but why not use one of the many existing good implementations?

[dwar0123]

Have to admit, that is surprisingly inefficient.

 

But beyond that, if there is any tilt to rand()% implementation, the order and method of dealing cards is greatly magnifying it.

 

Player 1 is getting the first 13 cards dealt and as such any tilt means that he is vastly more likely to get the more common rand results. Player 4 is in the exact opposite position.

 

If you merely reversed the order of the w and c for loops, you would nullify the vast majority of this bias. This would effectively be equivalent to dealing around the table rather then taking 13 cards off the top and giving them to player 1.

 

Of course, if rand()% is effectively random and unbiased, then everything is fine. But a lot of literature says that this can be very problematic.

[barmar]

The documentation I've read says that rand() is uniformly distributed, and in current implementations the low-order bits are as random as the high order ones. RAND_MAX is the same as INT_MAX, and they're both 2^32-1, so rand()%(2^N) should be unbiased. rand()%13 will have a tiny bias because INT_MAX+1 is not a multiple of 13; I believe it's 0.0000003% in favor of 2-10 versus J-A. At our current rate and allowing for generous growth, that's 1-2 hands per decade.

 

I think that's negligible. So while there may be better ways to deal, I don't think we gain much by "fixing" it.

[nigel_k]

Looks fine to me. You guys nitpick too much. It isn't efficient, but that's irrelevant when the time cost of operations and number of hands to deal is so small.

[dwar0123]

Fair enough, my assumptions were that any modern implementation of rand() would be so close to random as to be indiscernible to a semi-serious observer. Seeing the details sadly focused me on the flaws, no matter how indiscernible they might still have been.

 

I wonder how much dealing the first 13 cards to player 1 increases the 0.0000003% for that player.

[barmar]

Fair enough, my assumptions were that any modern implementation of rand() would be so close to random as to be indiscernible to a semi-serious observer. Seeing the details sadly focused me on the flaws, no matter how indiscernible they might still have been.

 

I wonder how much dealing the first 13 cards to player 1 increases the 0.0000003% for that player.

If the dealer were perfectly random, each card dealt to a player would have a 9/13 chance of being 2-10. Because of this minor flaw, that chance is increased to 9.000000027/13 for the first card dealt to player 1. As each card is dealt, the probabilities change a bit because of the cards that are no longer available to be dealt, but I believe the difference from perfection will be of a similar magnitude.

 

So player N is slightly more likely to have low cards than player N+1. But this extra likelihood is on the order of 1 in 10 million. While this is better than playing the lottery, it still doesn't seem like something you can take advantage of. If you play 1,000 hands a day, and play these odds, you'll get a benefit once every 10,000 days, which is 27 years. Most of the probability factors that we deal with in bridge are on the order of a percent or more, and this additional factor is totally negligible compared to them. If you had a true 2-way guess for an honor, you might as well finesse away from a lower-numbered hand; but I'll bet if you really thought about it you could find some information that helps you more than this tiny fraction -- it's negligible compared to a single vacant space.

 

BTW, if you play best-hand robot tourneys, hand 1 is the human's hand, and his hand is swapped with the best hand after the dealing. So there's no way of knowing where hand 1 ended up (but I suppose hand 4 is infinitessimally more likely to be the best hand, so a 1<->4 swap is ever so slightly more likely).

[cloa513]

Looks fine to me. You guys nitpick too much. It isn't efficient, but that's irrelevant when the time cost of operations and number of hands to deal is so small.

To answer to that you need to estimate how big BBO is now? I bet GIB running simulations during bidding is the heaviest part since its supposed to simulate the complete bidding sequence and play sequence.

[nathan2008]

According to what i've learned in the school, I totally agree with Barmar. But my teacher tells me that it is 2^31-1, not 2^32-1 lol. (Because 2^31-1 is a prime number while 2^32-1 isn't :( ) That is how comupter makes random number. I feel confident to programmers.

[billw55]

If you wanted, you could get seeds from true random generators like hotbits. The hands themselves would not be distinguishable, but it might make some people feel better about it.

[dwar0123]

If you wanted, you could get seeds from true random generators like hotbits. The hands themselves would not be distinguishable, but it might make some people feel better about it.

That wouldn't actually solve the (non)problem. The problem is that max number that rand() can come up with isn't divisible by 13, thus when you use the % operator(mod), there are more cases for the lower numbers than the higher numbers.

 

As an example, we can use a really tiny max number to make it really explicit.

 

If the max number rand() can come up with is 2^4-1(15). Thus rand() will generate an integer between 0 and 15 inclusive.

 

0 % 13 = 0

1 % 13 = 1

2 % 13 = 2

3 % 13 = 3

4 % 13 = 4

...

13 % 13 = 0

14 % 13 = 1

15 % 13 = 2

 

If we assign 0 to represent dealing a 2 of a suit and 12 to an Ace of a suit than the first card dealt is twice as likely to be a 2(0) than an A(12). What seed we use has no impact on this.

 

However using a really gigantic MAX_RAND diminishes the biases to the level Barmar stated.

[mycroft]

I would suggest that if their idle thread (or another process) busy-waited calling rand() that I would feel better.

 

Unix/Linux has /dev/urandom, which is non-pseudo RNG, it generates bits out of an entropy pool it tries to keep up by using environmental randomness. For BBO, I wouldn't worry about rand(); for people making hand records for Bermuda Bowl and the like, avoiding a PRNG is probably worth it - I postulated years ago that someone with $1M to build special hardware and access to the vugraph could likely crack a 36-deal set made from a single seed in time to know the last few boards. Computing power hasn't got *more expensive*.

 

Take log₂(hands^36) bits of true randomness (or log₂(hands)*36, if randomness is cheaper than huge modulo division (which it probably is)) and build 36 unconnected, true random hands for each set, and you've OTPed it. But, as I said, that's almost certainly overkill for BBO.

[barmar]

To answer to that you need to estimate how big BBO is now? I bet GIB running simulations during bidding is the heaviest part since its supposed to simulate the complete bidding sequence and play sequence.

That code isn't in GIB, it's just the BBO server.

[barmar]

For BBO, I wouldn't worry about rand(); for people making hand records for Bermuda Bowl and the like, avoiding a PRNG is probably worth it - I postulated years ago that someone with $1M to build special hardware and access to the vugraph could likely crack a 36-deal set made from a single seed in time to know the last few boards. Computing power hasn't got *more expensive*.

So if JEC or Nickell wanted to cheat, they could afford to build that machine. I'm not too worried about it. It's still out of reach of some random player trying to win the BB.

[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]

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.