# An Efficient Optimization of the Monte Carlo Tree Search Algorithm for Amazons
## 3 Research Methodology
### Parallel Evaluation Strategy in Algorithm  
The core idea of the Parallel Evaluation strategy is that the time-consuming evaluation part of the MCTS simulation is processed in parallel optimization. It has been shown in the literature [35] that accelerating this labor-intensive evaluation function allows the Monte Carlo Tree Search algorithm to be iterated more frequently. This metric is very beneficial in compensating for the fact that the Move Groups strategy might fall into a local optimum (worst case); specifically, speeding up the evaluation function enables the Monte Carlo Tree Search to scale as quickly as possible, minimizing the impact of the worst-case scenario associated with the Move Groups strategy. The pseudo-code for the Parallel Evaluation part is as shown in Algorithm 2. ```
0:\(s_{0}\) (The current Game State)
0:Situation Evaluation Value
1:functionSituationEvaluation(\(s_{0}\))
2:\(t_{1}\), \(t_{2}\), \(p_{1}\), \(p_{2}\), \(mobility\)\(\leftarrow\) ParallelEvaluationMetrics (\(s_{0}\))
3:\(Value=k1*t1+k2*t2+k3*p1+k4*p2+k5*mobility\)
4:returnValue
```  
**Algorithm 2**SituationEvaluation  
Nodes undergo evaluation, and the resulting value scores guide node selection. Traditional Monte Carlo tree search algorithms typically choose the child node with the highest node score (winning rate) based on the current game state [36]. However, this selection method is not ideal, as it tends to prioritize immediate gains and can lead to local optima. To address this issue, this paper incorporates the \"Shallow Rollout strategy\" [37] and the \"tree-based upper confidence interval\" algorithm [19] to refine node selection. Specifically, the utilization value derived solely from decision-level nodes may be inaccurate. To enhance precision, a Shallow Rollout strategy is employed, simulating scenarios closer to the endgame. Additionally, the algorithm considers the magnitude of a node's exploratory value, which is elevated for nodes exhibiting high uncertainty and numerous future possibilities. In summary, the approach assesses both partial equilibrium utilization value and exploration value to facilitate more informed decision-making. 1. \"Shallow Rollout Strategy\": This means that the utility value is not calculated, not only based on the next move but also on the position of the game after randomly simulating the move several times. In this algorithm, we set the number of Rollouts to be two, and the depths to be 4 and 5. Specifically, after expanding the complete decision node (Amazon Movement plus Arrow Shot), we perform two Rollouts for the current situation. In each Rollout, we simulate two steps: the opponent's next decision (Amazon Movement plus Arrow Shot) and our subsequent decision (Amazon Movement plus Arrow Shot), to obtain a more forward-looking utility value. See pseudo-code Algorithm 3 for details. For the analysis of the relevant parameters, see Appendix A. 2. \"Tree-based Upper Confidence Interval\": As shown in Equation (8), the calculation formula of UCT consists of two components. The first term, \(X_{i}\), represents the utility value of the information in the constructed search tree, and the second term represents the exploration value of the unvisited nodes. The constant \(C\) is used to adjust the proportion of the algorithm's trade-off between the two values. Note that the value of the root formula is infinite because of the presence of unreachable child nodes, which ensures that unreachable child nodes under the current node will be visited at least once. \[UCT=X_{i}+C\sqrt{\frac{\ln N}{n_{i}}} \tag{8}\]  
where \(X_{i}\) is the winning rate of the child node. \(N\) is the number of times the parent node is accessed. \(n_{i}\) is the number of times the child node is accessed. \(C\) is a constant (\(\frac{1}{\sqrt{2}}\)). [PERSON] and [PERSON] [36] showed that the value satisfies the Hoeffding inequality with rewards in the range of \([0,1]\). Here, we can provide the complete pseudo-code as shown in Algorithm 3.