Mark Winands (DKE, Maastricht University)

On December 2, in collaboration with SIKS and the BNVKI, the Department of Knowledge Engineering (DKE) at Maastricht University organized a symposium called “Monte-Carlo Search is Everywhere”. The symposium was held in honour of Pim Nijssen’s Ph.D. defence. The purpose of the symposium was to give an overview on recent developments on the topic of Monte-Carlo search techniques for different classes of games (one-, two- or multi-player games, sequential or simultaneous, stochastic or deterministic, and perfect- or imperfect-information games). Approximately 25 participants attended the talks. An outline of the four talks is given below.

Marc Lanctot (UM)

Marc Lanctot stated his presentation by briefly introducing Monte-Carlo Tree Search (MCTS) to the audience. Next, he discussed its application for a various range of domains. Most of these applications assumed sequential movement.  Therefore he focused in his presentation on the adaptation of MCTS to simultaneous-move games. He discussed alternatives to the UCT selection algorithm such as Exp3, Regret Matching, and ε-minmax. He proposed a new algorithm, called Online Outcome Sampling (OOS), which approaches a Nash equilibrium strategy over time. Marc compared head-to-head performance of several MCTS variants in Goofspiel and Tron.

Tristan Cazenave (Université Paris-Dauphine)

Tristan Cazenave presented his Nested Monte-Carlo Search algorithm, which is especially suited for puzzle, scheduling and optimization problems. Nested Monte-Carlo Search combines nested calls with randomness in the playouts and memorization of the best move sequence. In nested rollouts the base rollouts can be based on a heuristic. When the base level does not use a heuristic but selects the moves uniform randomly, it is possible that a nested search gives worse results than a lower level search. It is then useful to memorize the best sequence found so far in order to follow it when the randomized searches give worse results than the best sequence.  Next, Tristan discussed the performance of the algorithm for three different puzzles: Morpion Solitaire, SameGame and 16×16 Sudoku. He continued to show applications of his algorithm in optimization problems such as to minimize passengers’ waiting times at the bus, expression discovery, traveling salesman problems with time windows. Finally, Nested Monte-Carlo Search is also used in his General-Game Playing agent Ary forhandling one-player games.

Hendrik Baier (UM)

The playouts allow MCTS to take distant consequences of moves into account, giving MCTS a strategic advantage in many domains over traditional depth-limited minimax search with alpha-beta pruning. However, MCTS builds a highly selective tree and can therefore miss crucial moves and fall into traps in tactical situations. Classic minimax search may less suffer from this weakness. Hendrik Baier discussed MCTS-minimax hybrids that employ shallow minimax searches within the MCTS framework.  He proposed three approaches that use minimax in the selection/expansion phase, the playout phase, and the backpropagation phase of MCTS. Without requiring domain knowledge in the form of evaluation functions, these hybrid algorithms are a first step at combining the strategic strength of MCTS and the tactical strength of minimax. Their effectiveness was shown in Connect-4 and Breakthrough.

Peter Cowling (University of York)

Peter Cowling discussed MCTS for games with hidden information and uncertainty. He proposed information set MCTS (ISMCTS) method to handle this. Instead of searching minimax trees of game states, ISMCTS explores trees of information sets, more directly analyzing the true structure of the game. Peter discussed first the performance of the search methods in the following three domains Lord of the Rings: The Confrontation, Phantom (4, 4, 4) and the card game Dou Di Zhu. Next, he discussed how ISMCTS can be applied to create engaging AI for a popular commercial mobile phone game: Spades by AI Factory.The MCTS-based player performs better by a statistically significant margin, than the existing knowledge-based AI for Spades. To ensure a high quality AI opponent in a commercial game, search based methods require some tweaking in order to ensure the AI behaves plausibly in all situations.  It was not sufficient for the AI to be strong empirically, it had to be perceived as strong by the human player as well .By injecting specific knowledge the MCTS-based AI was be modified to behave more plausibly without compromising playing strength.

The presentations can be downloaded at: https://project.dke.maastrichtuniversity.nl/games/symposium2013/.