Representing Kriegspiel States with Metapositions

Abstract

We describe a novel approach to incomplete information board games, which is based on the concept of 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 metaposition trees and describe a weighed maximax algorithm for evaluating metapositions. We have tested our approach competing against both human and computer players.