Monte Carlo tree search in Kriegspiel

Partial information games are excellent examples of decision making under uncertainty. In particular, some games have such an immense state space and high degree of uncertainty that traditional algorithms and methods struggle to play them effectively. Monte Carlo tree search (MCTS) has brought significant 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 insufficient: in particular, this is the case of games with long matches, dynamic information, and complex 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 refined versions for playing the game with little specific knowledge. We compare these MCTS-based programs to the strongest known minimax-based Kriegspiel program, obtaining significantly better experimental results with less domain-specific knowledge. (C) 2010 Elsevier B.V. All rights reserved.