TLDR: Monte Carlo Permutation Search (MCPS) is a new Monte Carlo Tree Search algorithm that enhances the GRAVE algorithm by incorporating a third source of statistics based on permutations of moves within playouts. It consistently outperforms GRAVE in two-player games, requires no hyperparameter tuning, and benefits significantly from the use of abstract codes for moves. MCPS is a robust and general-purpose MCTS algorithm suitable for various problem domains, especially when deep reinforcement learning is not feasible or computing power is limited.
Monte Carlo Tree Search (MCTS) has revolutionized artificial intelligence in games and various other complex problem-solving domains. From mastering the ancient game of Go with AlphaGo to tackling challenges like interplanetary trajectory planning and disaster response, MCTS has proven to be a powerful framework for decision-making. However, many MCTS applications, particularly in General Game Playing, rely on playouts (simulated games) rather than computationally intensive neural network evaluations, especially when deep reinforcement learning isn’t an option or computing power is limited.
A new algorithm, Monte Carlo Permutation Search (MCPS), has been proposed by Tristan Cazenave from LAMSADE, Universit´e Paris Dauphine – PSL, CNRS, Paris, France. MCPS aims to significantly improve upon existing MCTS algorithms like GRAVE, which is recognized as a strong performer in general MCTS scenarios. The core innovation of MCPS lies in its enhanced exploration strategy, incorporating a third source of statistics into its decision-making process.
Traditional MCTS algorithms gather statistics on playouts that start with a specific move and All Moves As First (AMAF) statistics, which consider all playouts below a node that contain a particular move. MCPS introduces a third, crucial element: permutation statistics. These statistics consider playouts that contain a sequence of moves in *any order*, not just the order they were played. This means MCPS can leverage information from playouts where the same set of moves occurred, even if their sequence was different, providing a richer understanding of move effectiveness. For games like Hex, where move order can sometimes be irrelevant to the final state, this approach is particularly intuitive and effective.
One of the key advantages of MCPS is its mathematical foundation. The paper provides a detailed derivation of the formulas used to weight these three sources of statistics. This derivation eliminates the need for a ‘bias’ hyperparameter, which is present in GRAVE and often requires careful tuning. Furthermore, MCPS has been shown to be less sensitive to the ‘ref’ hyperparameter, meaning it performs consistently well across different games without extensive parameter optimization. This makes MCPS a more robust and user-friendly algorithm for general-purpose applications.
The research extensively tested MCPS against GRAVE across a diverse range of games, including various two-player board games (Atarigo, Breakthrough, Gomoku, Hex, Knightthrough, Nogo), a sequential wargame, an investment game, and a video game inspired by Team Fight Tactics (TFT). In almost all two-player games, MCPS demonstrated superior performance, often showing greater improvement as the number of simulated playouts increased. For instance, in Hex, MCPS achieved win rates significantly higher than GRAVE, highlighting the benefit of its permutation statistics where move order flexibility is more pronounced.
A notable finding from the experiments is the utility of ‘abstract codes’ for moves. Instead of using exact codes that uniquely identify every possible move, abstract codes encode only the most relevant parts of a move (e.g., attacking unit and target unit in a wargame, rather than also including the unit’s position). This approach leads to abstract codes appearing more frequently in playouts, thereby increasing the amount of available statistics for both AMAF and permutation calculations. The study showed that using abstract codes significantly boosted the performance of both MCPS and GRAVE, with MCPS benefiting even more, especially in complex games like the 21×21 Investment Pair Game.
While MCPS consistently outperformed GRAVE in two-player scenarios, results for multi-player games (Three-player Nogo, Wargame, and Investment Pair Game) were more balanced. This is attributed to the inherent dynamics of multi-player games, where players might form implicit coalitions, leading to more balanced outcomes even when one player’s algorithm is technically stronger.
Also Read:
- Neural Bayesian Filtering: A New Method for Tracking Hidden States in Complex Systems
- A New Algorithm for Multi-Agent Pathfinding Prioritizes Objectives for Enhanced Efficiency
In conclusion, Monte Carlo Permutation Search represents a significant advancement in general-purpose MCTS algorithms. By intelligently incorporating permutation statistics and leveraging abstract codes, MCPS offers improved performance, eliminates the need for hyperparameter tuning, and scales effectively with increased computational resources. This makes it a promising tool for a wide array of problems where deep reinforcement learning is impractical, offering a powerful and adaptable solution for complex decision-making. You can read the full research paper here: Monte Carlo Permutation Search.
