2005 · 25 citations · 6 references
ComputingComputer ScienceAlgorithmsArtificial IntelligenceGame TheoryIncomplete Information GamesStatistical InferenceBelief StatesGame Tree SearchGame TreesRandom SamplingSamplingStatistical Sampling DesignTree Search
In games such as kriegspiel chess (a chess variant where players have no direct knowledge of the opponent’s pieces ’ locations) the belief state’s sizes dwarf those of other partial information games like bridge, scrabble, and poker–and there is no easy way to generate states satisfying the given observations. We show that statistical sampling approaches can be developed to do well in such games. We show that it is not necessary for the random sample to consist only of game boards that satisfy each and every one of a player’s observations. In fact, we win 24 % more often by beginning with such completely consistent boards and gradually switching (as the game progressed) to boards that are merely consistent with the latest observation. This surprising result is explained by noting that as the game progresses, a board that is consistent with the last move becomes more and more likely to be consistent with the entire set of observations, even if we have no idea what sequence of moves might have actually generated this board. 1
6
Approximating game-theoretic optimal strategies for full-scale poker
Darse Billings, Neil Burch, Aaron Davidson et al. · 2003 · 214 citations
Brian Sheppard · Artificial Intelligence · 2002 · 124 citations
GIB: Steps Toward an Expert-Level Bridge-Playing Program
Matthew L. Ginsberg · 1999 · 112 citations
Computer Bridge: A Big Win for AI Planning
Stephen J. Smith, Dana Nau, Thomas A. Throop · 1998 · 79 citations