GIB: Imperfect Information in a Computationally Challenging Game

Abstract

This paper investigates the problems arising in the construction of a program to play the game of contract bridge. These problems include both the difficulty of solving the game's perfect information variant, and techniques needed to address the fact that bridge is not, in fact, a perfect information game. GIB, the program being described, involves five separate technical advances: partition search, the practical application of Monte Carlo techniques to realistic problems, a focus on achievable sets to solve problems inherent in the Monte Carlo approach, an extension of alpha-beta pruning from total orders to arbitrary distributive lattices, and the use of squeaky wheel optimization to find approximately optimal solutions to cardplay problems. GIB is currently believed to be of approximately expert caliber, and is currently the strongest computer bridge program in the world.

Cited by in corpus (9)

• Decision-Theoretic Bidding Based on Learned Density Models in Simultaneous, Interacting Auctions
• Improving Search with Supervised Learning in Trick-Based Card Games
• Re-determinizing Information Set Monte Carlo Tree Search in Hanabi
• Combining Prediction of Human Decisions with ISMCTS in Imperfect Information Games
• Neural Network-based Information Set Weighting for Playing Reconnaissance Blind Chess
• Learning to Play Imperfect-Information Games by Imitating an Oracle Planner
• Competing in a Complex Hidden Role Game with Information Set Monte Carlo Tree Search
• BridgeHand2Vec Bridge Hand Representation
• A Complexity of double dummy bridge