Monte Carlo Tree Search for Games and Beyond

Research

Introduction

Monte Carlo Tree Search (MCTS) is a method for making optimal decisions in artificial intelligence (AI) problems, typically move planning in combinatorial games. It combines the generality of random simulation with the precision of tree search. Research interest in MCTS has risen sharply due to its spectacular success with computer Go and potential application to a number of other difficult problems. The following diagram shows one step of the basic MCTS algorithm. Starting with a given initial state (root node), a sequence of child states are selected until the most urgent incomplete node is reached (tree policy). A new node is added, a semi-random playout is performed to give a value estimate for this new state (default policy), and the resulting reward is backpropagated up through the sequence of selected nodes. Decisions typically converge to the optimal solution as the number of iterations increases and the tree fills out, growing asymmetrically into higher-reward areas of the search space.

The Upper Confidence Bounds for Trees (UCT) algorithm is a particular instance of MCTS which has had spectacular success with the demanding problem of Computer Go. UCT now powers the world’s strongest AI players for many difficult games including Go, Hex, Havannah, as well as the broader task of General Game Playing (GGP). However, its application extends beyond games and MCTS can theoretically be applied to any domain that can be described in terms of {state, action} pairs and simulation used to forecast outcomes. The Computational Creativity Group’s particular interest in MCTS lies in its potential use as a creative search algorithm for game design and other creative tasks. Evolutionary approaches such as genetic algorithms (GAs) are typically used for such tasks, but the tree-based nature of MCTS inherently results in a strong form of local search that makes it more likely that high-reward neighbours of known states will be found. For example, the following figure shows the chance of visiting all 64 mutations of a given state using UCT versus GA, over a given number of iterations.

Cameron Browne and Simon Colton are investigating MCTS as part of the EPSRC project UCT for Games and Beyond in collaboration with the universities of Essex and York, project partners from Reykjavik University (Iceland) and industry partners Nestorgames and AIFactory.

Publications

Browne, Cameron B; Powley, Edward; Whitehouse, Daniel; Lucas, Simon M; Cowling, Peter; Rohlfshagen, Philipp; Tavener, Stephen; Perez, Diego; Samothrakis, Spyridon; Colton, Simon

A Survey of Monte Carlo Tree Search Methods Journal Article

In: IEEE Transactions on Computational Intelligence and AI in Games, 4 (1), pp. 1–43, 2012.

Abstract | Links | BibTeX

Browne, Cameron

Towards MCTS for Creative Domains Inproceedings

In: 2nd International Conference on Computational Creativity, 2011.

Abstract | Links | BibTeX

The Essen Game Convention (Essen SPIEL’13)

In October 2013 we hired a UCT for Games and Beyond booth at the Essen Internationale Spieltage SPIEL’13. This is the world’s largest board game trade show with around 150,000 attendees each year. Our aim was to inform the public about UCT for board game AI and design, and disseminate our key findings from the project. Project members manning the booth were Cameron Browne from Goldsmiths, and Peter Cowling, Edward Powley, Daniel Whitehouse and Nick Sephton from the University of York. We were also joined by Industry Partner Néstor Romeral Andrés and his range of Nestorgames, including Yavalath, the first (and only) computer-invented game to be commercially published.

Our main prop for the booth was a giant Shibumi set made from 2 inch snooker balls. Shibumi is a game system designed specifically for the project, for an ongoing experiment in automated game design. The giant set proved a hit with visitors, catching the eye of everyone who walked past, most of whom would stop to admire it if not play with the balls and chat with us about it. Ken Shoda (Japanese journalist, Shibumi game tester, rule set translator and general friend of Nestorgames) also helped man the booth for several hours and explain Shibumi to visitors.

[metaslider id=277]