Efficient belief-state AND-OR search, with application to Kriegspiel

摘要

The paper reports on new algorithms for solving partially observable games. Whereas existing algorithms apply AND-OR search to a tree of black-box belief states, our "incremental" versions treat uncertainty as a new search dimension, examining the physical states within a belief state to construct solution trees incrementally. On a newly created database of checkmate problems for Kriegspiel (a partially observable form of chess), incrementaliza-tion yields speedups of two or more orders of magnitude on hard instances.