Representing Kriegspiel states with Metapositions

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.