MCTS-Minimax Hybrids with State Evaluations (Extended Abstract)

1 Introduction

Monte-Carlo Tree Search (MCTS) [Coulom, 2007; Kocsis and Szepesvári, 2006] is a best-first tree search algorithm based on Monte-Carlo simulations for state evaluation. It has shown considerable success in a variety of domains-see [Silver et al., 2016] for the prominent recent example of Google DeepMind's AlphaGo, and [Browne et al., 2012] for an earlier literature survey. However, there are still a number of adversarial domains such as the games of Chess and (International) Checkers in which the traditional approach to adversarial planning, minimax search with αβ pruning [Knuth and Moore, 1975], remains superior. Part of the reason could be the selectivity of MCTS, its focusing on only the most promising lines of play. In tactical games such as Chess, a large number of terminal states and shallow traps exist in the search space [Ramanujan et al., 2010a]. These require precise play to avoid immediate loss, and the selective sampling and averaging value backups of MCTS can easily miss or underestimate an important move.

∗This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Baier and Winands, in press].

Conversely, MCTS could be more effective in domains such as Go, where terminal states and potential traps do not occur until the latest stage of the game. Here, MCTS can fully play out its strategic and positional understanding resulting from Monte-Carlo simulations of entire games.

Note that the recent publication of AlphaZero [Silver et al., 2017] points towards MCTS possibly becoming the dominant approach even for Chess-like games. Deep reinforcement learning seems to be able to produce state evaluators that avoid traps surprisingly well on their own. Regardless of the state evaluator however, MCTS is still more susceptible to traps than alpha-beta, and deep neural networks may give a boost to alpha-beta as well. While AlphaZero opens new questions, this article could give an indication as to how the strengths of MCTS and alpha-beta can be combined using any evaluation function, hand-coded or learned.

In previous work [Baier and Winands, 2015], MCTSminimax hybrids have been introduced, embedding shallow minimax searches into the MCTS framework. This was a first step towards combining the strategic strength of MCTS with the tactical strength of minimax. The results of the hybrid algorithms MCTS-MR, MCTS-MS, and MCTS-MB have been promising even without making use of domain knowledge such as heuristic evaluation functions. However, their inability to evaluate non-terminal states makes them ineffective in games with very few or no terminal states throughout most of the search space, such as the game of Othello. Furthermore, some form of state evaluation is often available in practiceas AlphaGo [Silver et al., 2016] demonstrated, deep learning makes this possible even for domains where hand-crafting evaluation functions has traditionally been considered very difficult. This article therefore continues this line of research by addressing the case where domain knowledge is available.

The algorithms discussed in this article make use of state evaluations. These state evaluations can either be the result of simple evaluation function calls, or the result of minimax searches using the same evaluation function at the leaves. Three different approaches for integrating state evaluations into MCTS are considered. The first approach uses state evaluations to choose rollout moves (MCTS-IR for informed rollouts). The second approach uses state evaluations to terminate rollouts early (MCTS-IC for informed cutoffs). The third approach uses state evaluations to bias the selection of moves in the MCTS tree (MCTS-IP for informed priors). Using minimax with αβ to compute state evaluations means accepting longer computation times in favor of typically more accurate evaluations as compared to simple evaluation function calls. Only in the case of MCTS-IR, minimax has been applied before [Ramanujan et al., 2010b]; the use of minimax for the other two approaches is newly proposed in the form described here. The MCTS-minimax hybrids are tested and compared to their counterparts using evaluation functions without minimax in the domains of Othello, Breakthrough, and Catch the Lion.

After the branching factor of a domain is identified as a limiting factor of the hybrids' performance, further experiments are conducted using domain knowledge not only for state evaluation, but also for move ordering. Move ordering reduces the average size of αβ trees, and furthermore allows to restrict the effective branching factor of αβ to only the k most promising moves in any given state (k-best pruning). Again, this has only been done for MCTS with minimax rollouts before [Winands et al., 2010]. The enhanced MCTS-minimax hybrids with move ordering and k-best pruning are tested and compared to the unenhanced hybrids as well as the equivalent algorithms using static evaluations in all three domains. They are also tested against each other to determine the relative strongest hybrid, compared across domains, studied at different time settings and different branching factors, combined with each other, and finally compared to an αβ baseline.

2 Hybrid Algorithms

This section describes the three different approaches for employing heuristic knowledge within MCTS that we explore in this article. For each approach, a variant using simple evaluation function calls and a hybrid variant using shallow minimax searches is considered. Two of the three hybrids are newly proposed in the form described here.

2.1 MCTS with Informed Rollouts (MCTS-IR)

The convergence of MCTS to the optimal policy is guaranteed even with uniformly random move choices in the rollouts. However, more informed rollout policies can greatly improve performance [Gelly et al., 2006], and preserve convergence if they explore sufficiently. When a heuristic evaluation function is available, it can be used in every rollout step to compare the states each legal move would lead to, and choose the most promising one. Instead of choosing this greedy move, it is effective in some domains to choose a uniformly random move with a low probability ϵ, so as to avoid determinism and preserve diversity in the rollouts. Our implementation additionally ensures non-deterministic behavior even for ϵ = 0 by picking moves with equal values at random both in the selection and in the rollout phase of MCTS. The resulting rollout policy is typically called ϵ-greedy [Sturtevant, 2008]. In the context of this work, we call this approach MCTS-IR-E (MCTS with informed rollouts using an evaluation function).

The depth-one lookahead of an ϵ-greedy policy can be extended in a natural way to a depth-d minimax search for every rollout move [Winands and Björnsson, 2011; Nijssen and Winands, 2012]. We use a random move ordering in minimax as well in order to preserve non-determinism. In contrast to [Winands and Björnsson, 2011] and [Nijssen and Winands, 2012] where several enhancements such as move ordering, k-best pruning, and killer moves were added to αβ, we first test unenhanced αβ search in Subsection 3.1. We are interested in its performance before introducing additional improvements, especially since our test domains have smaller branching factors than e.g. the games Lines of Action (around 30) or Chinese Checkers (around 25-30) used in [Winands and Björnsson, 2011] and [Nijssen and Winands, 2012], respectively. Move ordering and k-best pruning are then added in Subsection 3.2. Using a depth-d minimax search for every rollout move aims at stronger move choices in the rollouts, which make rollout returns more accurate and can therefore help to guide the growth of the MCTS tree. We call this approach MCTS-IR-M (MCTS with informed rollouts using minimax).

2.2 MCTS with Informed Cutoffs (MCTS-IC)

The idea of rollout cutoffs is an early termination of the rollout in case the rollout winner, or the player who is at an advantage, can be reasonably well predicted with the help of an evaluation function. The statistical noise introduced by further rollout moves can then be avoided by stopping the rollout, evaluating the current state of the simulation, and backpropagating the evaluation result instead of the result of a full rollout to the end of the game [Lorentz, 2008; Winands et al., 2010]. If on average, the evaluation function is computationally cheaper than playing out the rest of the rollout, this method can also result in an increased sampling speed as measured in rollouts per second. A fixed number m of rollout moves can be played before evaluating in order to introduce more non-determinism and get more diverse rollout returns. If m = 0, the evaluation function is called directly at the newly expanded node of the tree. As in MCTS-IR, our MCTS-IC implementation avoids deterministic gameplay through randomly choosing among equally valued moves in the selection policy. We scale all evaluation values to [0, 1]. In the following, we call this approach MCTS-IC-E (MCTS with informed cutoffs using an evaluation function).

We propose an extension of this method using a depth-d minimax search at cutoff time in order to determine the value to be backpropagated. In contrast to the integrated approach taken in [Winands and Björnsson, 2011], we do not assume MCTS-IR-M as rollout policy and backpropagate a win or a loss whenever the searches of this policy return a value above or below two given thresholds. Instead, we play rollout moves with an arbitrary policy (uniformly random unless specified otherwise), call minimax when a fixed number of rollout moves has been reached, and backpropagate the heuristic value returned by this search. Like MCTS-IR-M, this strategy tries to backpropagate more accurate rollout returns, but by computing them directly instead of playing out the rollout. We call this approach MCTS-IC-M (MCTS with informed cutoffs using minimax).

2.3 MCTS with Informed Priors (MCTS-IP)

Node priors [Gelly and Silver, 2007] represent one method for supporting the selection policy of MCTS with heuristic information. When a new node is added to the tree, or after it has been visited n times, the heuristic evaluation h of the corresponding state is stored in this node. This is done in the form of virtual wins and virtual losses, weighted by a prior weight parameter γ. The following formulas show how to update the win (w) and visit (v) counters of the node at hand.

We assume h ∈ [0, 1]. If the evaluation value h is 0.6 and the weight γ is 100, for example, 60 wins and 100 visits are added to the node at hand. This is equivalent to 60 virtual wins and 100 - 60 = 40 virtual losses. Since heuristic evaluations are typically more reliable than the MCTS value estimates resulting from only a few samples, this prior helps to guide tree growth into a promising direction. If the node is visited frequently however, the influence of the prior progressively decreases over time, as the virtual rollout returns represent a smaller and smaller percentage of the total rollout returns stored in the node. Thus, MCTS rollouts progressively override the heuristic evaluation. We call this approach MCTS-IP-E (MCTS with informed priors using an evaluation function) in this article.

We propose to extend MCTS-IP with a depth-d minimax search in order to compute the prior value to be stored. This approach aims at guiding the selection policy through more accurate prior information in the nodes of the MCTS tree. We call this approach MCTS-IP-M (MCTS with informed priors using minimax).

3 Experimental Results

We tested the algorithms in three different domains: Othello, Catch the Lion, and 6×6 Breakthrough. These are all deterministic perfect-information turn-taking zero-sum games. As baseline algorithm for comparison, we used MCT S-Solver, an MCTS variant that is able to handle proven game-theoretic values [Winands et al., 2008].

We first briefly summarize the main takeaways of our experimental results for MCTS-IR-E, MCTS-IC-E, and MCTS-IP-E, as well as MCTS-IR-M, MCTS-IC-M, and MCTS-IP-M using unenhanced αβ. After identifying the branching factor of a domain as an important limiting factor for algorithm performance, we then provide the main findings of our improved results for MCTS-IR-M-k, MCTS-IC-M-k, and MCTS-IP-Mk using αβ with move ordering and k-best pruning. Please refer to the full article for detailed results, and for a description of the heuristic board evaluation functions used in the three test domains.

3.1 Results with Unenhanced αβ

In all experimental conditions, we compared the hybrids (ending -M) as well as their counterparts using heuristics without minimax (ending -E) against regular MCTS-Solver as the baseline. Rollouts were uniformly random except for MCTS-IR. Optimal MCTS parameters such as the exploration factor C were determined once for MCTS-Solver in each game and then kept constant for both MCTS-Solver and the MCTSminimax hybrids during testing. Draws, which are possible in Othello, were counted as half a win for both players. We used minimax with αβ pruning, but no other search enhancements. Computation time was 1 second per move.

Main Findings

• MCTS-IR-E works well in all three domains. However, MCTS-IR-M does not improve on it in any domain. The reason is the high computational cost of calling minimax many times in each MCTS simulation.
• MCTS-IC-E works well in all domains but Breakthrough (the evaluation function we used in Breakthrough may not be accurate enough for MCTS to fully rely on it instead of rollouts). However, MCTS-IC-M does not improve on MCTS-IC-E in any domain, the reason again being the high computational cost of calling minimax even just once in every MCTS simulation.
• MCTS-IP-E works well in all domains. MCTS-IP-M improves on it in all domains but Breakthrough. The reason is probably that the parameters of MCTS-IP make it easier to control the computational cost, but the branching factor of Breakthrough (15.5 compared to 10.5 in Catch the Lion and 8 in Othello) is still causing problems.
• In conclusion, MCTS-IP-M seems to be a promising hybrid, but the sensitivity to the branching factor of the given domain is a problem for the hybrids in general.

3.2 Results withMove Ordering and k-best Pruning

In Subsection 3.1, αβ search was used in its basic, unenhanced form. This was sufficient to improve MCTS-IP in Othello and Catch the Lion, but too computationally expensive for MCTS-IR and MCTS-IC in these two domains, as well as for all hybrids in Breakthrough. The performance difference between the hybrids can be explained by the fact that MCTSIP allows to control the frequency of minimax calls with the parameter n, while MCTS-IC needs to call minimax once in every simulation, and MCTS-IR even for every single simulation move. This makes it easier for MCTS-IP to trade off the computational cost of embedded minimax searches against their advantages over static evaluation function calls. The performance difference between the domains can be explained by the larger branching factor of Breakthrough compared to Othello and Catch the Lion, which affects full-width minimax more strongly than for example the sampling-based MCTS. The main problem of MCTS-minimax hybrids seems to be their sensitivity to the branching factor of the domain.

We therefore conduct further experiments applying limited domain knowledge not only for state evaluation, but also for move ordering. The application of move ordering is known to strongly improve the performance of αβ through a reduction of the average size of the search tree [Knuth and Moore, 1975]. Additionally, with a good move ordering heuristic one can restrict αβ to only searching the k moves in each state that seemmost promising to the heuristic (k-best pruning). The number of promising moves k is subject to empirical optimization. Move ordering and k-best pruning could make all MCTS-minimax hybrids viable in domains with much higher branching factors, including the newly proposed MCTS-IC-M and MCTS-IP-M. We call the hybrids with activated move ordering and k-best pruning enhanced hybrids or MCTS-IRM-k, MCTS-IC-M-k, and MCTS-IP-M-k, respectively. Please refer to the full article for detailed results, for a description of the move ordering functions used, and for an analysis of their effectiveness at reducing effective branching factors.

Main Findings

• MCTS-IR-M-k improves on MCTS-IR-E in all three domains. However, its strength comes from move ordering and k-best pruning alone, not from embedded minimax searches: The optimal minimax search depth is the minimal depth of 1.
• MCTS-IC-M-k improves on MCTS-IC-E in Othello and Breakthrough. However, its strength again comes from move ordering and k-best pruning, not from minimax - the optimal search depth for minimax is 1 here, too.
• MCTS-IP-M-k improves on MCTS-IP-E (and MCTS-IP-M) in all three domains, and truly profits from the embedded minimax searches (optimal minimax depths are larger than 1 in all test domains). It is significantly stronger than the best player found with unenhanced αβ in all domains, and stronger than all other hybrids tested.
• A comparison of domains shows that all hybrids are most successful in Catch the Lion, probably due to the higher number of shallow hard traps in this Chess-like domain.
• MCTS-IP-M-k works well at all tested time settings from 250 ms per move to 5 s per move, but can overfit to the time settings it was tuned for.
• MCTS-IP-M-k and MCTS-IC-M-k, the hybrids proposed in this article, become considerably more effective as we increase the branching factor in Breakthrough by enlarging the board from 6×6 to 18×6. MCTS-IR-M-k cannot handle larger branching factors this well due to the much higher number of minimax calls.
• It is potentially useful to combine different ways of using identical domain knowledge in MCTS-minimax hybrids. MCTS-IP-M-k for example profits from the combination with MCTS-IR-M-k in Breakthrough and Catch the Lion.
• The combination of MCTS-IP-M-k and MCTS-IR-M-k outperforms both its MCTS part and its αβ part in Breakthrough, demonstrating a successful combination of the advantages of the two search approaches. In Catch the Lion and Othello however, regular αβ is still stronger than the best MCTS hybrids found for each domain.
• In conclusion, MCTS-IP-M-k is the strongest standalone MCTS-minimax hybrid investigated in all three tested domains. The use of enhanced minimax for computing node priors is therefore a promising new technique for integrating domain knowledge into an MCTS framework.

4 Conclusion and Future Research

In this article, we continued the research on MCTS-minimax hybrids for the case where domain knowledge in the form of heuristic evaluation functions is available. Three approaches for integrating such knowledge into MCTS were considered. MCTS-IR uses heuristic knowledge to improve the rollout policy. MCTS-IC uses heuristic knowledge to terminate rollouts early. MCTS-IP uses heuristic knowledge as prior for tree nodes. For all three approaches, we compared the computation of state evaluations through simple evaluation function calls (MCTS-IR-E, MCTS-IC-E, and MCTS-IP-E) to the computation of state evaluations through shallow-depth minimax searches using the same heuristic knowledge (MCTS-IR-M, MCTS-IC-M, and MCTS-IP-M).

Experiments with unenhanced αβ in the domains of Othello, Breakthrough and Catch the Lion showed that the embedded minimax searches improve MCTS-IP in Othello and Catch the Lion, but are too computationally expensive for MCTS-IR and MCTS-IC in these two domains, as well as for all hybrids in Breakthrough. The main problem of MCTS-minimax hybrids with unenhanced αβ seems to be the sensitivity to the branching factor of the domain at hand.

Further experiments introduced move ordering and k-best pruning to the hybrids in order to cope with this problem, resulting in the enhanced hybrid players called MCTS-IRM-k, MCTS-IC-M-k, and MCTS-IP-M-k. Results showed that with these simple enhancements, MCTS-IP-M-k is the strongest standalone MCTS-minimax hybrid investigated in this article in all three tested domains. Because it does not have to call minimax in every rollout or even in every rollout move, it performs better than the other hybrids at low time settings when performance is most sensitive to a reduction in rollouts. It was also shown to work well at higher branching factors. Additionally, it was shown that the combination of MCTS-IPM-k with minimax rollouts can lead to further improvements in Breakthrough and Catch the Lion. Moreover, the bestperforming hybrid outperformed a simple αβ implementation in Breakthrough, demonstrating that at least in this domain, MCTS and minimax can be combined to an algorithm stronger than its parts. MCTS-IP-M-k, the use of enhanced minimax for computing node priors, is therefore a promising new technique for integrating domain knowledge into an MCTS framework.

A first direction for future research is the application of additional αβ enhancements. As a simple static move ordering has proven quite effective in all domains, one could for example experiment with dynamic move ordering techniques such as killer moves or the history heuristic.

Second, some combinations of the hybrids play at a higher level than the hybrids in isolation, despite using the same heuristic knowledge. This may mean we have not yet found a way to fully and optimally exploit this knowledge, which should be investigated further.

Third, differences between test domains such as their density of terminal states, their density of hard and soft traps, or their progression property [Finnsson and Björnsson, 2011] could be studied in order to better understand the behavior of MCTS-minimax hybrids with heuristic evaluation functions, and how they compare to standalone MCTS and minimax.

Finally, recent work on AlphaZero [Silver et al., 2017] has demonstrated the impressive success of using deep reinforcement learning to train a neural network which encodes domain knowledge. This network was then used within MCTS both for biasing the selection policy as well as for replacing the rollout policy with a state evaluation. It remains an interesting line of future work to see if powerful function approximators such as deep neural networks can also be even more effectively used in hybrid search algorithms such as those proposed here.