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.

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.

Pictures from the Event

The giant snooker ball Shibumi set. We call this set Shibumo (= Shibumi Sumo).

Some Shibumi action. Visitors were asked to play with the set and devise new games for it, to add to the database of games for the game design experiment.

Decisions, decisions... The beauty of the set is that the 3D stacking can trigger surprising behaviour which may not be obvious from looking at the simple 4x4 board. Shibumi games can be trickier than you'd expect! This emergent property is exactly what we look for in new Shibumi games, and is the epitome of the original concept shibumi in Japanese aesthetics.

Ken demos the giant Shibumi set. That's a standard 1 inch board on the left.

Serious gamers in action. The snooker ball set was a hit with all ages.

Ed and Dan entertain (and educate) a customer. Dan is manually demonstrating one iteration of a UCT playout... which is a polite way of saying he's making a random move while learning about the game.

Ed mans the desk with Nick looking on.

Nestor lures passing gamers into the booth and doesn't let them escape until hearing about UCT.

A happy Yavalath player. Surprisingly, there has been no backlash over the fact that Yavalath was invented by computer — players love it! Visitors to the booth included several German doctoral psychology students fascinated by the idea that a computer program could invent a game, and more importantly recognise that it would be interesting for humans to play. Automated game design has previously been done using an evolutionary approach, but we are investigating the use of UCT for this purpose instead, exploiting its inherent local search to achieve a more thorough exploration of the game design space than is likely using evolution.

Gaming... it's all about trust.