---
title: "Efficient belief-state AND-OR search, with application to Kriegspiel"
authors:
  - "Stuart J. Russell"
  - "Jason Andrew Wolfe"
doi: ""
url: "https://ijcai.org/proceedings/2005/110"
pdf: "https://ijcai.org/proceedings/2005/0110.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "278-284"
track: ""
keywords:
---

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

Stuart J. Russell, Jason Andrew Wolfe

*Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence*, pages 278-284.

## 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.