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.

Retrograde analysis of Kriegspiel endgames

CIANCARINI, PAOLO;FAVINI, GIAN-PIERO
2010

Abstract

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.
Proceedings 1st IEEE Conference on Computational Intelligence and Games
411
418
P.Ciancarini; G. Favini
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/93683
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact