# A Continuous Space Neural Language Model for Bengali Language

Hemayet Ahmed Chowdhury  Department of Computer
Science and Engineering
Shahjalal University of
Science and Technology
Sylhet, Bangladesh
Email<EMAIL_ADDRESS>Md. Azizul Haque Imon  Department of
Computer
Science and Engineering
Shahjalal University of
Science and Technology
Sylhet, Bangladesh
Email<EMAIL_ADDRESS>Anisur Rahman  Department of Computer
Science and Engineering
Shahjalal University of
Science and Technology
Sylhet, Bangladesh
Email<EMAIL_ADDRESS>Aisha Khatun  Department of Computer
Science and Engineering
Shahjalal University of
Science and Technology
Sylhet, Bangladesh
Email<EMAIL_ADDRESS>Md. Saiful Islam  Department of Computer
Science and Engineering
Shahjalal University of
Science and Technology
Sylhet, Bangladesh
Email<EMAIL_ADDRESS>
###### Abstract

Language models are generally employed to estimate the probability
distribution of various linguistic units, making them one of the fundamental
parts of natural language processing. Applications of language models include
a wide spectrum of tasks such as text summarization, translation and
classification. For a low resource language like Bengali, the research in this
area so far can be considered to be narrow at the very least, with some
traditional count based models being proposed. This paper attempts to address
the issue and proposes a continuous-space neural language model, or more
specifically an ASGD weight-dropped LSTM language model, along with techniques
to efficiently train it for Bengali Language. The performance analysis with
some currently existing count based models illustrated in this paper also
shows that the proposed architecture outperforms its counterparts by achieving
an inference perplexity as low as 51.2 on the held out data set for Bengali.

###### Index Terms:

Language Model, Bengali, AWD-LSTM, Continuous-Space Language Model, Neural
Language Model, Deep Learning

††publicationid: pubid: 978-1-7281-5842-6/19/$31.00 ©2019 IEEE

##  I Introduction

Language Models (LMs) can generally be categorized into two variants:
continuous-space language models [1] and count based language models [2].
Traditional statistical models, which constitute of a large proportion of the
count-based architectures, follow the general idea of making n-th order Markov
assumptions and calculating the n-gram probabilities through the means of
counting and subsequent smoothing. Most of the work in Bengali Language has
been focused on count based approaches [3] and delivered decent performances
in tasks such as word clustering. A major drawback of this approach of
representing feature spaces through n-gram models is extreme sparsity and
often limits the performance of the n-gram models in their applications.

Despite being a revelation in the art of language modelling, very little work
has been done on continuous space language models for Bengali. Variants
include the feed-forward neural probabilistic language models (NPLMs) [1] and
recurrent neural language models (RNNs) [1], which solve the problem of data
sparsity that occurs in the traditional n-gram methods. This is done by
representing words as vectors (word embeddings) and using them as inputs to a
neural language model (NLM). The parameters are learned during the back-
propagation phase of the training process. The vectors are created to maintain
the property where semantically similar words are kept close to each other in
the induced vector space [1]. Neural Language Models have also been used to
capture the contextual information at multiple levels including that of
sentence, corpus and sub-word.

In this paper, we propose a variant of the recurrent neural language model
proposed in [4], named Average-Stochastic-Gradient-Descent Weight-Dropped
LSTM. We also present a framework that holds multiple techniques to optimize
the training of the language model to produce significantly low perplexities
on data sets. This paper follows the structure provided below:

  * •

Related Works - This sections provides the necessary background study on some
works relevant to this paper. Architectures, strategies and methods described
in this section are frequently used in the proposed methodology.

  * •

Corpus - The corpus used in the experiments for this paper are summarized in
this section.

  * •

Methodology - The proposed architecture for language modelling along with the
strategies used during the training phase of the neural networks are described
in depth.

  * •

Experiments - Describes the experimental setup, along with some models used
for comparative evaluations.

  * •

Results and Discussion - Analysis of the results along with possible reasons
are discussed.

  * •

Conclusion - The paper concludes with some recommendations and provides scope
for future research on this field.

##  II Related Works

###  II-A On Bengali Language

Despite being the $7^{th}$ most spoken language in the world, Bengali suffers
from a lack of fundamental resources for natural language processing.
Unsurprisingly, the work done so far on language models can be, at the very
least, considered unsatisfactory as most of the published researches propose
count-based models [3]. Although some substantial work was done [5][6] the
scarcity of continuous-space models in Bengali language still remains and thus
hampers the progress in tasks like text classification, summarization and
translation.

###  II-B On Language Models

Language Models(LMs) generally come in two major variants, count-based LM and
continuous-space LM, along with their own merits and shortcomings.

####  II-B1 Count-based language models

Constructing a joint probability distribution of a sequence of words is the
fundamental statistical approach to Language Model. n-gram LM model based on
Markov assumption can be regarded as an example of this type. In n-gram model,
we proceed by predicting one word at a time based on the previous history of
the preceding words to get the full sequence. For a preceding sequence of
words LM probability is the product of all those word probabilities
$p(w_{1},w_{2},...,w_{n})$. Previous m words are considered as history.

$p(w_{n}\mid w_{1},w_{2},\ldots,w_{n-1})\approx p(w_{n}\mid
w_{n-m},\ldots,w_{n-2},w_{n-1})$

This is called Markov chain, and order of the model is the number of previous
states(words in this case). The main idea behind n-gram is to predict the
probability of $w_{n}$ based on preceding context. If we take only one word
$w_{n-1}$ then its called bi-gram. If we divide the frequency of
$w_{n-1},w_{n}$ by frequency of $w_{n-1}$ we get the desired result. If we
only consider frequency for $w_{n}$ then it would be a uni-gram. The straight
forward equation for tri-gram(most often used) can be described as below:

$p(w_{3}\mid
w_{1},w_{2})=\frac{count(w_{1},w_{2},w_{2})}{\sum{}_{w}count(w_{1},w_{2},w)}$

However, if a combination of words is not encountered in the training corpus,
a simple n-gram model would predict zero probability for that sequence. But,
out-of-sample test cases are likely to occur and assigning zero is not
correct. This problem is called sparsity. To counter this problem, various
back-off [7] and smoothing techniques [8] were introduced, but no good
solution exists.

Despite the above mentioned smoothing techniques, another drawback of n-gram
is the curse of dimensionality. Because, there can be a huge number of
possible combination of word sequences and LM has to identify them separately.

Besides, n-gram models rely on the exact pattern (i.e. string matching), which
is linguistically uninformed. Similarity of different sentences which are
syntactically and semantically same can not be provided by n-gram models.
Another problem is that we ignore dependency beyond the window. We only take
context for n words. So, true conditional probability under Markov assumption
is not modeled.

####  II-B2 Continuous-space language models

The short-comings of n-gram LM led to the idea of applying Neural Networks and
Deep learning on LM so as to be able to extract syntactic and semantic
features of languages.

This type of language model is also known as neural language model (NLM).
There are two main types of NLM: feed-forward neural network based LM for
tackling data sparsity and recurrent NN based LM for addressing the problem of
limited context. As of late, state-of-the-art performance was achieved by
recurrent neural network approaches. Later works are focusing on different
(i.e. sub-word level modelling and corpus-level modelling) directions based on
RNN and its variant such as LSTM.

  * •

Feed-Forward Neural Network Based Models:

Neural probabilistic language model[9] is the first neural approach to LM. It
learns the parameters for conditional probability for next word using a three
layer feed-forward NN for previous n-1 words. In figure 1 an overview is given
for the architecture. In the architecture:

  1. 1.

A mapping C is built from each word of vocabulary V to a real-valued,
distributed feature vector $C(i)\in R^{m}$, where m is the number of features.
C is a matrix of $\mid V\mid\times m$, whose i-th row indicates feature vector
of word i.

  2. 2.

A function g calculates and maps conditional probability of word $w_{t}$ with
context $(C(w_{t-n+1}),\ldots,C(w_{t-1}))$ of the input sequence of feature
vectors.

  3. 3.

Lastly, both the word feature vectors and parameters of probability function
is learned with composite function f, where mappings C and g is used.

Figure 1: An overview of the network architecture of a neural probabilistic
language model [9]

In this model, we have a distributed word feature vector for each word in the
vocabulary. And a function of these feature vector express joint probability
function of the words in the sequence. The model then simultaneously learns
feature vector and parameters of the probability. Sparseness problem is solved
because of the neural network. It also tends to generalize well in comparison
to the n-gram model discussed above. However, very long training and testing
time is considered a major weakness to this approach.

To improve the training and testing speed of NLM, two models were
proposed[10][11]. The basic idea is to cluster words which are similar to
reduce calculation and load of the NN. One[10] builds a binary hierarchical
tree on the vocabulary words using expert knowledge. The other[11] uses a
data-driven method instead of expert knowledge. The best HLBL model[11]
truncates perplexity by 11.1% compared to the Kneser-Ney smoothed 5-gram LM

  * •

Recurrent Neural Network Based Models:

Unlike feed-forward neural network, we do not use limited size context in
recurrent neural networks. When using recurrent connections, information keep
circulating inside the networks for arbitrary time as long as needed. We can
have better generalization with recurrent neural network based
model(RNNLM)[12]. Recurrently connected neurons are considered to be short
term memory. For a simple architectural overview we can refer to the figure 2.

Figure 2: Recurrent neural network model [12]

For further improvement a variant of RNNLM was presented [13] where they
implemented factorization on the output layer using classes, which resulted in
reducing the computational complexity of the original RNNLM. For applications
on statistical LM, RNN usually performs better than FNN.

###  II-C On Neural Network Architectures

As of recent times, the AWD-LSTM showed excellent performances by reaching the
state-of-the-art for language modelling.[14]. AWD-LSTM stands for ASGD(Average
Stochastic Gradient Descent) Weight-Dropped LSTM. It uses various
regularization strategies, which includes DropConnect[15], a variant of
Average-SGD (NT-ASGD) and some other minor techniques in a very effective way.
The generic equation for LSTM can be described as follows:

$i_{t}=\sigma(W^{i}x_{t}+U^{i}h_{t-1})$
$f_{t}=\sigma(W^{f}x_{t}+U^{f}h_{t-1})$
$o_{t}=\sigma(W^{o}x_{t}+U^{o}h_{t-1})$
$\widetilde{c}_{t}=tanh(W^{c}x_{t}+U^{c}h_{t-1})$
$c_{t}=i_{t}\odot\widetilde{c}_{t}+f_{t}\odot+\widetilde{c}_{t-1}$
$h_{t}=o_{t}\odot tanh(c_{t})$

where, $W^{i},W^{f},W^{o},W^{c},U^{i},U^{f},U^{o},U^{c}$ represents weight
matrices, $x_{t}$ is the vector input to timestep t, $h_{t}$ is the current
exposed hidden state, $c_{t}$ is the memory cell state, and $\odot$ is
element-wise multiplication.
In conventional LSTM, over-fitting of the RNN creates problem. That is where
the DropConnect comes to play. It is applied to randomly selected activation
subset on the hidden-to-hidden weight matrices $(U^{i},U^{f},U^{o},U^{c})$
instead of hidden or memory states. This prevents over-fitting without
disrupting RNN’s ability to retain long-term dependencies. Figure 3 provides
an illustration of the DropConnect network.

Figure 3: DropConnect Network

ASGD is identical with SGD on updating steps, but ASGD also considers previous
iterations and return an average value. The variant of ASGD that is used in
AWD-LSTM is NT-ASGD(non-monotonically triggered ASGD). In this method ASGD is
triggered if validation metric fails to improve for a fixed number of cycles.
A constant learning rate is used throughout the experiment.
Other techniques include variational dropout[16] which generates the dropout
mask once upon the first call. variable length backpropagation helps reducing
the divisibility problem of elements. Embedding Dropout[16], Reduction in
Embedding Size, Activation Regularization all resulted in the improvement of
the overall structure. Successful application in achieving state-of-the-art
performance on language modeling is what makes it the best choice till date.

###  II-D On Training Neural Networks

Training neural networks so that the performance culminates as efficiently as
possible for the necessary task has become almost an art form in the recent
years. This section illustrates some of the techniques that will be employed
by this paper.

Learning rates constitute of some of the most important hyper-parameters
during the training phase. A technique known as differential learning rates
has been seen in numerous researches including the work by [17]. The
implementation of the technique makes sure that higher layers of the neural
network train at a faster rate than the deeper ones. Building deep learning
models on top of pre-existing elements, such as embedding layers, has
delivered excellent performances as of late. The general idea also means that
the latter layers will need to be somewhat modified. Figure 4 provides an
illustration of differential learning rates [18].

Figure 4: Application of Differential Learning Rates

Another technique introduced by [17] employs gradual unfreezing of the layers.
For instance, in cases of transfer learning, trying to train all the layers of
an entire model consisting of pre-trained weights at once creates the risk of
catastrophic forgetting of the pre-trained weights. [17] proposed to gradually
unfreeze the layers, starting from the last, which contains the least bit of
relevant information initially.

Despite being one of the most deciding factors in the efficient training of a
neural network, finding the right learning rate has been incredibly tedious
over the years, often involving multiple trial and error experiments. To
address the issue, Leslie Smith published an impressive approach [19]. The
method includes doing a trial run and training the neural network using a low
learning rate, but increasing it exponentially with each batch. Meanwhile, for
every value of the learning rate, the loss is recorded. The point where the
learning rate is highest but the loss is still descending is taken as the
optimum learning rate.

A common issue during the training phase of deep neural networks is the
gradient descent getting stuck at a local minima, instead of reaching the
global minimum. [20] suggests that by increasing the learning rate abruptly,
the gradient descent can be expected to jump out of the local minima and start
searching for the global minimum again. The technique was named stochastic
gradient descent and it proved quite effective in the experiments performed by
[20]. Figure 5 provides a diagrammatic representation of the issue of local
minima. Figure 6 describes how learning rates are restarted after every epoch
to avoid the problem.

Figure 5: Gradient Descent Stuck at Local Minima [18] Figure 6: Resetting
Learning Rate after each Epoch [18]

##  III Corpus

Using a custom web crawler, we created a large corpus of Bengali Newspaper
articles based on 6 topics. Accident, crime, education, entertainment,
environment and sports. The training set consists of 10564543 tokens while the
test set has 1197254. None of the documents in the test set are present in the
training set. The corpus is relatively large compared to the language
modelling experiments performed previously for Bengali Language.

##  IV Methodology

###  IV-A Proposed Architecture

The architecture employed in the neural language model is a variant of the
Recurrent Neural Network with LSTM gates[21], or more specifically the AWD-
LSTM [4], described in Section II. The model uses specialized regularization
techniques and optimizations that enables high performance for language
generation and context generalization. Due to the recurring nature of Bengali
language, using the AWD-LSTM RNN seemed like the most appropriate choice.

The language model mainly consists of 3 intermediate regular LSTM layers with
no attention, some short-cut connections and a few other additional mechanisms
with numerous drop-out hyper-parameters. The number of hidden activation per
layer is 1150. An embedding layer lies beneath, with the chosen embedding size
set to 400. A softmax layer is stacked on top of the LSTM layers to provide
probabilistic estimates of the next word. The linear decoder is used along
with the Adam optimizer and the flattened categorical cross-entropy as the
loss function. An illustration of the architecture is provided in figure 7.

Figure 7: Language Model Architecture

###  IV-B Training the language model

With the maximum vocabulary size set to 60,000, words that occurred in the
training corpus less than 2 times were discarded and replaced with the ’unk’
token. Other specialized tokens were added to identify pre-processing methods
such as padding(pad), beginning of strings(bos), end of strings(eos) etc. Due
to a lack of specialized tokenizers for Bengali Language, space separated
words were taken as tokens. The batch size was set to 32, while the back-
propagation-through-time window was set to 70. The weight decay for all the
layers was set to 0.1 and a drop-out multiplier of 0.5 was used for all the
LSTM weights to avoid early over-fitting.

With all layers frozen, using the cyclic learning rate (CLR) finder technique
[19], an appropriate learning rate of 1e-1 was selected and the model was
trained for 4 epochs. All the layers were unfrozen next, and as per the
differential learning rate technique mentioned in Section II, different
learning rates were picked for the layers based on their depth for efficient
training. A learning rate of 1e-4 was picked for the last layer and 1e-2 was
selected for the layer before that. The model was trained for a further 4
epochs, at which point, signs of over-fitting started to occur and the
terminal point was called. For every epoch, the technique of stochastic
gradient descent with restarts (SGDR) mentioned in Section II is applied.
Given a phrase of 3 initial words, the language model at this point was
capable of completing entire paragraphs in Bengali language as illustrated in
figure 8.

Figure 8: Example Predictions from the Language Model

##  V Experiments

To analyze the performance of the proposed framework, we attempt to recreate
some previously proposed models and see how they fair in terms of perplexity
on the held out data set. Perplexity is a measurement of how well a
probability model predicts a test data. In the context of Natural Language
Processing, perplexity is one way to capture the degree of ’uncertainty’ a
model has in predicting (assigning probabilities to) some text. Low perplexity
is good and high perplexity is bad since the perplexity is the exponentiation
of the entropy. The models used for performance analysis are as follows:

###  V-A Bi-gram language model

We draw our first comparison with the very famous and traditionally used bi-
gram language model, much similar to the work done in [22]. Variants of this
model has been seen to be used repeatedly for modelling Bengali Language.
Suppose $q_{t}=l(freq(w_{t-1},w_{t-2}))$ represents the frequency of
occurrence of the window $(w_{t-1},w_{t-2})$. The conditional probability,
thereby, take the form of a conditional mixture:

$P(w_{t}|w_{t-1})=\alpha_{0}(q_{t})p_{0}+\alpha_{1}(q_{t})p_{1}(w_{t})+\alpha_{2}(q_{t})p_{2}(w_{t}|w_{t-1})$

with conditional weights $\alpha_{i}(q_{t})\geq
0,\sum{}_{i}\alpha_{i}(q_{t})=1$. The base predictors here are as follows:
$p_{0}=1/|V|,p_{1}$ is a uni-gram and $p_{2}(i|j)$ is the bi-gram . We keep
rest of the experimental measures much similar to the models proposed by [3].

###  V-B LSTM and CNN language models

We also draw comparisons with a variation of a continuous space neural
language models to see how the proposed framework, with it’s own
modifications, compares against simpler models. We train an LSTM based
language model (Simple LSTM) following much of the conventions by [23]. The
model has two layers of LSTMs that are unrolled for 10 epochs. Hidden states
are initialized to 0. The batch size if kept 32. The number of activation per
layer is chosen to be 200. An initial learning rate of 1 is used.

We also try a character level CNN (Character CNN) language model that accepts
a sequence of encoded characters as input, much similar to the architecture
used for text classification by [24]. The alphabet used in our model consists
of all bengali letters, 10 bengali digits, 25 other characters including the
new line. The model is 3 layers deep with 2 convolutional and 1 fully
connected layer. The input features equal to 85 due to our character count and
the input feature length is set to 1000. The rest of the parameters are kept
consistent with the model used in [24].

##  VI Results and Discussion

The perplexities of the models achieved on the test set of the corpus are
summarized in table I.

TABLE I: Perplexity Comparison of the Language Models Model | Perplexity on Test Set
---|---
AWD-LSTM (Proposed) | 51.2
Simple LSTM | 227
Character CNN | 125
Bi-gram | 860.1

The diagrammatic representation provides us with a clear view that the
proposed architecture outperforms all the other models, some by an impressive
margin. The Simple LSTM architecture, which was used as a control, achieves a
perplexity of 227 while the character level CNN language models seems to
perform slightly better, achieving 125. The bi-gram model did not seem to work
well for the corpus, with a perplexity of 860.1, which highlights the
weaknesses of n-gram models mentioned in Section II. The AWD-LSTM LM achieves
a perplexity as low as 51.2. This improvement over the other models may be due
the employment of careful regularization and dropouts through out the
intermediate layers, which prevent over-fitting and shift the model towards
better generalization and less memorization. The training strategies used in
the AWD LSTM which are absent in the other models also seem to compliment the
architecture for a performance boost.

##  VII Conclusion

In this work, we discuss strategies for effective training of continuous-space
neural language models and introduce the weight-dropped LSTM to Bengali
Language. On the corpora consisting of Bengali news articles, the proposed
approach yields a perplexity of 51.2 which is significantly lower than the
perplexities achieved through traditional language models currently existing
in Bengali. We believe that, the core reason for these improvements over the
pre-existing models is that the proposed architecture employs DropConnect mask
on the hidden-to-hidden weight matrices, as a means to prevent over-fitting
across the recurrent connections, thus being able to generalize much better
than most continuous-space neural models. Since the applications of language
models have flourished over the years, we hope to see the implementation of
this model for tasks such as text summarization, classification and
translation of Bengali language in the future.

##  VIII Acknowledgement

This paper owes its gratitude to the Department of Computer Science and
Engineering, Shahjalal University of Science and Technology (SUST) and SUST
NLP Research Group for providing us with the right facilities and research
environment. All authors of this paper have major contributions in the
research and rightfully deserve equal credit.

## References

  * [1] H. Schwenk, D. Dchelotte, and J.-L. Gauvain, “Continuous space language models for statistical machine translation,” Proceedings of the COLING/ACL on Main Conference Poster Sessions, 2006.
  * [2] V. Siivola and B. L. Pellom, “Growing an n-gram language model,” INTERSPEECH, 2005.
  * [3] S. Ismail and M. S. Rahman, “Bangla word clustering based on n-gram language model,” 2014 International Conference on Electrical Engineering and Information Communication Technology, 2014.
  * [4] S. Merity, N. S. Keskar, and R. Socher, “Regularizing and optimizing LSTM language models,” CoRR, 2017.
  * [5] M. Haque, M. Habib, and M. Rahman, “Automated word prediction in bangla language using stochastic language models,” International Journal in Foundations of Computer Science & Technology, 2015.
  * [6] H. Ahmed Chowdhury, M. Imon, and M. Saiful Islam, “A comparative analysis of word embedding representations in authorship attribution of bengali literature,” 21st International Conference of Computer and Information Technology (ICCIT), 2018.
  * [7] R. Kneser and H. Ney, “Improved backing-off for m-gram language modeling,” 1995 International Conference on Acoustics, Speech, and Signal Processing, 1995.
  * [8] S. F. Chen and J. Goodman, “An empirical study of smoothing techniques for language modeling,” Computer Speech & Language, 1999.
  * [9] Y. Bengio, R. Ducharme, P. Vincent, and C. Janvin, “A neural probabilistic language model,” J. Mach. Learn. Res., 2003.
  * [10] F. Morin and Y. Bengio, “Hierarchical probabilistic neural network language model.,” Aistats, 2005.
  * [11] A. Mnih and G. E. Hinton, “A scalable hierarchical distributed language model,” Advances in neural information processing systems, 2009.
  * [12] T. Mikolov, M. Karafiát, L. Burget, J. Černockỳ, and S. Khudanpur, “Recurrent neural network based language model,” Eleventh annual conference of the international speech communication association, 2010.
  * [13] T. Mikolov, S. Kombrink, L. Burget, J. Černockỳ, and S. Khudanpur, “Extensions of recurrent neural network language model,” 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2011.
  * [14] S. Merity, N. S. Keskar, and R. Socher, “Regularizing and optimizing lstm language models,” CoRR, 2018.
  * [15] L. Wan, M. Zeiler, S. Zhang, Y. Le Cun, and R. Fergus, “Regularization of neural networks using dropconnect,” International conference on machine learning, 2013.
  * [16] Y. Gal and Z. Ghahramani, “A theoretically grounded application of dropout in recurrent neural networks,” Advances in neural information processing systems, 2016.
  * [17] J. Howard and S. Ruder, “Fine-tuned language models for text classification,” CoRR, 2018.
  * [18] S. Lynn-Evans, “Ten techniques learned from fast.ai,” 2019.
  * [19] L. N. Smith, “No more pesky learning rate guessing games,” CoRR, 2015.
  * [20] I. Loshchilov and F. Hutter, “SGDR: stochastic gradient descent with restarts,” CoRR, 2016.
  * [21] F. A. Gers, J. Schmidhuber, and F. A. Cummins, “Learning to forget: Continual prediction with lstm,” Neural Computation, 2000.
  * [22] F. Jelinek and R. L. Mercer, “Interpolated estimation of Markov source parameters from sparse data,” Proceedings, Workshop on Pattern Recognition in Practice, 1980.
  * [23] W. Zaremba, I. Sutskever, and O. Vinyals, “Recurrent neural network regularization,” CoRR, 2014.
  * [24] X. Zhang, J. Zhao, and Y. LeCun, “Character-level convolutional networks for text classification,” 2015.


* Zhao and Small [2018] Qingyuan Zhao and Dylan S. Small.  Graphical diagnosis of confounding bias in instrumental variable analysis.  _Epidemiology_ , 29(4):e29–e31, July 2018.  ISSN 1044-3983.  doi:10.1097/ede.0000000000000822.  URL https://doi.org/10.1097/ede.0000000000000822.
  * Mueller et al. [2005] Susanne G. Mueller, Michael W. Weiner, Leon J. Thal, Ronald C. Petersen, Clifford R. Jack, William Jagust, John Q. Trojanowski, Arthur W. Toga, and Laurel Beckett.  Ways toward an early diagnosis in alzheimer’s disease: The alzheimer’s disease neuroimaging initiative (ADNI).  _Alzheimers Dement_ , 1(1):55–66, July 2005.  ISSN 1552-5260, 1552-5279.  doi:10.1016/j.jalz.2005.06.003.  URL https://doi.org/10.1016/j.jalz.2005.06.003.
  * Gupta [2011] SandeepK Gupta.  Intention-to-treat concept: A review.  _Perspect Clin Res_ , 2(3):109, 2011.  ISSN 2229-3485.  doi:10.4103/2229-3485.83221.  URL https://doi.org/10.4103/2229-3485.83221.
  * Chernozhukov et al. [2016] Victor Chernozhukov, Chris Hansen, and Martin Spindler.  High-Dimensional Metrics in R.  _arXiv_ , August 2016.  doi:10.48550/arXiv.1603.01700.  URL http://arxiv.org/abs/1603.01700.


# Dual Monte Carlo Tree Search

Prashank Kadam  Ruiyang Xu  Karl Lieberherr

###### Abstract

AlphaZero, using a combination of Deep Neural Networks and Monte Carlo Tree
Search (MCTS), has successfully trained reinforcement learning agents in a
tabula-rasa way. The neural MCTS algorithm has been successful in finding
near-optimal strategies for games through self-play. However, the AlphaZero
algorithm has a significant drawback; it takes a long time to converge and
requires high computational power due to complex neural networks for solving
games like Chess, Go, Shogi, etc. Owing to this, it is very difficult to
pursue neural MCTS research without cutting-edge hardware, which is a
roadblock for many aspiring neural MCTS researchers. In this paper, we propose
a new neural MCTS algorithm, called Dual MCTS, which helps overcome these
drawbacks. Dual MCTS uses two different search trees, a single deep neural
network, and a new update technique for the search trees using a combination
of the PUCB, a sliding-window, and the $\epsilon$-greedy algorithm. This
technique is applicable to any MCTS based algorithm to reduce the number of
updates to the tree. We show that Dual MCTS performs better than one of the
most widely used neural MCTS algorithms, AlphaZero, for various symmetric and
asymmetric games.

Machine Learning, ICML

##  1 Introduction

$\text{MB}(q,n)=\begin{cases}\text{True},\quad\text{if }n=2\\\
\text{False},\quad\text{if }n<2\vee(q=0\wedge n>2)\\\ \exists
m\in[1...n-1]:\\\ \text{MB}(q-1,m)\wedge\text{MB}(q-1,n-m)\end{cases}$

Deepmind’s AlphaGo (Silver et al., 2016b) was the first algorithm to be able
to beat the human Go champion. AlphaGo uses a combination of Monte Carlo Tree
Search (MCTS) and a Deep Neural Network (DNN). However, the algorithm had some
game-specific configurations, which did not make it a generic algorithm that
could be used for playing any game. Deepmind later came up the AlphaZero
(Silver et al., 2017) which was a generic algorithm that could be used to play
any game. Since then, a combination of MCTS and a DNN is the most widely used
way to build game-playing programs. There is a need to balance accurate state
estimation by the DNN and the number of simulations by the MCTS. Larger DNNs
would be better for accurate evaluations but will take a toll on the cost of
computation.

On the other hand, a smaller network could be used for faster evaluations and
thus a larger number of MCTS simulations for the given amount of time. There
is a need to find the optimum trade-off between the network’s size and the
number of MCTS simulations. One of the recently developed methods for this
purpose is the Multiple Policy Monte Carlo Tree Search (MPV-MCTS) algorithm
(Lan et al., 2019) which combines two Policy-Value Neural Networks (PV-NNs) of
different sizes to retain the advantages of each network. The smaller network
would perform a larger number of simulations on its tree to assign priorities
to each state based on its evaluations. The more extensive network would then
evaluate these states starting from the highest priority to achieve better
accuracy. This algorithm shows a notable improvement in the convergence over
games compared to AlphaZero, but the two-network configuration requires high
run-time memory due to which the algorithm is difficult to run locally on
average hardware.

Another problem that all the neural MCTS algorithms face is the large number
of updates required during the backup phase of the tree. These updates
increase exponentially as the tree depth increases. The computational time
takes a big hit due to these updates, and there is a need to reduce the number
of updates to the tree while keeping the values of each tree node highly
accurate. We propose a technique that uses a combination of a sliding window
and $\epsilon$-greedy search over a Polynomial Upper Confidence Tree (PUCT)
(Rosin, 2011), for achieving this objective, thus reducing the time required
for updates considerably. This technique can be applied to any MCTS-based
algorithm as it optimizes over the core algorithm.

In this paper, we developed a novel algorithm that helps overcome the
drawbacks of AlphaZero, MPV-MCTS, and MCTS and helps in accelerating the
training speeds over various symmetric and asymmetric games. We show our
improvements over AlphaZero and MPV-MCTS using Elo-rating, $\alpha$-rank, and
training times, which are the most widely used metrics for evaluating games.
We train our model for symmetric and asymmetric problems with different
complexities and show that our model performance would improve considerably
compared to other neural-MCTS algorithms as the game’s state space increases.

##  2 Background

###  2.1 AlphaZero

In a nutshell,AlphaZero uses a single neural network as the policy and value
approximator. During each learning iteration, it carries out multiple rounds
of self-plays. Each self-play runs several MCTS simulations to estimate an
empirical policy at each state, then sample from that policy, take a move, and
continue. After each round of self-play, the game’s outcome is backed up to
all states in the game trajectory. Those game trajectories generated during
self-play are then be stored in a replay buffer, which is used to train the
neural network.

In self-play, for a given state, the neural MCTS runs a given number of
simulations on a game tree ,rooted at that state, to generate an empirical
policy. Each simulation, guided by the policy and value networks, passes
through 4 phases:

  1. 1.

SELECT: At the beginning of each iteration, the algorithm selects a path from
the root (current game state) to a leaf (either a terminal state or an
unvisited state) according to a predictor upper confidence boundary (PUCB)
algorithm (Rosin, 2011). Specifically, suppose the root is $s_{0}$. The UCB
determines a serial of states $\\{s_{0},s_{1},...,s_{l}\\}$ by the following
process:

$\begin{split}&a_{i}=\operatorname*{arg\,max}_{a}\left[Q(s_{i},a)+c\pi_{\theta}(s_{i},a)\frac{\sqrt{\sum_{a^{\prime}}N(s_{i},a^{\prime})}}{N(s_{i},a)+1}\right]\\\
&s_{i+1}=\text{move}(s_{i},a_{i})\end{split}$ (1)

It has been proved in (Grill et al., 2020) that selecting simulation actions
using Eq.1 is equivalent to optimize the empirical policy

$\begin{split}&\hat{\pi}(s,a)=\frac{1+N(s,a)}{|A|+\sum_{a^{\prime}}N(s,a^{\prime})}\end{split}$
(2)

where $|A|$ is the size of current action space, so that it approximate to the
solution of the following regularized policy optimization problem:

$\begin{split}\pi^{*}&=\operatorname*{arg\,max}_{\pi}\left[Q^{T}(s,\cdot)\pi(s,\cdot)-\lambda
KL[\pi_{\theta}(s,\cdot),\pi(s,\cdot)]\right]\\\
\lambda&=\frac{\sqrt{\sum_{a^{\prime}}N(s_{i},a^{\prime})}}{|A|+\sum_{a^{\prime}}N(s,a^{\prime})}\end{split}$
(3)

That also means that MCTS simulation is an regularized policy optimization
(Grill et al., 2020), and as long as the value network is accurate, the MCTS
simulation will optimize the output policy so that it maximize the action
value output while minimize the change to the policy network.

  2. 2.

EXPAND: Once the selected phase ends at an unvisited state $s_{l}$, the state
will be fully expanded and marked as visited. All its child nodes will be
considered as leaf nodes during next iteration of selection.

  3. 3.

ROLL-OUT: The roll-out is carried out for every child of the expanded leaf
node $s_{l}$. Starting from any child of $s_{l}$, the algorithm will use the
value network to estimate the result of the game, the value is then backed up
to each node in the next phase.

  4. 4.

BACKUP: This is the last phase of an iteration in which the algorithm updates
the statistics for each node in the selected states
$\\{s_{0},s_{1},...,s_{l}\\}$ from the first phase. To illustrate this
process, suppose the selected states and corresponding actions are

$\\{(s_{0},a_{0}),(s_{1},a_{1}),...(s_{l-1},a_{l-1}),(s_{l},\\_)\\}$

Let $V_{\theta}(s_{i})$ be the estimated value for child $s_{i}$. We want to
update the Q-value so that it equals to the averaged cumulative reward over
each accessing of the underlying state, i.e.,
$Q(s,a)=\frac{\sum_{i=1}^{N(s,a)}\sum_{t}r_{t}^{i}}{N(s,a)}$. To rewrite this
updating rule in an iterative form, for each $(s_{t},a_{t})$ pair, we have:

$\begin{split}N(s_{t},a_{t})&\leftarrow N(s_{t},a_{t})+1\\\
Q(s_{t},a_{t})&\leftarrow
Q(s_{t},a_{t})+\frac{V_{\theta}(s_{r})-Q(s_{t},a_{t})}{N(s_{t},a_{t})}\end{split}$
(4)

Such a process will be carried out for all of the roll-out outcomes from the
last phase.

Once the given number of iterations has been reached, the algorithm returns
the empirical policy $\hat{\pi}(s)$ for the current state $s$. After the MCTS
simulation, the action is then sampled from the $\hat{\pi}(s)$, and the game
moves to the next state. In this way, for each self-play iteration, MCTS
samples each player’s states and actions alternately until the game ends,
which generates a trajectory for the current self-play. After a given number
of self-plays, all trajectories will be stored into a replay buffer so that it
can be used to train and update the neural networks.

###  2.2 Multiple Policy Value Monte Carlo Tree Search

AlphaZero uses a single DNN, called a Policy-Value Neural Network (PV-NN),
consisting of two heads, one for the policy and one for value approximation.
In this subsection, we explain the Multiple Policy Value Monte Carlo Tree
Search algorithm (Lan et al., 2019) in which the overall system consists of
two PV-NNs $f_{S}$ and $f_{L}$ (smaller and the larger network, respectively).
Let $b_{S}(b_{L})$ be an assigned number of simulations or budget, the
corresponding network used would be $f_{S}(f_{L})$ this network would have its
search tree $T_{S}(T_{L})$. As a part of this problem, we would now like to
find a stronger policy:

$\pi(s,(f_{S}(b_{S}),(f_{L}(b_{L})))$

such that $b_{S}\geq b_{L}$. If the state is common to both the trees, $V(s)$
and prior probability $P(s,a)$ would be the same. For each simulation, we
choose either $f_{S}$ or $f_{L}$ and depending on the value chosen. We further
choose the leaf state of $T_{S}$ or$T_{L}$ to evaluate and update the tree.
Any number of ways could be defined for the networks to take turns as long as
$b_{S}\geq b_{L}$

This architecture’s objective is for $T_{S}$ to provide the benefits of the
look-ahead search where it balances between exploration and exploitation as it
grows. Thus $f_{S}$, being a smaller network, should perform a higher number
of simulations than $f_{L}$ with the same amount of resources. In each
simulation for $f_{S}$, a leaf is selected, using the simulation count of
$f_{S}$. In the case of $f_{L}$, for each simulation, we need to identify the
critical states. Here we assume that the nodes in $T_{S}$ with higher visit
counts are more important, and hence these states are assigned a higher value
while evaluating $T_{L}$. To achieve this, we select the states with the
highest visit counts from $T_{S}$ for each simulation. In case a particular
leaf is not visited by $f_{S}$ (rare), we re-select an unevaluated leaf state
using PUCB for $f_{L}$ instead. This process is repeated until convergence is
achieved. Here the overall network is expected to have faster convergence due
to the advantage of having a look ahead search using $T_{S}$.

##  3 Dual Monte Carlo Tree Search (Dual MCTS)

This section defines the neural MCTS algorithm that we have developed as a
part of this paper, which we call the Dual MCTS algorithm. The idea behind
this algorithm is similar to MPV-MCTS, where we have two different tree
simulations, i.e., a smaller tree and a larger tree, and we want to provide a
look-ahead to the larger tree by running a higher number of simulations on the
smaller tree and prioritizing the states evaluated by the smaller tree. In our
case, we have used a single neural network to simulate both the trees instead
of using two separate networks like MPV-MCTS. We also introduce a novel method
to reduce the number of value updates to the MCTS using a combination of the
PUCT, a sliding window over the tree levels, and the $\epsilon$-greedy
algorithm. This technique applies to any neural-MCTS based algorithm.

We have a single DNN that generates two different trees. This network would
consist of two policy-value heads connected to one of the network’s
intermediate layers, and the other one is connected to the last layer of the
network. What we are essentially doing here is subsetting a single network
into two different sub-networks where one acts as a smaller network and the
other acts as a larger network. We can consider the network from the input
layer to the first policy-value head as the smaller network of $f_{sub}$ and
the network from the input layer to the second policy-value head, i.e., the
complete network as the larger network or $f_{full}$. Each of the networks
$f_{sub}$ and $f_{full}$ generate their own trees, $T_{sub}$ and $T_{full}$.
Since $f_{sub}$ is a smaller network, we can allocate a large simulation
budget $b_{sub}$ to this network. Thus, $f_{sub}$ will generate large self-
plays in a short period. Although this network’s value estimations will not be
very accurate, we only want to prioritize the most visited states. This
priority list can then be used by $f_{full}$ to give a higher preference to
states with higher priorities while simulating the search tree. The two
networks can then be represented by $f_{sub}(f_{full})$ and the corresponding
search trees can be represented by $T_{sub}(T_{full})$. The policy over which
we would like to optimize can therefore be given by:

$\pi(s,(f_{sub}(b_{sub}),(f_{full}(b_{full})))$

such that $b_{sub}\geq b_{full}$. Where $b_{sub}$ and $b_{full}$ are budgets
assigned to $f_{sub}$ and $f_{full}$ respectively. In case that we find a
state which is common between both the tress, the policy, and the value for
that state would be the same. Several methods can be used to combine multiple
strategies during MCTS value evaluations. Some of these include Rapid Action
Value Evaluation (RAVE) (Gelly & Silver, 2011), implicit minimax backups
(Lanctot et al., 2014) and asynchronous policy value MCTS (APV-MCTS) (Silver
et al., 2016a). The first two combine MCTS evaluations with other heuristics.
Meta MPV-MCTS is most related to Asynchronous Policy Value-MCTS (Silver et
al., 2016a). Hence, we will use the following method, which is similar to
Asynchronous Policy Value-MCTS:

$V(s)=\alpha V_{sub}(s)+(1-\alpha)V_{full}(s)$

$P(s,a)=\beta p_{sub}(a|s)+(1-\beta)p_{full}(a|s)$

where $\alpha,\beta\in[0,1]$, are weight coefficients. Any of the two networks
can go for the first simulation based on the approach of the implementation,
suppose $f_{sub}$ is selected to go first, then we select a leaf from
$T_{sub}$ to be evaluated and accordingly the values are updated for each of
the states. The value of $b_{sub}$ and $b_{full}$ can be chosen conveniently.
For this paper, we choose the value of $b_{L}$ as a random number between 1
and n and then choose $b_{sub}$ to be $\gamma b_{full}$, where
$\gamma\in[1,1.5]$ and throughout multiple runs, we figure out which
combination of $b_{sub}$ and $b_{full}$ fits the best for our combinatorial
game.

We now introduce a novel way of updating the MCTS algorithm. Here, we use a
combination of PUCT, a sliding window ($\tau$), and an $\epsilon$-greedy
algorithm for action selection. During the MCTS search tree’s backup phase, we
update the values evaluated using the PUCT algorithm only up to the window
$\tau$ previous nodes for the trajectory being followed in the current
iteration. This method considerably reduces the number of updates required to
be made to the MCTS, but this also impacts our PUCT algorithm’s exploration
term as $N(s,a)$ would not be updated for states outside our sliding window.
For this purpose, we combine our sliding window approach with an
$\epsilon$-greedy algorithm, which would help us facilitate exploration. The
mathematical formalism of our action selection approach can be given as
follows:

The PUCB action selection is defined as:

$A_{k}=\operatorname*{arg\,max}_{a}\left[Q(s_{i},a)+cP_{\phi}(a|s_{i})\frac{\sqrt{\sum_{a^{\prime}}N(s_{i},a^{\prime})}}{N(s_{i},a)+1}\right]$

Here we add a sliding window to our PUCB algorithm such that the algorithm
updates only the node upto window size ($\tau$) from the current node. The
sliding window PUCB action selection will then occur in the following way:

$\begin{cases}\forall 0\leq k\leq\tau-1,\quad A_{k}=a_{k}\\\ \forall\tau\leq
k\leq K-1,\quad A_{k}=\operatorname*{arg\,max}_{a}[Q(s_{i},a,\tau)+\\\ \hskip
99.58464ptcP_{\phi}(a|s_{i})\frac{\sqrt{\sum_{a^{\prime}}N(s_{i},a^{\prime},\tau)}}{N(s_{i},a,\tau)+1}]\end{cases}$

where $a_{k}$ is the action evaluated for that node once the state is out of
the window. Here we introduce the $\epsilon$-greedy algorithm in order to
balance the exploitation and exploration outside the window $\tau$. As for
within the window, the PUCB will take care of this. The $\epsilon$-greedy
sliding window PUCB thus becomes:

$\begin{cases}\forall 0\leq k\leq\tau-1\quad\&\quad
U_{k}\geq\epsilon_{0}\nu^{k},\quad A_{k}=a_{k}\\\ \forall 0\leq
k\leq\tau-1\quad\&\quad U_{k}<\epsilon_{0}\nu^{k},\quad A_{k}=Y_{k}\\\ \forall
N\leq k\leq K-1\quad,\quad
A_{k}=\operatorname*{arg\,max}_{a}[Q(s_{i},a,\tau)+\\\ \hskip
99.58464ptcP_{\phi}(a|s_{i})\frac{\sqrt{\sum_{a^{\prime}}N(s_{i},a^{\prime},\tau)}}{N(s_{i},a,\tau)+1}]\end{cases}$

Notice that we have introduced the term $\nu^{k}$, this is the decay term that
is tuned for exploration depending on the state space of the game. The update
for our $\epsilon$-greedy sliding-window PUCB then becomes:

$\begin{cases}\forall 0\leq k\leq\tau-1,\quad
Q^{new}(s_{i},a_{i})=Q^{old}(s_{i},a_{i}),\\\ \hskip
68.2866ptN^{new}(s_{i},a_{i})=N^{old}(s_{i},a_{i})\\\ \forall\tau\leq k\leq
K-1,\\\ \hskip 34.1433ptQ^{new}(s_{i},a_{i})=\frac{Q^{old}(s_{i},a_{i})\times
N^{old}(s_{i},a_{i})+V_{\phi}(s_{r})}{N^{old}(s_{i},a_{i})+1},\\\ \hskip
34.1433ptN^{new}(s_{i},a_{i})=N^{old}(s_{i},a_{i})+1\end{cases}$

Figure 1: Dual MCTS block diagram

During each simulation for $T_{sub}$, the leaf state is selected based on our
action selection algorithm, and for $T_{full}$ each state is selected based on
the priorities assigned by $T_{sub}$ to each state, higher the state value,
higher the priority. In case a particular state has not been visited by
$T_{sub}$, the evaluation in $T_{full}$ is done using our action selection
technique. The choice of $\tau$ for the sliding window is based on the state
space of the game being evaluated. For smaller games like Nim, the value of
$\tau$ would be small, but as the board size would increase, $\tau$ would also
increase proportionally to the state space logarithmically.

Algorithm 1 Dual MCTS

$s\leftarrow Initialboardstate$

$f_{full}\leftarrow Initializethefullnetwork$

$b_{full}\in[1,n],\quad b_{sub}\leftarrow\gamma b_{full},\gamma\in[1,1.5]$

for $i=1$ to $b_{sub}+b_{full}$ do

if $i\in[1,b_{sub}]$ then

$s_{leaf}=SelectUnevaluatedLeafState(T_{sub})$;

$(p,v)=f_{sub}(s_{leaf});$

$Update(T_{sub},s_{leaf},(p,v));$

else

$s_{leaf}=SelectUnevaluatedLeafStateby$

$Priority(T_{full})$;

if $N_{sub}(s_{leaf})=0$ then

$s_{leaf}=SelectUnevaluatedLeafState(T_{full})$;

end if

$(p,v)=f_{full}(s_{leaf});$

$Update(T_{full},s_{leaf},(p,v));$

end if

end for

Algorithm 2 Dual MCTS

##  4 Experiments

This section describes our experiments to evaluate the Dual MCTS algorithm
that we have defined above. The algorithm has been implemented in Python in
Deepmind’s OpenSpiel framework (Lanctot et al., 2019). All the experiments
have been performed on a core i7-7500U processor with 8 Gigabytes of RAM. For
these experiments, we will use two problems: The first one is the single pile
Nim problem, which is a symmetric problem where both the players will have the
same action space. The second one is the Highest Safe Rung (HSR) (Xu &
Lieberherr, 2019, 2020) which is an asymmetric problem which means that both
the players have different action spaces. We claim that our algorithm performs
better as the state space of the game increase. We also show our evaluations
over the Connect-four game, which has a considerably larger state space than
HSR or Nim. Since the Connect-four game took a long time to run on our current
configuration, we upgraded the system to 16 Gigabytes of RAM. Note that this
configuration is specific to the Connect-4 evaluations only.

The hyper-parameters used for the neural network are kept constant through all
the different algorithms that we evaluate. In the case of the number of MCTS
simulations, the number of simulations for smaller and the larger tree is kept
the same in MPV-MCTS and Dual MCTS. The number of simulations applied to the
AlphaZero search tree is the sum of the simulations of Dual MCTS’s two search
trees. For the DNN, we use ResNet with four layers and 64 neurons each. For
Dual MCTS, $f_{sub}$ consists of the first two layers, and its output is
connected to a policy-value head, and the complete network acts as the
$f_{full}$. For MPV-MCTS, we have two separate networks, each having 2 and 4
layers for the smaller and the more extensive network, respectively. The
number of simulations assigned to the smaller tree is 50, and that to the
larger tree is 35.

##  5 Evaluations

We are going to evaluate each of the algorithms including AlphaZero, MPV-MCTS
and Dual MCTS for HSR, Nim and Connect-4 using the following four metrics:

  * •

Elo Rating (Elo, 1978)

  * •

$\alpha$-rank (Omidshafiei et al., 2019)

  * •

Time per Iteration

  * •

Time required for convergence

For the purpose of comparisons, we assume the convergence when the
$\alpha$-rank score of the algorithm crosses 0.9. Note that this does not mean
that the algorithm has for the optimal strategy to play the game but we use
this metric to compare these algorithms which each other and it gives us a
fair estimate of how these algorithms are performing.

###  5.1 HSR Evaluations

The Highest Safe Rung (HSR) (Kleinberg & Tardos, 2005) (Xu & Lieberherr, 2019,
2020) is an asymmetric problem in which both the agents’ action spaces are
different. HSR(k,q,n) basically defines a stress testing problem, where one,
given $k$ jars and $q$ test chances, throwing jars from a specific rung of a
given ladder with height $n$ to locate the highest safe rung. If $n$ is
appropriately large, then one can locate the highest safe rung with at most
$k$ jars and $q$ test times; otherwise, if $n$ is too big, then there is no
way to locate the highest safe rung. This problem can be described as
following:

$HSR(k,q,n)=\begin{cases}\mbox{True},\ \mbox{if }n=1\\\ \mbox{False},\
\mbox{if }n>1\wedge(k=0\vee q=0)\\\ \exists m\in[1..n]:HSR(k-1,q-1,m)\\\
\wedge HSR(k,q-1,n-m)\end{cases}$

It is well known that the above formulae can be translated into a logic game
using Hintikka rules. (Hodges & Väänänen, 2019).

Figure 2: HSR Evaluations

Here we use HSR(4,4,16), which means that the board size is (1x16) with four
tests available and four questions that could be asked. Figure 2 shows how
each of the algorithms performs for the HSR problem. As we see from Figure 2,
MPV-MCTS converges a step faster than AlphaZero and Dual MCTS for both Elo-
rating as well as the $\alpha$-rank. However, the time required per training
step for AlphaZero and Dual MCTS is much lesser than MPV-MCTS, due to which
the total time taken for convergence of MPV-MCTS is much more than AlphaZero
or Dual MCTS, we see that Dual MCTS outperforms AlphaZero by 11.58%. Dual MCTS
outperforms MPV-MCTS by 29.42%.

###  5.2 Nim Evaluations

Nim (Frankl & Tokushige, 2003) is a symmetric problem, where each player is
allowed to choose $x$ stones from a pile of $n$ stones turn by turn where
$x\leq n$. The player to pick the last stone wins. Figure 3 the results of our
evaluations on the Nim(3,20) game

Figure 3: Nim Evaluations

Here we see quite similar results to the HSR problem, where although the MPV-
MCTS converges a step faster than AlphaZero or Dual MCTS, it takes a much
longer time per each training iteration due to its dual network configuration.
Dual MCTS, in this case, surpasses AlphaZero by 8.84% and MPV-MCTS by 27.78%
faster training.

###  5.3 Connect 4 Evaluations

To show that our algorithm outperforms the more conventional algorithms like
AlphaZero and MPV-MCTS by even larger margins, we evaluate the game of
Connect-4 (Hill & Kemp, 2018). Connect-4 has a much larger state space than
HSR(4,4,16) or Nim (3,20). Figure 4 shows the results of our evaluations for
all the models that we are testing.

Figure 4: Connect-4 Evaluations

As we can see from Figure 4, Dual MCTS performs much better than AlphaZero or
MPV-MCTS. As we have seen from our previous evaluations, there is a similar
pattern where MPV-MCTS takes a lower number of timesteps to converge than
AlphaZero or Dual MCTS, but it is taking a much longer time per iteration. As
a result, Dual MCTS outperforms AlphaZero by 32.30% in training time and MPV-
MCTS by 33.92% in training time. This result provides a piece of conclusive
evidence that our algorithm will work much better for problems with larger
state spaces.

Note that throughout all the experiments which we have performed, Dual MCTS
constantly outperforms AlphaZero and MPV-MCTS in terms of the convergence
time. All these experiments are run on very modest hardware and we show here
that Dual MCTS could be a very useful algorithm for use-cases where high-end
hardware is unavailable. Another thing to notice here is how both MPV-MCTS and
Dual MCTS perform across various state spaces. MPV-MCTS converges much faster
for Connect-4 than for HSR/Nim as compared to the other algorithms but takes
more time per training step as it has to update two different neural networks.
In the very same, Dual MCTS also shows faster convergence for Connect-4 game,
this shows us the advantage of multiple tree searches. Along with this a
single network configuration and an efficient update strategy help Dual MCTS
converge much faster than its competitors.

Table 1: Table showing the details of the average time required per training
step, no. of steps required for convergence and the total time for convergence
for each of the algorithms Evaluations
---
Algorithm | HSR | Nim | Connect-4
Time (Step) |  Steps (Conv.) |  Time (Conv.) |  Time (Step) |  Steps (Conv.) |  Time (Conv.) |  Time (Step) |  Steps (Conv.) |  Time (Conv.)
AlphaZero |  9.34 |  8 |  74.72 |  10.71 |  7 |  74.97 |  18.71 |  13 |  243.23
MPV-MCTS |  12.38 |  7 |  86.66 |  14.67 |  6 |  88.02 |  24.62 |  10 |  246.20
Dual MCTS |  8.37 |  8 |  66.96 |  9.84 |  7 |  68.88 |  15.32 |  12 |  183.84

##  6 Conclusions

In this paper we have proposed a new neural MCTS algorithm, Dual MCTS which
uses a combination of two MCTSs along with an novel update technique for the
Monte Carlo Search Tree to reduce the number of updates to the tree. This
whole contraption accelerates the agent training and we train our agents for
different symmetric and asymmetric problems using Dual MCTS and show that Dual
MCTS performs better than more conventionally used algorithms like AlphaZero
(Silver et al., 2017) and MPV-MCTS (Lan et al., 2019). We also show how Dual
MCTS shows even better improvements in convergence times as the state space of
the problems that we solve, increases. We show our evaluations using different
metrics.

Dual MCTS can also be scaled up for larger problems by creating smaller
intermediate trees ($>2$), which could provide a look-ahead to the following
tree in a chained fashion and help achieve even faster convergence in huge
state spaces. Establishing a constraint which can accurately form such
hierarchies and form a balance between the state space of the problem and the
number of trees required for the fastest solution is a part of our future
work.

## References

  * Elo (1978) Elo, A. E.  The rating of chessplayers, past and present.  1978\.
  * Frankl & Tokushige (2003) Frankl, P. and Tokushige, N.  The game of n-times nim.  _Discrete Math._ , 260(1–3):205–209, January 2003.  ISSN 0012-365X.  doi: 10.1016/S0012-365X(02)00667-2.
  * Gelly & Silver (2011) Gelly and Silver, D.  Monte carlo tree search and rapid action value estimation in computer go.  _Artificial Intelligence_ , 175, 2011.
  * Grill et al. (2020) Grill, J.-B., Altché, F., Tang, Y., Hubert, T., Valko, M., Antonoglou, I., and Munos, R.  Monte-carlo tree search as regularized policy optimization.  _ArXiv_ , abs/2007.12509, 2020.
  * Hill & Kemp (2018) Hill, G. and Kemp, S. M.  Connect 4: A novel paradigm to elicit positive and negative insight and search problem solving.  9(1755), 2018.
  * Hodges & Väänänen (2019) Hodges, W. and Väänänen, J.  Logic and Games.  In Zalta, E. N. (ed.), _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, fall 2019 edition, 2019.
  * Kleinberg & Tardos (2005) Kleinberg, J. and Tardos, E.  _Algorithm Design_.  Addison-Wesley Longman Publishing Co., Inc., USA, 2005.  ISBN 0321295358.
  * Lan et al. (2019) Lan, L.-C., Li, W., Wei, T.-H., and Wu, I.  Multiple policy value monte carlo tree search.  In _IJCAI_ , 2019.
  * Lanctot et al. (2014) Lanctot, M., Winands, M. H., Pepels, T., and Sturtevant, N. R.  Monte carlo tree search with heuristic evaluations using implicit minimax backups.  _IEEE Conference on Computational Intelligence and Games_ , pp. 1–8, 2014.
  * Lanctot et al. (2019) Lanctot, M., Lockhart, E., Lespiau, J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J., Srinivasan, S., Timbers, F., Tuyls, K., Omidshafiei, S., Hennes, D., Morrill, D., Muller, P., Ewalds, T., Faulkner, R., Kramár, J., Vylder, B. D., Saeta, B., Bradbury, J., Ding, D., Borgeaud, S., Lai, M., Schrittwieser, J., Anthony, T., Hughes, E., Danihelka, I., and Ryan-Davis, J.  Openspiel: A framework for reinforcement learning in games.  2019\.
  * Omidshafiei et al. (2019) Omidshafiei, S., Papadimitriou, C., Piliouras, G., Tuyls, K., Rowland, M., Lespiau, J.-B., Czarnecki, W. M., Lanctot, M., Perolat, J., and Munos, R.  $\alpha$-rank: Multi-agent evaluation by evolution.  _Nature_ , 1038, Jul 2019.
  * Rosin (2011) Rosin, C. D.  Multi-armed bandits with episode context.  volume 61, pp. 203–230, 2011.
  * Silver et al. (2016a) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Driessche, G. V. D., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., and Lanctot, M.  Mastering the game of go with deep neural networks and tree search.  _Nature_ , 529, Jul 2016a.
  * Silver et al. (2016b) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, D.  Mastering the game of go with deep neural networks and tree search.  _Nature_ , 529:484,503, 2016b.
  * Silver et al. (2017) Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap, T., Hui, F., Sifre, L., van den Driessche, G., Graepel, T., and Hassabis, D.  Mastering the game of go without human knowledge.  _Nature_ , 550:354, Oct 2017.
  * Xu & Lieberherr (2019) Xu, R. and Lieberherr, K.  Learning self-game-play agents for combinatorial optimization problems.  _AAMAS, Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems_ , pp. 2276–2278, 2019.
  * Xu & Lieberherr (2020) Xu, R. and Lieberherr, K.  Learning self-play agents for combinatorial optimization problems.  _The Knowledge Engineering Review_ , 35:e11, 2020.  doi: 10.1017/S026988892000020X.