# An Efficient Optimization of the Monte Carlo Tree Search Algorithm for Amazons
## 1 Introduction  
Amazons is a two-player board game that was introduced by [PERSON] of Argentina in 1988 [1, 2]. It is the designated game for the Olympia computer game programming competition. Due to its complex gameplay, Amazons is very challenging for humans [3], making it a popular subject for computer game competitions and research. The game rules are as follows: The game is played on a 10 \(\times\) 10 square board. Each player controls four identical pieces called \"Amazons\". These pieces and arrows follow the same rules as a queen in chess: They can move any number of squares in any direction--horizontal, vertical, or diagonal--but cannot jump over other pieces or arrows. The objective is to restrict the opponent's movement by shooting arrows until none of the opponent's four pieces can move. If, on a player's turn, all four of their pieces are immobilized, that player loses, and the other player wins. Notably, there are no ties in Amazons. The main challenge of the Amazons game lies in its complexity: Each move offers a vast number of possible choices, typically more than 500 [4, 5], and the game can extend for over 80 moves [6, 7]. This high level of complexity makes Amazons an excellent experimental sample for testing search strategy algorithms [8, 9]. Since its invention, it has garnered significant attention from computer scientists [10] and computer science students [11]. The Monte Carlo method [12] is a computational technique that produces numerical results through repeated random sampling. When integrated with tree search algorithmsand suitable evaluation functions, the Monte Carlo tree search (MCTS) algorithm has yielded impressive results in board games with a high-branching factor (such as Go) [13; 14; 15], and in real-time strategy games (such as StarCraft [16]). For instance, in 2016, DeepMind's AlphaGo program [17] defeated the Korean world champion of Go, [PERSON], with a score of 4:1. In 2018, OpenAI's OpenAI Five program [18] defeated the world champion team in Dota 2 with an overwhelming advantage; both accomplishments are based on the Monte Carlo tree search algorithm. The 'Move Groups-Parallel Evaluation' optimization strategy (MG-PEO) accommodates the rules of the Amazons board game by subdividing a complete move into two parts: Amazon Movement and Arrow Shot. Both Amazon Movement and Arrow Shot are treated as tree nodes, rather than considering a complete move as a single tree node. This approach is known as the Move Groups strategy in the literature [19]. While this strategy has been applied to the Amazons game [20], it still lacks an objective analysis of its effectiveness. Moreover, there is a widespread belief that this method only possesses advantages without any drawbacks. In this paper, we explain the high efficiency of the Move Groups strategy in Amazons by defining a new criterion: the winning convergence distance. We also identify certain shortcomings of this strategy. To address these, we propose using a Parallel Evaluation mechanism to compensate for the limitations of the Move Groups strategy. Our experimental results demonstrate that MG-PEO is an effective fusion optimization strategy. The main contributions of this paper are as follows:  
* We propose an effective optimization of the Monte Carlo tree search algorithm for the Amazons game: the MG-PEO algorithm optimization, which combines the Move Groups strategy with the Parallel Evaluation strategy. * We provide a performance analysis of the Move Groups strategy in Amazons. By defining a new criterion, the winning convergence distance, we explained the high efficiency of the strategy. Moreover, we also highlight that this strategy has certain shortcomings. The Move Groups strategy involves refining the rules of the Amazons game and using simulations to assign corresponding value scores to additional layer nodes. By utilizing these value scores (e.g., the Upper Confidence Bound Apply to Tree (UCT) strategy [15]), we can achieve effective pruning to save time.