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.
Cite
Text
Russell and Wolfe. "Efficient Belief-State AND-OR Search, with Application to Kriegspiel." International Joint Conference on Artificial Intelligence, 2005.Markdown
[Russell and Wolfe. "Efficient Belief-State AND-OR Search, with Application to Kriegspiel." International Joint Conference on Artificial Intelligence, 2005.](https://mlanthology.org/ijcai/2005/russell2005ijcai-efficient/)BibTeX
@inproceedings{russell2005ijcai-efficient,
title = {{Efficient Belief-State AND-OR Search, with Application to Kriegspiel}},
author = {Russell, Stuart and Wolfe, Jason Andrew},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2005},
pages = {278-285},
url = {https://mlanthology.org/ijcai/2005/russell2005ijcai-efficient/}
}