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

Abstract

The paper reports on new algorithms for solving partially observable games. Whereas existing algorithms apply AND-OR search to a tree of blackbox 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), incrementalization yields speedups of two or more orders of magnitude on hard instances.