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.
Type de document :
Communication dans un congrès
Gerhard Goos; Juris Hartmanis; Jan van Leeuwen. 11th International Confernece on Entertainment Computing (ICEC), Sep 2012, Bremen, Germany. Springer, Lecture Notes in Computer Science, LNCS-7522, pp.333-340, 2012, Entertainment Computing - ICEC 2012. 〈10.1007/978-3-642-33542-6_29〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01556114
Contributeur : Hal Ifip <>
Soumis le : mardi 4 juillet 2017 - 17:02:13
Dernière modification le : mardi 4 juillet 2017 - 17:35:05
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 03:15:29

Fichier

978-3-642-33542-6_29_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Paolo Ciancarini, Andrea Gasparro. Priority Level Planning in Kriegspiel. Gerhard Goos; Juris Hartmanis; Jan van Leeuwen. 11th International Confernece on Entertainment Computing (ICEC), Sep 2012, Bremen, Germany. Springer, Lecture Notes in Computer Science, LNCS-7522, pp.333-340, 2012, Entertainment Computing - ICEC 2012. 〈10.1007/978-3-642-33542-6_29〉. 〈hal-01556114〉

Partager

Métriques

Consultations de la notice

28

Téléchargements de fichiers

24