Progress Through Uncertainty in Some Kriegspiel Endings
Andrea Bolognesi, Paolo Ciancarini, Gian Piero Favini · IEEE Transactions on Computational Intelligence and AI in Games · 2010
Kriegspielis a wargame based on the rules ofChess. In fact, the only difference betweenKriegspielandChessis that each player does not know his opponent's moves: the two players use different boards. A player only knows the position of his own pieces, while his opponent's pieces are invisible. A referee maintains the full state of the game on a third board. He answers a player's move attempt with information on its outcome, such as checks or piece captures. The referee also rejects illegal moves, forcing the player to try again. In this case, the player can exploit the negative information he received from the referee. AsKriegspielhas a very large state space and highly dynamic uncertainty, it is a very hard game for computers to play. In this paper, we focus on the simpler, but still difficult, task of playing the endgame. While manual algorithms have been developed to checkmate the lone King in various scenarios, they are often hard to translate into code, partially or ambiguously defined, and quite inefficient in the number of moves to mate. We describe a search algorithm for exploring theKriegspielendgames, and provide relatively simple evaluation functions able to progress through uncertainty. We show that our algorithm achieves quick checkmate in the vast majority of situations and significantly outperforms existing manual methods.