well that deal generator

[Free]

Why would it be easy for quantum computers? AFAIK they can only search through lists and factor better than normal computers...this exhaust would actually be slower on one.

If I remember correctly, there are roughly 2^95 or 2^96 possible deals (vulnerability included - this is important in bridge but always gets ignored!). Our normal algorithm would take 2^96 invocations to generate all deals, while quantum computers require only 2^48 using Grover's algorithm. That's a around 256.000.000.000.000 times faster than a classic computer.

[BunnyGo]

If I remember correctly, there are roughly 2^95 or 2^96 possible deals (vulnerability included - this is important in bridge but always gets ignored!). Our normal algorithm would take 2^96 invocations to generate all deals, while quantum computers require only 2^48 using Grover's algorithm. That's a around 256.000.000.000.000 times faster than a classic computer.

 

Grover's algorithm is a searching algorithm. It'd help you find a specific deal in the list of all deals, but I don't understand how it would help generate deals faster.

[Free]

Grover's algorithm is a searching algorithm. It'd help you find a specific deal in the list of all deals, but I don't understand how it would help generate deals faster.

Hmm I must be confused or it's too early in the morning to discuss quantum computers. :)

[hrothgar]

wyman, I believe that comes out to the same thing.

PRNG people, quite simply, a PRNG that has dead zones is not a PRNG by the cryptographic definition. I suspect we may be discussing different things?

 

Now you have me confused...

 

As I under these things, the requirements for a cryptographically secure PRNG have nothing to do with coverage, but rather with being able to predict the bit stream.

 

Quoting wikipedia:

 

The requirements of an ordinary PRNG are also satisfied by a cryptographically secure PRNG, but the reverse is not true. CSPRNG requirements fall into two groups: first, that they pass statistical randomness tests; and secondly, that they hold up well under serious attack, even when part of their initial or running state becomes available to an attacker.

 

Every CSPRNG should satisfy the "next-bit test". The next-bit test is as follows: Given the first k bits of a random sequence, there is no polynomial-time algorithm that can predict the (k+1)th bit with probability of success better than 50%. Andrew Yao proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.

Every CSPRNG should withstand "state compromise extensions". In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation. Additionally, if there is an entropy input while running, it should be infeasible to use knowledge of the input's state to predict future conditions of the CSPRNG state.

Example: If the CSPRNG under consideration produces output by computing bits of π in sequence, starting from some unknown point in the binary expansion, it may well satisfy the next-bit test and thus be statistically random, as π appears to be a random sequence. (This would be guaranteed if π is a normal number, for example.) However, this algorithm is not cryptographically secure; an attacker who determines which bit of pi (i.e. the state of the algorithm) is currently in use will be able to calculate all preceding bits as well.

 

Most PRNGs are not suitable for use as CSPRNGs and will fail on both counts. First, while most PRNGs outputs appear random to assorted statistical tests, they do not resist determined reverse engineering. Specialized statistical tests may be found specially tuned to such a PRNG that shows the random numbers not to be truly random. Second, for most PRNGs, when their state has been revealed, all past random numbers can be retrodicted, allowing an attacker to read all past messages, as well as future ones.

 

CSPRNGs are designed explicitly to resist this type of cryptanalysis.

[wyman]

How is it easier? Permute 52 cards: 52! divide by internal order of each hand: /4*13!. Rotations and dealer positions cancel each other out, so just add vulnerability and you're set.

Your way: C(13, 52) = 52!/(13! * 39!) * C(13, 39) = 39!/(13! * 26!) * C(13, 26) = 26! / (13! * 13!) and then you just notice some things cancel each other out and end with the same expression.

you got yours wrong, proving my point

[helene_t]

FWIW' date=' most of the standard random number generators in common use have dead zones.[/quote']

Yes but a "dead zone" in the random seed domain is not the same as a dead bridge deal.

 

If you use a 32-bit (somewhat dated, I know) seed then you have less entropy than required to deal all bridge deals so there will be dead deals even if there are no dead seeds.

 

If you use a 128-bit seed then there might be no dead deals even if there are dead seeds.

 

Anyone volunteers to compute the probability of there being no dead deals if you have an n-bit seed without dead zones and the seed->deal mapping is random?

[helene_t]

zip

[hrothgar]

 

Anyone volunteers to compute the probability of there being no dead deals if you have an n-bit seed without dead zones and the seed->deal mapping is random?

 

 

Better yet, anyone want to give Hans van Stavern a shout?

 

He's in a good position to provide practical guidance...

[Antrax]

As I under these things, the requirements for a cryptographically secure PRNG have nothing to do with coverage, but rather with being able to predict the bit stream.

You understand correctly. So let p be some point that's in a dead zone for your PRNG. I'll build the circuit that returns "1" if p is in the stream and 0 otherwise. The circuit distinguishes between the PRNG and a random stream with non-negligible probability. QED.

 

wyman, elaborate? I didn't add 1/13! to yours because the point was already made. What did I get wrong?

[Free]

Anyone volunteers to compute the probability of there being no dead deals if you have an n-bit seed without dead zones and the seed->deal mapping is random?

No offense, but isn't that irrelevant? The "impossible bridge book" explains a 1 to 1 mapping (Richard Pavlicek also explains a method on his website). All you need to do is being able to generate every possible integer from 1 to 53,644,737,765,488,792,839,237,440,000. This means that a 96 bits RNG (98 if you want to include vulnerability) without dead zones will be able to generate every possible bridge deal.

 

What I don't understand is why people don't use a TRNG to generate only 96 or 98 bits. It doesn't take much time and it doesn't have any flaws like a PRNG. No whining about dead deals, predictability,... Perhaps because the PRNG flaws are usually too theoretical that we won't even notice the difference?

[wyman]

wyman, elaborate? I didn't add 1/13! to yours because the point was already made. What did I get wrong?

 

You divided out by 4*13!, when you meant (13!)^4.

 

I am half-kidding. Certainly our ways are equivalent: your 52! "shuffles" the cards, hence it determines a deal, and then we need only divide out by shuffles that yield equivalent deals. Different explanations work better for different people, but when I ask students "Are you sure you accounted (appropriately) for all the symmetries?" they usually are not 100% sure, whereas counting as I suggested clearly does the trick.

 

Both ways are fine.

[hrothgar]

 

What I don't understand is why people don't use a TRNG to generate only 96 or 98 bits. It doesn't take much time and it doesn't have any flaws like a PRNG. No whining about dead deals, predictability,... Perhaps because the PRNG flaws are usually too theoretical that we won't even notice the difference?

 

 

Few quick comments:

 

First: A few years back, some of the bridge organizations were using VERY badly flawed hand generators. "Cracking" deals in real time was a practical possibility. As I understand matters things have gotten a lot better on this front.

 

Second: I'm not sure whether a true random number generator would add much security. (I suspect that physical issues are much more practical a concern than the cryptographic properties of the RNGS)

 

Third With these caveats in place, I think that one COULD develop a basic highly secure hand dealer using the following principles.

 

1. Start with something like Thomas Andrews deal library which maps all possible bridge deals onto an integer

2. Go to random.org and grab a byte string: http://www.random.org/bytes/

3. Use this to permute the order of the hands and then grab however many you need

[Free]

Richard, a few years ago I already created a little java program using a TRNG for generating an integer and the mapping method to generate the deals and place the cards in the right hands. It's not that difficult. The biggest problem imo with this approach is proving that the TRNG is truely random.

 

The way I generate my bits is as follows:

- define a fixed period of time (can also be flexible, but nvm)

- keep track of the number of interrupts generated during that period of time

- if even => 0, if odd => 1 (basically: interrupts MOD 2)

 

There are tweaks obviously: you could take a longer period and use MOD 4, MOD 8, or whatever to generate more than 1 bit per period. But it's still the same concept.

 

Using this method, it takes much more time than using a decent 96+ bits PRNG. But for online bridge for example, they can just generate the deals in advance and put them in a queue.

[barmar]

The September 2011 ACBL Bulletin has a letter to the editor asking about the randomess of their deal generator. The answer describes their algorithm.

 

It's available online to ACBL members at acbl.org, but they use a flash application for the reader, which doesn't allow copying.

[Pertinax]

The September 2011 ACBL Bulletin has a letter to the editor asking about the randomess of their deal generator. The answer describes their algorithm.

 

 

Has anyone checked the algorithm?

It is not as easy as you think to get right. We were using a dealer written by an applied maths lecturer in our club a decade ago and there were complaints. We checked it and the algorithm was not truly random.

 

I have noticed playing Rubber and Total Point on BBO that one side seems to win a lot of the time. So I had a look at 50 hands from yesterday and they averaged 20.80 HCP, so definitely was a streak I spotted and not just my bad play. Now I will have to write some code to analyse all my old hand record files and look at a decent sample.

 

And until I do guess which way I am sitting.

[Free]

The problem with taking averages is that 50 hands is way too few to draw any conclusions. Pretty much every tournament you will ever play, one side will have more HCP than the other, even with hand dealt cards or a true randomizer. It's like flipping a coin 50 times: the chance that you flip exactly 25 times heads is rather small.

20.80HCP on average is not that big a difference.

 

What made me stop playing moneybridge is the fact that we keep changing sides. Although it has no influence on the long run average, I got the impression there were huge streaks of HCP either for me or for my opponent. In fact, I even calculated it once, and not switching sides would've resulted in an average closer to 20HCP. And this happened every single time. NS gets 25HCP 2 deals in a row while we're sitting EW, you expect EW to get some HCP soon and what happens: you were right but you also switched sides, so another game for your opponent. And vulnerabilities are also cruel: you have streaks where you're Vul 75% of the time (great, but then your opponent leaves) but you also have streaks were your opponent is Vul 75% of the time while you stay NV 75% of the time. One should expect to be Vul 50% of the time and NV 50% of the time and the same for opponent, and it's not even difficult to force this. But having NV-NV, NV-V, V-NV and switched sides, V-V is simply unfair to one of the players. I don't know if this "switching sides" has be changed, but there were no ears when I previously mentioned this on the forums so I guess not. :)

[BunnyGo]

I don't know why this is actually interesting, but when somebody starts posting incorrect mathematics I feel a strong urge to correct them before anybody gets harmed.

 

I too have this impulse.

 

The problem with taking averages is that 50 hands is way too few to draw any conclusions. Pretty much every tournament you will ever play, one side will have more HCP than the other, even with hand dealt cards or a true randomizer. It's like flipping a coin 50 times: the chance that you flip exactly 25 times heads is rather small.

20.80HCP on average is not that big a difference.

True. There are tables that you can look at (or calculate yourself) that will tell you how much bigger than 20 HCP is "significant" for a given number of hands.

 

What made me stop playing moneybridge is the fact that we keep changing sides. Although it has no influence on the long run average, I got the impression there were huge streaks of HCP either for me or for my opponent.

This. Even with long run averages being "equal", one can expect that streaks of arbitrary long length will occur.

 

In fact, I even calculated it once, and not switching sides would've resulted in an average closer to 20HCP. And this happened every single time. NS gets 25HCP 2 deals in a row while we're sitting EW, you expect EW to get some HCP soon and what happens: you were right but you also switched sides, so another game for your opponent. And vulnerabilities are also cruel: you have streaks where you're Vul 75% of the time (great, but then your opponent leaves) but you also have streaks were your opponent is Vul 75% of the time while you stay NV 75% of the time. One should expect to be Vul 50% of the time and NV 50% of the time and the same for opponent, and it's not even difficult to force this. But having NV-NV, NV-V, V-NV and switched sides, V-V is simply unfair to one of the players. I don't know if this "switching sides" has be changed, but there were no ears when I previously mentioned this on the forums so I guess not. :)

Not this. In fact, you too seem to have drawn conclusions from too few observations. When you switch sides, you are just as likely to have joined NS and get lots of points as you are to have left EW when they start to get points.

[helene_t]

last week, I had had (my guess) an average of 12 HCPs per hand in the club mitchell. Apparently the cards were in favor of East. Last two rounds were arrow-switched so if I had been superstitious I might have expected bad cards now that I was North. I got 21 points on the first of the remaining boards and also opening strength on two others.

 

Maybe our dealer software is skewed but I would need much, much, much stronger evidence to take such a suspicion seriously. I would expect standard random number generators to have been tested on millions if not billions of samples before being released. So I wouldn't second-guess them just because I found a p-value of say 0.001 when testing some random null hypothesis on bridge hands. Much less if it was just a vague feeling not based on a formal statistical test.

 

If there is a real skew in in bridge hands then I would guess that it would be due to a data management flaw or (less likely) a flaw in the bridge part of the dealer software. That it could be related to a flaw in the underlying random number generator is not plausible.

[Free]

Not this. In fact, you too seem to have drawn conclusions from too few observations. When you switch sides, you are just as likely to have joined NS and get lots of points as you are to have left EW when they start to get points.

I admit that my decision is based on a few observations. Frankly, it's my money, so I don't care... ;)

 

Random direction and random deals shouldn't make much difference. However, you can't deny the fact that it's simply ridiculous to randomize something as simple as the vulnerability and claim that it's ok because in the long run the variance will cancel out. There's no reason to add vulnerability and direction to the luck factors.

 

Perhaps an interesting problem: does anyone know how many deals you need to play before you can speak of "the long run"? Does it change if your direction is randomized as well? And what about changing vulnerability?

[hrothgar]

Perhaps an interesting problem: does anyone know how many deals you need to play before you can speak of "the long run"? Does it change if your direction is randomized as well? And what about changing vulnerability?

 

This does strike me as vaguely interesting

If no one beats me to it, I'll throw together a quick sim later in the week.

 

FWIW, I'd bet dollars to donuts that introducing directions and vulnerabilities will increase the number of samples that one needs, however, I'm not sure how quickly things will converge.

[helene_t]

My guess would be that the vulnerable player has a slight edge so to make the game fair, the vulnerability should be equal throughout.

 

Then again, you can't make the dealer neutral and presumably the dealer has an edge (however, someone once posted some weird statistics showing that when Jack plays against itself, the dealer is actually disadvantaged). Maybe it should always be w/r for dealer to neutralize dealer's advantage?

 

Not sure if making the vulnerability deterministic (as in real bridge) is better than random. Someone who perceives (say) red colours to be best could game the system by leaving prior to a w/r board.

 

Edit: it was Cascade who did the Jack study. http://www.bridgebase.com/forums/topic/5946-are-there-any-benefit-of-sitting-in-1st3rd-seat/