1999aaaiss Darse Billings, Denis Papp, Lourdes Peña, Jonathan Schaeffer, Duane Szafron, Using Selective-Sampling Simulations in Poker,1999 AAAI Spring Symposium on Search Techniques for Problem Solving under Uncertainty and Incomplete Information, March 1999, Menlo Park, California, pp. 13-18. abstract or pdf.
Abstract:

Until recently, AI research that used games as an experimental testbed has concentrated on perfect information games. Many of these games have been amenable to so-called brute-force search techniques. In contrast, games of imperfect information, such as bridge and poker, contain hidden knowledge making similar search techniques impractical. This paper describes work being done on developing a world-class poker-playing program. Part of the program's playing strength comes from real-time simulations. The program generates an instance of the missing data, subject to any constraints that have been learned, and then searches the game tree to determine a numerical result. By repeating this a sufficient number of times, a statistically meaningful sample can be obtained to be used in the program's decision­making process. For constructing programs to play two-player deterministic perfect information games, there is a well-defined framework based on the alpha-beta search algorithm. For imperfect information games, no comparable framework exists. In this paper we propose selective sampling simulations as a general-purpose framework for building programs to achieve high performance in imperfect information games.