International Association for Cryptologic Research

Bridge Tournament Deals

Bridge tournaments have been using computer-generated deals for many years. The deals are printed on sheets of paper, carried to the tournament site in sealed envelopes, and read by humans who hand-sort the physical cards. Unfortunately, there is a growing dissatisfaction with the process, partly because (a) the hand-generation algorithm is secret, and (b) sets of deals have been observed to recur.

A search for better methods is being coordinated by The Bridge World Magazine. I think the problem may interest some of IACR's members, so I'd like to act as a "synapse" between the two communities. Jeff Rubens has given us permission to reprint his recent editorial, which is attached below. It includes an email address (dealing@bridgeworld.com) for getting included in their discussions.

Matt Franklin
franklin@parc.xerox.com


Reprinted from The Bridge World Magazine, Editorial, May 1999:

Humans: Unite!

Computers are messing up our tournaments, and that must stop.

In a previous Editorial, we complained about the laxity that more than once allowed the reuse of sets of machine-produced deals to wreak havoc on an American event. This affliction is worldwide: Repeat sessions turned up in a major Australian championship and in the 1997 World Junior Teams. And the reported sightings are only the ones we know about. Obviously, administrators are not coping with this problem and need help. Let's see that they get it.

We propose, will help to organize, and will act as a clearinghouse for a worldwide effort to produce a standard deal-generating procedure. If implemented with care, checked thoroughly, and adopted everywhere, such a method would have many significant advantages over the current approach, including:

(1) Avoiding the unrecoverable disaster of players' recognizing the reappearance of an old set of deals.

(2) Facilitating the distribution of information. Organizers of multi-site events using duplicated boards could distribute the information needed to create the deals cheaply and quickly, reducing expenses and minimizing some security problems.

(3) Producing instantaneity. Enthusiasts everywhere could play the deals from a major event, such as a world or national championship, soon after (or even, with appropriate security at the tournament site, simultaneously with) the participants, then compare their results with the stars'. This capability could open a new avenue for increasing the popularity of bridge.

(4) Keystroking reduction. Less typing would be needed for the publication of deals on the Internet and in books that record the proceedings of major events.

(5) Eliminating accusations of rigging. Sponsors of events featuring duplicated boards at multiple sites are sometimes accused of editing the deal sets, perhaps of "giving ample opportunities to both North-South and East-West." Such manipulating, which changes the nature of the game, is the organizational equivalent of prearranged secret signals between partners; both behaviors should engender severe, permanent penalties. It is extremely difficult either to sustain or to defend such a charge. A good way to handle the situation is to make fixing as close to impossible as we can, eliminating both the act and the charges.

To stimulate thought about and action on the problem, we've put some preliminary discussion and a sample outline into a sidebar (see "A Three-Minute Algorithm"). If you want to participate in the creation, evaluation and testing of a standard dealing algorithm and programs that implement it, send an e-mail to dealing@bridgeworld.com that includes in its body your name, postal address, and e-mail address. After allowing time for signups, we will send the list of e-mail addresses to all participants, anticipate discussion and sharing of ideas among interested parties, and keep track of any results that arrive later at the "dealing" e-mail address.


"A Three-Minute Algorithm"

The first task in developing or comparing algorithms is to establish the relative importance of potential objectives, so as to be able to judge tradeoffs among different possibilities. This is our list:

1. Highest importance: Capability of convincing the public both that the dealing is mathematically correct and that everything is on the up-and-up.

2. High importance: Simple involvement in each job of a very long "seed" number that avoids reruns.

3. Fairly high importance: Ease of understanding and use, hence accessibility to "home" programmers with only moderate effort.

4. Medium importance: High difficulty of cryptanalysis from observed partial output.

5. Low importance: Machine efficiency. (Any reasonable program is going to run much faster than needed and take up less space than available, even on somewhat outdated personal computers.)

Having done that, the next time we were stuck waiting for an egg-timer to trigger our further activities, we considered what algorithm might meet the criteria. Here is what we produced before the egg was ready to eat:

(a) Establish a bank of a moderate number (six, say) of easy-to-program pseudorandom number generators (linear congruential, perhaps).

(b) When ready to generate a set of deals, create a long seed number whose inputs are the date, the standard time at a fixed location (Greenwich, England?), the international calling code for the home country of creation, and many digits from each of at least three people (of whom at least one is local and at least one is not, the latter presumably communicating by telephone or by e-mail--a distant contributor may send digits unencrypted and need verify only that the set was created immediately after his portion was sent, making prearrangement impossible without his participation).

(c) Use subsets of the seed's digits to initialize the number generators. Whenever a pseudorandom value is needed, use output from the first generator to create an integer that points at one of the others, then use the indicated generator to create a value in the interval from zero to less than one.

(d) Use a number derived from (c) to determine how many of the deals first produced (or how many pseudorandom numbers) to discard. Then, for each deal, use 39 outputs from (c) to distribute one of the remaining cards to the appropriate players, by thinking of the unit interval first as broken into fifty-seconds, then into fifty-firsts, etc.

We anticipate that a collective effort based on longer periods of thought (perhaps by programmers who prefer their eggs hard-boiled), whether using our general approach or not, will produce a satisfactory universal standard.


[ IACR home page | IACR Newsletter page and archive | This issue ] © IACR