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 metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01556114
Contributor : Hal Ifip <>
Submitted on : Tuesday, July 4, 2017 - 5:02:13 PM
Last modification on : Tuesday, July 4, 2017 - 5:35:05 PM
Long-term archiving on: : Friday, December 15, 2017 - 3:15:29 AM

File

978-3-642-33542-6_29_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

89

Files downloads

162