Skip to Main content Skip to Navigation
Conference papers

Priority Level Planning in Kriegspiel

Abstract : Back in 1950, Shannon introduced planning in board games like Chess as a selective approach, where the main idea is to select specific branches of the game tree that satisfy certain conditions. He contrasted this approach with brute force Minimax-like methods, based on an exhaustive search of the game tree, that aims to select the best path inside a given search horizon. Historically, the brute force approach won hands down against planning in complex games such as Chess, as the strongest Chess programs nowadays all exploit brute force algorithms. However, planning is still interesting and even necessary in some game-playing domains, for instance based on incomplete information, where there is no way to evaluate precisely or even build the game tree. In this paper we describe a technique that produced positive results in Kriegspiel, a variant of Chess played as an incomplete information game. Our main result is the definition of an algorithm for combining MonteCarlo search with planning; we tested the algorithm on a strong Kriegspiel program based on MonteCarlo search, and obtained a clear improvement.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Tuesday, July 4, 2017 - 5:02:13 PM
Last modification on : Friday, October 30, 2020 - 12:04:03 PM
Long-term archiving on: : Friday, December 15, 2017 - 3:15:29 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Paolo Ciancarini, Andrea Gasparro. Priority Level Planning in Kriegspiel. 11th International Confernece on Entertainment Computing (ICEC), Sep 2012, Bremen, Germany. pp.333-340, ⟨10.1007/978-3-642-33542-6_29⟩. ⟨hal-01556114⟩



Record views


Files downloads