Do evaluation functions really improve Monte-Carlo tree search?

Abstract

Monte-Carlo tree search (MCTS) algorithms play an important role in developing computer players, especially for games for which good evaluation functions are hard to obtain, like Go. The performance of MCTS players is often leveraged in combination with online and/or offline knowledge, despite the lack of game-theoretic guarantees. For the games for which we already have good evaluation functions, the use of evaluation functions in MCTS algorithms achieved a success. However, the effect of evaluation functions on the performance of MCTS algorithms have not been investigated well, especially in terms of the quality of evaluation functions. In this study, we try to address this issue by using Othello (Reversi) as the target game. Based on the evaluation function used in Zebra, a top-level open-source player, we design 15 variants of evaluation functions and use them in three ways in MCTS algorithms. We conduct a set of experiments exhaustively and analyze the effect of evaluation functions in MCTS algorithms.

Keywords

Monte-Carlo tree search evaluation functions Othello (Reversi)

1. Introduction

In game programming, Monte-Carlo tree search (MCTS) (Coulom (2006); Kocsis and Szepesvári (2006); Browne et al. (2012)) is a method for finding an optimal move by performing random simulations of games called playouts or rollouts and building a search tree according to the results. After the first proposal by Coulom (2006), MCTS has been intensively studied for computer Go. Now MCTS is an absolutely necessary algorithm for many games, for which evaluation functions are difficult to obtain and thus it is hard to apply minimax search (Browne et al. (2012)).

In theory, the upper confidence bounds for trees (UCT) algorithm is proved by Kocsis and Szepesvári (2006) to return an optimal move after an infinite number of playouts. In practice, however, we are requested to select a move in a limited amount of time. For this aim, despite the lack of game-theoretic guarantees, the majority of MCTS players perform tree traversals and/or playouts with some game-specific heuristic bias. Among them, a popular enhancement is rapid action value estimation (RAVE) algorithm by Gelly and Silver (2007), which utilizes online knowledge obtained through playouts.

In rather long history, several researchers and game-player developers devoted themselves to obtaining good position evaluation functions. Several stronger MCTS players have also been developed by combining evaluation functions, for example, for Amazons (Lorentz (2008); Kloetzer et al. (2007)), Breakthrough (Lorentz and Horey (2013)), Havannah (Lorentz (2016)), and Lines of Actions (Winands and Björnsson (2010)). Even for Go, AlphaGo (Silver et al. (2016)) combined MCTS with evaluation functions developed with deep convolutional neural networks and caught up human top-players.

Intuitively, those evaluation functions are desired to be more accurate for stronger MCTS players. However in fact, we often encounter trade-offs between the accuracy and speed of evaluation functions. More interestingly, Gelly and Silver (2007) reported that the use of more accurate evaluation function performed worse when used in playouts. As far as the authors know, the effect of evaluation functions remains unclear especially in the combination of MCTS. Recently, James et al. (2017) studied this topic using a synthetic game and curious evaluation functions.

In this study, we tackle the problem using Othello (Reversi) as the target game, for which we have already obtained very good evaluation functions. We use the evaluation function of Zebra (Andersson (2011)), an open-source champion-level computer player, and its 15 variants. As MCTS enhancements with evaluation functions, we test three popular ones, namely: Node Prior that uses evaluation functions at each node in a search tree (Gelly and Silver (2007); Chaslot et al. (2009)), Progressive Bias that uses evaluation functions for selecting random moves in playouts (Gelly and Silver (2011); Gelly et al. (2006); Bouzy (2005)), and Early Playout Termination that uses evaluation functions for the rewards of playouts (Lorentz (2016); Kloetzer et al. (2007)). We generate a set of test data that consist of game positions associated with the scores of the moves, and analyze the effect of evaluation functions from an exhaustive set of experiments. We also test the strength of MCTS players with evaluation functions against the baseline MCTS player.

Here we summarize some interesting findings in this paper.

For an earlier stage of Othello, we find linear relation between the performance of the single use of evaluation functions and that of MCTS players (Figs 3 and 4).

For a later stage of Othello, we find not linear but quadratic (or higher) relation between the performance of the single use of evaluation functions and that of MCTS players (Figs 5 and 6).

If the evaluation functions are good enough (including Zebra’s evaluation function), the MCTS players perform even worse than the single use of evaluation functions (Figs 3 and 4).

The algorithm called early playout termination performs better in many cases but we find contradictory results with a very bad evaluation function. (Fig. 12)

The rest of the paper is organized as follows. In Section 2, we introduce the test data and the evaluation measures used in this study. In Section 3, we introduce Zebra’s evaluation function and then design 15 variants of it. In Section 4, we review three MCTS algorithms that combines with evaluation functions. In Section 5, we report the experiment results and analyze the results from three viewpoints. We review related work in Section 6 and conclude the paper in Section 7.

2. Test positions and evaluation measure

In game programming, the players (and algorithms) are often evaluated by the winning ratio or some rating scores through a number of games. In our previous work, we did preliminary evaluation in this manner (Kitamura and Matsuzaki (2018)). In this study, we generated a set of test data that consist of game positions associated with the scores of the moves to make it possible to analyze the characteristics more in detail. It is worth noting that the approach of using test data of game positions was in existing papers (Hashimoto et al. (2013); Matsumoto and Kobayashi (2013)), in which the evaluation was just based on win/lose.

We generated two sets of test data from self-matches of a simple MCTS player with 1000 playouts; T-20 consisting of 100 positions after 20 moves (Fig. 1), and T-40 consisting of 100 positions after 40 moves. For each position, every legal move is associated with a score computed as follows. For the positions after 20 moves (in T-20), we used WZebra (the Windows client of Zebra) to compute the evaluation values with the setting of look-aheads of 24 moves. Note that the evaluation values of WZebra are normalized to the scale of the number of stones. For the positions after 40 moves (in T-40), we perform perfect analysis to compute the difference of the numbers of stones. We removed (almost) one-sided positions from both of data set: more concretely, we excluded the positions if the score of the best move is less than $- 12$ or larger than $+ 12$ .

Using the scores associated with the moves, we can consider the following more useful measures of players instead of win/lose. Rank Rate

Let rank be normalized so that the best move is zero and the worst move is one. Rank rate is the average of normalized ranks of selected moves (the best is zero).

Error Rate

Let error be defined as the difference of scores of the best move and the selected move. Error rate is the average of errors of selected moves (the best is the zero). When a move has ties, we count the rank of the selected move as the best of them.

Best-move Ratio

The ratio (in percent) that the selected moves are the best moves (the best is 100).

From our preliminary experiments using both T-20 and T-40, we observed strong linear relation between rank rate and error rate. Therefore, we use error rate and best-move ratio as the measures of strength of players. Note that the error rate of a random player is 12.13 for T-20 and 11.92 for T-40.

Fig. 1.

Example position in T-20 and normalized rank and error of moves.

3. Design of evaluation functions

In this study, we borrow the evaluation function used in Zebra, an open-source top-level computer player. The evaluation function uses a pattern-based evaluation scheme (also known as N-tuple networks), where 11 configurations (N-tuples) are from row/column, diagonal, edge + adjacent X-squares, and corners (The patterns are illustrated by black dots in the first row of Table 1).

We designed 15 variants by removing 1–9 of these patterns from the original evaluation function. The evaluation functions used in this study are summarized in Table 1. We tested more than 30 variants of evaluation functions and extracted those 15 variants to cover a wide range of characteristics.

We evaluated the original evaluation function and the 15 variants with the two measures in Section 2. The results are given in the second columns in Tables 2 and 3. Figure 2 plots the error rate for T-20 against that for T-40. As expected, the original evaluation function is the best among the designed ones, meanwhile it still has larger error rates than expected: 2.10 for T-20 and 4.68 for T-40. It is interesting that the error rates may differ significantly by the removal of patterns (for example, see the pairs Z7-b and Z9, or Z3-a and Z8-a). In the later evaluation in Section 5, we look close the results of Z0, Z1-c, Z3-a, Z8-a, Z7-b, and Z9.

Table 1
N-tuples used in evaluation functions

Z0 ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Z1-a ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Z1-b ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Z1-c ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Z1-d ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Z2-a ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Z2-b ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Z3-a ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Z3-b ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

Z4-a ✓ ✓ ✓ ✓ ✓ ✓ ✓

Z4-b ✓ ✓ ✓ ✓ ✓ ✓ ✓

Z7-a ✓ ✓ ✓ ✓

Z7-b ✓ ✓ ✓ ✓

Z8-a ✓ ✓ ✓

Z8-b ✓ ✓ ✓

Z9 ✓ ✓


Z0	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓
Z1-a		✓	✓	✓	✓	✓	✓	✓	✓	✓	✓
Z1-b	✓		✓	✓	✓	✓	✓	✓	✓	✓	✓
Z1-c	✓	✓	✓	✓	✓	✓	✓	✓		✓	✓
Z1-d	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓
Z2-a			✓	✓	✓	✓	✓	✓	✓	✓	✓
Z2-b	✓	✓	✓	✓	✓	✓	✓	✓	✓
Z3-a		✓	✓	✓	✓	✓	✓	✓	✓
Z3-b	✓	✓	✓	✓	✓	✓	✓	✓
Z4-a					✓	✓	✓	✓	✓	✓	✓
Z4-b	✓	✓	✓	✓					✓	✓	✓
Z7-a					✓	✓	✓	✓
Z7-b	✓	✓	✓	✓
Z8-a							✓	✓	✓
Z8-b					✓	✓	✓
Z9										✓	✓

Fig. 2.

Error rates of designed evaluation functions (single use).

4. Monte-Carlo tree search using evaluation functions

Monte-Carlo tree search (MCTS) Coulom (2006) is a method for finding an optimal move by performing random simulations of games (called playouts) and building a search tree. In our study, we use the upper confidence bounds for trees (UCT) algorithm as the base MCTS algorithm. In each iteration of UCT, we compute as follows.

Traverse the search tree down to a leaf. Here, a child with the highest UCB1 value is selected at each step.

If the number of playouts at the leaf exceeds some threshold (in this study, 20), the leaf is expanded and the children are added to the search tree.

Perform a playout (random simulation) from the position of the leaf until the end of the game.

Update the values on nodes by the result of the playout.

The UCB1 value of a node s is defined as

UCB 1 (s) = \bar{X} (s) + C \sqrt{(log n) / n (s)}

. Here,

\bar{X} (s)

denotes the average score1

¹
It is known that using only win/lose mapped to 1/0 is often better than using game scores. In this study, we use the game scores without converting to win/lose to see the effects of evaluation functions more directly.

of playouts under node s,

n (s)

the number of playouts under node s, n the total number of playouts. The parameter C is set 1 in the experiments.

We extend the UCT algorithm by combining evaluation functions in the following three ways. Node Prior

(N-Prior) (Gelly and Silver (2007); Chaslot et al. (2009)) In the computation of the UCB1 value, we consider that we have in advance w times of playouts whose results are the evaluation value of the position. In the experiments, we use $w = 5$ .

Progressive Bias

(P-Bias) (Gelly and Silver (2011); Gelly et al. (2006); Bouzy (2005)) This is also know as pseudo-random playouts. Instead of perfectly random playouts, we bias the selection of move by the evaluation values. In the experiments, we use a softmax function to map the evaluation values to selection probabilities.

Early Playout Termination

(EPT) (Lorentz (2016); Kloetzer et al. (2007)) Instead of doing a playout until the end of the game, we stop the random simulation at a certain depth (counted from the leaf in the search tree) and use the evaluation value as the result of the playout. In this study, we limit the depth $d = 5$ .

5. Experiments and evaluation

5.1. Comparison of error rate and best-move ratio

We implemented 15 variants of evaluation functions (Section 3) and 3 enhancements of MCTS algorithms (Section 4), and conducted a set of experiments exhaustively for test data T-20 and T-40 changing the number of playouts from $1 \times 10^{3}$ to $256 \times 10^{3}$ . For each configuration, we conducted 20 runs with different seeds, and computed the averages of error rates and best-move ratios. Due to the limitation of space, we show the experiment results in detail only for the cases of $1 \times 10^{3}$ playouts and $256 \times 10^{3}$ playouts: Table 2 for T-20 and Table 3 for T-40.

As the first analysis, we compare the error rates of the single use of evaluation functions and those of MCTS players. Figure 3 plots the experiment results for T-20 with $1 \times 10^{3}$ playouts, where the horizontal axis indicates the error rates of the single use of evaluation functions and the vertical axis indicates the error rates of MCTS players. Similarly, Fig. 4 plots for T-20 with $256 \times 10^{3}$ playouts, Fig. 5 for T-40 with $1 \times 10^{3}$ playouts, and Fig. 6 for T-40 with $256 \times 10^{3}$ playouts.

Table 2
Experiment results for test data T-20. Each column shows the error rate and best-move ratio in brackets

Single use $1 \times 10^{3}$ playouts $256 \times 10^{3}$ playouts

N-Prior P-Bias EPT N-Prior P-Bias EPT

Z0 2.10 [49] 3.53 [36.9] 4.70 [28.2] 3.26 [39.5] 3.03 [39.7] 4.58 [29.5] 2.75 [42.8]

Z1-a 3.90 [41] 4.21 [35.4] 5.57 [24.4] 3.47 [39.3] 3.78 [37.3] 5.44 [26.0] 3.04 [41.8]

Z1-b 2.44 [49] 3.91 [33.3] 5.32 [26.4] 3.31 [39.9] 3.34 [37.0] 4.88 [27.0] 2.85 [43.5]

Z1-c 3.69 [39] 4.62 [28.8] 5.69 [22.4] 3.84 [35.2] 4.04 [32.8] 5.31 [24.5] 3.50 [38.2]

Z1-d 2.37 [48] 3.08 [41.8] 4.84 [28.0] 3.13 [40.0] 2.67 [43.3] 4.60 [30.4] 2.78 [44.6]

Z2-a 4.59 [41] 4.82 [33.6] 5.73 [24.6] 3.41 [41.7] 3.96 [37.5] 5.39 [26.3] 2.85 [43.8]

Z2-b 2.15 [50] 2.86 [43.1] 5.09 [27.3] 3.40 [40.2] 2.33 [45.7] 4.84 [29.5] 2.74 [43.4]

Z3-a 3.46 [45] 3.59 [42.4] 5.16 [25.4] 3.24 [43.3] 3.15 [43.9] 4.65 [30.7] 3.04 [43.9]

Z3-b 4.73 [35] 4.82 [30.7] 5.93 [26.2] 4.01 [35.1] 4.21 [32.9] 5.61 [28.5] 3.83 [36.6]

Z4-a 5.26 [32] 4.87 [31.0] 5.99 [23.2] 4.32 [33.9] 4.47 [32.8] 5.52 [24.0] 3.62 [36.6]

Z4-b 3.10 [43] 5.03 [28.8] 5.91 [21.8] 4.11 [34.9] 3.87 [34.1] 5.18 [26.2] 3.71 [36.6]

Z7-a 10.51 [26] 9.15 [23.3] 7.72 [15.3] 5.60 [29.4] 7.48 [26.9] 7.22 [17.7] 5.43 [30.2]

Z7-b 5.49 [27] 6.71 [21.7] 7.61 [21.1] 5.81 [26.0] 5.26 [29.4] 6.69 [24.1] 5.67 [25.3]

Z8-a 6.52 [29] 7.07 [24.5] 7.05 [24.0] 5.37 [31.0] 6.59 [26.9] 4.57 [31.6] 5.50 [30.3]

Z8-b 8.48 [23] 8.43 [19.0] 9.29 [11.7] 6.34 [22.7] 8.02 [19.7] 8.49 [14.4] 5.68 [26.8]

Z9 13.34 [10] 10.68 [11.0] 8.39 [16.8] 10.29 [13.0] 9.72 [14.1] 7.52 [17.0] 9.77 [14.2]

	Single use	$1 \times 10^{3}$ playouts	$256 \times 10^{3}$ playouts
Z0	2.10 [49]	3.53 [36.9]	4.70 [28.2]	3.26 [39.5]	3.03 [39.7]	4.58 [29.5]	2.75 [42.8]
Z1-a	3.90 [41]	4.21 [35.4]	5.57 [24.4]	3.47 [39.3]	3.78 [37.3]	5.44 [26.0]	3.04 [41.8]
Z1-b	2.44 [49]	3.91 [33.3]	5.32 [26.4]	3.31 [39.9]	3.34 [37.0]	4.88 [27.0]	2.85 [43.5]
Z1-c	3.69 [39]	4.62 [28.8]	5.69 [22.4]	3.84 [35.2]	4.04 [32.8]	5.31 [24.5]	3.50 [38.2]
Z1-d	2.37 [48]	3.08 [41.8]	4.84 [28.0]	3.13 [40.0]	2.67 [43.3]	4.60 [30.4]	2.78 [44.6]
Z2-a	4.59 [41]	4.82 [33.6]	5.73 [24.6]	3.41 [41.7]	3.96 [37.5]	5.39 [26.3]	2.85 [43.8]
Z2-b	2.15 [50]	2.86 [43.1]	5.09 [27.3]	3.40 [40.2]	2.33 [45.7]	4.84 [29.5]	2.74 [43.4]
Z3-a	3.46 [45]	3.59 [42.4]	5.16 [25.4]	3.24 [43.3]	3.15 [43.9]	4.65 [30.7]	3.04 [43.9]
Z3-b	4.73 [35]	4.82 [30.7]	5.93 [26.2]	4.01 [35.1]	4.21 [32.9]	5.61 [28.5]	3.83 [36.6]
Z4-a	5.26 [32]	4.87 [31.0]	5.99 [23.2]	4.32 [33.9]	4.47 [32.8]	5.52 [24.0]	3.62 [36.6]
Z4-b	3.10 [43]	5.03 [28.8]	5.91 [21.8]	4.11 [34.9]	3.87 [34.1]	5.18 [26.2]	3.71 [36.6]
Z7-a	10.51 [26]	9.15 [23.3]	7.72 [15.3]	5.60 [29.4]	7.48 [26.9]	7.22 [17.7]	5.43 [30.2]
Z7-b	5.49 [27]	6.71 [21.7]	7.61 [21.1]	5.81 [26.0]	5.26 [29.4]	6.69 [24.1]	5.67 [25.3]
Z8-a	6.52 [29]	7.07 [24.5]	7.05 [24.0]	5.37 [31.0]	6.59 [26.9]	4.57 [31.6]	5.50 [30.3]
Z8-b	8.48 [23]	8.43 [19.0]	9.29 [11.7]	6.34 [22.7]	8.02 [19.7]	8.49 [14.4]	5.68 [26.8]
Z9	13.34 [10]	10.68 [11.0]	8.39 [16.8]	10.29 [13.0]	9.72 [14.1]	7.52 [17.0]	9.77 [14.2]

Table 3

Experiment results for test data T-40. Each column shows the error rate and best-move ratio in brackets

	Single use	$1 \times 10^{3}$ playouts			$256 \times 10^{3}$ playouts

		N-Prior	P-Bias	EPT	N-Prior	P-Bias	EPT
Z0	4.68 [44]	4.27 [42.2]	4.22 [38.0]	3.87 [45.5]	3.33 [48.5]	3.84 [41.7]	3.45 [47.9]
Z1-a	4.96 [39]	4.68 [41.0]	4.91 [34.3]	4.01 [45.0]	3.85 [46.7]	4.46 [38.7]	3.54 [47.5]
Z1-b	5.00 [40]	4.40 [40.0]	4.18 [39.3]	3.84 [44.4]	3.58 [44.1]	3.86 [42.0]	3.44 [47.9]
Z1-c	5.88 [36]	5.36 [39.5]	4.62 [35.7]	3.86 [44.6]	3.87 [46.9]	4.11 [38.8]	3.08 [50.9]
Z1-d	4.86 [44]	4.24 [42.4]	4.70 [36.4]	4.06 [44.6]	3.14 [51.2]	4.10 [39.1]	3.53 [48.1]
Z2-a	4.96 [38]	4.81 [39.0]	4.84 [37.4]	4.39 [41.5]	3.70 [45.7]	4.44 [39.7]	3.62 [46.3]
Z2-b	5.50 [44]	5.09 [39.2]	5.22 [34.5]	4.82 [41.1]	4.17 [42.7]	4.14 [40.2]	4.40 [44.0]
Z3-a	6.82 [29]	6.15 [31.4]	5.65 [31.7]	5.68 [36.4]	4.89 [38.3]	4.57 [38.3]	4.94 [41.9]
Z3-b	7.26 [35]	6.55 [32.9]	6.04 [31.3]	5.05 [41.3]	5.06 [38.2]	5.00 [37.2]	4.51 [43.5]
Z4-a	5.06 [36]	4.83 [37.4]	4.83 [37.0]	4.14 [41.5]	3.73 [44.9]	4.37 [40.7]	3.43 [47.3]
Z4-b	4.84 [37]	4.52 [39.6]	5.01 [34.9]	5.93 [33.2]	4.34 [39.4]	4.52 [37.4]	5.39 [34.7]
Z7-a	7.74 [31]	8.17 [26.7]	8.63 [20.0]	6.32 [34.0]	6.09 [31.8]	7.01 [27.4]	5.60 [35.4]
Z7-b	9.06 [22]	8.99 [20.7]	11.47 [15.7]	8.65 [24.2]	8.74 [21.7]	9.55 [19.4]	8.34 [26.2]
Z8-a	5.42 [40]	5.74 [40.8]	6.01 [32.0]	5.80 [33.4]	5.15 [44.6]	3.77 [46.7]	5.28 [39.5]
Z8-b	8.20 [24]	8.52 [23.0]	15.21 [4.7]	7.39 [26.5]	8.26 [23.5]	13.70 [6.9]	7.42 [25.9]
Z9	8.00 [23]	7.56 [23.8]	7.06 [24.5]	7.19 [27.8]	7.31 [25.3]	5.94 [28.1]	6.70 [29.4]

From Figs 3 and 4, we can find several interesting facts in the case of T-20 (an earlier stage). Firstly, EPT performs better in most of the cases than N-Prior and P-Bias. This supports the success of existing MCTS players with evaluation functions (Lorentz (2016, 2008); Kloetzer et al. (2007); Lorentz and Horey (2013); Winands and Björnsson (2010)). Secondly, we find linear relation between the error rates of the single use and those of MCTS players. In particular, the gradients are ordered as P-Bias < EPT < N-Prior. Thirdly, when the evaluation functions are good enough (i.e., the error rates are less than 4), the MCTS players perform worse. For example, with Zebra’s original evaluation function, we could not improve the performance by combining MCTS and the evaluation function. This is an unexpected but interesting result. Fourthly, the overall trend does not change with respect to the number of playouts, while the error rates gradually decrease.

Fig. 3.

T-20 with $1 \times 10^{3}$ playouts.

Fig. 4.

T-20 with $256 \times 10^{3}$ playouts.

Fig. 5.

T-40 with $1 \times 10^{3}$ playouts.

Fig. 6.

T-40 with $256 \times 10^{3}$ playouts.

From Figs 5 and 6, we can also find some interesting facts in the case of T-40 (a later stage). As we can see rather clearly in Fig. 6 ( $256 \times 10^{3}$ playouts), the relation between the error rates is not linear but rather quadratic (or higher degree). In particular, the MCTS players keep small error rates when the error rate of the single use is less than 6. When the error rate of the single use becomes large, the performance of MCTS players becomes worse than the single use. We can see a similar trend for the best-move ratios. Since this may be a general trend for near-end positions or specific to Othello, we need careful analyses using different games to make a conclusion for this finding.

5.2. Error rates with respect to number of playouts

As the second analysis, we plot the error rates of MCTS players changing the number of playouts, for six evaluation functions Z0, Z1-c, Z3-a, Z8-a, Z7-b and Z9 (Figs 7–12). As a general trend, the error rates decrease when we increase the number of playouts. An interesting fact can be seen on the gradients of P-Bias of Z7-b (Fig. 11) and Z8-a (Fig. 10). The error rates of EPT and N-Prior are smaller than those of P-Bias in many cases (especially with Z0 and Z1-c), but we find contradictory results with Z9 for T-20. The reason of this would be the too-large error rate of Z9 for T-20 (which is larger than random plays).

Fig. 7.

MCTS players with Z0.

Fig. 8.

MCTS players with Z1-c.

Fig. 9.

MCTS players with Z3-a.

Fig. 10.

MCTS players with Z8-a.

Fig. 11.

MCTS players with Z7-b.

Fig. 12.

MCTS players with Z9.

Fig. 13.

Win ratios w.r.t. error rates for T-20.

Fig. 14.

Win ratios w.r.t. error rates for T-40.

5.3. Comparison of players’ strength

As the second set of experiments, we had matches of the MCTS players with evaluation functions against the baseline MCTS player. The baseline MCTS player did not use any evaluation function but it performed 128,000 playouts for each move. The MCTS player with evaluation functions performed 1,000 playouts for each move. The number of matches was 1,000 for each evaluation function.

Figures 13 and 14 plot the win ratio of the MCTS players against the error rate of single-use evaluation function for T-20 and T-40, respectively. Roughly speaking, the players developed with EPT were the strongest, which was congruent with the results of previous experiments. For two evaluations Z3-a and Z3-b, the players with EPT were weaker than ones with P-Bias. Though this is a interest result, we do not have concrete evidences to explain it. Another interesting result is that we have smaller win ratios with evaluation functions with not large error rates (corresponding evaluations functions are Z7-b, Z8-a, and Z8-b).

6. Related work

Despite the lack of game-theoretic guarantees, the majority of MCTS players perform tree traversals and/or playouts with some game-specific heuristic bias (Browne et al. (2012)). Among them, a popular enhancement is rapid action value estimation (RAVE) algorithm by Gelly and Silver (2007), which utilizes online knowledge obtained through playouts. Similar approaches include move-average sampling technique (MAST) by Finnsson and Björnsson (2008) and playout policy adaptation (PPA) by Cazenave (2015).

As we discussed in Section 4, several MCTS algorithms have been developed to utilize offline knowledge like evaluation functions. The most promising approach is early playout termination (EPT) (Lorentz (2016)), which was used in several players for Amazons (Lorentz (2008); Kloetzer et al. (2007)), Breakthrough (Lorentz and Horey (2013)), Havannah (Lorentz (2016)), Lines of Action (Winands and Björnsson (2010)). In this study, we also confirmed the advantage of EPT, compared with node prior or progressive bias. Recently, Lanctot et al. (2014) proposed an integration of minimax and MCTS to enhance the advantage of evaluation functions. Hsueh et al. (2015) proposed to combine EPT implicitly with minimax, which provided improvements.

In this study, we try to analyze the effect of evaluation functions in MCTS using Othello, for which we already have very strong players (also we can do perfect analysis for later positions of the game). This is on a recent trend of game-informatics research. For instance, the characteristics of the MCTS algorithms were studied using perfectly-analyzed subset of the game (Hashimoto et al. (2013); Matsumoto and Kobayashi (2013); Kato et al. (2015)). The most related study was by James et al. (2017), in which MCTS algorithms combined with evaluation functions were analyzed with a synthetic game.

7. Conclusion

In this study, we have tried to clarify the effects of evaluation functions combined with MCTS algorithms, using Othello as the target game. The method we used was (i) designing several evaluation functions as variants of Zebra’s evaluation function and (ii) evaluating the performance of evaluation functions through the test positions associated with exact (or almost exact) scores.

We have found several interesting facts from the experiments. For instance, linear relation between error rates of the single use and MCTS players for an earlier stage (T-20) but non-linear relation between them for a later stage (T-40), degradation of error rates combined with MCTS for very good evaluation functions.

We have noticed that several important issues still remain unclear after this study. Since we checked the performance of evaluation functions only for the positions after 20 moves and after 40 moves, we cannot do further analyses for each of evaluation functions. We may find more interesting facts if we plot the error rates over the progress of the games, which remains as our future work. It is also an interesting future work to apply the method to other games to derive game-generic trends.

Footnotes

Acknowledgement

Most of the experiments in this paper were conducted on the IACP cluster in Kochi University of Technology.

References

Andersson, G. (2011). Zebra. http://radagast.se/othello/zebra.html.

Bouzy, B. (2005). Associating domain-dependent knowledge and Monte Carlo approaches within a Go program. Information Sciences, 175, 247–257. doi:10.1016/j.ins.2004.04.010.

Browne, C.B., Whitehouse, D., Cowling, P.I. & Samothrakis, S. (2012). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43. doi:10.1109/TCIAIG.2012.2186810.

Cazenave, T. (2015). Playout policy adaptation for games. In Proceedings of 14th International Conference on Advances in Computer Games (ACG 2015) (pp. 20–28).

Chaslot, G., Fiter, C., Hoock, J.-B., Rimmel, A. & Teytaud, O. (2009). Adding expert knowledge and exploration in Monte-Carlo tree search. In Proceedings of 12th International Conference on Advances in Computer Games (ACG’09) (pp. 1–13).

Coulom, R. (2006). Efficient selectivity and backup operators in Monte-Carlo tree search. In Proceedings of 5th International Conference on Computers and Games (CG 2006) (pp. 72–83).

Finnsson, H. & Björnsson, Y. (2008). Simulation-based approach to general game playing. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI 2008) (pp. 259–264).

Gelly, S. & Silver, D. (2007). Combining online and offline knowledge in UCT. In Proceedings of 24th International Conference on Machine Learning (ICML’07) (pp. 273–280). doi:10.1145/1273496.1273531.

Gelly, S. & Silver, D. (2011). Monte-Carlo tree search and rapid action value estimation in computer Go. Artificial Intelligence, 175, 1856–1875. doi:10.1016/j.artint.2011.03.007.

10.

Gelly, S., Wang, Y., Munos, R. & Teytaud, O. (2006). Modification of UCT with patterns in Monte-Carlo Go. Technical report 6062, INRIA.

11.

Hashimoto, T., Maehara, S., Kawashima, T. & Kobayashi, Y. (2013). A new UCT search method using position evaluation function and its evaluation by Othello. IPSJ Journal, 54(7), 1930–1936. In Japanese.

12.

Hsueh, C.-H., Wu, I.-C., Tseng, W.-J., Yen, S.-J. & Chen, J.-C. (2015). Strength improvement and analysis for an MCTS-based Chinese dark chess program. In Proceedings of 14th International Conference on Advances in Computer Games (ACG 2015) (pp. 29–40).

13.

James, S., Konidaris, G. & Rosman, B. (2017). An analysis of Monte Carlo tree search. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (pp. 3576–3582).

14.

Kato, H., Takaya, M. & Yamamura, A. (2015). Analysis of a Monte Carlo tree search in Knight-Amazons. In Proceedings of the 2015 International Conference on Soft Computing and Software Engineering (SCSE 2015) (pp. 31–38).

15.

Kitamura, N. & Matsuzaki, K. (2018). Influence of difference of evaluation functions on the strength of Monte-Carlo tree search players. In Proceedings of 59th Programming Symposium. In Japanese.

16.

Kloetzer, J., Iida, H. & Bouzy, B. (2007). The Monte-Carlo approach in Amazons. In Proceedings of Computer Games Workshop (pp. 113–124).

17.

Kocsis, L. & Szepesvári, C. (2006). Bandit based Monte-Carlo planning. In Proceedings of 17th European Conference on Machine Learning (ECML 2006) (pp. 282–293). doi:10.1007/11871842_29.

18.

Lanctot, M., Winands, M.H.M., Pepels, T. & Sturtevant, N.R. (2014). Monte Carlo tree search with heuristic evaluations using implicit minimax backups. In Proceedings of 2014 IEEE Conference on Computational Intelligence in Games (CIG 2014) (pp. 1–8).

19.

Lorentz, R. (2008). Amazons discover Monte-Carlo. In Proceedings of 6th International Conference on Computers and Games (CG 2008) (pp. 13–24).

20.

Lorentz, R. (2016). Using evaluation functions in Monte-Carlo tree search. Theoretical Computer Science, 644, 106–113. doi:10.1016/j.tcs.2016.06.026.

21.

Lorentz, R. & Horey, T. (2013). Programming breakthrough. In Proceedings of 8th International Conference on Computers and Games (CG 2013) (pp. 49–59).

22.

Matsumoto, W. & Kobayashi, Y. (2013). Performance evaluation and how to use position evaluation function in UCT search method. In Proceedings of 18th Game Programming Workshop (GPW 2013) (pp. 170–174). In Japanese.

23.

Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T. & Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484–489. doi:10.1038/nature16961.

24.

Winands, M.H.M. & Björnsson, Y. (2010). Evaluation function based Monte-Carlo LOA. In Proceedings of 12th International Conference on Advances in Computer Games (ACG’09) (pp. 33–44).