Monte Carlo Tree Search in Kriegspiel

Partial information games are excellent examples of decision making un- der uncertainty. In particular, some games have such an immense state space and high degree of uncertainty that traditional algorithms and meth- ods struggle to play them eectively. Monte Carlo tree search (MCTS) has brought signicant improvements to the level of computer programs in games such as Go, and it has been used to play partial information games as well. However, there are certain games with particularly large trees and reduced information in which a naive MCTS approach is insucient: in particular, this is the case of games with long matches, dynamic information, and com- plex victory conditions. In this paper we explore the application of MCTS to a wargame-like board game, Kriegspiel. We describe and study three MCTS- based methods, starting from a very simple implementation and moving to more rened versions for playing the game with little specic knowledge. We compare these MCTS-based programs to the strongest known minimax-based Kriegspiel program, obtaining signicantly better experimental results with less domain-specic knowledge.