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

Russell, Stuart J.; Wolfe, Jason Andrew

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

Download BibTeX Cite

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.

Stuart J. Russell, and Jason Andrew Wolfe. 2005. Efficient belief-state AND-OR search, with application to Kriegspiel. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05. IJCAI, 278–284. https://ijcai.org/proceedings/2005/110

@inproceedings{ijcai2005p110,
  title     = {Efficient belief-state AND-OR search, with application to Kriegspiel},
  author    = {Russell, Stuart J. and Wolfe, Jason Andrew},
  booktitle = {Proceedings of the Nineteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-05}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  pages     = {278--284},
  year      = {2005},
  url       = {https://ijcai.org/proceedings/2005/110},
}

TY  - CPAPER
TI  - Efficient belief-state AND-OR search, with application to Kriegspiel
AU  - Russell, Stuart J.
AU  - Wolfe, Jason Andrew
T2  - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2005
SP  - 278
EP  - 284
UR  - https://ijcai.org/proceedings/2005/110
ER  -