Monte Carlo Permutation Search

Tristan CazenavearXiv 2025 · DOI · arXiv

Introduction

Monte Carlo Tree Search (MCTS) has been a cornerstone of artificial intelligence in games since its pivotal role in the success of AlphaGo. However, modern high-performance implementations typically rely on massive neural networks and extensive pre-training. In the domain of General Game Playing (GGP), where rules are often revealed only at runtime, such pre-training is impossible. This necessitates "zero-knowledge" search algorithms that can efficiently extract information from random playouts.

In the paper "Monte Carlo Permutation Search," Tristan Cazenave introduces Monte Carlo Permutation Search (MCPS). This variant of MCTS rethinking how playout data is utilized by incorporating "permutation statistics," effectively outperforming current state-of-the-art methods like GRAVE without the need for manual hyperparameter tuning.

The Challenge of Playout Noise

Standard MCTS learns by simulating random games (playouts) and recording which moves lead to victories. Because these playouts are inherently noisy, researchers developed heuristics such as AMAF (All Moves As First) and GRAVE to accelerate convergence. These methods operate on the assumption that a move that is good later in a playout might also be a strong candidate for the current search node.

Despite their success, these algorithms suffer from two primary drawbacks:

  1. Hyperparameter Sensitivity: They rely on "magic numbers" (e.g., bias and ref) that require extensive tuning for different games.
  2. Order Sensitivity: They often fail to exploit the "transpositional" nature of games, where reaching the same set of moves in a different order results in the same board state.

Methods: The MCPS Framework

MCPS addresses these issues by introducing a third source of information: Permutation Statistics. The algorithm balances three distinct data streams:

  1. Standard Statistics ($Q$): Success rates for the exact sequence of moves currently being explored.
  2. AMAF/RAVE Statistics ($\tilde{Q}$): Success rates for a move appearing anywhere in a playout.
  3. Permutation Statistics ($\hat{Q}$): Success rates for playouts that contain all the moves on the current search path, regardless of their chronological order.

Analytical Weighting

A key innovation of MCPS is its move away from heuristic tuning. By utilizing a mathematical derivation to minimize the Mean Squared Error (MSE) of the value estimate, Cazenave developed formulas for weights ($\alpha, \beta, \gamma$) that adapt automatically based on the number of playouts. This makes MCPS effectively parameter-free regarding the bias term, allowing it to generalize across different games without manual intervention.

Abstract Codes

To further enhance the utility of permutation statistics, the paper explores Abstract Codes. Instead of identifying a move by rigid coordinates, the algorithm tracks moves by their functional meaning (e.g., "Unit A attacks Unit B"). This abstraction allows the algorithm to aggregate statistics across functionally similar moves, significantly accelerating the learning process in complex environments.

Experimental Evaluation

The algorithm was tested across a diverse battery of environments, including classic board games (Hex, Atarigo, Breakthrough, Gomoku) and custom environments such as a tactical video game inspired by Teamfight Tactics (TFT) and multi-player variants of Nogo.

Key Results

  • Superiority in Board Games: MCPS consistently outperformed the GRAVE algorithm in every two-player board game tested. In Hex 7x7, MCPS achieved a 77% win rate against GRAVE at 5,000 playouts. The algorithm is particularly effective in Hex because the game's win condition is inherently permutation-invariant (the order of stones placed does not change the connectivity).
  • Scaling Performance: As the number of playouts increased from 1,000 to 5,000, the performance gap between MCPS and GRAVE widened, suggesting that MCPS scales more effectively with additional computational resources.
  • Tactical Success: In the TFT-inspired tactical game, the combination of MCPS and specific abstract codes (encoding attacker, move, and health) resulted in a dominant 84.5% win rate against standard GRAVE.
  • Multi-player Dynamics: In 3-player games, win rates converged toward 33%. The author observed that in these settings, "implicit coalitions" often form where trailing players target the leader, which can mask the individual strength of the search algorithm.

Limitations and Future Directions

While MCPS represents a significant step forward, it introduces certain trade-offs. Calculating permutation statistics is computationally more intensive than standard MCTS, requiring the maintenance of move arrays and logical operations during the search. Additionally, while the analytical weights perform well in practice, the current formulas do not yet strictly guarantee "consistency" (the property where standard statistics completely dominate as playouts approach infinity).

Future work may focus on optimizing the computational overhead of permutation tracking and refining the weighting formulas to ensure theoretical consistency in the infinite limit.

Conclusion

Monte Carlo Permutation Search demonstrates that rethinking the statistical foundations of MCTS can yield significant performance gains in zero-knowledge environments. By leveraging the order-independent nature of many game states and replacing heuristic tuning with analytical optimization, MCPS provides a robust, high-performance alternative for General Game Playing.

Summary updated

Abstract

We propose Monte Carlo Permutation Search (MCPS), a general-purpose Monte Carlo Tree Search (MCTS) algorithm that improves upon the GRAVE algorithm. MCPS is relevant when deep reinforcement learning is not an option or when the computing power available before play is not substantial, such as in General Game Playing. The principle of MCPS is to include in the exploration term of a node the statistics on all the playouts that contain all the moves on the path from the root to the node. We test MCPS on a variety of games: Hex, Go, AtariGo, NoGo and a Wargame. MCPS almost always outperforms GRAVE. We also provide a mathematical derivation of the formulas used for weighting the three sources of statistics. These formulas are an improvement on the GRAVE formula since they no longer use the bias hyperparameter of GRAVE.
BibTeX
@misc{cazenave2025monte,
  author = {Tristan Cazenave},
  title = {{Monte Carlo Permutation Search}},
  year = {2025},
  eprint = {2510.06381},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.06381},
}
Figure