Memory-Efficient MCTS: Extending GRAVE for Resource-Constrained Game Playing

Paper: 2602.23318 Authors: Aloïs Rautureau, Tristan Cazenave, Éric Piette Categories: cs.AI

Abstract

Generalized Rapid Action Value Estimation (GRAVE) has proven to be a powerful Monte-Carlo Tree Search (MCTS) variant for General Game Playing, but its memory footprint limits practical deployment. This paper addresses GRAVE’s memory constraints by introducing three novel algorithms: GRAVE2 (two-level search), GRAVER (node recycling), and GRAVER2 (combined approach). These methods achieve dramatic reductions in stored nodes while preserving the algorithm’s playing strength, making GRAVE viable for memory-constrained environments such as embedded systems and mobile devices.

Key Contributions

• Introduction of GRAVE2, which implements a two-level search strategy to reduce memory overhead while maintaining search quality
• Development of GRAVER, a node recycling mechanism that reuses memory allocations across different search branches
• Presentation of GRAVER2, combining two-level search and node recycling for maximum memory efficiency
• Empirical demonstration that all three variants match GRAVE’s playing strength while drastically reducing the number of stored nodes
• Validation across multiple games in the Ludii General Game System, showing consistent performance improvements in memory-constrained scenarios

Methodology and Technical Approach

The core challenge addressed is GRAVE’s requirement to store AMAF (All Moves As First) statistics at each node, which accumulates win/visit counts for all actions encountered during playouts. While this information improves action selection, it creates substantial memory overhead proportional to the tree size and action space.

GRAVE2 implements a two-level search architecture where the first level performs shallow exploration with full GRAVE statistics, while the second level conducts deeper searches with reduced memory allocation. This hierarchical approach concentrates expensive memory usage at critical decision points near the root while using lighter-weight search in deeper portions of the tree.

GRAVER introduces node recycling by maintaining a pool of reusable node structures. When a subtree is abandoned during search, its nodes are returned to the pool rather than deallocated. This reduces allocation overhead and enables more efficient memory utilization, particularly in games with high branching factors where many nodes are created and discarded during search.

GRAVER2 synergistically combines both techniques, applying node recycling within the two-level search framework. The first level maintains a recycling pool for its full-featured nodes, while the second level uses a separate pool for its lightweight nodes, maximizing memory efficiency across both search levels.

Experimental Results and Performance Analysis

The authors evaluated their algorithms on a diverse set of games from the Ludii platform, including both deterministic games (like Chess variants and connection games) and stochastic games (dice games and card games). The experiments measured both playing strength (through head-to-head matches) and memory efficiency (nodes stored per search).

Results demonstrate that GRAVE2, GRAVER, and GRAVER2 achieve comparable win rates to standard GRAVE while reducing memory consumption by factors ranging from 2x to 10x depending on the game and time constraints. In games with large action spaces, the memory savings are particularly pronounced, with GRAVER2 showing the most consistent improvements.

The two-level search in GRAVE2 proves especially effective in games requiring deep tactical calculation, where the shallow first level quickly identifies promising lines while the deeper second level validates them efficiently. Node recycling in GRAVER shows benefits across all game types, with particularly strong performance in games with repetitive position structures where node reuse is frequent.

Interestingly, in some games, the memory-constrained variants slightly outperform standard GRAVE, suggesting that the architectural constraints impose a beneficial regularization effect that prevents over-exploration of unpromising branches.

Implications for General Game Playing and Beyond

This work has significant implications for deploying MCTS-based agents in resource-constrained environments. The ability to maintain competitive performance while reducing memory footprint by an order of magnitude opens new application domains for general game playing systems, including mobile gaming, embedded systems, and large-scale game servers running multiple concurrent instances.

The techniques introduced are not limited to GRAVE but can be adapted to other MCTS variants that maintain additional statistics at nodes, such as RAVE (Rapid Action Value Estimation) and progressive history-based methods. The node recycling approach, in particular, represents a general optimization applicable to any tree search algorithm with dynamic node allocation.

For the broader AI community, this research demonstrates that algorithmic efficiency improvements can sometimes match or exceed the benefits of simply adding more computational resources. The careful engineering of memory management strategies proves as important as the underlying search algorithm itself.

Takeaways

1. GRAVE2, GRAVER, and GRAVER2 successfully reduce MCTS memory requirements by 2-10x while maintaining playing strength equivalent to standard GRAVE
2. Two-level search architectures effectively balance memory efficiency with search quality by concentrating resources at critical decision points
3. Node recycling provides consistent memory benefits across diverse game types and can be combined with other optimization techniques
4. Memory-constrained algorithm variants can sometimes outperform their unrestricted counterparts through implicit regularization effects
5. These techniques enable practical deployment of sophisticated MCTS variants in resource-limited environments previously unsuitable for such algorithms