Retrograde Analysis of Kriegspiel endgames
Paolo Ciancarini, Gian Piero Favini · 2010
A game tree can be constructed starting from its leaves with a technique called Retrograde Analysis. It is useful to solve some specific subsets of a game like chess, in order to achieve optimal play in endgame situations. Position values can then be stored in databases for instant access, in order to obtain perfect play at no time cost. This paper shows that such an approach can be used to solve subsets of Kriegspiel, an imperfect information game. Using a brute force retrograde analysis algorithm, a suitable data representation and a special lookup algorithm, we achieved perfect play, perfection meaning fastest checkmate in the worst case and without making any assumptions on the opponent's strategy. We investigate some classic Kriegspiel endgames. We have built databases for each of these endgames and cast light on some long standing open problems.