Monte Carlo tree search techniques in the game of Kriegspiel

Abstract

Monte Carlo tree search has brought significantimprovements to the level of computer players ingames such as Go, but so far it has not been usedvery extensively in games of strongly imperfect in-formation with a dynamic board and an emphasison risk management and decision making under un-certainty. In this paper we explore its application tothe game of Kriegspiel (invisible chess), providingthree Monte Carlo methods of increasing strengthfor playing the game with little specific knowl-edge. We compare these Monte Carlo agents to thestrongest known minimax-based Kriegspiel player,obtaining significantly better results with a con-siderably simpler logic and less domain-specificknowledge.