Understanding the Nature of Monte-Carlo Tree Search
04 / 2010 - unknown
Two-person zero-sum games with perfect information such as Chess and Checkers have been addressed by many Artificial Intelligence (AI) researchers with great success, but the game of Go is a notable exception. Despite significant attention the best computer Go programs still lag far behind the level of professional players. Recently, a new technique, called Monte-Carlo Tree Search (MCTS), started a revolution and increased the level of play of computer Go programs substantially. Whereas in first instance the focus of MCTS with respect to Go has been on the practical application, the current research proposal addresses the problem of understanding the nature, the underlying principles, of MCTS. A careful understanding of the nature of MCTS will lead to (better) effective search algorithms. Hence, the two interrelated research questions are: 1) How to formulate models that increase the understanding how Monte-Carlo Tree Search (MCTS) works? and 2) How to use the developed MCTS models to create effective search algorithms? Three programs, MANGO, MOGO and STEENVRETER, will act as the main test environment for investigating, tuning and testing the new techniques. The research will be executed by a Postdoc (underlying principles) and PhD researcher (application in Go) and be performed at the Department of Knowledge Engineering, Maastricht University, under supervision of Prof. G. Weiss, in collaboration with AI researchers of University of Bologna, INRIA Paris, Reykjavik University, MTA SZTAKI Budapest and GN Algorithm R&D Eindhoven.