GIB: Steps Toward an Expert-Level Bridge-Playing Program

Abstract

This paper describes Goren In a Box (gib), the first bridge-playing program to approach the level of a human expert. We give a basic overview of the algorithms used, describe their strengths and weaknesses, and present the results of experiments comparing gib to both human opponents and earlier programs. Introduction Of all the classic games of skill, only card games and Go have yet to see the appearance of serious computer challengers. In Go, this appears to be because the game is fundamentally one of pattern recognition as opposed to search; the brute-force techniques that have been so successful in the development of chess-playing programs have failed almost utterly to deal with Go's huge branching factor. Indeed, the arguably strongest Go program in the world was beaten by Janice Kim in the AAAI-97 Hall of Champions after Kim had given the program a monumental 25 stone handicap. Card games appear to be different. Perhaps because they are games of imperfect information, or perhaps...