We describe a novel approach to incomplete information board games, which is based on the concept of {it metaposition} as the merging of a very large set of possible game states into a single entity which contains at least every state in the current information set. This merging operation allows an artificial player to apply traditional perfect information game theory tools such as the Minimax theorem. We apply this technique to the game of Kriegspiel, a variant of chess characterized by strongly incomplete information as players cannot see their opponent's pieces but can only try to guess their positions by listening to the messages of a referee. We provide a general representation of Kriegspiel states through metapositions and show a Minimax-like algorithm for building a metaposition game tree. We have evaluated our approach competing against both human and computer players.

Representing Kriegspiel states with Metapositions

CIANCARINI, PAOLO;FAVINI, GIAN-PIERO
2007

Abstract

We describe a novel approach to incomplete information board games, which is based on the concept of {it metaposition} as the merging of a very large set of possible game states into a single entity which contains at least every state in the current information set. This merging operation allows an artificial player to apply traditional perfect information game theory tools such as the Minimax theorem. We apply this technique to the game of Kriegspiel, a variant of chess characterized by strongly incomplete information as players cannot see their opponent's pieces but can only try to guess their positions by listening to the messages of a referee. We provide a general representation of Kriegspiel states through metapositions and show a Minimax-like algorithm for building a metaposition game tree. We have evaluated our approach competing against both human and computer players.
Proc. 20th Int. Joint Conf. on Artificial Intelligence (IJCAI 07)
2450
2455
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/29989
 Attenzione

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

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