REFINING MONTE CARLO TREE SEARCH AGENTS BY MONTE CARLO TREE SEARCH
Authors: Katsuki Ohto
Venue:  (2020)
Keywords: Reinforcement Learning
Monte Carlo Tree Search
Alpha Zero

Abstract: Reinforcement learning methods that continuously learn neural networks by episode generation with game tree search have been successful in two-person complete information deterministic games such as chess, shogi, and Go. However, there are only reports of practical cases and there are little evidence to guarantee the stability and the final performance of learning process. In this research, the coordination of episode generation was focused on. By means of regarding the entire system as game tree search, the new method can handle the trade-off between exploitation and exploration during episode generation. The experiments with a small problem showed that it had robust performance compared to the existing method, Alpha Zero.

Under review as a conference paper at ICLR 2020
REFINING MONTE CARLO TREE SEARCH AGENTS BY MONTE CARLO TREE SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Reinforcement learning methods that continuously learn neural networks by episode generation with game tree search have been successful in two-person com- plete information deterministic games such chess, shogi, and Go. However, there are only reports of practical cases and there are little evidence to guaran- tee the stability and the final performance of learning process. In this research, the coordination of episode generation was focused on. By means of regarding the en- tire system game search, the new method can handle the trade-off between exploitation and exploration during episode generation. The experiments with a small problem showed that it had robust performance compared the existing method, Alpha Zero.
INTRODUCTION
The result that computer programs beat professional human players chess, shogi and Go huge achievement in computer science. In particular, the development of highly general methods totally changed our perspective about two-person complete information deterministic games.
Then, has this field already finished " My answer is no. To deal with many games, more robust methods are required free humans from hyperparameter tuning. Moreover, the challenge the god of games won't 't be finished and we want algorithms that can achieve better final performance.
This study attempts bring suggestions for recent achievements in two-player complete information deterministic games from classical game tree search" context. More specifically, this is new approach which the reinforcement learning system using game tree search itself is handled as game tree search.
APPROACH TO COMPLETE INFORMATION GAMES
2.1 REINFORCEMENT LEARNING
Tum-based complete information environments this report deals with is called Markov decision process. When the state 8; observed at the time and the action a, performed, environment returns immediate reward and the next state 8:-1.
In general, reinforcement learning is a framework which improves agent's policy p and value esti- mation in given environment. While p and can be stored in a table for all states in small environment, function approximation commonly used for larger problems. Model-free reinforce- ment learning using deep neural network (DNN) has been achieving great resutls after the success on several video game environments.
This study is aimed at two-person complete information deterministic games. While various model- free reinforcement learning algorithms can be applied to these games, we can also apply model- based reinforcement learning because agents keep the state transition model of the environment.
2.2 GAME TREE SEARCH
In particular, we can apply forward planning to the two-person complete information deterministic game using the fact that the progress of the game is represented tree structure. Ideally, the

---

Under review as a conference paper at ICLR 2020
winning player and the optimal action in any two-player complete information deterministic game in which a finite number states can appear can determined by performing minimax search on the game tree within finite time.
Actually, it is not necessary to search all states in order to determine the winner at the initial state. We can use alpha-beta search which reduces useless search. However, if the game is not very easy, is not realistic to complete alpha-beut beta search that takes exponential time against the size of the game.
For this reason, various methods have been developed so far that can be executed in a realistic time and achieve sufficient performance. Roughly, both the algorithmic improvement of the search and the reduction of the search amount by the function approximation have been much effective.
For example, Monte Carlo tree search (MCTS), which is the base of this research, performs effec- tive forward search using function approximations, With the good property that the performance improves monotonously the the time being spent is, MCTS is widely used in this field.
2.3 MONTE CARLO TREE SEARCI
There are a number of variants of Monte Carlo tree search, but the algorithm PUCT in algorithm 2 is described in this report. In that pseudo code, it is assumed that the turn player is changed every turn, and the discount factor 1, and the immediate reward is obtained only at the terminal state.
The Monte Carlo tree search starts from empty game- and the node which represents one state is added to expand the game tree in each simulation. After expanding tree, the new state value which approximation function (e.g. neural nets) has returned is fed back to the upper nodes to update the estimated action value of each node.
The core of the Monte Carlo tree search is how decide action response the game tree, where the bandit algorithm is used.
The bandit algorithm is algorithm for maximizing the cumulative reward in problem setting where we select one of multiple slot machines that we do not know the true average reward in one turn. is required for bandit algorithms to handle the trade-off between exploration and exploitation.
In the Monte Carlo tree search, by using this bandit algorithm for selection phase at each node, the best action is asymptotically proven and selected at each node, and result, asymptotically find the optimal action. PUCT uses the following PUCB formula I as the bandit algorithm.
(qs.a + Cps.a 22 Dadb
action
arg max LegaiAAcc
n2,a +
In previous research, the output of Monte Carlo search usually only consists the best action or the new policy probability distribution at the root node. However, the new estimated value at the root node (F, algorithm 2) also returned in algorithm in order to use it in this research.
Although it is detailed point, there is important point that is heavily related to the experimental results of this report, which is that some noise is added to the policy by applying AddNoise() function only at the root node shown in the algorithm 1. This is because the root node is recognized not only as bandits but also as best arm identification problems. Therefore the action selection should be more exploratory to find good actions which have been evaluated poorly.
In previous method, noises generated by the Dirichlet distribution are added described in This study follows that.
p p (1-e) P Dirichlet(a)
2.4 REINFORCEMENT LEARNING WITH MONTE CARLO TREE SEARCH
Also from the viewpoint reinforcement learning, it is useful for agents to be able to perform the game tree search using the true environment model. This is because agents can usually obtain
2

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Simulation in PUCT
Data: state 8, neural net net, depth d Result: reward or new q-value begin
s terminal state then
return reward at
end
if nz.a = 0 for all LegalActions(s) then
Ps. U/ f net(s)
return U.
end
Ps
if d
0 then AddNoise(p)
end
action
- select by PUCB(n, 9s p)
Transition(s, action)
qnew
Simulation s', + 1)
9s.0
(gs,n + (new) (n 1)
Ns.a
Ns.,a +
return Quew
end
Algorithm 2: PUCT
Data: state 8p, neural net net, total simulation count N Result: posterior estimation of policy and value at 8p begin
while E < N do Simulation(sn,, net, 0)
end
Ppost Posterior(n,. (D 9xpr )
Upost Ppost qsp
return Ppost, Upost
end
3

---

Under review as a conference paper at ICLR 2020
better strategy and more accurate value estimation by performing the game tree search. Therefore, the game tree search can be seen as kind of operator to improve there estimates.
Various reinforcement learning studies using this property have been done. In particular Alpha Zero and EXpert I'Teration are the great success, which enables us to handle various games. These algorithms continuously update approximation function by making training targets by using Monte Carlo tree search as such operator.
The procedure in Alpha Zero is followed in this research. The algorithm 3 describes the single thread version of Alpha Zero
Algorithm 3: Alpha Zero (single thread version)
Data: total epochs E, games per epoch G, each simulation count N Result: trained neural net begin
net <- initialized neural
episodes &- (
for e E 1..E do for g 1..G do traj - 0
original state so
while is not terminal state do
Ps: U2 v PuCT(s, net, N) action + sampled from ps
traj k traj U (p., Ua action) Transition action)
end
r - reward at episodes t- episodes U (traj, r)
end
net TrainNeuraaNee((ne,,, episodes)
end
return net end
REINFORCEMENT LEARNING WITH MASTER GAME TREE
In the previous method, the variety of generated episodes is dependent random action selection after Monte Carlo tree search.
However, if there is state where the policy calculated by the neural network sharp, it might be difficult to reverse action evaluation in a limited number of simulations. Therefore, there may be several weak states even after long-time learning process. The experimental results in this study suggest that such phenomena can be actually observed.
Wo (2019) proposed the preprocess and the post-process to the simulation counts in order to improve explorability at the root node. His result suggested that this method can accelarate the learning speed in leaning Go.
In this report, from the other perspective, a method to apply Monte Carlo tree search to the whole episode generation procedure is proposed.
3.1 MASTER GAME TREE
The output of the Monte Carlo tree search is probability distribution and new state value estimation. Therefore, the Monte Carlo tree search itself can be also regarded as a function of policy and value estimation.
4

---

master game policy by MCTS value by MCTS Under review as a conference paper at ICLR 2020
The fact that the Monte Carlo tree search itself can be regarded function of policy and value estimation implies that we can execute Monte Carlo tree search which uses this function. In the proposed method, the Monte Carlo tree search is performed on the master side that organizes episode generation. This is hereinafter referred as a master game tree.
The value of the table 1 is stored in each node of the master game tree.
Table I:
Values stored in ordinal game tree and master game tree
variable
ordinal game
Pa.a
policy by DNN
Us
value by DNN
7,,aa
the number of simulations
the number of episodes estimated action value in episodes
qs,a
estimated action value in simulations
Thus, the values stored in each node in the master game tree has one-to-one correspondence with the values stored the ordinal Monte Carlo tree search node. Therefore the master game tree can be implemented as same as the ordinal one.
desired that the master game tree converges to the optimal strategy asymptotically by assigning episode generation by this master game tree. It seems that theoretical convergence will be guaranteed same classic bandit algorithm with no prior information is used each action selection on the master game tree.
However, through the success rescarch on the Monte Carlo tree search so far, function approxi- mation is also used on the master game tree side in the proposed implementation in this report. It means that PUCT is also applied to the master game tree.
Since the proposed method uses the master game tree as to refine the performance of Monte Carlo tree search by the other Monte Carlo tree search, this report named it MbM (MCTS-by-MCTS),
3.2 UPDATE POLICY AND VALUE THE MASTER GAME TREE
The difference between this master game tree search and the ordinal Monte Carlo tree search is that the accuracy of the policy and the value estimation returned by neural nets is increased through proceeding training. Therefore, by updating the p and v, which fixed after the node creation timing in ordinal PUCT, bandits on the nodes that has already created can behave as if they had created recently.
Instead of replacing calculated after each episode the proposed method. helps absorb the fluctuation of the result of each trial of the Monte Carlo tree search. This weighting ratio can be increased as the generation of neural networks progresses to emphasize newer estimation. In this report, however, a simple average is used.
with new ones, the weighted average between old ones and new ones are
Specifically, the master game tree updated as in the algorithm 4. The state value estimate of the newly added node and the difference between the old and the new state value estimation inside the tree are summed and propagated to the upper nodes.
Using this update rule, the entire proposed method is discribed in the algorithm 5. The NextPathBy- MasterTree() function, which generates the opening action sequence by descending the master game tree, is almost the same the operation of descending the tree in the algorithm 1. When going down the master game tree, the noise is always added to p, in the algorithm in the regular version the proposed method. This point will be discussed the later part of this report.
5

---

Under review as a conference paper at ICLR 2020
Algorithm 4: Master Game Tree Update
Data:
state 8, guide path path, trajectory (sequence (policy, value, action) tuple) traj, reward
Result: reward or new q-value with internal tree updates begin
path then
if terminal state then
return
end
Pa. c. action traj(0]
return
end
Psnew: Usnew action (0]
1/ LaataoplAAttiooo As,a
Usold
Us
P,
Ps
w) + Panew w
0, - Ug (1 w) + Vsnew *
Transition(s. action)
Qnew UpdateMasteris path(1 :), traj(1 :),r)
1s.a
(gs,a + (now) (nx,a +
N2..a
Ns, +1
return Inew + U2 Usold
end
Algorithm 5: Proposed Method: MbM (single thread version)
Data: total epochs E, games per epoch G, each simulation count N Result: trained neural net begin
nel - initialized neural net
episodes +- 0
for e E 1..E do
for g 1..G do
path NextPathByMasttrTTeeed
traj < 0
s original state 50
while is not terminal state do
Pa. U4 - PUCT(s, net, N)
if [raj] < |path then action + path[[traj]]
else
action sampled from Pa end
traj f- traj U (ps: Us. action) 8' Transition(s, 8, action)
end
reward at
episodes UpdateMaster(S., path, traj, r) end
t- episodes U (traj, r)
nel TrainNeuralNe((neel,, episodes)
end
return net end

---

Under review as a conference paper at ICLR 2020
4 EXPERIMENTS
4.1 COMPARISON IN VARIOUS GENERATION TEMPERATURE
In the experiment, in the tic-tac-toe where the solution is already sought for the small size, the existing method AlphaZero and the proposed method learned for 20,000 battles, The following points were compared by the obtained neural network policy.
Ratio of defeating against random players
Ratio of defeating to perfect players
Tic-tac-toe is obviously very simple task, and easy to obtain perfect strategy by minimax search. Only by function approximation using neural network, however, it may be necessary to generate a certain number of episodes and train from them obtain good policy. Still, it is so easy problem that we desire that neural nets can output the optimal strategy.
The experiments were performed with the following settings.
In the proposed method, in the bandit on the master game tree side, the same as the root node on the episode generation side. We tried two ways of adding Dirichlet noise the policy and adding it.
Especially when adding Dirichlet noise to the policy, if the other parameters are the same in Alpha Zero and the MbM, episode generation become more exploratory in the proposed method than Alpha Zero. The performance can vary greatly depending on the effect (actually shown in the experimental results in this paper).
Therefore, the initial values of episode generation temperature parameters were varied as 0.3, 0.6, 1.2, and 2.4, respectively into both the previous method and the proposed method.
Other experimental settings and hyperparameters are shown below. For details, please refer to the online experimental code.
attenuation rate of generation temperature: 0.8
C in PUCB: 2.0
noise to the policy 0.1, 0.25
the number of epochs: 200
the number of episodes per epoch: 100
input feature: 2 planes (the position mine, the position of opponents)
detail of neural nets: (3x3 convolution with 32 filters + BN), (Wide Resnet x 4 layers), (Ix1 convolution with 2 filters BN fully connected + softmax in policy head). (Ix1 convolution with 2filters + BN + fully connected tanh)
detail of training data: (batch size 32 x the number episodes before x 50 loop) per epoch,
detail of optimization: SGD (learning rate=le-3, momentum=0.75 weight decay=le-4)
The experimental results are plotted in the figure 1 2, comparing the temperature conditions for each opponent (random player, perfect player) in the previous method AlphaZero and the proposed method MbM.
From the result of AlphaZero in the Flg. 2, Alpha Zero has not reached the optimal strategy within 200 epochs when the temperature of episode generation is low. In comparison, the result of MbM Fig. 2 shows that almost optimal strategies seem to be obtained under all conditions.
Compared through those results, the performance of proposed methods are equal to or better than the best one of AlphaZero.

---

Under review as a conference paper at ICLR 2020
AphaZero - 0.3
MaW
Aphazerot
Appazwot-11 Aphuzeet-
0020
020
oetente ra0o
0.25
0.05
0.5
0.03
100 opoch
125
150
175
200
50
75
100
125
150
175
200
opoch
Figure 1: Match results against random player
AphaZaro 0.3
MDN t- 0.3
AlphaZerot--
022
020
dcfated r00
0.25
0.05
0.05
0.03
300 epoch
125
150
175
75
300 epoch
125
150
200
Figure 2: Match results against perfect player
8

---

Under review as a conference paper at ICLR 2020
4.2 EFFECT OF NOISE ADDED POLICIES MASTER GAME TREE
In the result of the previous experiment, the proposed method MbM showed good performance- However, compared the result of Alpha Zero, there seems be the possibility that the difference of performance caused only by the explorability of episode generation by adding noise to the policy when going down the master game tree.
Additional experiment was done with the following two modified versions of the proposed method under the temperature low 0.3 or 0.6).
MbM-NoNoise: no noise added to the policy
MbM-Relaxation: applying conversion to the policy in order to soften sharpness of it.
In the latter one, the policy is modified p f- (p 0.1)/(E + 0.1)). The figure shows
learning up 100 epochs under each condition and comparing the results with those in previous experiment.
AlpnaZero
AlphwTern
0.25
MEN-Nokoset-
MEN hoNose - 0.6
0.25
Ahma m w
MEN neN-leeecettnnt 0.3
0.2
SEN Retrattnnt- 06
0.0
Alpliacans
d-festedrsto
Alpha t.
C.6
0.3
010
0.10
0.05
0.05
0.00
36
60
80
100
20
60
80
100
spoch
spoch
Figure 3: Comparison between modified version of MbM
The results in Fig. show that MbM-NoNoise, which does not add noise, is even worse than Alpha Zero. MbM-UnifomRellxattio which the fixed amount of diversity is added to the policy, was not so good as MbM but pretty better than Alpha Zero. This point will be discussed in the final section.
5 DISCUSSION
In this study, we examined very simple task, Tic-tac-toe. First of all, it was shown that obtaining the optimal strategy is sometimes difficult depending on parameters.
The results suggest that reinforcement learning methods like Alpha Zero often suffer from naiveness against exploration.
In the proposed method, it is possible to vary the beginning of the game in the episode generation by the master game tree. The results suggest that the proposed method has ability to control the search for the beginning of the game by adding proper noise.
On the other hand, when PUCT using the strategy as it is applied to the master game tree (MbM- NoNoise), the performance was lower than the bascline. The reason of this result is that the policy has converged earlier than the effect of exploration the master game tree. Due to this point, it was not effective.
In this report, PUCT is applied to the master game tree as same as ordinal game tree. However, is necessary to examine mechanism that makes it more exploratory.
Lastly, in this study, we verified only one of the simplest games, Tic-tac-toe. From the experimental results in this paper, it is expected that the proposed method produce robust results with respect

---

Under review as a conference paper at ICLR 2020
to temperature parameters even for larger games. It will also be necessary to verify whether the speed of improvement in real time better that previous methods.
I hope that the combination of tree search and reinforcement learning will be used for wider range of domains if there exists the method in which both stableness and speed are better performance.
10


Reviews:
[{"review_id": "rklDTxPsKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper appears to be attempting to improve Monte Carlo tree search, though it's not clear how. The paper is very poorly written, with many incomprehensible passages. Moreover there are no references at all. It does not appear to be a serious academic endeavor, merely a set of notes. There are many mathematical symbols not defined, much of the paper consists of blank space yet it goes up to 10 pages, the algorithm boxes are very difficult to follow, the writing is so poor that I cannot decipher what the intent even was. A significant amount of work would be required to make this acceptable for publication in any venue.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A"}, "extra_text": {}}, {"review_id": "r1xxIGWhFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Badly and unprofessionally written\n\nI had and still have a hard time to report what this paper is about. Generally, I can tell probably this paper study the Monte Carlo Tree Search-based methods in the field of Reinforcement Learning. \n\nThe paper is badly written with grammatical issues almost in all the sentences. I definitely urge the author(s) to take the writing significantly more seriously. I almost all the time do not end up rejecting a paper due to the lack of clear writing, but for this paper, unfortunately, despite spending time, I could not understand the paper.\n\n\nComments beside the grammatical issues:\nI am sorry but I could not understand the abstract.\nWhat does the author(s) mean by \"In this research, the\ncoordination of episode generation was focused on.\" Same issue with almost all the sentences in the abstract. Unfortunately, I could not follow any of them. Moreover, this paper is full of inaccurate and unjustified statements. Furthermore, again, unfortunately, this paper does not represent even the preliminary elements of scientific writing.\n\n\nI decided to provide further comments, but sadly I had to change my mind because otherwise, I had to write at least one paragraph of explanation for each paragraph of this paper. With that regard, I do not think it is an appropriate way to utilize the review process. But I would be happy to provide more abstract comments upon request. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1g9iFA2KH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper tries to improve exploration performed by alphazero in a game of tic-tac-toe using MCTS. The paper proposes to use master game tree (which is MCTS as well) to control the generation of episodes when solving a game using MCTS.\nThis is a clear case of less than half-baked paper. The paper does not cite any previous research (no references) and is poorly written. I believe this is sufficient ground for not recommending accept. I would suggest the authors to re-submit when the paper is complete, maybe, start with related work and references.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is a clear reject. The paper is very poorly written and contains zero citations. Also, the reviewers have a hard time understanding what the paper is about.
Decision: Reject