Abstract
Monte Carlo Tree Search (MCTS) is the state of the art algorithm for many games including the game of Go and General Game Playing (GGP). The standard algorithm for MCTS is Upper Confidence bounds applied to Trees (UCT). For games such as Go a big improvement over UCT is the Rapid Action Value Estimation (RAVE) heuristic. We propose to generalize the RAVE heuristic so as to have more accurate estimates near the leaves. We test the resulting algorithm named GRAVE for Atarigo, Knighthrough, Domineering and Go.
Introduction
Monte Carlo Tree Search (MCTS) has revolutionized game AI, but it faces a fundamental "cold start" problem. To make good decisions, the algorithm needs to run many simulations (playouts) from a given board position. Deep in the search tree—near the "leaves"—nodes often have very few playouts, making their statistical estimates noisy and unreliable.
The standard solution is RAVE (Rapid Action Value Estimation), which uses AMAF (All Moves As First) statistics. AMAF essentially says: "If a move was good later in a random playout, it was probably a good move to start with." While RAVE helps, its estimates are still local to a specific node. If that node has only been visited twice, its RAVE values are still shaky. The author, Tristan Cazenave, tackles this by asking: Can we use more stable statistics from higher up in the tree to guide us when local data is lacking?
The GRAVE Algorithm
The paper introduces GRAVE (Generalized Rapid Action Value Estimation), which addresses the noise in leaf nodes by "borrowing" move statistics from more reliable ancestor nodes.
Core Innovation: The ref Threshold
GRAVE introduces a threshold parameter, ref. When the algorithm evaluates a move at a specific node, it checks if that node has at least ref playouts.
- Borrowing from Ancestors: If the current node is "under-sampled" (playouts <
ref), GRAVE doesn't just rely on local noisy data. Instead, it uses the AMAF statistics from the closest ancestor in the tree that does meet therefthreshold. - Stability vs. Specificity: An ancestor node represents a more general state but has many more associated playouts, providing a more stable (if slightly less specific) estimate of which moves are generally "good" in this region of the search space.
- Generalization: If you set
refto zero, GRAVE behaves exactly like standard RAVE, making it a true generalization of the existing state-of-the-art.
The algorithm uses a transposition table to store these statistics (wins, playouts, AMAF wins, and AMAF playouts) and dynamically updates a tref (reference) pointer as it descends the tree.
Experimental Results
GRAVE was tested across a diverse set of board games to prove its general-purpose utility. The experiments compared GRAVE against both standard UCT and finely-tuned RAVE implementations.
Performance in Atarigo
In Atarigo 8x8, GRAVE achieved a peak win rate of 88.4% against the best-tuned RAVE. The performance is sensitive to the ref and bias parameters, as shown in the table below.
Performance in Knightthrough
Knightthrough, a chess-like game, also saw significant improvements. GRAVE achieved a win rate of 67.8% against RAVE. Detailed results for various parameter configurations are shown in Table 8.
Summary of Key Results
GRAVE showed significant performance gains over RAVE across almost every test case:
- Go 19x19: With 1,000 playouts, GRAVE won 81.8% of games against RAVE.
- Domineering 8x8: GRAVE won 62.4% against RAVE.
- Three Color Go: In this more complex multi-player setting, GRAVE maintained a strong lead, winning 57.17% of games (where a "fair" score among three equal players would be 33.3%).
Conclusion
GRAVE demonstrates that "borrowing" ancestor statistics is a robust way to improve MCTS performance without needing game-specific knowledge. By providing better estimates near the leaves, GRAVE allows the search to navigate deep tactical sequences more effectively than standard RAVE. Future work includes exploring how GRAVE's ancestor-based estimation interacts with the policy and value networks used in modern deep learning agents.
Summary updated