# An Efficient Optimization of the Monte Carlo Tree Search Algorithm for Amazons
## 4 MG-PEO Performance Analysis
### Performance of Parallel Evaluation Strategy  
In this subsection, we delve into the number of threads required for the Parallel Evaluation mechanism, as well as the speedup ratio that multithreading can bring. Since the time consumption of the evaluation function mainly comes from the time from calculating each evaluation metric, the Parallel Evaluation part is essentially a multi-threaded calculation of evaluation metrics. The pseudo-code for the Parallel Evaluation metric function is shown in Algorithm 4.  
```
0:\(s_{0}\) (The current Game State)
0:\(t_{1}\),\(t_{2}\),\(p_{1}\),\(p_{2}\),\(mobility\)
1:functionParallelEvaluationMetrics(\(s_{0}\))
2: //* The calculation of Territory(\(t_{1}\),\(t_{2}\)) and Position(\(p_{1}\),\(p_{2}\)) metrics uses the same independent function four times, based on the King Move and QueenMove methods, which are calculated once for black and once for white.
3: //* We optimize its external calls in parallel.
4: Module1 = lambda (range)
5: for the \(index\) in the range:
6: \(color\gets index/2\)
7:\(type\gets index\%2\)
8: CalITP(\(color\),\(type\))
9: parallel_for(block_range(0,2),Module1)
10: //* The Mobility(\(mobility\)) metric is calculated one function at a time, and the internal logic is to process each board position (\(GridSize\) = 100) independently.
11: //* We optimize its inner loop processing logic in parallel.
12: Module2 = lambda (range)
13: for the \(index\) in the range:
14: \(color\gets index/2\)
15: \(type\gets index\%2\)
16: CalEveryBoardPosition()
17: parallel_for(block_range(0,GridSize),Module2)
```  
**Algorithm 4** Parallel Evaluation Metrics  
A. Discussion on the number of threads: Since the main metrics of the evaluation function include territory, position, and maneuverability metrics, values of the territory and position metrics can be calculated using a single function; however, as the calculations of these two metrics are related to the colors of the pieces and the calculation method (KingMove method and QueenMove method), four independent calculations are needed for the values of the territory and position metrics. The mobility indicator is calculated by a function that requires one independent calculation. The algorithm is optimized in parallel for the territory and position indicators, which theoretically require a total of four threads. For the maneuverability indicator, ten threads are theoretically needed for internal calculations related to the size of the board.  
B. Exploration of the acceleration ratio that multi-threading can bring: In order to accurately explore the acceleration ratio, we counted the time consumed by the computation function of each evaluation metric, and the data are shown in Table 3.  
As shown in Table 3, the calculation time for the optimized territory and position metrics achieved a 2.379-fold speedup, while the calculation time for the optimized mobility metric achieved a 1.956-fold speedup. The overall speedup ratio for the evaluation part was 2.111. In section A, we discussed the number of threads and noted that the theoretical speedup of parallelization should correspond to the number of threads. However, the time consumption of each module before and after optimization differed somewhat from the discussion in section A. We consider that the overhead of third-party parallel libraries[38] has consumed some computing resource performance. See Appendix B for details on the CPU usage analysis. Nevertheless, the parallel optimization mechanism reduced the time required to process the same tasks by 2.111 times, resulting in a significant performance improvement in practical applications.