The Chamberlain Bridge Problem
I have used this problem as a testing ground for a variety
of problem solving techniques. In all cases I have labeled
the players A-X to simplify representation.
The paper and pencil method
Initially, my mother tried to solve the problem with paper,
pencil, and a big eraser. I don't recall the exact score
but it was clear that there was more to this problem than
meets the eye. The natural method of doing this is to
make a table of 24 rows and 24 columns. Label them any
way you like but they correspond to the 24 players.
Using only the lower-left half of the table, choose four
players to play at a table in the first game. Find the
six boxes that are intersections of the four players
and write a 1 in each box. Then find the next four
players for the next table and do the same, and so
on until you have done all 24 players. Then start
again but write a 2 in each box. Anytime you write
two numbers in the same box is a "bad seating" and counts
one point against you.
Attempts to refine the table quickly become very
frustrating and complicated. My experience is
that picking the groups in any orderly fashion
seems to be counter-productive and that ANY random
order would be more likely to be successful.
Unfortunately, no records from the paper and pecil
method can be found now. I seem to recall that
the best score arrived at by this method was around
48, but there is disagreement amongst my family on that.
Random Selection
I didn't spend any time on a program that merely chooses
random arrangements and scores them but
my father tried it for a while and decided that
it would never work.
Brute force
I tried implementing an exhaustive search for the best
solution. I even tried to eliminate obvious wastes of
time that show up as a result of symettries in the
problem. I noticed that this was moving very slowly
and tried to estimate the size of the problem.
I wrote a script for bc -- the Unix arbitrary
precision calculator to
calculate the size of the solution space. The
script says that the number of possible ways to seat
24 people at 6 tables is given by this expression where
each table is represented by a Combination of N things
taken M at a time:
24C4 *
20C4 *
16C4 *
12C4 *
8C4 *
4C4
which evaluates to:
3246670537110000
And to pick any set of 8 of these would be
306185934084510823129302222161577624553431326207206900843538687047438038575560093872988377112293067944802385719050986250
Obviously, I wasn't going to be able to try each of
these during this century.
The look-ahead strategy
I eventually arrived at the concept of picking each table's
seating arrangement by looking at what problem's my choice
would cause while selecting the next table's seating. This
look-ahead strategy resembled that used by game-playing
strategy programs. Despite complications unique to our
challenge I eventually had
a program that could look-ahead
about 6 tables (a whole bridge-game) ahead and still
be quick enough to make some progress. After weeks of CPU
time, with frequent restarts I arrived at a solution which
scored 33 bad seatings.
This seating arrangement was used for quite a while by my
mother's bridge club.
Simulated Annealing
Later, I tried something called
Simulated Annealing.
This algorithm is modeled after the
shaping and cooling, shaping and cooling used by a blacksmith.
A small change and a large change are defined. A mixture of
the two are used to try to locate an optimum in the solution
space. As the program progresses, less and less of the large
changes are used. This is supposed to zero in on a global
optimum but
my attempt at simulated annealing
failed miserably. I'm sure the definition
of a small change and a large change are key to the success of
this algorithm so perhaps my choices were unsuitable.
Genetic Algorithm
I stumbled across another method of finding an optimal
solution in a huge solution space. A
Genetic Algorithm
is used to solve the typical example problem of the
Traveling Salesman
(Find the shortest path for a salesman to visit each
of 100 cities). I realized that I could use the
Genetic Algorithm for my bridge problem.
I was able to generate a solution which scored
31 bad seatings
in less than a day!
Spiked Genetic Algorithm
[At this time I modified my scoring algorithm to score 5
points for the bad seating, 10 for bad partnering, and 2
for bad tabling. Although I still refer to my results
simply by the number of bad seatings.]
I devised an
Improved Genetic Algorithm which spikes the
genetic soup with already successful creatures.
After repeatedly tweaking and running I came up with a setup
that has 28 bad seatings,
no bad partnerings, and just a few bad tablings!
A huge improvement over the original setup.
I Challenge you
Now, any of you math or programming wizards want to
see if you can improve on this solution?
Paul Chamberlain
tif@tifster.com