Mining Expert Play to Guide Monte Carlo Search in the Opening Moves of Go

Erik S. Steinmetz, Maria L. GiniIJCAI 2015

Introduction

The game of Go presents a massive computational challenge due to its immense branching factor. At the start of a game, there are 361 possible moves, creating a search space that dwarfs that of Chess. While Monte Carlo Tree Search (MCTS) revolutionized computer Go by using stochastic simulations (playouts) to evaluate positions, it inherently struggles during the "opening" phase. Because the game tree is at its widest and deepest, MCTS often wastes thousands of playouts on moves that a human novice would instantly recognize as strategically poor.

Traditional "opening books" attempt to solve this by storing sequences of professional moves. However, these databases are brittle: if an opponent makes a single move not found in the records, the engine is "out of book" and must fall back to a raw, unguided search. This paper introduces SMARTSTART, a method designed to bridge the gap between rigid move-matching and unguided search by using expert knowledge that generalizes across similar board positions.

The SMARTSTART Methodology

SMARTSTART replaces rigid exact-match lookups with a similarity-based approach to guide the early game search. The process involves several key steps:

  1. Vector Representation: Each board position is converted into a 722-element vector, with two elements per intersection representing the presence or absence of black or white stones.
  2. Clustering: Using the Cluto clustering toolkit, the authors grouped thousands of professional board positions from the "Games of Go on Disk" collection into clusters (ranging from 64 to 256 groups) based on cosine similarity. Each cluster center represents a "typical" opening scenario.
  3. Matching: During live play, the engine calculates the cosine similarity between the current board and the pre-computed cluster centers. It then identifies the moves professional players made when they were in that specific cluster neighborhood.

To handle the eight-fold symmetry of the Go board (rotations and reflections) without impacting real-time performance, the authors expanded their database eight-fold offline.

Integration with MCTS

The authors explored two primary ways to integrate these expert suggestions into the MCTS framework:

  • Filtering: The engine is strictly forbidden from searching any move not suggested by the expert cluster, effectively pruning the search tree.
  • Biasing (Priors): The engine can search any move, but expert-suggested moves are given "virtual wins" (e.g., starting with 40 wins out of 40 visits) to encourage the search to prioritize them.
Accuracy of expert move prediction by cluster size over move number.

As shown in Figure 1, the effectiveness of clustering is highest in the very early moves. The authors found that the predictive power of these clusters drops off significantly after move 12. As stones spread across the board, configurations become too unique for simple similarity clusters to provide reliable guidance.

Experimental Results

The SMARTSTART method was integrated into two engines: Orego (Java-based) and Fuego (high-performance C++). These were tested against established opponents like GNU Go and Pachi.

The results demonstrated statistically significant improvements. For Orego playing against GNU Go, SMARTSTART filtering up to move 12 increased the win rate from 40.41% to 41.74% (p=0.0119). The gains were even more pronounced in the high-performance Fuego engine.

Win rates of Fuego with SMARTSTART against Pachi.

As detailed in Figure 4, Fuego's win rate against Pachi rose from a baseline of 54.27% to 55.35% using filtering, and to 55.84% using biasing (p=0.0058). Notably, in head-to-head tests, a standard opening book provided no statistically significant improvement to Fuego, whereas SMARTSTART's generalized approach did.

Discussion and Future Work

A key advantage of SMARTSTART is its low computational overhead. Using 128 clusters resulted in less than a 5% slowdown in playouts per second, a trade-off easily justified by the higher quality of the search. By reducing the number of candidate moves from approximately 350 down to 34 in the opening, the engine can allocate its "thinking time" much more effectively.

Future work may involve dynamic cluster granularity, where the number of clusters increases as the game progresses to capture more specific board states. Additionally, scaling the training data from 1,000 games to tens of thousands could further improve the precision of the move suggestions.

Summary updated

BibTeX
@inproceedings{steinmetz2015mining,
  author = {Erik S. Steinmetz and Maria L. Gini},
  title = {{Mining Expert Play to Guide Monte Carlo Search in the Opening Moves of Go}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure