Some improvements in Monte Carlo tree search algorithms for sudden death games

Abstract

The average reward problem in the traditional Monte-Carlo tree search algorithms troubles the sudden death games for a long time, because of the average reward criterion will reduce the probability of a deterministic result. But this does not bother the non-sudden death games, such as Go, which can focus only on higher win rates rather than higher scores. In this work, we propose the miniMax-Monte-Carlo tree search with depth rewards to Outer-Open Gomoku (a variant of Gomoku) to discover a forced win/lose without any human knowledge, evaluation function, or pre-training. And it can solve not only the average reward problem but also the inaccurate win-rate problem in deep playout simulation in sudden death games. Finally, we propose a new integrated framework named BBQ (Big, Best, Quick win) MCTS for improving the performance of traditional MCTS.

Keywords

Monte-Carlo tree search miniMax search depth rewards sudden death games Outer-Open Gomoku Tic-Tac-Toe

1. Introduction

The miniMax algorithm is a traditional search strategy for two-player zero-sum games. A full search miniMax solution is optimal in the combinatorial game theory. Due to the limitations of time and space, a fixed-depth miniMax algorithm is usually used for game tree search. Instead of searching enormous space, Monte-Carlo Tree Search (Coulom, 2007; Kocsis & Szepesvári, 2006) samples the search space to approximate the optimal solution. Moreover, UCT leads MCTS to converge to the game-theoretical optimum if enough time and space are given (Browne et al., 2012). So it is hard to choose between MCTS and miniMax approach when encountering a problem.

In the past decade, MCTS has been applied to many applications and got great success. But MCTS could not work very well on sudden death games (like connection games). As far as we observed, the MCTS accumulates the results of random playouts in the Backpropagation stage. It means that the win rate of a parent node is the average of all its children’s rewards. For example, assume a game state has two moves, one will lead to winning this game and get 1 point, the other will lose and get 0 point. In this case, the win rate of the game state will be averaged by MCTS algorithm. But a deterministic result should be recorded exactly or the win rate will confuse the result, as shown in Fig. 1.

Although MCTS has been studied extensively, the average reward problem still troubles the sudden death games. Herein the sudden death games, such as Outer-Open Gomoku, are games in which a single move can determine a win/lose. However, AlphaGo and AlphaGo Zero (Silver et al., 2016; 2017) did not need to deal with the average reward problem because their policy networks take over the tasks of random playouts and can suggest many good moves for MCTS. A single move of Go usually does not determine a win/lose result, so the average reward of those good moves is also excellent. And this is why MCTS can work well on computer Go.

Fig. 1.

Two different moves with the same win rate but different results.

2. Related work

2.1. Monte-Carlo tree search

Monte-Carlo tree search (Coulom, 2007; Kocsis & Szepesvári, 2006; Browne et al., 2012) is a general-purpose search algorithm based on random sampling of the search space to approximate the optimal strategy. MCTS algorithm, illustrated in Fig. 2 (Chaslot, Bakkes, Szita & Spronck, 2008; Liu, 2017), consists of the following steps:

Selection: start from the root node R to descend through the tree until a leaf node D is reached.

Expansion: expand one (or more) child node F. In this work, we only expand one child node for each simulated game.

Simulation: play a random playout from node F until the end of the game.

Backpropagation: update the final game result of each playout from the newly expanded node F to the root node R.

For the game tree in Fig. 2, the nodes represent states of the game and the edges represent legal moves. Each node statistics the number of wins and simulations for the node considered from itself. For example, the win rate of node B is

\frac{0}{2}

, where 0 denotes it did not win any game after the node B, and 2 is the total number of simulations after the node B. The game search tree grows up by repeating these four steps until reaching the ending condition. Then the move with the highest win rate is considered to be the best move to play and is returned by the algorithm.

Fig. 2.

An iteration of the MCTS in practice.

2.2. Monte-Carlo tree search and miniMax hybrids

MCTS-miniMax Hybrids was introduced by Baier & Winands (2013; 2015) that integrated miniMax within MCTS using three different ways: the playout (rollout), the selection and expansion, and the backpropagation phase. We make a brief introduction about MCTS-miniMax hybrids as follows.

In the playout phase, a fixed-depth miniMax search is used for choosing playout moves. The miniMax search can only find forced wins and avoid forced losses because of not using evaluation functions. A random move is returned when the miniMax search cannot find a win or lose path. Moreover, a miniMax search can also be embedded in the selection and expansion phases. A miniMax search can be triggered everywhere in selecting the most promising move from root to leaf. This strategy checks a shallow and wide game tree to guide MCTS tree growth by detecting shallow wins and avoiding shallow losses. So the miniMax search within the backpropagation phase allows MCTS to prove win/lose more quickly and excludes useless moves effectively.

3. MiniMax-Monte-Carlo tree search

Monte-Carlo tree search has been a great success in many applications, computer Go especially, but not on sudden death games. The reason is that the average reward (win rate) problem will affect the accuracy of the result since the win rate of a game state is the average of all its sub-states’ rewards. So here we do not allow the average reward criterion to make a deterministic result become an uncertain outcome (see Fig. 1). In the practical situation, the first player would attempt to maximize their reward while the second player (his/her opponent) seeks to minimize the first player’s win rate when finding the most promising moves. To solve these problems, in this section, we propose to combine the miniMax idea into the MCTS. We divide the nodes of Monte-Carlo tree into min-nodes and max-nodes. The MCTS algorithm is modified as follows:

Selection: start from the root node to descend through the tree until a leaf node is reached. In this paper, we modify UCB1 policy to fit the sudden death games and to better balance between exploration and exploitation. The UCB1 policy is modified as: $\begin{matrix} (1) & UCB ({child}_{i}) = \{\begin{matrix} \frac{w_{i}}{n_{i}} + c \sqrt{\frac{ln N_{p}}{n_{i}}}, & if {child}_{i} is min-node \\ (1 - \frac{w_{i}}{n_{i}}) + c \sqrt{\frac{ln N_{p}}{n_{i}}}, & otherwise / / {child}_{i} is max-node \end{matrix} \end{matrix}$ Where $N_{p}$ is the total number of simulations after the current (parent) node, $n_{i}$ is the number of simulations after the child i, $w_{i}$ is the number of first-player’s wins after the child i, c is the exploration parameter chosen experimentally, the term $\frac{w_{i}}{n_{i}}$ is the win rate of the first-player after the child i which is a min-node, and the term ( $1 - \frac{w_{i}}{n_{i}}$ ) is the win rate of the second-player after the child i which is a max-node. The first component (win rate) of the UCB formula encourages the exploitation of higher-reward nodes and the second component encourages the exploration of less-visited nodes.

Expansion: expand one (or more) child node. In order to simplify it, in this paper, we only expand one child node for each simulated game.

Simulation: play a random playout until the end of the game.

Backpropagation: update the final result of each playout from the newly expanded node to the root node according to the following formula: $\begin{array}{l} (2) & N_{p} = \sum_{child i} n_{i}, \\ (3) & W_{p} = \{\begin{matrix} max_{child i} \frac{w_{i}}{n_{i}} \times \sum_{child i} n_{i}, & if node p is max-node \\ min_{child i} \frac{w_{i}}{n_{i}} \times \sum_{child i} n_{i}, & otherwise / / node p is min-node \end{matrix} \end{array}$ Where $N_{p}$ is the total number of simulations after the current (parent) node p, $n_{i}$ is the number of simulations after the child i, $W_{p}$ is number of first-player’s wins for the most promising moves after the current (parent) node p and $w_{i}$ is the number of first-player’s wins after the child i.

We give an example in Fig. 3 to illustrate how miniMax-Monte-Carlo tree search (miniMax-MCTS) works. In the Selection stage, node A chooses R1 to reach node B which is the most promising move with the larger UCB value from the first-player’s viewpoint according to the following UCB comparisons. Since both children of node A are min-nodes, we have

$L 1 = \frac{w_{1}}{n_{1}} + c \sqrt{\frac{ln N_{A}}{n_{1}}} = \frac{0}{2} + \sqrt{\frac{2 ln 4}{2}} = 0 + 0.78 = 0.78$

$R 1 = \frac{w_{B}}{n_{B}} + c \sqrt{\frac{ln N_{A}}{n_{B}}} = \frac{2}{2} + \sqrt{\frac{2 ln 4}{2}} = 1 + 0.78 = 1.78$

After that, node B chooses L2 to reach node C which is the most promising move with the larger UCB value from the second-player’s viewpoint according to the following UCB comparisons. Since both children of node B are max-nodes, we have

$L 2 = (1 - \frac{w_{C}}{n_{C}}) + c \sqrt{\frac{ln N_{B}}{n_{C}}} = (1 - \frac{1}{1}) + \sqrt{\frac{2 ln 2}{1}} = 0 + 0.78 = 0.78$

$R 2 = (1 - \frac{w_{2}}{n_{2}}) + c \sqrt{\frac{ln N_{B}}{n_{2}}} = (1 - \frac{1}{1}) + \sqrt{\frac{2 ln 2}{1}} = 0 + 0.78 = 0.78$

Now the Selection stage goes down to the leaf node C and then the Expansion stage expands a child node X. When the first-player draws a game from the Simulation stage, the result of node X is labelled to

\frac{0.5}{1}

. And the Backpropagation stage uses the result of the simulation to update information in the nodes on the path from node C to node A. Here we should pay attention to the difference between min-nodes and max-nodes in the Backpropagation stage. The calculation details are shown below:

$W_{X} = \frac{0.5}{1}$

$W_{C} = \frac{0.5}{1}$

Since node B is a min-node, we have

$N_{B} = \sum_{child i} n_{i} = 1 + 1 = 2$

$W_{B} = min_{child i} \frac{w_{i}}{n_{i}} \times \sum_{child i} n_{i} = min_{child i} (\frac{0.5}{1}, \frac{1}{1}) \times (1 + 1) = 1$

$B = \frac{W_{B}}{N_{B}} = \frac{1}{2}$

Since node A is a max-node, we have

$N_{A} = \sum_{child i} n_{i} = 2 + 2 = 4$

$W_{A} = max_{child i} \frac{w_{i}}{n_{i}} \times \sum_{child i} n_{i} = max_{child i} (\frac{0}{2}, \frac{1}{2}) \times (2 + 2) = 2$

$A = \frac{W_{A}}{N_{A}} = \frac{2}{4}$

In addition, we should take care of the Backpropagation stage. Here we do not reduce the term

N_{A}

with respect to

W_{A}

in order to keep both the total simulation number and the win ratio unchanged. With the design of miniMax-MCTS, the average reward problem in sudden death games would be solved.

Fig. 3.

An iteration of the miniMax-MCTS in practice.

4. MiniMax-Monte-Carlo tree search with depth rewards

In the previous section, the proposed miniMax-Monte-Carlo tree search can solve the average reward problem on sudden death games and works well on Tic-Tac-Toe. However, previous MCTS approaches do not consider the depth reward of the random playout. In this section, we desire to discriminate the orders from moves that have different search depths but with the same playout results. Because the win/lose of Gomoku is well defined, a critical move is usually followed by a clear-cut result. It means that the win/lose result will come very soon if we miss a critical move. So the difference in search depths between moves is large. For instance, whatever a game is won by randomly playing 1-ply or 31-ply, the result (1 point) is always the same. But the fewer steps we play to win a game, the higher confidence we get. On the other hand, the longer path we defend for a losing game, the more chance we have to turn the tables. Therefore, we discount the rewards for each move based on the depth it has simulated. Then the win rate is close to 1 or 0 if a move wins/loses a game immediately. Thus, the win rate of miniMax-MCTS is no longer 1, 0.5, or 0 when the random playout results in a win, draw, or lose. It is tuned between 0 and 1 according to the playout lengths.

In this work, we apply miniMax-MCTS to Outer-Open Gomoku without any human knowledge, evaluation function, or pre-training. The win rate formed with Monte-Carlo random playout might not be trusted. Moreover, it may simulate very deep and the final result is also not suitable for utilization. Therefore, we set a maximum depth for each simulation. The result will be regarded as a draw if a simulation plays beyond the maximum depth. In addition, to accomplish the miniMax-MCTS with depth rewards for sudden death games, we scale up the values to retain the win rates and the total simulation numbers. By this way, the miniMax-MCTS with depth rewards can find out a defending move for avoiding the forced loss and an attacking move to run into the forced win, that is the situations traditional MCTS could not find. Now the formula for the Backpropagation stage is modified as follows: $\begin{array}{l} (4) & n_{i} = 2 d \\ (5) & w_{i} = \{\begin{matrix} 2 d - s_{i}, & if child i wins \\ s_{i}, & otherwise / / child i loses or draws \end{matrix} \\ (6) & N_{p} = \sum_{child i} n_{i} \\ (7) & W_{p} = \{\begin{matrix} max_{child i} \frac{w_{i}}{n_{i}} \times \sum_{child i} n_{i}, & if parent node p is max-node \\ min_{child i} \frac{w_{i}}{n_{i}} \times \sum_{child i} n_{i}, & otherwise / / parent node p is min-node \end{matrix} \end{array}$ Where d is the maximum depth of a simulation, $n_{i}$ is a scaled up version of a simulation for child i, $s_{i}$ is the depth of a simulation for child i, $w_{i}$ is the depth reward for child i, $N_{p}$ is the total number of simulations after the current (parent) node p and $W_{p}$ is the number of wins for the most promising move after the current (parent) node p.

Figure 4 shows an iteration to illustrate how miniMax-MCTS with depth rewards works. The steps of these four stages are the same as Section 3. The differences are that all the values are scaled up by a factor of $2 * d$ and the rewards for each move are discounted by the depth it has simulated. Here the maximum depth d of a simulation is set to 10. In the Selection stage, node A chooses R1 to reach node B which is the most promising move with the larger UCB value from the first-player’s viewpoint according to the following UCB comparisons. Since both children of node A are min-nodes, we have

$L 1 = \frac{w_{1}}{n_{1}} + c \sqrt{\frac{ln N_{A}}{n_{1}}} = \frac{8}{40} + \sqrt{\frac{2 ln 80}{40}} = 0.2 + 0.31 = 0.51$

$R 1 = \frac{w_{B}}{n_{B}} + c \sqrt{\frac{ln N_{A}}{n_{B}}} = \frac{20}{40} + \sqrt{\frac{2 ln 80}{40}} = 0.5 + 0.31 = 0.81$

$L 2 = (1 - \frac{w_{C}}{n_{C}}) + c \sqrt{\frac{ln N_{B}}{n_{C}}} = (1 - \frac{10}{20}) + \sqrt{\frac{2 ln 40}{20}} = 0.5 + 0.4 = 0.9$

$R 2 = (1 - \frac{w_{2}}{n_{2}}) + c \sqrt{\frac{ln N_{B}}{n_{2}}} = (1 - \frac{17}{20}) + \sqrt{\frac{2 ln 40}{20}} = 0.15 + 0.4 = 0.55$

Now the Selection stage goes down to the leaf node C and then the Expansion stage expands a child node X. Then, the first-player wins the game by randomly playing a 5-ply simulation and gets

\frac{2 d - s_{i}}{2 d} = \frac{2 * 10 - 5}{2 * 10} = \frac{15}{20}

points.

The Backpropagation stage uses the result of the simulation to update information in the nodes on the path from node C to node A. The calculation details are shown below:

$W_{X} = \frac{15}{20}$

$W_{C} = \frac{15}{20}$

Since node B is a min-node, we have

$N_{B} = \sum_{child i} n_{i} = 20 + 20 = 40$

$W_{B} = min_{child i} \frac{w_{i}}{n_{i}} \times \sum_{child i} n_{i} = min_{child i} (\frac{15}{20}, \frac{17}{20}) \times (20 + 20) = 30$

$B = \frac{W_{B}}{N_{B}} = \frac{30}{40}$

Since node A is a max-node, we have

$N_{A} = \sum_{child i} n_{i} = 40 + 40 = 80$

$W_{A} = max_{child i} \frac{w_{i}}{n_{i}} \times \sum_{child i} n_{i} = max_{child i} (\frac{8}{40}, \frac{30}{40}) \times (40 + 40) = 60$

$A = \frac{W_{A}}{N_{A}} = \frac{60}{80}$

Fig. 4.

An iteration of the miniMax-MCTS with depth rewards in practice.

5. Experiments

In this section, we pick two sudden-death games, Tic-Tac-Toe and Outer-Open Gomoku to test whether the traditional MCTS and our miniMax-MCTS work well.

5.1. Tic-Tac-Toe

For the Tic-tac-toe board shown in Fig. 5(a), the player “O” plays first and will be losing the game no matter where he/she plays. But only playing at C2, he/she can delay losing this game till 4-ply.

In this experiment, we repeat 100 iterations with 1 random playout per iteration. It means that the game tree will be expanded 100 nodes and will be played 1 random playout for each expanded node. Table 1 shows that the win rate for each “O” move evaluated by the traditional MCTS and our miniMax-MCTS with depth rewards. The traditional MCTS cannot distinguish between 2-ply (plays at B2 with win rate 0.2) and 4-ply (plays at C2 with win rate 0.2) losing, but our miniMax-MCTS with depth rewards can (plays at B2 with win rate 0 vs. plays at C2 with win rate 0.15). The results show that our miniMax-MCTS solves the average reward problem and our depth reward strategy distinguishes a contribution from the moves with different depths.

Fig. 5.

Two games with obvious results for testing traditional MCTS and miniMax-MCTS.

For the Tic-tac-toe board shown in Fig. 5(b), the player “X” plays first and will be winning the game unless he/she plays at B2 so that a draw is gotten.

Table 1

The win rate for each “O” move in Fig. 5(a)

100 iterations/1 playout	A1	A2	A3	B2	B3	C2
Traditional MCTS	0	0	0.11	0.2	0.17	0.2
miniMax-MCTS	0	0	0	0	0	0.15

We use the traditional MCTS for the game shown in Fig. 5(b), repeat 20, 100, 200 iterations respectively and do 1 random playout per iteration. The first player “X” will win the game unless he/she plays at B2, but the results in rows 2 to 4 of Table 2 confused us because the traditional MCTS cannot distinguish between winning and drawing moves since all the five moves have a win rates around 0.5 to 1 in the 2^nd to 4^th rows of Table 2 and their order of win rates is not right. In addition, we increase the number of random playout to 5 times and run the example again. The results shown in the 5^th to 7^th rows also confused us because the average reward problem still troubles the traditional MCTS. If we increase the number of iterations for the traditional MCTS to be much more than 200, we may get more accurate results, but the average reward problem in MCTS still exists.

On the other hand, we use our miniMax-MCTS with depth rewards to run the example in Fig. 5(b) again. Table 3 shows that the results are more reliable. But we should note that the win rate of A1 with 20 iterations and 1 playout is 0.1-extremely low (the 2^nd row of Table 3). This is because our miniMax-MCTS just do 1 random playout per iteration, and totally there are only 20 iterations-too small. So the result is not accurate. To solve this problem, we increase the number of random playouts to improve the accuracy of simulations, now the win rate is more stable and reliable by increasing the number of random playouts to 5 times. We can see that playing at B2 will have a win rate of about 0.5 and playing at C2 will have a win rate of about 1.

Table 2

The win rate for each “X” move in Fig. 5(b) evaluated by traditional MCTS

Traditional MCTS	A1	A2	B2	C1	C2
20 iterations/1 playout	1	0.75	1	1	0.5
100 iterations/1 playout	0.86	0.63	0.86	0.8	0.63
200 iterations/1 playout	0.83	0.74	0.81	0.83	0.69
20 iterations/5 playouts	0.75	0.73	0.6	0.68	0.85
100 iterations/5 playouts	0.89	0.72	0.87	0.87	0.86
200 iterations/5 playouts	0.83	0.77	0.79	0.85	0.72

Table 3

The win rate for Fig. 5(b) evaluated by miniMax-MCTS with depth rewards

miniMax-MCTS	A1	A2	B2	C1	C2
20 iterations/1 playout	0.1	0.85	0.5	0.85	0.85
100 iterations/1 playout	1	0.9	0.5	1	0.95
200 iterations/1 playout	1	0.95	0.5	1	0.95
20 iterations/5 playouts	0.89	0.55	0.44	0.82	0.57
100 iterations/5 playouts	1	0.9	0.66	1	0.9
200 iterations/5 playouts	1	0.95	0.5	1	0.95

5.2. Outer-open Gomoku

The search space of Outer-Open Gomoku is much large, but most of the legal moves are insignificant. In order to avoid searching those enormous and useless space, we aim to restrict the search space to grids near the occupied pieces on the board. We do self-play to compare unlimited (Dist(∞)), one-grid-apart (Dist(1)), two-grid-apart (Dist(2)) and three-grid-apart (Dist(3)) grids near the occupied pieces. Table 4 shows that Dist(1) wins more games than the others, so we restrict the search space in our Outer-Open Gomoku program to one-grid-apart grids near the occupied pieces.

Outer-Open Gomoku is a sudden death game in which a single move can determine a win/lose. It means that the win/lose result will come quickly if we miss a critical move. Furthermore, the result of a random playout is not accurate, so it is useless to simulate too deep on Outer-Open Gomoku. Therefore, we restrict the simulation depth of random playouts to 30-ply (Depth(30)), 40-ply (Depth(40)) and 50-ply (Depth(50)). Table 5 shows that the Depth(50) is the best and the difference between Depth(50) and Depth(40) is small. Due to time limit, we discard comparing 60-ply, 70-ply, etc.

Table 4
Comparison between different versions

Dist(1) Dis(2) Dist(3) Dist(∞) Total Rank

Dist(1) – 18 13 16 47 1

Dist(2) 2 – 11 18 31 2

Dist(3) 7 9 – 18 34 3

Dist(∞) 4 2 2 – 8 4

	Dist(1)	Dis(2)	Dist(3)	Dist(∞)	Total	Rank
Dist(1)	–	18	13	16	47	1
Dist(2)	2	–	11	18	31	2
Dist(3)	7	9	–	18	34	3
Dist(∞)	4	2	2	–	8	4

Table 5

Comparison between different simulation depths

	Depth(30)	Depth(40)	Depth(50)	Total	Rank
Depth(30)	–	4	1	5	3
Depth(40)	16	–	9.5	25.5	2
Depth(50)	19	10.5	–	29.5	1

6. Conclusions

In the traditional Monte-Carlo tree search algorithms, the win rate is the average reward for all random playouts. But the average reward problem will make a deterministic result become non-deterministic. So this work proposes the miniMax-Monte-Carlo Tree Search to solve those problems and can get the best winning strategy.

In addition, the conventional random playout approaches do not consider the accuracy of each playout. It means that the results formed with Monte-Carlo random playouts might not be reliable. So it is useless to simulate too deep on sudden death games. Therefore, we apply the miniMax-MCTS with depth rewards for solving the average reward problem and the problem of too deep simulating with useless results. We call the miniMax-MCTS with depth rewards as the quick win strategy.

The results of Tic-Tac-Toe in Section 5 show that the miniMax-MCTS can evaluate more accurately with less simulations because our miniMax-MCTS algorithm chooses the best move instead of the move with the highest averages of all its descendants. Unfortunately, at the present time, we don’t have an accurate neural network (evaluation function) to suggest where to put a good move and how good it is. Maybe our miniMax-MCTS could challenge the AlphaZero approach if we are able to train a good neural network like theirs.

7. Future work

Finally, we propose a new integrated framework named BBQ-MCTS (Big, Best and Quick win-Monte-Carlo Tree Search) for improving the performance of traditional MCTS. The Best win strategy is explained as the miniMax-MCTS where the best (not the averaged) value of the descendants is back-propagated at the Backpropagation stage of the MCTS. The Quick win strategy is to evaluate the rewards according to the winning depth.

The Big win strategy, is an on-going project in which we desire to win the game with the largest points/scores. In order to achieve the Big win strategy, we could keep a complete final points/scores in the process of training the neural network. The neural network will no longer only output win, draw or lose, but instead it will output how many points the player wins in the game. Therefore, the Big win neural network will suggest the BBQ-MCTS where to play in order to win the largest points/scores. On the other hand, when facing disadvantageous boards, it will suggest where to play in order to lose with the smallest points/scores.

Footnotes

Acknowledgements

This research was supported by the Ministry of Science and Technology (R.O.C.) under grants MOST 106-2221-E-003-027-MY2 and MOST 107-2634-F-259-001.

References

Baier, H. & Winands, M.H. (2013). Monte-Carlo tree search and minimax hybrids. In 2013 IEEE Conference on Computational Intelligence in Games (CIG) (pp. 1–8).

Baier, H. & Winands, M.H. (2015). MCTS-minimax hybrids. IEEE Transactions on Computational Intelligence and AI in Games, 7, 167–179. doi:10.1109/TCIAIG.2014.2366555.

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

Chaslot, G., Bakkes, S., Szita, I. & Spronck, P. (2008). Monte-Carlo tree search: A new framework for game AI. In 4 ^th Conference on Artificial Intelligence and Interactive Digital Entertainment (pp. 216–217).

Coulom, R. (2007). Efficient selectivity and backup operators in Monte-Carlo tree search. In

H.J.

van den Herik ,

Ciancarini and

H.H.L.M.

Donkers (Eds.), Computers and Games. CG 2006. Lecture Notes in Computer Science (Vol. 4630). Berlin: Springer.

Kocsis, L. & Szepesvári, C. (2006). Bandit based Monte-Carlo planning. In

Fürnkranz ,

Scheffer and

Spiliopoulou (Eds.), 17 ^th European Conference on Machine Learning, ECML 2006 . Lecture Notes in Computer Science (Vol. 4212). Berlin: Springer.

Liu, M. (2017). General game-playing with Monte Carlo tree search. Available at: https://medium.com/@quasimik. Retrieved July 28, 2018.

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

Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L.R., Lai, M., Bolton, A., Chen, Y., Lillicrap, T.P., Hui, F., Sifre, L., Driessche, G.V., Graepel, T. & Hassabis, D. (2017). Mastering the game of Go without human knowledge. Nature, 550, 354–359. doi:10.1038/nature24270.