REPORT ON THE 4^th ACBL WORLD COMPUTER-BRIDGE CHAMPIONSHIP

Maastricht, The Netherlands

September 1-5, 2000

Alvin Levy¹

Commack, USA

Introduction

The 2000 Microsoft Network Gaming Zone World Computer-Bridge Championship, the 4^th 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 North American Bridge 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 this, the 2000 event, was held 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 is not 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, President of the ICCA, favourably 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 programmers². 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. Details are given in Table 1.

Program	Programmers	Country	Email/web address
Blue Chip Bridge	Ian Trackman and Mike Whittaker	UK	www.bluechipbridge.co.uk
Bridge Baron	Stephen Smith and George Yanakiev	USA	www.bridgebaron.com
Bridge Buff	Doug Bennion	Canada	www.bridgebuff.com
Jack	Hans Kuijf	USA
Meadowlark Bridge	Rodney Ludwig	USA	rrnet.com/meadowlark
Micro Bridge	Tomio and Yumiko Uchida	Japan	www.threeweb.ad.jp/~mcbridge
Oxford Bridge	Andrew Bracher	UK	www.thinkgam.demon.co.uk
Q-Plus Bridge	Hans Leber	Germany	www.q-plus.com
WBridge5	Yves Costel	France	ourworld.compuserve.com/homepages/yvescostel

Table 1: The competitors.

Matt Ginsberg’s GIB (www.gibware.com), U.S., winner of the 1999 title during the Orbis World Computer-Bridge Championships in Bermuda, did not compete in Maastricht.

The 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 semi-final 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; (1) those bids that are standard conventions, such as transfers and weak NT, and (2) 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 is 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 honour 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 given tests. 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. Ian Trackman, the creator of Blue Chip Bridge, designed the protocol system. 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 Q-Plus Bridge 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 solves the game. 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 12 high card points (hcp) then it opens 1 spade; if responder has 5 clubs, 10 hcp and less than 4 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 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 consistent 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 (see Table 2).

	Meadowlark Bridge	Jack	WBridge5	Q-Plus Bridge	Bridge Baron	Blue Chip Bridge	Oxford Bridge	Bridge Buff	Micro Bridge	Total pts
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

Table 2: The standings at the end of the round robin (VPs and IMP scores).

The following two hands from the round robin demonstrated some interesting aspects of computer bridge play.

Dealer: South

Vul: none

North	East	South	West
Jack	Baron	Jack	Baron
-	-	1C	Pass
1S	3D	Pass	Pass
4S	All Pass

Bridge Baron East led the DA and gave its favourite partner a ruff. West did not 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 the following position:

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

West	North	East	South
Baron Q-Plus	Blue Chip Buff	Baron Q-Plus	Blue Chip 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 Bridge played in 5NT. The D4 was led and declarer led a heart toward the Q. East won the K and returned a diamond. Declarer then 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 loses when declarer has the heart J. A spade discard wins when declarer takes the spade finesse and loses when declarer plays for the drop of the spade Q. Its 50 percent 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 not 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 semi-final matches were 52-board KOs, including a full carryover from the 12-board round robin:

Semi-finals	1-12	13-28	29-44	45-52
Q-Plus Bridge	47	77	120	163
Jack	34	71	98	113
Meadowlark Bridge	77	126	145	168
WBridge5	24	58	133	150

Meadowlark Bridge survived a late rally by WBridge5 in the semi-final 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 percent 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 percent grand slam, while earlier in the match they would be looking for 67 percent. Of course the programs make decisions independent of the state of the match. Trumps were unfavourable 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

Acknowledgement

On a personal note, I want to thank the many people that contributed to the success of this event, including the participants, for their cooperation and sportsmanship, Sol Weinstein, Tournament Director, for his advice and directing duties, Ton Kooyman, WBF Chief of Operations, for his invaluable on-site help, and Lorne Russell of Microsoft, for his support. Thanks to the ACBL for sanctioning and sponsoring the Annual World Computer Bridge Championship, and to the WBF for its support.  Special thanks to José Damiani, WBF president, whose interest and support made this happen in Maastricht in conjunction with the World Bridge Olympiad.