Article in International Computer Games Association Journal, Vol. 23, No. 4, December 2000, pp. 237-241
REPORT ON THE 4TH ACBL WORLD COMPUTER BRIDGE CHAMPIONSHIP
Maastricht, The Netherlands
September 1-5, 2000
By Alvin Levy
INTRODUCTION
The 2000 Microsoft Network Gaming Zone World Computer Bridge Championship, the 4th annual world computer-bridge championship conducted by the American Contract Bridge League, was held in Maastricht, the Netherlands, September 1-5, 2000, in conjunction with the World Bridge Federation's World Bridge Team Olympiad.
In 1996 the ACBL established an annual World Computer Bridge Championship and had its first two tournaments at their 1997 and 1998 summer national championships. In 1999 and 2000 the World Bridge Federation encouraged the ACBL to hold the event in conjunction with the world bridge championships. The 1999 event took place in January 2000 as part of the Bermuda Bowl, and the 2000 event took place in conjunction with the World Bridge Team Olympiad.
As a member of the ACBL Board of Directors, I had the opportunity to establish this event. Of course, I then had the obligation, albeit self-imposed, of running the event, which I have since its inception. It has turned out to be a most rewarding and pleasurable experience. I originally had in mind a future great PR happening, the equivalent of an IBM's Deep Blue defeating a team of Garry Kasparov. That kind of defeat isn't going to happen soon. Predictions are that it is at least five to ten years away, as computer-bridge programming is in its infancy. At last year's Orbis World Computer Bridge Championship in Bermuda, David Levy, then president of the ICCA, favorably compared the current development of computer bridge to that of the early development of computer chess, noting the available research and funding that was available to the early chess programmers1. He also expressed his opinion that running these computer bridge championships is a major contributing factor to increasing the rate of improvement of bridge programs.
This year's contestants are all in the software business and most of the programs that competed can be obtained commercially. Even though the contestants are business competitors they interacted with each other in a very friendly manner and with the highest level of sportsmanship and cooperation. During the competition several brainstorming sessions took place that focused on future conditions of contest as well as exchanging programming ideas. This kind of cooperation can only lead to the rapid improvement of bridge playing software.
THE CONTESTANTS
Nine computer programs from around the world came to Maastricht to vie for the title of World Computer Bridge Champion. The competitors were:
Rodney Ludwig and David Walker's Meadowlark Bridge (rrnet.com/meadowlark), USA
Ian Trackman and Mike Whittaker's Blue Chip Bridge (www.bluechipbridge.co.uk), Great Britain;
Stephen Smith and George Yanakiev's Bridge Baron (www.bridgebaron.com), USA,
Doug Bennion's Bridge Buff (www.bridgebuff.com), Canada;
Hans Kuijf's Jack, Netherlands; Rodney Ludwig's Meadowlark Bridge (rrnet.com/meadowlark), USA;
Tomio and Yumiko Uchida's Micro Bridge (www.threeweb.ad.jp/~mcbridge), Japan;
Andrew Bracher's Oxford Bridge (www.thinkgam.demon.co.uk), United Kingdom;
Hans Leber's Q-Plus Bridge (www.q-plus.com), Germany; and
Yves Costel's WBridge5 (ourworld.compuserve.com/homepages/yvescostel), France.
Matt Ginsberg's GIB (www.gibware.com), USA, which won the 1999 title during the Orbis World Computer Bridge Championships in Bermuda, did not compete in Maastricht.
CONDITIONS OF CONTEST
The competition started with a complete 12-board round robin, with the top four finishers going on to a single elimination KO format. The semifinal KOs were 50-board matches including the 12 boards played in the round robin. The final was a 62-board KO match including the 12 boards from the round robin.
600 MHz Intel based PCs were provided, and some participants used their own Laptops or PCs with a top speed of 800 MHz, as allowed by the conditions of contest. Playing time for a deal was established at eight minutes, approximately the same as in human competition, so each side, at each table, was limited to four minutes of thinking time per deal.
There were allowable bidding systems and conventions. Convention Cards were due one month before the competition so that the contestants could program defenses against any unusual bidding conventions.
As in human play there are 'alertable' situations. In human situations the meaning of the bid is explained in detail, usually by the partner of the one making the bid. In computer-bridge competition these alertable bids are broken down into two parts, those bids that are standard conventions, such as transfers and weak NT, and those that are highly unusual, such as minor suit Blackwood, or unusual versus unusual. Before each match the contestants input their opponent's Convention Card into their computer system. The standard alertable bids and conventions are assumed to be known to the opponent computer and therefore not explained while the highly unusual bids are still explained. The meaning of these bids are manually input into their opponent's computer system at the time they are made. This manual input consisted of possible suit distributions, high card points, and specific honor holdings.
As in all past championships all the hands of a given deal were input and visible on each computer. This is a controversial issue because it raises the question of a player seeing the hidden hands. To check that the programs are not peeking, tests are made from time to time. For example, a hand might be selected where a contestant bid and made a difficult game or slam. The deal would then be replayed with only one partner (holding the same cards as before) playing in computer mode, and the other partner (holding a weaker hand than before) and with the opponents playing in human mode, and forced to bid as they did in the original deal. If the computer mode partner then bids the hand the same way as it did originally, it passes the test. Similarly, a hand might be chosen where the declarer's or defender's line of play was successful, some cards changed, and the hand replayed. Certain tests are statistical, such as declarer finding a missing Q if the program is simulation based. In this case, replaying the hand a number of times will produce a finding.
All the programs passed all the tests given. Also, as in human play, if a good player consistently makes bad (anti-percentage) bids or plays that are successful, they would be suspect. Here, with all the deals carefully scrutinized by the operators and their colleagues, there were no suspicions.
A complete write-up on the Conditions of Contest can be found on the Internet at http://members.aol.com/allevy/maastricht
As an experiment, this was the first major event at which computer-bridge programs played against each other completely automatically and without human intervention. The protocol system was designed by Ian Trackman, the creator of Blue Chip Bridge. There were five networked computers. One copy of the North/South program played on the North computer, the other copy on the South computer, and likewise for the East/West team. The fifth computer ran as the Table Manager, which dealt the cards to the four computer players, received a bid (or a card to play) from each player in turn and transmitted the information to the other players. Electronic traffic around the network was monitored. One of the round robin matches, Blue Chip Bridge versus WBridge5 was played this way. The playing time was approximately 1/4 that of normal playing time, or 30 seconds per computer per deal.
Having one hand per computer will, in all likelihood, be required for the next competition. The use of this new table manager system is under discussion. One advantage is that it will allow for longer matches. One negative is that it requires additional programming and might stop an unprepared entrant from competing.
METHODS OF BIDDING AND PLAY
Without comparing the difficulties of programming chess to programming bridge, it is fair to say that they are very different. Chess is a game of perfect information and therefore a deterministic game. Theoretically a chess program can be developed that will always win. Bridge is a game of imperfect information and therefore a game of probability. Theoretically, a bridge program can be developed, using game theory methods, to compete perfectly. Of course, throw in bridge strategy and tactics, and we leave behind the theoretical notion of developing a perfect player.
One method of bidding is to use an algorithm of coded rules. For example: if opener has 5 spades and 11 high card points (hcp) then it opens 1 spade; if responder has 5 clubs, 12 hcp and less than three spades, then responder bids 2 clubs when partner opens 1 spade. Other methods use an extensive database of bidding sequences, or pattern matching. Combinations of the above methods are also possible.
Another method is to use a Monte Carlo simulation method in conjunction with one of the above methods. The simulation first generates a Monte Carlo sample of hidden hands, consistent with previous bidding. It then chooses the bid that appears to work best on average. When a critical point in the bidding occurs, based on some set of rules, a simulation method can take over. This hybrid method may offer the best chance at accurate bidding. A simulation alone offers little hope of an accurate bidding method as the information transmitted in the early rounds lays the foundation for a successful auction. In human bidding contests where only a critical decision is to be made, a simulation works best, while in bidding contests where the partners bid an entire deal, good bidding methods along with good decision making at critical points works best. If this method is employed in computer-bridge, a determination must be made as to when bidding rules are best and when a simulation is best.
In the play there are also rule-based and simulation-based methods. In the simulation method, a Monte Carlo simulation randomly generates a number of sets of unknown hands consist with the bidding and play. For each deal generated the computer can use a double dummy solver using artificial intelligence techniques to achieve a deep search.
THE COMPETITION
The round robin matches were scored by IMPS and then converted to a 30-point victory scale, with 15 VPs added awarded for a bye. The standings at the end of the round robin were (VPs and IMP scores):
|
Meadowlark Bridge |
Jack |
WBridge5 |
Q-Plus Bridge |
Bridge Baron |
BlueChip Bridge |
Oxford Bridge |
Bridge Buff |
Micro Bridge |
Total | |
|
Meadowlark Bridge |
15 |
7 12-43 |
25 77-24 |
19 38-25 |
14 17-22 |
17 30-21 |
19 32-17 |
25 63-20 |
9 28-49 |
150 |
|
Jack |
23 43-12 |
15 |
10 12-30 |
11 34-47 |
25 67-6 |
15 25-24 |
10 13-31 |
24 52-18 |
16 20-14 |
149 |
|
WBridge5 |
2 24-77 |
20 30-21 |
15 |
14 41-45 |
17 41-32 |
23 39-10 |
16 26-22 |
19 37-21 |
14 26-28 |
140 |
|
Q-Plus Bridge |
11 25-38 |
19 47-34 |
16 45-41 |
15 |
16 24-18 |
14 22-27 |
21 43-20 |
11 28-41 |
18 36-24 |
139 |
|
Bridge Baron |
16 22-17 |
1 6-67 |
13 32-41 |
14 18-24 |
15 |
14 40-44 |
23 41-11 |
11 22-37 |
25 57-11 |
134 |
|
Blue Chip Bridge |
13 21-30 |
15 24-25 |
7 10-39 |
16 27-22 |
16 44-40 |
15 |
14 28-32 |
14 28-33 |
22 31-5 |
132 |
|
Oxford Bridge |
11 17-32 |
29 31-13 |
14 22-26 |
9 20-43 |
7 11-41 |
16 32-28 |
15 |
11 27-40 |
18 30-18 |
121 |
|
Bridge Buff |
4 20-63 |
6 18-52 |
11 21-37 |
19 41-28 |
19 37-22 |
16 33-28 |
19 40-27 |
15 |
12 5-15 |
121 |
|
Micro Bridge |
21 49-28 |
14 14-20 |
16 28-26 |
12 24-36 |
3 11-57 |
8 5-31 |
12 18-30 |
18 15-5 |
15 |
119 |
The following two hands from the round robin demonstrated some interesting aspects of computer bridge play.
Dealer: South
Vul: none
AQJ82
K87
T9
KT3
T976 53
T632 Q94
J AQ 87542
AJ76 4
K4
AJ5
K63
Q9852
North East South West
Jack Bridge Jack Bridge
Baron
Baron
- - 1C Pass
1S 3D Pass Pass
4S All Pass
Bridge Baron East led the DA and gave its favorite partner a ruff. West didn’t find the killing return of the CA and club ruff, but rather returned a safe looking trump to dummy's K. Declarer Jack led a club to the 10, playing West to have longer clubs than East. Jack then pulled trumps and made the strange play of a club to the Q. Clearly the simple play, the one that any human player would take, is the CK. If East has the CA (unlikely) the clubs are dividing, and if West has the CA, there is no safe return.
Jack decides on its plays by randomly creating a number of EW hands consistent with the bidding and play. It then determines the expected result of each card it can play and plays the card that works best on average. With the assumption that West held the CJ, Jack's simulation determined that both plays would work in all cases and it happened to choose the more complex looking play. West won the A and returned a club. Declarer played a trump leaving this following position:
A
K87
-
-
- -
T63 Q94
- Q
J -
-
AJ
6
9
Jack now executed a double squeeze with the lead of the SA. East was squeezed and discarded a heart, South a diamond, and now West was squeezed and discarded a heart. North now won three heart tricks and scored its contract.
Dealer: South
Vul: none
K J 4 2
Q 5
A K 8 2
A Q 9
T 7 5 Q 9 3
T 6 4 K 9 8 7
J 5 4 9 7 3
8 7 6 4 J T 3
A 8 6
A J 3 2
Q T 6
K 5 2
West North East South
Bridge Blue Chip Bridge Blue Chip
Baron
Bridge Baron Bridge
Q-Plus Bridge Q-Plus Bridge
Bridge
Buff Bridge Buff
- - - 1 NT*
Pass 2 C Pass 2 H
Pass 6 NT All Pass
*12-14 hcp
At two tables the bidding and play were identical. Blue Chip Bridge and Bridge Buff played in a reasonable 6NT contract against Bridge Baron and Q-Plus Bridge, respectively. At the other tables Bridge Baron played in 3NT and Q-plus played in 5NT. The D4 was led and declarer led a heart toward the Q. East won the K and returned a diamond. Declarer than ran diamonds and clubs, forcing East to make a critical discard. At both tables East discarded a heart and 12 tricks were scored. A heart discard always wins when partner has the heart J and always losses when declarer has the heart J. A spade discard wins when declarer takes the spade finesse and losses when declarer plays for the drop of the spade Q. Its 50% that declarer has the heart J (South and West each have two unknown hearts and South has already shown 13 hcp). If East gives equal weight to declarer playing for the drop of the spade Q or finessing for it, then a heart or spade discard is equally correct. However, if East puts itself in declarer's place and determines that the finesse is the percentage play, then it will always discard a spade. Now if declarer puts itself in East's place and sees that a spade discard is best, then declarer will alter its thinking. A clear game theory decision. That is one defect of using a straight simulation in which all plays are equally likely.
Now we can do something that can't happen in human play, namely, go back and have East discard a spade and see what declarer will do. In human play the tempo of East's discard might influence declarer to play for the drop of the spade Q offside. How will Blue Chip Bridge handle the problem? In the replay, with East forced to discard a spade rather than a heart, declarer took the percentage play of the finesse and went down.
The semifinal matches were 52-board KOs, including a full carryover from the 12-board round robin:
|
Meadowlark Bridge survived a late rally by WBridge5 in the semifinal KO match. One board that could have swung the match was a hand that WBridge5 bid a grand slam off QJxx of trumps (a 50% grand) while Meadowlark Bridge was only in game. If WBridge5 had bid 6 Diamonds, or made 7 Diamonds, it would have defeated Meadowlark Bridge. In human play decisions might be based on the perceived state of the match. Behind near the end of a match, a pair might bid a 50% grand slam, while earlier in the match they would be looking for 67%. Of course the programs make decisions independent of the state of the match. Trumps were unfavorable and the hand went down one.
It was Meadowlark Bridge against Q-Plus Bridge for the championship. With one board to play in the finals, Q-Plus Bridge led Meadowlark Bridge by 2 IMPs. With human emotions flying high, the computers coldly started playing the last board of the 62-board KO final. Meadowlark Bridge picked up 5 IMPs to take the championship 143-141, and along with the title of World Computer Bridge Champion, first place prize money of $1,500.
| Finals | 1-12 | 13-22 | 23-39 | 40-54 | 55-62 |
| Meadowlark Bridge | 38 | 67 | 105 | 131 | 143 |
| Q-Plus Bridge | 25 | 45 | 82 | 116 | 141 |
REFERENCE
1 Orbis World Bridge Championship DAILY NEWS, Tuesday, January 18, 2000, Issue 11