Game-tree search with combinatorially large belief states

Austin Parker, Dana Nau, V. S. Subrahmanian

Research output: Contribution to journalConference articlepeer-review

22 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)254-259
Number of pages6
JournalIJCAI International Joint Conference on Artificial Intelligence
StatePublished - 2005
Externally publishedYes
Event19th International Joint Conference on Artificial Intelligence, IJCAI 2005 - Edinburgh, United Kingdom
Duration: Jul 30 2005Aug 5 2005

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Game-tree search with combinatorially large belief states'. Together they form a unique fingerprint.

Cite this