Improved simulation adjusting

1. Introduction

The Monte-Carlo (MC) method was first applied to the game of Go by Brügmann (1993). This method evaluates candidate moves in a board position by performing many random simulations and returns the move with the best win rate. Although theoretically interesting, the methodology presented in the paper had little success from the viewpoint of enhancing the strength of Go programs. Later, the idea of applying the MC method to Go was picked up by Coulom (2007), and Gelly and Silver (2007) in the form of the Monte-Carlo Tree Search (MCTS), which is now viewed as being indispensable for modern strong Go programs. In October 2015, Silver et al. (2016) and their program AlphaGo beat a professional Go player with no handicap for the first time using MCTS and other methods.

MCTS is supported by two major techniques, each of which has made significant contributions to the strength of Go programs. The first technique, Upper Confidence bound applied to Trees (UCT, Kocsis and Szepesvári, 2006), is a system that efficiently allocates computational resources (Gelly and Silver, 2007); the UCT algorithm gradually concentrates computing power on promising nodes. The other important technique is the machine learning method due to Coulom (2007) that learns a policy to perform smarter simulations from human game records. Coulom (2007) considered the problem of predicting the next move from a current position, modeled it using a generalized Bradley-Terry model, and optimized the parameters of the model to fit the expert players’ game records by using the Minorization-Maximization (MM) method (Hunter, 2004). Coulom’s method significantly raises the correct answer ratio of the next move prediction, and it has been empirically shown that the simulation policy developed by Coulom’s method outperforms a uniformly random simulation policy. Coulom’s method is currently widely used, including in AlphaGo.

Looking at these two techniques from the theoretical viewpoint, we can notice that they have different statuses. UCT has a firm theoretical basis that comes from the theory of the bandit problems (Auer et al., 2002; Kocsis and Szepesvári, 2006). And also, UCT has been proved to be correct in the sense that the probability of selecting the best move converges to 1 as the number of simulations grows to infinity. In contrast, the validity of Coulom’s method has been supported on an experimental basis. In fact, Coulom’s model is aimed at better move prediction, not a correct result of MCTS method. As such, a natural question arises; is it possible to develop a better method than Coulom’s method if the aim is a correct result of MCTS method? In other words, can we develop a method to make a policy that gives correct moves when it is used in MCTS? This question motivates the current paper.

One may think that a stronger simulation policy would make an MCTS Go program stronger, but this is not true. Gelly and Silver (2007) reported that a stronger simulation policy may not enhance the strength of an MCTS Go program. Their experiments show that their Go program MoGo was stronger when a handmade simulation policy was used, which was a weak player itself. In particular, the famous policy of MoGo decides a move almost deterministically. MoGo’s policy works fine in practice, and it is sometimes better than policies developed with the MM method. As a result, many MCTS Go programs still use it. To the best of the authors’ knowledge, however, the reason why MoGo style simulation policies work well is as yet unclear.

Silver and Tesauro (2009) proposed a new learning method called simulation balancing to acquire a better simulation policy with the help of a stronger trainer Go program. After that, Huang et al. (2010) tried simulation balancing on a 9 × 9 board. In simulation balancing, they tried to make neither strong simulation policies nor better move prediction systems, but rather simulation policies that would attain a strong Artificial Intelligence (AI) player whose win rates, as computed in simulations, would be close to those of strong trainer AIs. Simulation balancing requires a strong trainer AI to train a weak trainee AI. Here, Huang et al. (2010) tried to use the same program as a trainer program and a trainee program by adjusting simulation amounts, but the trainee program’s win rate against GNU Go hardly improved.

Inspired by simulation balancing, Araki et al. (2014) proposed a method to learn a simulation policy in a MC method, called simulation adjusting. Simulation adjusting aims to match an AI’s move to a correct move in game records of experts by using gradient descent as in simulation balancing. Unlike Coulom’s method, simulation adjusting aims at directly developing a better simulation policy, not a better move predictor. Moreover, unlike simulation balancing, simulation adjusting does not require a strong trainer AI. We can find some existing work that aim to match moves of AI to those of human experts in chess (Tesauro, 2001) and shogi (Hoki and Kaneko, 2014). Their work trained evaluation functions of heuristic minimax search method. Therefore, it would be interesting to research such idea to train a policy function of MCTS method.

This paper is a continuation of the conference paper (Araki et al., 2014), which for the first time proposed the idea of simulation adjusting and reported preliminary experiments on 4 × 4 Go problems. Compared with the conference paper, in this paper, we give: (i) a new model of the objective function that enables us to avoid undesirable leaning results, (ii) a firm theoretical basis for improved simulation adjusting, (iii) more tests using 5 × 5 Go problems.

After the second submission of this paper, we have noticed the work by Graf and Platzner (2016), which also have reexamined simulation balancing and improved the playing strength of a Go program.

2. Theory

Following Coulom (2007), we shall use the soft-max model (Bishop, 2006) in simulations of primitive MC. Let F be the set of features, and a move at a position can have one feature or more in F . For i ∈ F , let us define the indicator function of a position s and a move a by ϕ i ( s , a ) s.t. ϕ i ( s , a ) = 1 when a has feature i at s and otherwise ϕ i ( s , a ) = 0 .

Next, we construct a model parameterized by θ ∈ R | F | , where θ i represents the weight of feature i. The policy function π θ ( s , a ) represents the probability that a move a is chosen at a position s as (1) π θ ( s , a ) = exp ( ∑ i ∈ F ϕ i ( s , a ) θ i ) ∑ b ∈ M ( s ) exp ( ∑ i ∈ F ϕ i ( s , b ) θ i ) where M ( s ) is the set of legal moves at position s. We assume that 2 ⩽ | M ( s ) | ⩽ ∞ .

The game record G is a set of tuples ( s , a ) , wherein s is a position with at least two legal moves, and a is a move played by a strong human player at s. Coulom (2007) considered the maximum likelihood problem: (2) θ ∗ = argmax θ ∏ ( s , a ) ∈ G π θ ( s , a ) , and proposed to solve the problem by using the MM method. Theoretically, this aims to increase the probability that the next move of a position in a simulation is the move that is likely to be chosen by expert players when they play at the same position.

In contrast, we propose to adjust the parameter θ to increase the probability that the selected move after simulations is the experts’ move. For this purpose, we design our objective function in the following way. First, defining the notation s ∘ a to express the position that appears after move a from s, we let V ( s , a , θ ) be the win rate of s ∘ a according to the simulation policy π θ . Then, we denote by a ∗ the correct move, i.e., ( s , a ∗ ) ∈ G . We try to adjust θ so that the win rate of a simulation starting from a ∗ at s is larger than that of a simulation starting from any other a at s. We denote the distribution of position s in the training data G by ρ, and propose the objective function to be minimized as: E ρ [ σ ( max a ≠ a ∗ V ( s , a , θ ) − V ( s , a ∗ , θ ) ) ] . Here, σ ( x ) = ( 1 + e − x ) − 1 − 1 / 2 is the shifted sigmoid function.

Below, we describe some of the properties of the objective function. We define for i ∈ F , ψ i ( s , a , θ ) = ∂ ∂ θ i ln π θ ( s , a ) .

Lemma 1.

We have, for i ∈ F , (3) ψ i ( s , a , θ ) = ϕ i ( s , a ) − ∑ b ∈ M ( s ) π θ ( s , b ) ϕ i ( s , b ) .

We assume that any simulation ends by a finite move sequence, and the reward of a simulation ξ is given by z ( ξ ) = 1 if ξ ended as winning position 0 otherwise, and P θ , s ( ξ ) is the probability of a simulation ξ starting from s under the policy π θ . Suppose that from a position s, we choose a ∈ M ( s ) and perform a simulation ξ from s 1 = s ∘ a . We define η i ( s , a , θ ) = ∂ ∂ θ i V ( s , a , θ ) for a ∈ M ( s ) and i ∈ F . When a simulation ξ consists of a finite sequence of positions s 1 , s 2 , … , s T where s t + 1 = s t ∘ a t for t = 1 , 2 , … , T − 1 , we denote L ( ξ ) = { ( s 1 , a 1 ) , … , ( s T − 1 , a T − 1 ) } . We have the following lemma, whose proof we put in the Appendix. Lemma 2.

It holds that for i ∈ F , (4) η i ( s , a , θ ) = E P θ , s ∘ a [ z ( ξ ) ∑ ( s ′ , a ′ ) ∈ L ( ξ ) ψ i ( s ′ , a ′ , θ ) ] .

We can compute the partial derivative of our objective function as follows. Theorem 3.

We have ∂ ∂ θ i E ρ [ σ ( max a ≠ a ∗ V ( s , a , θ ) − V ( s , a ∗ , θ ) ) ] = E ρ [ σ ′ ( V ( s , a max , θ ) − V ( s , a ∗ , θ ) ) ( η i ( s , a max , θ ) − η i ( s , a ∗ , θ ) ) ] , where a max = argmax a ≠ a ∗ V ( s , a , θ ) .

3. Algorithm

From Theorem 3, we can find a descent direction by approximating the partial derivatives, and construct the improved simulation adjusting algorithm. Since E ρ is the expectation with respect to the empirical distribution, we can compute it easily from the data. Suppose we perform a finite number of simulations from s, and let χ ¯ θ ( s ∘ a ) be the set of simulations performed from the position s ∘ a under the policy θ. Then we make the following approximations: V ( s , a , θ ) ∼ V ¯ ( s , a , θ ) = | χ ¯ θ ( s ∘ a ) | − 1 ∑ ξ ∈ χ ¯ θ ( s ∘ a ) z ( ξ ) , and a max ∼ a ¯ max = argmax a ≠ a ∗ V ¯ ( s , a , θ ) . Furthermore, we make the approximation, (5) η i ( s , a , θ ) = E P θ , s ∘ a [ z ( ξ ) ∑ ( s ′ , a ′ ) ∈ L ( ξ ) ψ i ( s ′ , a ′ , θ ) ] ∼ | χ ¯ θ ( s ∘ a ) | − 1 ∑ ξ ∈ χ ¯ θ ( s ∘ a ) z ( ξ ) ( ∑ ( s ′ , a ′ ) ∈ L ( ξ ) ψ i ( s ′ , a ′ , θ ) ) . On the basis of the above discussion, we arrive at the algorithm of improved simulation adjusting, which is described in Algorithm 1.

Several remarks on the algorithm follow.

OPEN IN VIEWER

Algorithm 1

Improved Simulation Adjusting

The subscript F means that the corresponding variable is a vector, each of whose elements is indexed by a feature i ∈ F .

N is the number of simulations starting from a ∈ M ( s ) ; in this version, we assume that the number of simulations is the same for every a. Of course, we can consider a variant of the algorithm that distributes simulations non-uniformly according to, say, the Upper Confidence Bound (Auer et al., 2002). L is the loop counter for specifying iteration.

Since the supposed application of improved simulation adjusting is the game of Go, which, in general, has a large set of candidate moves, using all candidate moves poses a significant drawback in performance. However, in other games, it might be possible to use all candidate moves.

The approximate value of the objective function is computed as follows: (6) ∑ ( s , a ∗ ) ∈ G | G | − 1 σ ( V ¯ ( s , a ¯ max , θ ) − V ¯ ( s , a ∗ , θ ) ) .

As we have mentioned, the conference paper (Araki et al., 2014) already proposed the idea of improved simulation adjusting. In the conference paper, the objective function to be minimized is defined as E ρ [ ( V ( s , a max , θ ) − V ( s , a ∗ , θ ) ) 2 ] . After the conference paper was published, we extensively performed experiments on this method and found the following.

First, the objective function had a drawback: with θ minimizing this objective function, V ( s , a , θ ) tended to have the same value for every move a and position s. This was not desirable and was a natural consequence of the objective function. To avoid this tendency, the new objective function is designed to use the shifted sigmoid function of the difference between V ( s , a max , θ ) and V ( s , a ∗ , θ ) .

Second, the size of the training data was 60, whereas the number of features was several thousands. Therefore, the learned parameters could easily overfit the data. To overcome this difficulty, we discarded 3 × 3 patterns and used only tactical features. As a result, in this paper, we adjusted only 28 parameters based on 286 Go problems.

Third, the objective function value did not decrease steadily, and the variance of it was not negligible. As a result, the variance of correct answer ratio was relatively large, too. To obtain more reliable results, we increase the number of simulations N in the experiments from 50 to 1000 on the larger board in this paper.

5. Preliminary experiments on improved simulation adjusting

We tested the improved simulation adjusting algorithm on a set of Go endgame problems on 5 × 5 board. The set of problems were taken from the book (Fukui, 2002). Although the problems in the book are made for Japanese rules, we modified their komi so that black wins according to Chinese rules, as well. Other than the original problems, all of black’s moves shown in the answers were also used because all problems begin from black’s turn; black always has a winning move. In this way, we generated G , a set of 286 pairs of a problem and its answer.

To avoid data bias, we used cross validation as follows. First, we divided G into G 1 , G 2 , … , G 11 , where every G i ( i = 1 , … , 11 ) contained 26 pairs, and were disjoint from each other. Then, for each i ∈ { 1 , … , 11 } , we used G i as the test data and the others as training data. In other words, we used 260 pairs as training data, and 26 pairs as test data. Moreover, the training data were shuffled at the beginning of each iteration.

Our original program, called “MC_ark” was used in the experiments. MC_ark is based on the MCTS technique and uses the maximum entropy method (Berger et al., 1996) to generate a policy. MC_ark won 7^th place in the 8^th UEC Cup.1

As we stated in the previous section, we restricted the candidate moves because of computational performance limitations. Instead of the set of all legal moves on s, M ( s ) , we used a subset M ¯ ( s ) of M ( s ) constructed as follows. First, we applied MC_ark’s original move evaluation system to select four candidate moves on s and added them to M ¯ ( s ) . Then, if the 4 candidates does not contain the answer move, we also added it to M ¯ ( s ) .

We imposed an upper bound of ln 10 = 2.30 and lower bound of ln 0.01 = − 4.61 on the value of θ i for each i ∈ F during the learning processes. In this way, we avoided overflow and underflow. In this experiment, α is 1 / ( 5 × 10 5 × ( N + 1 ) ) , and the initial vector θ is zero.

Figure 1 shows the experimental results. The bottom axis is the number of iteration L. It took one 16-core machine (Xeon E5-2687W) about half a day to obtain the results. We can see that the objective function values have steadily decreased in the first several iterations. After the decrement, the value fluctuates. Improved simulation adjusting achieved the correct answer rate of test data 0.70, whereas MM method did 0.67. Our experiment showed that improved simulation adjusting reached to a comparable level of MM method. It would be difficult to see a result that outperforms MM method by a statistically significant amount when the policy function is modeled by only 28 parameters and the training and test data contain only 286 correct moves on the 5 × 5 board. For further improvement, an extension which enables us a large-scale experiment from this work might be necessary.

OPEN IN VIEWER

Fig. 1.

Change in the objective function value estimated by using 11-fold cross validation.

This paper has shown an advanced version of simulation adjusting. The differences from the original work are: (i) the new objective function is capable of avoiding the case where the simulation values reduce to a constant value, (ii) the number of weights is less than the number of training data to avoid overfitting, and (iii) the number of simulations is increased to compute the objective function and its partial derivative values accurately.

We have carried out numerical optimization of 28 weights in the policy function by using 5 × 5 Go problems. We confirmed that both of the objective function values of training and test data decreased steadily. We also observed that simulation adjusting improves the performance of Monte-Carlo simulations in terms of the correct answer rates.

We have revealed a barrier in applying simulation adjusting to a 19 × 19 board. It took a half day to learn only 28 weights on 5 × 5 board, thus it consumes too much time to adjust thousands or more weights to play decent games on a 19 × 19 board.

There are some future works that are necessary to be investigated. First, we shall develop a method to combine simulation adjusting with Upper Confidence Bound (Auer et al., 2002) or its variants to balance exploration and exploitation of candidate moves. Note that, in this paper, candidates were narrowed down by means of the static evaluation function without using simulation results. Second, we shall examine the performance of MCTS when a policy learned by simulation adjusting is used. Note that, in this paper, the performance of policy was measured by using the primitive Monte-Carlo method instead of using MCTS. Third, we shall improve computational efficiency of simulation adjusting to enlarge the size of board and training data.