Generalized Rapid Action Value Estimation (GRAVE) has been shown to be a strong variant within the Monte-Carlo Tree Search (MCTS) family of algorithms for General Game Playing (GGP). However, its reliance on storing additional win/visit statistics at each node makes its use impractical in memory-constrained environments, thereby limiting its applicability in practice. In this paper, we introduce the GRAVE2, GRAVER and GRAVER2 algorithms, which extend GRAVE through two-level search, node recycling, and a combination of both techniques, respectively. We show that these enhancements enable a drastic reduction in the number of stored nodes while matching the playing strength of GRAVE.
Figures & tables
Figure 1: Relationships between GRAVE, GRAVE 2 , GRAVER and GRAVER 2 . N indicates the total number of nodes stored, P the total number of playouts performed, and Nsec the nodes stored in the second-level tree.
Figure 2: Forward node sharing in GRAVE 2 . The selection path in the top-level tree is fixed while the second-level search is running, and the latter may use AMAF values aggregated in the top-level tree to guide its exploration as long as the second-level root has fewer visits than the parameterized reference threshold. Values obtained from playouts in the second-level tree are backpropagated to the top-level tree after each iteration, rather than in a single batch once the second-level search terminates. If a child of the currently referenced node exceeds the reference threshold, it becomes the new referenced node.
Figure 3: Winrates of GRAVE 2 with and without forward sharing and UCT² against GRAVE with P=N=10,000 . The dotted lines indicate the 95% confidence interval of the winrate of GRAVE against itself, representing the region in which compared algorithms can be considered to have playing strength equal to GRAVE.
Table 1: Winrate of GRAVE 2 with forward sharing for varying node pool sizes and λ values against GRAVE running for P=10,000 . Confidence intervals are omitted for clarity, and lie in the range [4.0%,4.4%] .
Figure 4: Winrates of GRAVER and UCT with node recycling against GRAVE with P=10,000 . The node pool size used is presented on a logarithmic scale. The red dashed line indicates the threshold N=10,000 , beyond which all expanded nodes can be stored and node recycling no longer takes effect.
Figure 5: Winrate of GRAVER 2 against GRAVE ( P=10,000 ), varying the ratio of playouts to stored nodes in the top-level tree ( Left ) and second-level tree ( Right ).
Figure 6: Winrate of GRAVER 2 against GRAVE ( P=10,000 ), varying the ratio of playouts to stored nodes in both the top and second-level trees. The values are given with a confidence interval of ±4.2 .
Monte Carlo Tree Search is a cornerstone algorithm for online planning, and its root-parallel variant is widely used when wall clock time is limited but best performance is desired. In environments with continuous action spaces, how to best aggregate statistics from different threads is an important yet underexplored question. In this work, we introduce a method that uses Gaussian Process Regression to obtain value estimates for promising actions that were not trialed in the environment. We perform a systematic evaluation across 6 different domains, demonstrating that our approach outperforms existing aggregation strategies while requiring a modest increase in inference time.
Junlin Xiao, Victor-Alexandru Darvariu, Bruno Lacerda +1
School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen · Oxford Robotics Institute, Department of Engineering Science, University of Oxford · Stateful Robotics
Combining search with function approximation has driven major advances in game-playing programs, making self-play algorithms more competitive than ever. Still, the computational overhead of the most popular methods, based on Monte Carlo Tree Search (MCTS), can be substantial. In this work, we investigate whether simpler methods remain competitive in non-trivial, moderately sized games such as Connect Four, Hex(7x7) and synthetic games. We train a minimal self-play implementation of Approximate Value Iteration (AVI) and use ground-truth oracles for exact evaluation. Contrary to expectations, our results demonstrate the surprising effectiveness of AVI: it learns more accurate value functions than those learned by AlphaZero, while its one-step-lookahead greedy policies remain competitive with MCTS-based policies at substantially lower training and inference costs. Preliminary experiments on Othello and Go(9x9) show that AVI trains stably on larger games and learns effective value functions. These findings suggest that the success of MCTS-based methods may have eclipsed simpler approaches that have become increasingly practical with modern deep-learning tools.
Raphael Boige, Amine Boumaza, Bruno Scherrer
Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Monte Carlo Tree Search (MCTS) and every-visit Monte Carlo (MC) control are usually presented as different methods. MCTS is described in the language of search (selection, expansion, simulation, and backup), whereas MC control is described in the language of reinforcement learning (trajectory sampling, return estimation, action-value updating, and policy improvement). This note argues that, at the level of trajectory generation and action-value updating, the distinction is largely terminological. The tree policy and rollout policy can be viewed as the learned and not-yet-learned parts of a single evolving policy; expansion corresponds to first visit and initialization; and backup is the ordinary every-visit Monte Carlo update. Under this interpretation, the four stages of MCTS reduce to two basic operations: trajectory sampling under the current policy and every-visit Monte Carlo updating. In this sense, MCTS is simply every-visit Monte Carlo control expressed in the language and data structure of search. The purpose of this note is expository: to make this equivalence explicit and easier to recognize.