Journal of Artificial Intelligence Research 14 (2001) 303–358 Submitted 10/00; published 6/01GIB: Imperfect Information in a ComputationallyChallenging GameMatthew L. Ginsberg [email protected] University of OregonEugene, OR 97405 USAAbstractThis paper investigates the problems arising in the construction of a program to play thegame of contract bridge. These problems include both the difficulty of solving the game’sperfect information variant, and techniques needed to address the fact that bridge is not, infact, a perfect information game. Gib, the program being described, involves five separatetechnical advances: partition search, the practical application of Monte Carlo techniques torealistic problems, a focus on achievable sets to solve problems inherent in the Monte Carloapproach, an extension of alpha-beta pruning from total orders to arbitrary distributivelattices, and the use of squeaky wheel optimization to find approximately optimal solutionsto cardplay problems.Gib is currently believed to be of approximately expert caliber, and is currently thestrongest computer bridge program in the world.1. IntroductionOf all the classic games of mental skill, only card games and Go have yet to see the ap-pearance of serious computer challengers. In Go, this appears to be because the game isfundamentally one of pattern recognition as opposed to search; the brute-force techniquesthat have been so successful in the development of chess-playing programs have failed al-most utterly to deal with Go’s huge branching factor. Indeed, the arguably strongest Goprogram in the world (Handtalk) was beaten by 1-dan Janice Kim (winner of the 1984 FujiWomen’s Championship) in the 1997 AAAI Hall of Champions after Kim had given theprogram a monumental 25 stone handicap.Card games appear to be different. Perhaps because they are games of imperfect in-formation, or perhaps for other reasons, existing poker and bridge programs are extremelyweak. World poker champion Howard Lederer (Texas Hold’em, 1996) has said that he wouldexpect to beat any existing poker program after five minutes’ play.†1Perennial world bridgechampion Bob Hamman, seven-time winner of the Bermuda Bowl, summarized the state ofbridge programs in 1994 by saying that, “They would have to improve to be hopeless.”†In poker, there is reason for optimism: the gala system (Koller & Pfeffer, 1995), ifapplicable, promises to produce a computer player of unprecedented strength by reducingthe poker “problem” to a large linear optimization problem which is then solved to generatea strategy that is nearly optimal in a game-theoretic sense. Schaeffer, author of the world1. Many of the citations here are the results of personal communications. Such communications are indi-cated simply by the presence of a†in the accompanying text.c°2001 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.Ginsbergchampion checkers program Chinook (Schaeffer, 1997), is also reporting significant successin the poker domain (Billings, Papp, Schaeffer, & Szafron, 1998).The situation in bridge has b een bleaker. In addition, because the American ContractBridge League (acbl) does not rank the bulk of its players in meaningful ways, it is difficultto compare the strengths of competing programs or players.In general, performance at bridge is measured by playing the same deal twice or more,with the cards held by one pair of players being given to another pair during the replay andthe results then being compared.2A “team” in a bridge match thus typically consists oftwo pairs, with one pair playing the North/South (N/S) cards at one table and the otherpair playing the E/W cards at the other table. The results obtained by the two pairs areadded; if the sum is positive, the team wins this particular deal and if negative, they loseit.In general, the numeric sum of the results obtained by the two pairs is converted toInternational Match Points, or imps. The purpose of the conversion is to diminish theimpact of single deals on the total, lest an abnormal result on one particular deal have anunduly large impact on the result of an entire match.Jeff Goldsmith†reports that the standard deviation on a single deal in bridge is about 5.5imps, so that if two roughly equal pairs were to play the deal, it would not be surprising if oneteam beat the other by about this amount. It also appears that the difference between anaverage club player and an expert is about 1.5 imps (per deal played); the strongest playersin the world are approximately 0.5 imps/deal better still. Excepting gib, the strongestbridge playing programs appear to be slightly weaker than average club players.Progress in computer bridge has been slow. An incorporation of planning techniques intoBridge Baron, for example, appears to have led to a performance increment of approximately1/3 imp per deal (Smith, Nau, & Throop, 1996). This modest improvement still leavesBridge Baron far shy of expert-level (or even good amateur-level) performance.Prior to 1997, bridge programs generally attempted to duplicate human bridge-playingmethodology in that they proceeded by attempting to recognize the class into which anyparticular deal fell: finesse, end play, squeeze, etc. Smith et al.’s work on the Bridge Baronprogram uses planning to extend this approach, but the plans continue to be constructedfrom human bridge techniques. Nygate and Sterling’s early work on python (Sterling &Nygate, 1990) produced an expert system that could recognize squeezes but not prepare forthem. In retrospect, perhaps we should have expected this approach to have limited success;certainly chess-playing programs that have attempted to mimic human methodology, suchas paradise (Wilkins, 1980), have fared poorly.Gib, introduced in 1998, works differently. Instead of modeling its play on techniquesused by humans, gib uses brute-force search to analyze the situation in which it finds itself.A variety of techniques are then used to suggest plays based on the results of the brute-forcesearch. This technique has been so successful that all competitive bridge programs haveswitched from a knowledge-based approach to a search-based approach.GIB’s cardplay based on brute-force techniques was at the exp ert level (see Section 3)even without some of the extensions that we discuss in Section 5 and subsequently. Theweakest part of gib’s game is bidding, where it relies on a large database of rules