A PROGRAM TO PLAY KRIEGSPIEL

Article type: Research Article

Authors: Ciancarini, Paolo | Favini, Gian Piero¹

Affiliations: Bologna, Italy

Note: [1] University of Bologna, Bologna, Italy. Email: cianca@cs.unibo.it

Abstract: The game of Kriegspiel is a variant of the game of Chess. Kriegspiel is interesting because most chess rules are still valid, but gameplay is characterized by incomplete information as players may not see their opponent’s pieces and can only try to guess their positions by listening to the messages of a referee. We describe a Kriegspiel-playing program based on the concept of metaposition, that is, the merging of a rather large set of possible game states into a single entity. This merging operation allows us to exploit traditional perfect-information game-theory tools, such as the Minimax theorem. We provide a general representation of Kriegspiel states through metapositions and describe an algorithm for building and exploring a game tree of metapositions. Our method does not assume that the opponent will react with a best defence model. We have evaluated our approach by competing against both human and computer players.

DOI: 10.3233/ICG-2007-30102

Journal: ICGA Journal, vol. 30, no. 1, pp. 3-24, 2007