View Full Document

GIB: Imperfect Information in a Computationally Challenging Game



View the full content.
View Full Document
View Full Document

6 views

Unformatted text preview:

Journal of Artificial Intelligence Research 14 2001 303 358 Submitted 10 00 published 6 01 GIB Imperfect Information in a Computationally Challenging Game Matthew L Ginsberg ginsberg cirl uoregon edu CIRL 1269 University of Oregon Eugene OR 97405 USA 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 1 Introduction Of all the classic games of mental 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 Handtalk was beaten by 1 dan Janice Kim winner of the 1984 Fuji Women s Championship in the 1997 AAAI 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 for other reasons existing poker and bridge programs are extremely weak World poker champion Howard Lederer



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view GIB: Imperfect Information in a Computationally Challenging Game and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view GIB: Imperfect Information in a Computationally Challenging Game and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?