# An Efficient Optimization of the Monte Carlo Tree Search Algorithm for Amazons
## 2 Related Work
### Evaluation Function  
At present, almost all search algorithms are faced with a problem: situation evaluation. Good situation evaluation is very important in the Amazons game and can even determine the quality of the game program [33]. Similar to many board games, Amazons can be roughly divided into three stages: opening, middle, and ending, with distinct strategies for each stage. The main indicators of the Amazons evaluation function include territory, position, and mobility, and the importance of these three characteristics varies across different stages. Based on these ideas, [PERSON] et al. [30] proposed a phased evaluation function, as shown in Equation (1):  
\[Value=k_{1}*t_{1}+k_{2}*t_{2}+k_{3}*p_{1}+k_{4}*p_{2}+k_{5}*mobility \tag{1}\]  
where \(t_{1}\) and \(t_{2}\) are territory metric values, which, respectively, represent the evaluation of each side's control over space, based on the QueenMove Method and KingMove Method. \(p_{1}\) and \(p_{2}\) are position metric values, reflecting the strategic position of each side's pieces, also based on the QueenMove and KingMove Methods relative to the space. _mobilityis the flexibility evaluation value of both Amazon pieces. \(k_{1}\), \(k_{2}\), \(k_{3}\), \(k_{4}\), and \(k_{5}\) are the corresponding weight values. How these values are calculated is described below. According to the literature [2], calculating territory and position values involves two types of methods: QueenMove and KingMove. QueenMove means that a move can be made as long as there are no obstacles to be crossed in any of the eight directions (the obstacles include pieces and arrows), while KingMove means that the distance of a single move is one, i.e., only one move can be made to a neighboring square. The QueenMove value represents the minimum number of moves a player's four pieces need to reach a given space (i.e., no pieces or arrows); the KingMove value represents the minimum number of moves a player's four pieces need to make to reach a given space. As shown in Figure 1 on the left side, value 2 in the upper-left corner of the upper-left (A, 1) square indicates that the white piece needs at least two moves to reach this space via the QueenMove method, and value 4 in the lower-right corner indicates that the black piece needs four moves. Similarly, values 2 and 7 in the same square in Figure 1 on the right side indicate the situation when the KingMove method is used. Accordingly, we can use the following calculation formula for all the indicators:  
\(t_{1}\) represents the difference in the control of the territory using the QueenMove method. \(t_{2}\) represents the difference in the control of the territory using the KingMove method. As shown in Equations (2) and (3):  
\[t_{i}=\sum\
u(B_{i},W_{i}) \tag{2}\]  
\[\
u(B_{i},W_{i})= \begin{cases}0,B_{i}(A)=W_{i}(A)=\infty\\ k,B_{i}(A)=W_{i}(A)\
eq\infty\\ 1,B_{i}(A)<W_{i}(A)\\ -1,B_{i}(A)>W_{i}(A)\end{cases}  \tag{3}\]  
where \(B\) represents black pieces, \(W\) represents white pieces, with the subscript 1 indicating the QueenMove method and 2 indicating the KingMove method. \(A\) represents empty squares. \(k\) represents the preponderance of the leading square, and the value range is greater than \(-1\) and less than 1. When the player with the first move is white, \(k\) is greater than 0, otherwise, it is less than 0. \(p_{1}\) represents the positions of the two pieces on control space A using the QueenMove method. \(p_{2}\) represents the positions of the two pieces on control space A using the KingMove method. As shown in Equations (4) and (5):  
Figure 1: Calculation results of the QueenMove and KingMove methods. The left is the result of the KingMove calculation, and the right is the result of the QueenMove calculation. \[p_{1}=2\Sigma\Big{(}2^{-B_{1}(A)}-2^{-W_{1}(A)}\Big{)} \tag{4}\]  
\[p_{2}=\sum_{A}\min(1,\max(-1,B_{2}(A)-W_{2}(A)/6)) \tag{5}\]  
_mobility_ means the flexibility of the pieces.