🤖 machine learning

Monte Carlo Permutation Search

This paper introduces Monte Carlo Permutation Search (MCPS), a general-purpose MCTS algorithm that outperforms the GRAVE algorithm in games like Hex and Go by incorporating path-wide playout statistics into the exploration term and deriving a new weighting formula that eliminates the need for GRAVE's bias hyperparameter.

Original authors: Tristan Cazenave

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tristan Cazenave

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a complex puzzle, like a game of Go or Hex, but you don't have a supercomputer or a trained AI to tell you the best move. Instead, you have to rely on "guessing and checking" by playing out thousands of random future scenarios in your head. This is how a computer program called Monte Carlo Tree Search (MCTS) works.

For a long time, the best way to do this guessing was an algorithm called GRAVE. It was good at looking at the past to predict the future, but the author of this paper, Tristan Cazenave, thought, "We can do better."

He created a new algorithm called MCPS (Monte Carlo Permutation Search). Here is how it works, explained simply:

The Three Ways to Look at the Past

To decide which move to make next, MCPS looks at its history of random games (called "playouts") in three different ways. Think of these as three different lenses on a camera:

The "Exact Path" Lens (Standard View):
This looks at games where the player made the exact same sequence of moves to get to the current spot, and then made the specific move we are testing.
- Analogy: "I walked down Main Street, turned left, and then bought a coffee. How did that go?"
The "Order Doesn't Matter" Lens (The GRAVE Upgrade):
This looks at games where the player made the same moves to get to the spot, but the order was slightly different, and the specific move we are testing appeared later in the game.
- Analogy: "I bought a coffee, then walked down Main Street, then turned left. It's the same ingredients, just a different recipe order. Did it still taste good?"
- Why it helps: In many games, the order you place your pieces doesn't change the final board state. So, this lens lets the computer learn from more games, not just the ones that matched the exact order.
The "Permutation" Lens (The New MCPS Secret Sauce):
This is the new addition. It looks at any game where the player used the exact same set of moves (the path to the current spot + the new move), regardless of the order they happened in.
- Analogy: "I used a hammer, a screwdriver, and a nail to build a shelf. It doesn't matter if I hammered first or screwed first; if I used those three tools, the shelf got built. How did that combination work out?"
- The Catch: In some games (like AtariGo), the order does matter because the game can end early (like capturing a stone). MCPS handles this by being smart about how it groups these moves.

The "Magic Formula"

The paper explains that MCPS doesn't just pick one of these views; it mixes them together. The author did some math to figure out the perfect way to blend these three sources of information.

Think of it like making a smoothie. You have three fruits (the three statistics). GRAVE used a fixed recipe that sometimes tasted off. MCPS uses a mathematically perfect recipe that automatically adjusts the amounts based on how much data it has for each fruit. The best part? It doesn't need a "taste test" (a human setting a bias parameter) to get it right; the math does it automatically.

How It Performed in the Real World

The author tested MCPS against the old champion (GRAVE) on five different types of games:

Hex (The Perfect Match): In this game, the order of moves never changes the final board. MCPS was a huge winner here, especially on larger boards. It was like having a map that showed every possible path, not just the one you took.
Go (The Deep Thinker): On small boards, they were about equal. But on large boards, as the computer was given more time to think, MCPS pulled ahead. It was better at using that extra time to dig deeper into the most promising lines of play, whereas the old method got stuck exploring shallow options.
AtariGo (The Fast Finisher): This is a game where the first capture wins. Here, the order does matter. Surprisingly, MCPS still won, but its advantage was biggest on small boards where the game ends quickly. On big boards, the game gets too long for the "order doesn't matter" trick to help as much.
NoGo (The Consistent Winner): This is a game where you lose if you capture. MCPS won almost everywhere, consistently beating the old method by a solid margin.
Wargame (The Speed Demon): In this custom strategy game, MCPS didn't just play better; it played faster. It simulated games that ended sooner and found the winning strategy more quickly, allowing it to run more simulations in the same amount of time.

The Bottom Line

The paper claims that MCPS is a smarter, more efficient way for computers to play games without needing deep learning or massive training.

It works by realizing that in many games, the set of moves you make is more important than the order you make them in. By counting all the times a specific set of moves appeared in random games, MCPS builds a better "intuition" about which moves are good. It's like a detective who realizes that even if the suspects arrived in a different order, the fact that they were all at the scene is the real clue.

The result is a general-purpose tool that beats the previous best method in almost every scenario tested, making it a powerful new standard for game-playing AI when you don't have a supercomputer at your disposal.

Technical Summary: Monte Carlo Permutation Search (MCPS)

Problem Statement

Monte Carlo Tree Search (MCTS) is a dominant algorithm for game playing and decision-making, particularly in domains where deep reinforcement learning is infeasible due to lack of training data or computational constraints (e.g., General Game Playing). While MCTS variants like GRAVE (Generalized RAVE) have improved upon standard UCT by utilizing statistics from ancestor nodes and All-Moves-As-First (AMAF) heuristics, they rely on two primary sources of information: statistics from playouts starting with a specific move and statistics from playouts where the move appears later.

The paper identifies a limitation in existing approaches: they do not fully exploit the statistical information contained in playouts where the sequence of moves leading to a node appears in a different order. In games with commutative properties (like Hex), any permutation of moves leads to the same state. In non-commutative games (like AtariGo), permutations may lead to different states, yet the paper hypothesizes that the statistical value of the moves remains informative. The goal is to develop a general-purpose MCTS algorithm that improves upon GRAVE without requiring problem-specific tuning, model training, or bias hyperparameters.

Methodology

Core Concept: Monte Carlo Permutation Search (MCPS)

MCPS introduces a third source of statistics to the node evaluation process. To evaluate an action $a$ at a node $s$ reached by a path $(a_0, a_1, \dots, a_d)$ , MCPS aggregates data from three distinct sets of playouts:

Direct Statistics ( $Q$ ): Playouts that start with the path to $s$ followed immediately by action $a$ .
AMAF Statistics ( $\tilde{Q}$ ): Playouts that start with the path to $s$ , where action $a$ appears later in the sequence (standard GRAVE approach).
Permutation Statistics ( $\hat{Q}$ ): Playouts that contain the set of moves $\{a_0, a_1, \dots, a_d, a\}$ in any order and at any positions.

Mathematical Derivation of Weights

The paper provides a mathematical derivation for combining these three estimators. Assuming the statistics are independent, the authors derive the weights that minimize the variance of the combined estimator.
Let $n$ , $\tilde{n}$ , and $\hat{n}$ be the sample counts for the three statistics. The optimal weights ( $\beta, \tilde{\beta}, \hat{\beta}$ ) are proportional to their sample counts:
$\beta = \frac{n}{n + \tilde{n} + \hat{n}}, \quad \tilde{\beta} = \frac{\tilde{n}}{n + \tilde{n} + \hat{n}}, \quad \hat{\beta} = \frac{\hat{n}}{n + \tilde{n} + \hat{n}}$
This convex combination eliminates the need for the bias hyperparameter used in the GRAVE algorithm, providing a parameter-free weighting scheme.

Algorithmic Implementation

Selection: The value of a move is calculated as the weighted average of the three estimators.
Permutation Statistics Computation: To efficiently compute $\hat{Q}$ , the algorithm uses a sliding window of recent playouts (default $W=10,000$ ) represented as bitsets. For a node $s$ , the algorithm intersects the bitsets of all moves on the path to $s$ to identify playouts containing the full path sequence. It then intersects this result with the bitset of the candidate move $a$ to isolate the relevant playouts. This is performed using 64-bit word operations (POPCOUNT and bit-scan) for efficiency.
Freezing: Once a node accumulates a threshold number of visits ( $\rho=30$ ), its permutation statistics are computed and "frozen." This node then acts as the reference for its entire subtree, allowing descendants to inherit these statistics without recomputing them.
Move Coding: To enable knowledge transfer between different board positions, moves are mapped to integer codes based on game-relevant features (e.g., player, destination cell, combat trigger) rather than exact coordinates.

Key Contributions

Algorithmic Extension: The proposal of MCPS, which integrates permutation statistics into the MCTS selection rule, extending the GRAVE algorithm.
Theoretical Improvement: A derivation of weighting formulas that minimize estimator variance under independence assumptions, removing the need for the GRAVE bias hyperparameter.
Efficient Implementation: A method for computing permutation statistics using bitsets and sliding windows, allowing the algorithm to handle the combinatorial explosion of move orders efficiently.
General Applicability: Demonstration that the algorithm works across diverse game types (commutative and non-commutative) without specific parameter tuning.

Experimental Results

The authors tested MCPS against GRAVE across five games: Hex, Go, AtariGo, NoGo, and a custom asymmetric Wargame. In all cases, 800 games were played per configuration (400 with each algorithm playing first) under identical time budgets.

Hex: MCPS outperforms GRAVE on boards $7\times7$ and larger, with winrates reaching 70–76% on larger boards. On $5\times5$ , the overhead of bitsets slightly disadvantages MCPS. The advantage grows with board size because MCPS builds deeper trees.
Go: MCPS outperforms GRAVE on boards $7\times7$ and larger. Notably, on larger boards ( $13\times13$ , $15\times15$ ), the winrate gap widens significantly as time budget increases (up to 63.75% at 2s). MCPS consistently builds deeper trees with more time, whereas GRAVE's tree depth often stagnates or decreases.
AtariGo: MCPS outperforms GRAVE in all configurations, with the largest gains on small boards ( $5\times5$ , $7\times7$ ). The advantage diminishes on larger boards because the game often terminates before the search reaches the terminal state, limiting the benefit of deeper trees.
NoGo: MCPS shows the most uniform improvement, outperforming GRAVE in every cell with winrates between 57% and 69%. The improvement is consistent across board sizes and time budgets.
Wargame: MCPS outperforms GRAVE on boards $9\times9$ and larger. The algorithm runs 15–33% faster (more playouts per second) due to shorter simulation lengths and converges on decisive game states faster.

Significance and Claims

The paper claims that MCPS represents a significant improvement over GRAVE for general-purpose MCTS applications, particularly in scenarios where deep learning is not an option. The primary mechanism for success is the "better-informed selection rule," which allows the algorithm to:

Build deeper search trees.
Reduce simulation work per iteration (in some games).
Reach closer to terminal states (in games like AtariGo).
Convert additional computation time into deeper exploration of promising lines (observed in Go).

The authors emphasize that the algorithm is general-purpose, requiring no problem-specific modifications or training. The results suggest that the benefit of MCPS is most pronounced when the resulting depth advantage falls within the relevant decision horizon of the game. The paper concludes that the concept of combining three sources of statistics is reusable for other types of statistics beyond permutations.