THE 12^th ANNUAL WORLD COMPUTER-BRIDGE CHAMPIONSHIP

Las Vegas, Nevada, USA

20-25 July 2008

by Alvin Levy

The 12th annual World Computer-Bridge Championship, recognized and supported by the American Contract Bridge League (ACBL) and World Bridge Federation (WBF) was held in Las Vegas, Nevada, USA alongside the ACBL’s summer North American Bridge Championship (NABC).

History

The ACBL inaugurated an annual computer-bridge championship in 1997, and in 1999 it became an ACBL/WBF joint venture.  Since its inception in 1997, the championship has been held every year alongside an important bridge championship.  The twelve championships have been held five times at an ACBL NABC, six times at a WBF World Championship and once at the European Bridge League’s first European Open Championship.  For a complete history and details of previous championships go to www.computerbridge.com or www.ny-bridge.com/allevy/computerbridge

Technical remarks

A bridge “table” consists of a central server (CS) that manages the game, and four connecting computers that “seat” the robots.  The CS manages and records the play.  Play proceeds automatically, with pauses for manual exchanges of information when explanations of bids are necessary.  The CS distributes the hands, receives and passes information from and to the robots and records the bidding and play.  This year Intel Core 2 Duo 2.4GHz/2GH Ram desktops were used, running under Windows XP Pro.  The timing of play was set at two minutes per pair per deal.

The contestants submit their robot's Convention Card (CC) containing their bidding and carding methods, at least one month before the competition so that the other competitors can prepare.  This information is stored in the opponent robot's memory before play begins.  Nevertheless, during the bidding there are some situations where bids are alerted and explained, and the meaning manually input into the opposing robots' memory.

Without getting into the details at this moment, most of the robots are programmed with a combination of knowledge-based AI (sets of rules) and search-based AI (simulations).

Play format

The format is team play.  Two teams play each other, with each team using four identical robots, one pair sitting North-South at one table and their teammates sitting East-West at the other table.

This event starts with a 32-board round-robin, a seven round affair with one bye each round.  The top four robot teams advance to the knockout stage, a 64-board semifinal followed by a 64-board final.  The round-robin is scored on an International 30-VP scale.

A new Individual event was introduced this year.  A one-day, 8-robot  Individual was held with Blue Chip Bridge joining the seven robots competing in the major championship.

The competitors

Seven robots entered this year’s major championship, including defending champion, Wbridge5, five-time champion Jack, previous champion Bridge Baron, previous runner-up Micro Bridge, three-time runner-up Q-Plus Bridge, third-year competitor Shark Bridge and second-year competitor RoboBridge.  Over the twelve years of this competition there have been fifteen different programs competing.

Table 1. Robots and their developers.

Results

The round-robin ended with Jack topping the field, followed by Shark Bridge, Wbridge5 and Micro Bridge.  Jack’s results are impressive, winning all its matches, and scoring 155 VPs out of a possible 165 VPs.  The semifinals pitted Jack, with an 16 Imps carryover, against Micro Bridge and Shark Bridge playing even against Wbridge5.

Table 2.  Round Robin results.

In the semifinal matches, Jack, starting with a 16 Imp carryover, defeated Micro Bridge, 166-112, and WBridge5 narrowly defeated Shark Bridge, 139-121.  WBridge5 overcame an 18 Imps carryover to defeat Jack, 172-157, in the finals, and repeated as world computer-bridge champion.

As an interlude between the round robin stage and the knockout stage, a 2-table, 8-robot, 112-board Individual was played.  Shark Bridge won the event with a 53.13% score.

                                                    Table 3. Individual results

While the robots never exhibit bidding misunderstanding when playing with an identical copy of themselves,  many misunderstandings occurred in the Individual, where robots played with 'strangers.'  One difficulty was that, even though a relatively simple common Convention Card was used, not all situations and bidding sequences were covered in their entirety.  If two human first-time partners used a simple Convention Card, without much discussion, they would draw on their experiences when a situation they hadn't discussed or couldn't remember, occurred.  For example, the humans would assume that fourth suit was forcing, at least for one round.  In a similar situation, robots might pass a fourth-suit bid, having no 'experience' to draw on.  The final results were extremely close, with less than a 5.5% difference between first and last place.  This suggests that the results were random, matching the randomness of the play.  This was an instructive event, and hopefully will be repeated with more care and more success, next year.  Not withstanding these issues, congratulations to Shark Bridge for winning the first Individual.

How robots 'think' during the play of the hand

One of the AI methods used to program bridge-playing robots is a double dummy simulation technique in which the unknown hands are constructed, many times over, consistent with the bidding and play, and each construction is analyzed double dummy.  If only this technique is used in the play of the cards, at each trick the card that has the best chance of achieving success (making the contract as declarer or defeating the contract as defender), as determined from this analysis, is played.

Watch Wbridge5 use this technique on the following deal from the round robin, hands rotated.

⁽¹⁾ Game forcing
⁽²⁾ 0 or 2 key cards without the trump queen

Against 6♥ by Wbridge5, Shark Bridge led the ♠Q. If trumps are 2-2, the slam is cold and if there is a trump loser, then there are squeeze possibilities with threats in the other three suits. The play requires that declarer 'best’ guess which distributions to play for.

Wbridge5 won the ♠K in hand. A double dummy simulation determined that the contract could be made, double dummy, against more distributions of the opponents' cards by winning the king in hand than by winning the ace in dummy.  A heart was played to the ace and a heart returned to the jack and 3 — Wbridge5 ducked the heart!  A simulation, at this point, determined that the contract could always be made, double dummy, if hearts are 2-2, and could be made, double dummy, more often by ducking than by winning the king when trumps are 3-1.  East returned the ♦10.  Wbridge5 won the ♦A in dummy, led a heart to the king and ran hearts coming down to the following position.

Now it was up to Wbridge5 to determine the end position.  A simulation is done for each card played.  On the ♥4, West discarded the ♠5 and Wbridge5 got it right by discarding the ♠7 from dummy.  Now a spade to dummy's ace squeezed West.  West blanked the ♣J, needing to keep three diamonds.  Then the ♦K and ♦Q squeezed East into keeping the ♠J and the lone ♣K and declarer pitched the ♠10. Wbridge5 now won the last two tricks with the ♣A10, for 1430.

A further step in robotic 'thinking' is to use single dummy techniques, which allow for the both sides going wrong, i.e., not playing double dummy.  To that end, a robot places itself in an opponent's seat and uses a variety of schemes to analyze the best play.  Generally, these schemes are either rule based, as opposed to simulation based, or a combination of a double dummy simulation with rule based corrections.  It is noted that using a 'pure' single dummy simulation, for each construction of the missing cards, is currently too inefficient, i.e., too time consuming.

In the following hand, the use of a single dummy technique helped Shark Bridge defend best.

⁽¹⁾ Transfer

In all three round robin matches (Wbridge5 had a bye), 4♠ was the contract, played five times by South and once by North (by Micro Bridge, playing weak NT).  When Shark Bridge defended against Bridge Baron, on the lead of a club Shark Bridge East went up with the ♣A and returned the small heart.  Declarer guessed wrong, playing the ♥J, and went down, losing two hearts, the ♣A and a diamond.

At the other five tables, the defense failed to give declarer a chance to go down by neither underleading the ♥A nor ducking it when declarer led a heart from the North hand.  The reason that a single dummy technique is needed to defend best in this hand, is that using only a double dummy simulation, which assumes that the opponents play as if they see all the cards, ducking or underleading the ♥A can never win.  While many of the robots employ single dummy techniques, only Shark Bridge got this defense right.

Bidding
The robots never forget their system, so using involved treatments, within the parameters of the conditions of  contest, can often prove beneficial.  Look at the following hand from the finals, a 25-high-card-point grand slam. While Wbridge5 did well to reach 6♦, Jack did even better, reaching the lay-down grand using a system perfect for these hands.

⁽¹⁾ 22+ total points
⁽²⁾ one or four key cards

⁽¹⁾ Strong one-suiter.
⁽²⁾ Positive, less than 2 spades, 3+ length in the other suits.
⁽³⁾ Agreed diamonds as trump, 10-12 support points.
⁽⁴⁾ One or four key cards.
⁽⁵⁾ Do you have the trump queen?
⁽⁶⁾ No.
⁽⁷⁾ I really didn't need the trump queen as partner has 3+ trumps, at most one spade and the heart ace.

Jack found the lay-down grand, while Wbridge5 didn't explore further over 5♦. 11 Imps to Jack

Jack was not as successful in at least two other deals from the finals.  On two deals Jack bid 3NT and 6NT, without a stopper in the opponents' bid suit.  On the 3NT mishap, going down, at the other table Wbridge5 did well to made 4♥.  On the 6NTx mishap Wbridge5 made 6♣, and won 19 Imps, more than the difference in the match.

Summary
Some statistical snapshots

The average swing-per-board (spb):
For the round robin: the average spb for all matches = 4.75
For the round robin: the average spb for matches between top four finishers (Jack, Shark Bridge, Wbridge5 and Micro Bridge) = 4.3
For the semifinal matches (Wbridge5 vs. Shark Bridge, Jack vs. Micro Bridge): the average spb  = 4.08
For the final match (Wbridge5 vs. Jack): the average spb = 4.86
For the top-four from the round robin and the semifinal and final matches: the average spb = 4.32, *Norm=4.25
* For the 2007 Bermuda Bowl/Venice Cup/Senior Bowl/Transnational Teams, the combined spb = 4.25

Imp swings:
Combined semifinal and final matches:
Imps  Occurrence  Percent  Norm*
0-2         107         55.7    50.0
3-5           33         17.2    16.0
6-8           23         12.0    12.0
9-12         24         12.5    16.0
13+            5           2.6      6.0
*norm based on 2007 Bermuda Bowl/Venice Cup/Senior Bowl/Transnational teams combined

While this is very limited data, the results point to lower Imp swings per board and less high swing occurrences when 'more evenly matched-higher ranked' robots are playing, with the results approaching those for high level human play.

Wbridge5 and Jack performed best, and based on recent performances, appear to be at the top of robotic play.  While Wbridge5 successfully defended its championship with its excellent play, Jack outscored Wbridge5 in their head-to-head matches (32 boards in the round robin and 64 boards in the final) 237-216.  Considering the robots aren't influenced by the importance of a board or the conditions under which a board or match is played, overall, Jack performed better than Wbridge5.  Wbridge5 performed better when it counted most, which for robots is a random event.  Along with Wbridge5 and Jack, Shark Bridge performed admirably, winning the Individual, finishing second in the round robin, and putting up a good match against Wbridge5 in the semifinals.

Randomness clearly plays a role in the short-term outcome.  For a best estimate of relative strength, 1,000+ board matches would be informative.  The World Computer-Bridge Championships, similar to human championships, aren't meant to determine who is best, only to crown a champion after much play.  Not withstanding, recent performances are a strong indication of the robots' relative strength.

For more information on this year’s championship, past championships, published articles, photos and the robots’ websites, go to www.computerbridge.com or www.ny-bridge.com/allevy/computerbridge