Retrograde analysis is a tool for reconstructing a game tree starting from its leaves; with these techniques one can solve specific subsets of a complex game, achieving optimal play in these situations, for example a chess endgame. Position values can then be stored in ``tablebases" for instant access, as is the norm in professional chess programs. While this technique is supposed to be only used in games of perfect information, this paper shows that retrograde analysis can be applied to certain Kriegspiel (invisible chess) endgames such as King and Rook versus King. Using brute force and a suitable data representation, one can achieve perfect play, with perfection meaning fastest checkmate in the worst case and without making any assumptions on the opponent.

Solving Kriegspiel endings with brute force: the case of KR vs. K

CIANCARINI, PAOLO;FAVINI, GIAN-PIERO
2010

Abstract

Retrograde analysis is a tool for reconstructing a game tree starting from its leaves; with these techniques one can solve specific subsets of a complex game, achieving optimal play in these situations, for example a chess endgame. Position values can then be stored in ``tablebases" for instant access, as is the norm in professional chess programs. While this technique is supposed to be only used in games of perfect information, this paper shows that retrograde analysis can be applied to certain Kriegspiel (invisible chess) endgames such as King and Rook versus King. Using brute force and a suitable data representation, one can achieve perfect play, with perfection meaning fastest checkmate in the worst case and without making any assumptions on the opponent.
Advances in Computer Games 12, revised papers
136
145
P. Ciancarini; GP. 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/83676
 Attenzione

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

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