[wyman]

hrothgar, on 2011-September-06, 12:55, said:

FWIW, most of the standard random number generators in common use have dead zones.

There are certain outputs that do not get generated.

This is very, very true. I don't know anything about BBO's RNG, though.

[BunnyGo]

wyman, on 2011-September-06, 12:53, said:

Why not just choose 13 for N, choose 13 for S, and choose 13 for E?

52C13 * 39C13 * 26C13

You have to then remove the rotational symmetries, but that's just a /4 at the end...Unless you count the same hand but rotated as different.

There are also dealer and vulnerability issues, but I didn't consider those.

[Antrax]

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?

[wyman]

Antrax, on 2011-September-06, 16:46, said:

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?

re: comment 1. Yeah, but my way is easier to compute

re 2: I think this is semantics. You can use, say, a 32-bit PRNG to generate "pseudorandom bridge deals" but certainly you won't see all of the deals. That's all whoever meant by "dead zones" as I read it.

[Antrax]

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.

[Free]

BunnyGo, on 2011-September-06, 09:58, said:

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]

Free, on 2011-September-07, 02:15, said:

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]

BunnyGo, on 2011-September-07, 02:18, said:

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]

Antrax, on 2011-September-06, 16:46, said:

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:

Quote

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]

Antrax, on 2011-September-07, 00:28, said:

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]

Quote

FWIW, most of the standard random number generators in common use have dead zones.

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]

helene_t, on 2011-September-07, 05:42, said:

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]

Quote

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]

helene_t, on 2011-September-07, 05:42, said:

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]

Antrax, on 2011-September-07, 07:03, said:

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]

Free, on 2011-September-07, 07:09, said:

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]

barmar, on 2011-September-07, 14:34, said:

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.