Search

Monte Carlo Tree Search (MCTS) is a popular approach for tree search in a variety of games. While MCTS allows for fine-grained time control, not much has been published on time management for MCTS programs under tournament conditions. This paper first investigates the effects of various time-management strategies on playing strength in the challenging game of Go. A number of domain-independent strategies are then tested in the domains Connect-4, Breakthrough, Othello, and Catch the Lion. We consider strategies taken from the literature as well as newly proposed and improved ones. Strategies include both semi-dynamic strategies that decide about time allocation for each search before it is started, and dynamic strategies that influence the duration of each move search while it is already running. Furthermore, we analyze the effects of time management strategies on the distribution of time over the moves of an average game, allowing us to partly explain their performance. In the experiments, the domain-independent strategy STOP provides a significant improvement over the state of the art in Go, and is the most effective time management strategy tested in all five domains.

The nine papers in this special section focus on the development of physics-based simulation video games (PBSG). The focus is on artificial intelligence for specific PBSGs competitions such as Angry Birds and computational pool, as well as on further developments of physics simulators in order to launch the next generation of PBSGs.

This paper describes how Monte Carlo tree search (MCTS) can be applied to the hide-and-seek game Scotland Yard. This game is essentially a two-player game in which the players are moving on a graph-based map. First, we discuss how determinization is applied to handle the imperfect information in the game. We show how using determinization in a single tree performs better than using separate trees for each determinization. We also propose a new technique, called location categorization, that biases the possible locations of the hider. The experimental results reveal that location categorization is a robust technique, and significantly increases the performance of the seekers. Next, we describe how to handle the coalition of the seekers by using coalition reduction. This technique balances each seeker's participation in the coalition. Coalition reduction improves the performance of the seekers significantly. Furthermore, we explain how domain knowledge is incorporated by applying epsilon-greedy playouts and move filtering. Finally, we compare the MCTS players to minimax-based players, and we test the performance of our MCTS player against a commercial Scotland Yard program on the Nintendo DS. Based on the results, we may conclude that the MCTS-based hider and seekers play at a strong level.

The aim of general game playing (GGP) is to create programs capable of playing a wide range of different games at an expert level, given only the rules of the game. The most successful GGP programs currently employ simulation-based Monte Carlo tree search (MCTS). The performance of MCTS depends heavily on the simulation strategy used. In this paper, we introduce improved simulation strategies for GGP that we implement and test in the GGP agent CADIAPLAYER, which won the International GGP competition in both 2007 and 2008. There are two aspects to the improvements: first, we show that a simple epsilon-greedy exploration strategy works better in the simulation play-outs than the softmax-based Gibbs measure currently used in CADIAPLAYER and, second, we introduce a general framework based on N-grams for learning promising move sequences. Collectively, these enhancements result in a much improved performance of CADIAPLAYER. For example, in our test suite consisting of five different two-player turn-based games, they led to an impressive average win rate of approximately 70%. The enhancements are also shown to be effective in multiplayer and simultaneous-move games. We additionally perform experiments with the last-good-reply policy (LGRP). The LGRP combined with N-grams is also tested. The LGRP has already been shown to be successful in Go programs and we demonstrate that it also has promise in GGP.

The success of Monte Carlo tree search (MCTS) in many games, where alpha beta-based search has failed, naturally raises the question whether Monte Carlo simulations will eventually also outperform traditional game-tree search in game domains where alpha beta-based search is now successful. The forte of alpha beta-based search are highly tactical deterministic game domains with a small to moderate branching factor, where efficient yet knowledge-rich evaluation functions can be applied effectively. In this paper, we describe an MCTS-based program for playing the game Lines of Action (LOA), which is a highly tactical slow-progression game exhibiting many of the properties difficult for MCTS. The program uses an improved MCTS variant that allows it to both prove the game-theoretical value of nodes in a search tree and to focus its simulations better using domain knowledge. This results in simulations superior in both handling tactics and ensuring game progression. Using the improved MCTS variant, our program is able to outperform even the world's strongest alpha beta-based LOA program. This is an important milestone for MCTS because the traditional game-tree search approach has been considered to be the better suited for playing LOA.