[hrothgar]

So, a friend of mine just asked me some questions about BBO's random number generator, claiming that he had seen some highly unlikely events occur over the past few years...

My reaction was that lots of hands get played on BBO, as such highly unlikely events happen.
Anecdotal claims really aren't a good way to address this issue and, as such, the only thing that I would find interesting is some kind of source code audit.

I'm curious whether BBO would ever consider standardizing on a hand generator that is know to be secure like Hans Van Stavern's Big Deal simply to forestall these sorts of discussions.

It would be convenient to simple be able to say

1. BBO uses Big Deal
2. Our PRNG is a Mersenne Twister
...

[fred]

Richard - I know very little about such things in general or how we do it on BBO (I am a client-side programmer and we generate deals on the server), but I am hoping you can explain something (only because I am ignorant and curious)...

Suppose you learned that BBO generates hands in some non-ideal way such that, in principle at least, it would be possible for a skilled person to be able to start making predictions about future deals by looking at past deals.

My guess is that in reality this wouldn't work because for every (badly-generated) deal you see on BBO, there would be a significant but unpredictable number of other deals (badly) generated before you would get a chance to see another one.

Is this correct? Sorry if it is a stupid question

[hrothgar]

 fred, on 2019-March-08, 11:10, said:

Richard - I know very little about such things in general or how we do it on BBO (I am a client-side programmer and we generate deals on the server), but I am hoping you can explain something (only because I am ignorant and curious)...

Suppose you learned that BBO generates hands in some non-ideal way such that, in principle at least, it would be possible for a skilled person to be able to start making predictions about future deals by looking at past deals.

My guess is that in reality this wouldn't work because for every (badly-generated) deal you see on BBO, there would be a significant but unpredictable number of other deals (badly) generated before you would get a chance to see another one.

Is this correct? Sorry if it is a stupid question

It depends very much on how badly the deals were being generated.

As a practical example, up until about two years ago, the hand generators that the ACBL was using for ALL of its major events were so badly broken that it was possible to look at a couple different boards that were being used in a ACBL tournament and successfully predict ALL of the other boards. (Nic Hammond and I were both able to come up with exploits. I wouldn't be surprised if other folks might have done so as well) This was only really possible because the system that the ACBL was using was particularly egregious. (The ACBL's system used whats known as a linear congruential generator which means that the PRNG always incremented by a fixed offset. Moreover, the period of the RNG was sufficiently small that you could fit everything into memory, so if you wee able to figure out the algorithm by which a given number translated into a "deal", all you needed to do was build an enormous rainbow table and ...

I started squawking about this publicly back in the middle of 2016 and Nic demonstrated a working exploit and low and behold, the ACBL now has a new hand generator...
(They're using Big Deal)

(Admittedly, none of this is specific to what's happening on BBO).

With BBO, I expect that the value of making such a change is being able to deal with the stream of questions from end users who are claiming that the RNG is flawed or rigged or that none of their finesses work or some such.

With this said and done, I do know that the hand generators used by a number of the online poker sites WERE compromised in the real world so these sorts of things are of practical concern when the stakes are high enough...

(Also, given the relatively small period of the ACBLhand generators, I vaguely wonder whether some of the cases where the same hands were played in multiple tournaments over the course of years were actually collisions in the seeding system)

[thepossum]

Hi Hrothgar

I dont know very much about hand generation and issue in tournaments, however I did have a few general queries/concerns about how random seeds work in different parts of a bridge site - hand generation, robot play, bidding etc. Is the handing of deals different in the BBO and ACBL tourneys and general club play. How random are the simulations used during bidding and play etc.

One thing I have noticed in tourneys is that there often seems to be a pattern of hands. This could of course just be observtion of patterns that arent there but I wondered if tournaments ever use themes or that the parameters used in hand generation could lead to those kinds of sequences in group of 8/12 hands

Obviously the site wouldnt want to give too much away since that information could be abused by people trying to game the site. But I'm very interested in all these issue. Would be interested in any thoughts you have from your experience and references

Generally my focus is on how "randomness" works/doesnt work in simulation models of play but the dealing is of interest to me too.

I'm also interested in aspects of "fairness" in computer bridge in relation to how random simulations should be during bidding and play to ensure reasonable fairness.

regards P

[hrothgar]

 thepossum, on 2019-March-08, 17:05, said:

Hi Hrothgar

I dont know very much about hand generation and issue in tournaments, however I did have a few general queries/concerns about how random seeds work in different parts of a bridge site - hand generation, robot play, bidding etc. Is the handing of deals different in the BBO and ACBL tourneys and general club play. How random are the simulations used during bidding and play etc.

One thing I have noticed in tourneys is that there often seems to be a pattern of hands. This could of course just be observtion of patterns that arent there but I wondered if tournaments ever use themes or that the parameters used in hand generation could lead to those kinds of sequences in group of 8/12 hands

Obviously the site wouldnt want to give too much away since that information could be abused by people trying to game the site. But I'm very interested in all these issue. Would be interested in any thoughts you have from your experience and references

Generally my focus is on how "randomness" works/doesnt work in simulation models of play but the dealing is of interest to me too.

regards P

My understanding is that F2F bridge games and bridge sites such as BBO current use different methods for generating hands.

Most "serious" F2F tournaments currently use a program called Big Deal that was written by Hans van Stavern which extended an earlier program that he developed called Dealer. (When I say most serious tournaments, I mean that I believe that the WBF, the EBU, and the ACBL are all currently using Big Deal as their hand generator)

From my perspective, Big Deal has three properties that recommend it for use in serious tournament play. Most importantly, the design is both simple and elegant. A couple decades ago Thomas Andrews created a scheme that efficiently maps each and every bridge deal onto a unique integer. In turn, this this allows one to create a dealing program that

1. Is capable of generating each and every deal
2. Will be cryptographically secure so long as your using a good PRNG

In addition, Hans added a few additional bells and whistles that allow the folks running the tournaments to assure the players that deals have NOT been manipulated (this is all documented at https://www.dropbox....-KLUVDLkKa?dl=0 There's also some good discussion at https://bridgewinner...t-organization/

Finally, the source code is open and available for inspection

As far as I know, BBO is not using this particular method to generate their hands.

BBO has stated in the past that they have run some statistical tests on their hand generation system and that it looks good. I have no reason to believe that they are wrong. (I've seen lots of claims over the years that the hand generators were bugged in some way, but nothing that ever stood up to serious scrutiny). As I mentioned earlier, from my perspective, the main reason that I think the BBO might want to consider moving over to Big Deal or some such is to have a good way of shutting down these complaints quickly and efficiently...

From my perspective, one of the most interesting discussions on the topic of the relationship between random number generation and card play is the following

https://bridgewinner...l-intelligence/

Veronique Ventos published a paper that I thought had some very counter intuitive results.
In turn, we were able to use this to identify a flaw in the implementation of WBridge5

[hrothgar]

 thepossum, on 2019-March-08, 17:05, said:

I'm also interested in aspects of "fairness" in computer bridge in relation to how random simulations should be during bidding and play to ensure reasonable fairness.

I don't know what you mean by "fairness"

[thepossum]

 hrothgar, on 2019-March-08, 17:47, said:

I don't know what you mean by "fairness"

Sorry. I should have clarified but its quite complex and my ideas may not be fully developed yet.

My query relates either to bidding or play when some form of simulation (eg DD) is used with current information to decide how to proceed

With human players we expect a certain amount of variance from the same player in how they would bid a hand and sequence, and play the hand. We also expect large variance between players - partners and opps. That is part of the game and nobody questions how fair the outcomes are.

If we are all playing the same hands with the same computer software there a various considerations and arguments about how much variance there is in bidding a particular sequence and playing a particular hand (leads etc)

One argument would say. To be fair every person playing S in an individual tourney should get the exact same bidding and play under identical bidding and play by them. This would require everyone to have the same random seed in any simulation at any stage of the process

An alternative argument is that this does not provide enough true variance in the game, is very artifical and does not reflect true bridge. So you could make a case for every simulation to use a different random seed. This could arguably be a more correct approach to simulation of bridge but could be argued against on fairness grounds.

It would take me a long time to fully explain what I am getting at. I can see both sides of the issue. If a bot is 100% predictable it may be regarded as fair but it is unrealistic and easy to game

It also relates to the broader issue of how valid DD approaches are. Whether the brdge bidding and play problem is correctly specified. Whether the model is being misfitted or overfitted. Whether distributions and variances are correct etc. How to correct simulated distributions to get more correct ones. etc I am not net well enough versed in the Bridge simulation field to have a grip on all the issues yet. I am coming at it from a different direction where these issues play out in other forms of modeling

EDIT Also it clearly relates to the nature of tournaments and the value of masterpoints in robot tourneys vs human tourneys, what the points actually mean, but clearly I am not experienced or any authority in that area of the Bridge World and I'm sure people in the ACBL, WBF etc take all those considerations into account. As I said on other threads I have no skin in the game, have no real interest in masterpoints (although its good to get the occasional point) but for many people in the game it is a valid and important area of concern no doubt that their points are not devalued. And despite having played for a long time I very much doubt I could just walk into any reasonable club and sit down with an average club player and score above 50% very often, whereas in robot tourneys I average around 55+% due to the different nature of the game (and having the bids explained as you go). My performance in a club would probably relate more to my partner's ability than mine (based on past experience)

regards P

[hrothgar]

Thanks for clarifying

 thepossum, on 2019-March-08, 19:08, said:

To be fair every person playing S in an individual tourney should get the exact same bidding and play under identical bidding and play by them. This would require everyone to have the same random seed in any simulation at any stage of the process

An alternative argument is that this does not provide enough true variance in the game, is very artifical and does not reflect true bridge. So you could make a case for every simulation to use a different random seed. This could arguably be a more correct approach to simulation of bridge but could be argued against on fairness grounds.

I believe that BBO currently uses the first of these two methods, however, what seems like meaningless differences in the bidding and play can lead to a different dramatically different results.

Consider the following: Suppose that you are holding AKQJT in a suit.
You are defending a hand and you start by running this suit against a 1NT contract
GIB is going to run a monte carlo sim each time that you play a card.

I suspect that the order in which you play these cards are played will can a significant impact on the sim that GIB is running EVEN if GIB is using the same seed.
(Using the same seed only guarantees the same results if the revealed state of the hand is identical as well)

[barmar]

 hrothgar, on 2019-March-08, 09:16, said:

So, a friend of mine just asked me some questions about BBO's random number generator, claiming that he had seen some highly unlikely events occur over the past few years...

My reaction was that lots of hands get played on BBO, as such highly unlikely events happen.
Anecdotal claims really aren't a good way to address this issue and, as such, the only thing that I would find interesting is some kind of source code audit.

I'm curious whether BBO would ever consider standardizing on a hand generator that is know to be secure like Hans Van Stavern's Big Deal simply to forestall these sorts of discussions.

It would be convenient to simple be able to say

1. BBO uses Big Deal
2. Our PRNG is a Mersenne Twister
...

We looked into using Big Deal a couple of years ago, but integrating it into the server software looked difficult, and we decided it wasn't a high enough priority.

We use different hand generation methods in different contexts. Newer tourney types -- daylong and challenges -- use the Dealer software, which was written by the same author as Big Deal, and I think has an early version of its algorithm. MBC hands and tournament types that predate these (pair and indy, robot duplicate) use our old, simple server code that just uses rand().

Although the deficiencies of rand() are well known, we don't think it significantly impacts us. We asked the Big Deal author to perform statistical analysis of our hands a while ago. He couldn't detect a problem. Anf the fact that the hands are being generated by the same supplier for all different uses adds noise to the system that should make it difficult for anyone to actually see the sequence of hands and use it for prediction.

Every now and then someone complains "My finesses always fail in robot tourneys". Whenever I've analyzed their hands, I can't find any such bias, it's just selective memory (I play lots of robot games, and I agree that it feels like finesses almost never win).

[barmar]

 hrothgar, on 2019-March-08, 21:59, said:

I believe that BBO currently uses the first of these two methods, however, what seems like meaningless differences in the bidding and play can lead to a different dramatically different results.

Consider the following: Suppose that you are holding AKQJT in a suit.
You are defending a hand and you start by running this suit against a 1NT contract
GIB is going to run a monte carlo sim each time that you play a card.

I suspect that the order in which you play these cards are played will can a significant impact on the sim that GIB is running EVEN if GIB is using the same seed.
(Using the same seed only guarantees the same results if the revealed state of the hand is identical as well)

That's basically true.

It might seem that the order you play equivalent cards shouldn't matter, but if this is happening in a hidden hand, the robot doesn't know that they're equivalent until after you've played them all, and by then it has already made different decisions.

[kvr_msk]

Perhaps the problem with random hands generator does exist. I play in a relaxed bridge club and when creating the table I always choose the option “random hands” without any additional parameters. But I often hear from my opponents that they do not want to play on EW, because EW always have weaker hands than NS. I wanted to prove them wrong, and analyzed the last 50 hands played by me. Unfortunately, the statistics are on their side: in 50 cases, the total amount of HCP on N is 485, on S - 490, on W - 424, and on E - 441. I understand that 50 hands is not a sufficiently representative sample, nevertheless it makes you think ...

[hrothgar]

If you are seriously interested in analyzing this, here's how to go about doing so.

• Decide what significance level you want for your test
  
• Decide how many trials you want to run / boards you want to play
  
• Specify a date / time in the future when you want to start your trial
  
• Once your trial starts, for each board played sum the number of HCPs that N/S holds. Record a 1 if N/S has more HCPs than E/W. Otherwise record a zero
  
• Do this for each and every board you play until your trial is complete
  
• You can then see whether your results are statistically significant

[kvr_msk]

Well, the only thing I want is to play really random hands, and I think it’s much easier for admins than for me to perform this analysis but, of course, I will also proceed with it if necessary.

[hrothgar]

 kvr_msk, on 2019-March-14, 06:15, said:

Well, the only thing I want is to play really random hands, and I think it’s much easier for admins than for me to perform this analysis but, of course, I will also proceed with it if necessary.

The admins HAVE performed this analysis...

The issue here is not whether or not the PRNG is glitched, but rather, trying to teach you how to properly examine whether the PRNG is glitched...

[barmar]

I just analyzed 10,000 MBC hands from the myhands DB

avg(south): 9.9105
avg(west): 9.9408
avg(north): 10.0347

[hrothgar]

 barmar, on 2019-March-15, 10:55, said:

I just analyzed 10,000 MBC hands from the myhands DB

avg(south): 9.9105
avg(west): 9.9408
avg(north): 10.0347

Hey there Barry

Would it be possible to run a slightly different analysis

For each hand, sum the HCP for (N+S) and (E+W)
How many times did N/S have more HCPs than E/W?

better yet, if you could post a CSV with 10,000 lines containing a 1 or a 0, each corresponding to one of the hands that you analyzed, I'd be happy to do a runs analysis

[kvr_msk]

 barmar, on 2019-March-15, 10:55, said:

I just analyzed 10,000 MBC hands from the myhands DB

avg(south): 9.9105
avg(west): 9.9408
avg(north): 10.0347

Thank you for the analysis.

Is there any flag in the DB record indicating that it was a randomly generated hand, not a hand from the Vugraph? Maybe the Vugraph hands are ok, and randomly generated ones aren't?

[barmar]

 kvr_msk, on 2019-March-15, 12:46, said:

Is there any flag in the DB record indicating that it was a randomly generated hand, not a hand from the Vugraph? Maybe the Vugraph hands are ok, and randomly generated ones aren't?

We don't save Vugraph hands in myhands.

[barmar]

 hrothgar, on 2019-March-15, 11:15, said:

Hey there Barry

Would it be possible to run a slightly different analysis

For each hand, sum the HCP for (N+S) and (E+W)
How many times did N/S have more HCPs than E/W?

With one batch of 10K hands, I got NS higher 4515 times, average NS HCP = 19.8788. With a different batch, NS higher = 4630, avg = 20.0443.

Quote

better yet, if you could post a CSV with 10,000 lines containing a 1 or a 0, each corresponding to one of the hands that you analyzed, I'd be happy to do a runs analysis

You understand that hands from the MBC are not all the hands that are being generated, right? The same deal generator is also used for tournaments. But it wouldn't be fair to include tournament hands, because many of them are best hand. Tourney information isn't on the same database server as all the archived hands, so filtering out the BH hands would be a PITA (I can't do it with just SQL queries, I'd need to write a script to correlate data between the two servers).

We also don't record the time that hands are generated, just the times that they're played, which I think is the time that the hand is completed. So ordering the hands by this timestamp won't accurately reflect the generation order.

So I don't think it's feasible to try to perform run analysis on our archived hands.

[hrothgar]

If your dataset include both the private tables and best hand tournaments (and you can't differentiate between the two) then any comparison between E/W and N/S is pretty much meaningless