######  Lemma 8.2.

(Cluster set of 1) Let $f$ be a transcendental entire function, and let $U$ be
an invariant parabolic basin, such that $\infty$ is accessible from $U$. Let
$\varphi\colon\mathbb{D}\to U$ be a Riemann map, and let $\varphi^{*}(1)=p$ be
the parabolic fixed point. Assume $U$ is PS. Then, $1$ is not a singularity
for the associated inner function.

In addition, if $U$ is SPS,

$Cl_{\mathbb{C}}(\varphi,1)\smallsetminus\left\\{p\right\\}\subset\mathcal{I}(f).$

###### Proof.

In the sequel, we let $F_{1}$ be the branch of $f^{-1}$ defined in $D(p,r)$,
$r>0$, such that $F_{1}(p)=p$. We shall prove the existence of a domain
$\Omega_{p}$ analogous to the one of Technical Lemma 1.

Indeed, the construction of the domain $\Omega_{p}$ follows the procedure of
Technical Lemma 1, applied not to $P(f)\cap U$, but to the following set of
singular values

$SV(f,p)=\left\\{v\in\mathbb{C}\colon v\textrm{ is a singularity for
}F_{1}\right\\}.$

We note that $SV(f,p)\subset P(f)$, and $SV(f,p)\cap D(p,r)=\emptyset$.
Therefore, $SV(f,p)\cap U$ does not accumulate at any point of
$Cl_{\mathbb{C}}(\varphi,1)$, and the arguments of Technical Lemma 1 apply.

Note that $\Omega_{p}$ is a simply connected domain with
$Cl_{\mathbb{C}}(\varphi,1)\subset\Omega_{p}$, and $\Omega_{p}\cap U$
connected and disjoint from $SV(f,p)\cap U$. Hence, $F_{1}$ is well-defined in
$\Omega_{p}\cap U$, and we apply the same arguments as in Theorem C to the
function $F_{1}|_{\Omega_{p}\cap U}$ to prove that 1 is not a singularity for
the associated inner function.

In the SPS case, $\Omega_{p}$ is disjoint from $SV(f,p)$, and hence $F_{1}$ is
well-defined in $\Omega_{p}$. To prove that every point in the cluster set is
escaping (except for the parabolic point), we follow the proof of Theorem D
(b), considering $\Omega_{p}$ as defined above. $\square$

## References

  * [Bak70] I. N. Baker “Completely invariant domains of entire functions” In _Mathematical Essays Dedicated to A. J. Macintyre_ Ohio Univ. Press, Athens, Ohio, 1970, pp. 33–35
  * [Bak84] I. N. Baker “Wandering domains in the iteration of entire functions” In _Proc. London Math. Soc. (3)_ 49.3, 1984, pp. 563–576
  * [BD99] I. N. Baker and P. Domínguez “Boundaries of unbounded Fatou components of entire functions” In _Ann. Acad. Sci. Fenn. Math._ 24.2, 1999, pp. 437–464
  * [BD00] I. N. Baker and P. Domínguez “Some connectedness properties of Julia sets” In _Complex Variables Theory Appl._ 41.4, 2000, pp. 371–389
  * [BW91] I. N. Baker and J. Weinreich “Boundaries which arise in the dynamics of entire functions” In _Rev. Roumaine Math. Pures Appl._ 36.7-8, 1991, pp. 413–420
  * [BF01] K. Barański and N. Fagella “Univalent Baker domains” In _Nonlinearity_ 14.3, 2001, pp. 411–429
  * [BFJK17] K. Barański, N. Fagella, X. Jarque and B. Karpińska “Accesses to infinity from Fatou components” In _Trans. Amer. Math. Soc._ 369.3, 2017, pp. 1835–1867
  * [BFJK19] K. Barański, N. Fagella, X. Jarque and B. Karpińska “Escaping points in the boundaries of Baker domains” In _J. Anal. Math._ 137.2, 2019, pp. 679–706
  * [BK07] K. Barański and B. Karpińska “Coding trees and boundaries of attracting basins for some entire maps” In _Nonlinearity_ 20.2, 2007, pp. 391–415
  * [Bar08] D. Bargmann “Iteration of inner functions and boundaries of components of the Fatou set” In _Transcendental dynamics and complex analysis_ 348, London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, 2008, pp. 1–36
  * [Bea91] A. F. Beardon “Iteration of rational functions” 132, Graduate Texts in Mathematics Springer-Verlag, New York, 1991
  * [BM07] A. F. Beardon and D. Minda “The hyperbolic metric and geometric function theory” In _Quasiconformal mappings and their applications_ Narosa, New Delhi, 2007, pp. 9–56
  * [Ber93] W. Bergweiler “Iteration of meromorphic functions” In _Bull. Amer. Math. Soc. (N.S.)_ 29.2, 1993, pp. 151–188
  * [BFR15] W. Bergweiler, N. Fagella and L. Rempe-Gillen “Hyperbolic entire functions with bounded Fatou components” In _Comment. Math. Helv._ 90.4, 2015, pp. 799–829
  * [BZ12] W. Bergweiler and J. Zheng “Some examples of Baker domains” In _Nonlinearity_ 25.4, 2012, pp. 1033–1044
  * [CG93] L. Carleson and T. W. Gamelin “Complex dynamics”, Universitext: Tracts in Mathematics Springer-Verlag, New York, 1993
  * [CP02] J. J. Carmona and C. Pommerenke “On prime ends and plane continua” In _J. London Math. Soc. (2)_ 66.3, 2002, pp. 641–650
  * [DG87] R. L. Devaney and L. R. Goldberg “Uniformization of attracting basins for exponential maps” In _Duke Math. J._ 55.2, 1987, pp. 253–266
  * [DM91] C. Doering and R. Mañé “The Dynamics of Inner Functions” In _Ensaios Matemáticos (SBM)_ 3, 1991, pp. 1–79
  * [Evd16] V. Evdoridou “Fatou’s web” In _Proc. Amer. Math. Soc._ 144.12, 2016, pp. 5227–5240
  * [EFJS19] V. Evdoridou, N. Fagella, X. Jarque and D.J. Sixsmith “Singularities of inner functions associated with hyperbolic maps” In _J. Math. Anal. Appl._ 477.1, 2019, pp. 536–550
  * [ERS20] V. Evdoridou, L. Rempe and D. J. Sixsmith “Fatou’s associates” In _Arnold Math. J._ 6.3-4, 2020, pp. 459–493
  * [FH06] N. Fagella and C. Henriksen “Deformation of entire functions with Baker domains” In _Discrete Contin. Dyn. Syst._ 15.2, 2006, pp. 379–394
  * [FJ23] Núria Fagella and Anna Jové “A model for boundary dynamics of Baker domains” In _Math. Z._ 303.4, 2023, pp. Paper No. 95, 36
  * [Gar81] J. B. Garnett “Bounded analytic functions” 96, Pure and Applied Mathematics Academic Press, Inc., New York-London, 1981
  * [Ima14] M. Imada “Periodic points on the boundaries of rotation domains of some rational functions” In _Osaka J. Math._ 51.1, 2014, pp. 215–224
  * [IU23] O. Ivrii and M. Urbański “Inner Functions, Composition Operators, Symbolic Dynamics and Thermodynamic Formalism”, 2023 arXiv:2308.16063 [math.DS]
  * [Kön99] H. König “Conformal conjugacies in Baker domains” In _J. London Math. Soc. (2)_ 59.1, 1999, pp. 153–170
  * [Mih12] H. Mihaljević-Brandt “Semiconjugacies, pinched Cantor bouquets and hyperbolic orbifolds” In _Trans. Amer. Math. Soc._ 364.8, 2012, pp. 4053–4083
  * [Mil06] J. Milnor “Dynamics in One Complex Variable. Third Edition.” Princeton University Press, 2006
  * [Per97] R. Pérez-Marco “Fixed points and circle maps” In _Acta Math._ 179.2, 1997, pp. 243–294
  * [Pom92] C. Pommerenke “Boundary behaviour of conformal maps” Springer-Verlag, Berlin, 1992
  * [PZ94] F. Przytycki and A. Zdunik “Density of periodic sources in the boundary of a basin of attraction for iteration of holomorphic maps: geometric coding trees technique” In _Fund. Math._ 145.1, 1994, pp. 65–77
  * [RS17] L. Rempe-Gillen and D. Sixsmith “Hyperbolic entire functions and the Eremenko-Lyubich class: class $\mathcal{B}$ or not class $\mathcal{B}$?” In _Math. Z._ 286.3-4, 2017, pp. 783–800
  * [RS19] L. Rempe-Gillen and D. Sixsmith “On connected preimages of simply-connected domains under entire functions” In _Geom. Funct. Anal._ 29.5, 2019, pp. 1579–1615
  * [RS18] P. J. Rippon and G. M. Stallard “Boundaries of univalent Baker domains” In _J. Anal. Math._ 134.2, 2018, pp. 801–810
  * [Sch97] W. Schmidt “Accessible fixed points on the boundary of stable domains” In _Results Math._ 32.1-2, 1997, pp. 115–120


# An Extensible and Modular Design and Implementation of Monte Carlo Tree
Search for the JVM

Larkin Liu<EMAIL_ADDRESS>
University of Toronto

Jun Tao Luo<EMAIL_ADDRESS>
Carnegie Mellon University

###### Abstract

Flexible implementations of Monte Carlo Tree Search (MCTS), combined with
domain specific knowledge and hybridization with other search algorithms, can
be very powerful for finding the solutions to problems in complex planning. We
introduce mctreesearch4j, a MCTS implementation written as a standard JVM
library following key design principles of object oriented programming. We
define key class abstractions allowing the MCTS library to flexibly adapt to
any well defined Markov Decision Process or turn-based adversarial game.
Furthermore, our library is designed to be modular and extensible, utilizing
class inheritance and generic typing to standardize custom algorithm
definitions. We demonstrate that the design of the MCTS implementation
provides ease of adaptation for unique heuristics and customization across
varying Markov Decision Process (MDP) domains. In addition, the implementation
is reasonably performant and accurate for standard MDP’s. Furthermore, the
nuances of different types of MCTS algorithms are discussed.

Keywords: Monte Carlo Tree Search, Software Design, Markov Decision Process

##  1 Introduction

Sampling based strategies for the optimal planning of Markov Decision
Processes (MDP) and adversarial games have been of great importance to the
improvement to discovery of approximate solutions for complex high
dimensionality domains where a full solution using complete methods are often
infeasible. Algorithms such as Monte Carlo Tree Search (MCTS) (Kocsis and
Szepesvári, 2006) have displayed a promising ability to generate competitive
solutions for domains exhibiting high dimensionality search spaces.

In recent memory, MCTS used in combination with other game solving strategies
have shown to be the world’s state-of-the-art for high branching factor games
such as Go (Silver et al., 2016). Other algorithms also frequently apply MCTS
to solve for games with high branching factors such as Kriegspiel (Ciancarini
and Favini, 2010) and Othello (Norvig, 1992). Our objective in this software
is to create a extensible implementation of MCTS which is adaptable into
multiple domains, applicable to either single player of multi player games.

###  1.1 Discrete Markov Decision Process

The Markov Decision Process (MDP), described in (Puterman, 1994), is a well-
developed framework for planning under uncertainty. The application of MDP’s
can be found in various optimization strategies to prescribe an optimal set of
actions given a stochastic environment where perfect observations are
available. An $MDP\langle S,A,\mathbb{P},R\rangle$ designates a set of states
$S$, where the agent traverses from $S_{t}$ to $S_{t+1}$, for a horizon of $T$
in $T$ distinct time increments $t$ (starting from $t=1$). $A$ is the action
space, which is the set of actions the agent can take at any $t$ and may or
may not be a function of $t$ itself. $\mathbb{P}$ is the probability space
that outlines the transition probability space for state-to-state transitions
for any action taken at time $t$, $\mathbb{P}:\\{S_{t}\times A\times
S_{t+1}\\}\to\\{R\in\mathbb{R}\\}$ subsequently returning a reward value,
which belongs to $\mathbb{R}$.

In a fundamental MDP, the state at any time $S_{t}$ is visible to the agent,
and a corresponding reward is associated with each state. Therefore, if the
state is observable, the value of each observable state is the reward
associated with the state, and the availability of actions leading to rewards
in the future. Evidently, they can form a recursive pattern to determine the
value of the state, which can be solved via dynamic programming. Suppose we
use $Q(S_{t},a)$ to denote the immediate value when accounting for the
immediate reward as well as the transitioned next state $S_{t+1}$. Where the
Value of any state is is denoted by $V(s)$.

$Q(S_{t},a)=R(S_{t},a)+\gamma\sum_{S_{t+1}\in S}P(S_{t+1}|S_{t},a)V(S_{t+1})$
(1)

$V(S)=\operatorname*{argmax}_{a\in A}Q(S,a)$ (2)

Traditionally the exact solution to Eq. (2) can be found using dynamic
programming algorithms such as Value Iteration or Policy Iteration (Bellman,
1957). Nevertheless, if the state space or branching factor is so large that
traditional solutions such as dynamic programming cannot produce a solution
within reasonable time or resource constraints, approximate methods via MCTS
is a viable alternative for producing approximate optimal policies. The
optimal policy denoted $\pi(S,a)$, is therefore the action, $a$ that maximizes
Eq. (2) at any particular state.

###  1.2 Monte Carlo Tree Search Algorithm

Monte Carlo Tree Search (MCTS) serves as an approach to solve the optimal
policy for any well-defined MDP that does not always involve an exhaustive
search through the entire search space. It has the potential to provide
feasible solutions to high dimension and high branching MDP’s, where dynamic
programming techniques are not feasible provided constraints on computing
resources. (Chang et al., 2010) demonstrates the specific use of the bandit
algorithm, especially its ability to converge to the optimal policy of an MDP.
Much research, such as (Coquelin and Munos, 2007) and (Kocsis and Szepesvári,
2006), demonstrates the effective usage of MCTS to obtain $\pi(S,a)$. The
primary advantage of MCTS over dynamic programming solutions of the MDP is
that, when implemented correctly, the number of iterations through the state
space is drastically reduced. Nevertheless, the use of DP or MCTS is not
mutually exclusive, as the combination of both algorithms can yield specific
advantages and/or disadvantages (Feldman and Domshlak, 2014). The key notion
of MCTS is the ability to guide the MC search down the tree efficiently, which
borrows itself from the bandit strategy UCB1 (Auer et al., 2002).

$UCT=E(S^{\prime})+C\sqrt{\frac{2\ln{n}}{n^{\prime}}}$ (3)

MCTS primarily makes use of a deterministic selection of actions and resulting
outcomes to estimate the reward function of the system. MCTS is a tree search
adaptation of the UCB1 Multi-Armed Bandit Strategy (Auer et al., 2002). When
performing one tree traversal in MCTS, a series of actions is randomly played.
This tree search is not entirely random as it is guided by the UCB1
illustrated in Eq. (3). The MCTS algorithm is distinctly divided into
4-phases, Selection, Expansion, Simulation, and Backpropagation, which are
clearly illustrated in Fig. 1. In Selection, a policy deterministically
selects which action to play, based on previously expanded states. This
selection is typically guided by the UCT measure, from Eq. (3). In the
Expansion phase, states that are unexplored, represented by a leaf node, are
added to the search tree one at time. Subsequently, in the Simulation phase, a
simulation is stochastically played out. Finally Backpropagation propagates
the final reward of either a terminal state, or a node at an arbitrary depth
limit, back to the root node. This 4-phase process is repeated until a maximum
number of iterations or a convergence criteria is established.

Figure 1: Outline of MCTS - from (Browne et al., 2012).

##  2 Software Framework

mctreesearch4j is designed follow three key design principles. Firstly, we
design for adaptability. Adaptability is defined as the ability for MDP domain
to be easily integrated into the mctreesearch4j framework with ease via class
abstractions. Our implementation seeks to simplify the adoption of MCTS
solutions for a variety of domains. Secondly, we design a software that is
fully compatible with the Java Virtual Machine (JVM), for the reasons to be
discussed in Section 2.1. And lastly, we design to achieve a high degree of
extensibility within the framework. Extensibility is the defined as the
ability for key mechanisms to be reused, redefined, and enhanced, without
sacrificing interoperability.

###  2.1 JVM Library

Open source implementations of MCTS exist, but have not gained widespread
adoption. (Cowling et al., 2012) presents an implementation in Python, where
multiple game engines can be plugged into the MCTS solver. (Lucas, 2018)
presents a simple implementation written in Java, written with some
categorization of the key MCTS mechanisms outlined in Fig. 1. However, both
implementations do not provide easy access to heuristics, nor do they
implement extensible and modular state action space abstractions.
Chatzilygeroudis (2016) presents a low-level implementation of MCTS in C++.
Yet because of its low-level implementation, it is not easy to interface a
custom MDP definitions with the MCTS solver, hindering its adaptability across
domains. Some MCTS implementations are available in Python, a widely adopted
scripting language popular in Machine Learning, but suffer performance issues
from utilizing an interpreter, causing computing overhead at runtime. Some
workarounds do exist, such as dispatching to more performant libraries written
in compiled code, but this is additional complexity we desire to avoid.
Therefore, compiled languages such as Java or C are preferred for MCTS
implementation primarily because of its more efficient resource consumption at
runtime compared to native Python. Thus in the current landscape, there is a
lack of open source MCTS implementations that provides the full list of
features offered by mctreesearch4j outlined in Section 2.

As of today, JVM language are widely adopted among many open source
frameworks***https://www.tiobe.com/tiobe-index/. JVM languages are used in a
variety of workloads including web, desktop and Android applications etc. The
long history of the Java language also contributes to the JVM extensive
knowledge base, language support and backwards compatibility. Furthermore, JVM
is known for its wide adoption particularly in the creation of mobile games,
many of which require online and/or offline planning solvable via MCTS.
Therefore, we chose to develop an MCTS Framework for the JVM ecosystem.

The Kotlin programming language was chosen for the development of
mctreesearch4j. Kotlin features a more modern syntax that is succinct and
expressive, containing powerful primitives, while simultaneously supporting a
wide range of programming paradigms. This language is also popular among many
software developers, particularly for the Android mobile operating system, a
platform where mctreesearch4j may find suitable adoption. The full
compatibility of Kotlin with other JVM languages also allows the adoption by
other languages within the JVM ecosystem. In addition Kotlin, along with many
JVM languages, has strong support for type generics enabling us to build and
reuse functions independent of types. It also offers better development
experience with compile time type checks without explicit casts.

###  2.2 MDP Domain Abstraction

Attempts to rigorously define MDP interfaces to plug into custom MDP solvers
have been attempted in the past. For example, RDDL (Sanner, 2010) provides an
interface for a formal MDP definition, but it is rather complex for
straightforward software implementations, and also adds additional overhead by
introducing a new programming language specifically for the definition of
MDP’s. We simplify the formal MDP definition by abstracting the MDP into its
base characteristics outlined in Listing 3.

The main abstraction that is used to define an MDP problem is the abstract
class defined in Listing 3, using generic type variables. Each of the methods
correspond to specific behaviour of a discrete MDP. In mctreesearch4j we use
generic types `StateType} and \mintinline`kotlinActionType to represent the
MDP states and actions respectively. This abstract class has five members that
must be implemented. These abstract class methods define the functionality of
an MDP. The MDP abstraction will be used by core MCTS solvers to compute the
optimal policy. The MDP interface can be written in any JVM language, we use
Kotlin and Scala for this paper, with the Scala implementation from (Liu,
2021). mctreesearch4j is designed to easily adapt to a variety of MDP
definitions without complex mathematical constructs. The computational
behaviour of mctreesearch4j is defined separately by user code outside of the
core library, for example via a game controller, see Fig. 2. This allows
programmers to define complex flexible systems, integrating seamlessly into
turn-based game applications, including single and multi agent turn-based
games such as 2048 and Reversi (Othello), respectively. In the user code layer
of the framework, the programmer can define custom solvers, where unique
heuristics can be implemented to add domain specific knowledge to improve the
performance of the base MCTS solver. Thus the adaptability of the solver to a
wide variety of MDP domains is one key design principle of mctreesearch4j, see
Section 3 for an overview of adapted domains.

Figure 2: Inheritance and class structure of mctreesearch4j.

mctreesearch4j is able to use the MDP definitions to execute a tree search
over the state action space. The MDP definitions used to interface with
mctreesearch4j should optimize its save and load functionalities, as it can
impact MCTS search performance if poorly constructed. Nevertheless, defining
the MDP space programmatically gives the strong advantage of having the
ability to define complex MDP’s without the need for rigorous mathematical
definitions. In our implementation, we aim to define a clear common
declarative interface to provide abstractions for the solver and the MDP
representation. The MDP abstraction ensures that the user defines the MDP
scenario consistently such that it can be queried by the default solver
provided in the library.

⬇

\parabstract class MDP<StateType, ActionType> {

abstract fun transition(StateType, ActionType) : StateType

abstract fun reward(StateType, ActionType?, StateType) : Double

abstract fun initialState() : StateType

abstract fun isTerminal(StateType) : Boolean

abstract fun actions(StateType) : Collection<ActionType>

}

Figure 3: Definition of the MDP abstract class.

###  2.3 MCTS Solver Design

mctreesearch4j also implements the core Monte Carlo Tree Search algorithm in
an extensible paradigm, maximizing the flexibility of the implementation by
following Object Oriented Programming (OOP) principles. This is useful because
it is possible to run MCTS with customized key mechanisms, and it is highly
efficient if the programmer is able to reuse, and/or redefine complete or
partial segments of the key mechanisms. In Listing 2.3 we define such key
mechanisms, all of which are inherited, and can be redefined or enhanced. This
is important both for the efficiency of development, as well as the
interoperability of the key MCTS mechanisms. Listing 2.3 defines four abstract
methods which are used to implement MCTS as illustrated in Fig. 1. The 4
phases, Selection, Expansion, Simulation, and Backpropagation defined in lines
LABEL:code:select to LABEL:code:backpropagate serve as the key mechanisms to
run mctreesearch4j and the class method `fun runTreeSearch()} is a predefined
method from the base \mintinline`kotlinclass Solver() responsible for
executing the key MCTS solver mechanisms defined in Lines LABEL:code:select to
LABEL:code:backpropagate. These open functions, which can be overridden in
subclasses, provide the flexibility to define the implementation of the solver
that is appropriate for the MDP domain. Furthermore, we introduce the

    NodeType} which is an abstract representation of the search space. It denotes how the state action space is represented in stages of the MCTS search, and must be explicitly defined by a subclass.
    \begin

listing

⬇

\parabstract class Solver<ActionType, NodeType>(

protected val verbose: Boolean,

protected val C: Double // Exploration Constant

) where NodeType : Node<ActionType, NodeType> {

protected abstract var root: NodeType

abstract fun select(node: NodeType) : NodeType !$\label{code:select}$!

abstract fun expand(node: NodeType) : NodeType

abstract fun simulate(node: NodeType) : Double

abstract fun backpropagate(node: NodeType, reward: Double)
!$\label{code:backpropagate}$!

open fun runTreeSearch(iterations: Int) {/* Predefined method */}

}

\par

Key Mechanisms of an MDP Solver  mctreesearch4j provides a default
implementation known as `class GenericSolver}, and an alternate
\mintinline`kotlinclass StatefulSolver. The abstract `class Solver} serves as
the base class for both versions, and defines a set of functionalities that
all solver implementations must provide as well as a set of extensible
utilities. Similar to the MDP abstraction, the solver uses a set of type
parameters to provide strongly typed methods that unify and simplify the MCTS
implementation. The programmer is free to select the data type or data
structure that best defines how states and actions are represented in their
MDP domain. Thus we can infer that, Generic and Stateful solvers have
different representations of the \mintinline`kotlinNodeType. The
differentiation lies in their respective memory utilization of abstract node
types to track states during MCTS iterations. The default `class
GenericSolver} provides a leaner implementation, where actions are tracked and
no explicit states are stored permanently. The states tracked with
\mintinline`kotlinclass GenericSolver are dynamic and the MDP transitions must
be rerun when traversing the search tree during selection in order to infer
the state. The `class StatefulSolver} keeps an explicit record of the visited
states, and additional information, such as terminality and availability of
downstream actions. The extra overhead of storing the state explicitly in the
MCTS node, allows the algorithm to optimize its search using information from
previously visited states. This is particularly useful for deterministic
games, where a re-computation of the MDP transition is not necessary to
determine the state of the agent after a particular taking a specific action.
This differentiation results in different implementations of the
\textit`Selection step, while maintaining identical implementations of
Expansion, Simulate and Backpropagation. Both implementation iterates the
algorithm in the most common pattern of Selection, Expansion, Simulation,
Backpropagation until a certain number of

    iterations}.
    \subsubsection

Generic Solver Design The Generic solver provides an MCTS solution where the
states are not explicitly stored in the search tree, but instead inferred from
the actions taken by the agent. Generic solvers are more memory efficient, and
are preferred for scenarios of high state State-Action-State (SAS) branching
factor. We define SAS branching factor as the average number of possible
states that the agent can arrive at, given any action from any state. For
stochastic domains, any action can lead to a multitude of states, so storing
states explicitly in the search tree can be infeasible. In this case the
Generic solver is preferred as it obviates the need to track states
explicitly. A downside of the Generic solver is that additional computation is
required to infer the state of the agent during the Selection phase of MCTS,
as accomplished via the method on Line LABEL:code:generic-simulateActions of
Listing 4. The Generic solver can also be extended to Partially Observable
MDP’s (POMDP’s), where we abstract away the state space altogether, and solve
over the estimation of state space as inferred by the action reward history,
this is also known as the Belief MDP approach. In the Belief MDP, a POMDP is
simplified into an MDP, by ignoring the potential discrepancy between the
observation and true state, treating the current observation as the true
state. This can create a tractable MDP solution at the cost of strict
accuracy, and is in principle, fully programmable into mctreesearch4j via the
Generic solver.

⬇

\parfun select(node: ActionNode): ActionNode {

if (node.getChildren().isEmpty()) {return node}

var currentNode = node

simulateActions(node) !$\label{code:generic-simulateActions}$!

while (true) {

if (mdp.isTerminal(currentNode.state)) {return currentNode}

val currentChildren = currentNode.getChildren()

if (currentNode.isNotFullyExplored()) {return currentNode}

currentNode = currentChildren.maxByOrNull{a -> calculateUCT(a)}

simulateActions(currentNode)

}

}

\par

Figure 4: Generic Solver Selection.

The most significant difference is the trade-off between memory and runtime.
The Generic solver does not track the possible states for each node of the
search tree and therefore reduces the memory consumption. The key benefit is
the ability to track the state space with actions alone. A disadvantage, is
that the agent must replay the game engine to approximate the state at any
time, which is where a computational bottleneck can arise.

####  2.3.1 Stateful Solver Design

We provide an alternate solver design targeted for MDP domains with low SAS
branching factors. In `StatefulSolver} the nodes of the solver explicitly
track the state, the metadata contained within the state. An
\mintinline`kotlinNodeType is used for Stateful search trees where the node
explicitly contains both the state of the agent, and the inducing action that
led to said state. The Stateful solver is computationally efficient when the
SAS branching factor is feasible, as it is able to store and look up the
current state of the agent and continue MCTS iterations from the recorded
state. Stateful solvers are generally preferred for low state space MDP’s,
where the SAS branching factor, defined earlier in Section 2.3, is relatively
manageable, such as in games where low SAS branching factors are exhibited.
However, this optimization will incur additional memory usage. Listing 5
illustrates the Selection and Expansion algorithm for Stateful MCTS. The
Stateful solver keeps track of all possible states at each node illustrated in
Lines LABEL:code:stateful-sa1 to LABEL:code:stateful-sa2. In the Selection
phase, the Stateful solver iterates until a leaf node is reached.

⬇

\parfun select(node: StateNode): StateNode {

if (mdp.isTerminal(node.state)) {return node} !$\label{code:stateful-sa1}$!

if (node.validActions.size > node.exploredActions.size) {return node}

var bestAction = exploredActions.getActionUCT(node, node.getChildren())

val newState = mdp.transition(node.state, bestAction)

val actionState = node.getChildren(bestAction)

.firstOrNull { s -> s.state == newState }

?: return createNode(node, bestAction, newState)

return select(actionState)

} !$\label{code:stateful-sa2}$!

\par\par

Figure 5: Stateful Selection.

####  2.3.2 Expansion, Simulation and Backpropagation

The Expansion, Simulation, and Backpropagation steps for Generic and Stateful
solvers remain virtually identical, notwithstanding specification of a
different `NodeType} for each solver, also resulting minor nuances in
instantiating said nodes in the \text`Expansion phase. The base `NodeType},
which is used by both the Generic and Stateful Solvers, store key metadata
such as the inducing action, expected reward, and number of visits. The
\mintinline`kotlinfun expand() method randomly selects an unexplored node, and
adds it to the search tree. This is done using the

    fun createNode()} method, which differs between Generic and Stateful solvers.
    In the Generic solver, no actual MDP state is required to create a new node of type \mintinline

kotlinActionNode. The current state of the agent is computed based on the
sequence of actions taken utilizing the specified `mdp} object, defined in
Listing \ref`code-listing:mdp-abstraction. The Stateful solver, on the other
hand, explicitly requires the tracking of states when creating a `StateNode}
via the \mintinline`kotlinfun createNode() method. The `fun simulate()} method
runs a purely randomized exploration of the MDP state-action space from a
specific state, until a terminal state or the simulation depth is reached. The
\mintinline`kotlinfun backpropagate() method is used to update the reward
values for the node where the simulation was run as well as all of its
ancestors.

⬇

\parfun expand(node: StateNode): StateNode {

if (node.isTerminal) {return node}

val unexploredActions = node.getUnexploredActions()

val actionTaken = unexploredActions.random()

return createNode(node, actionTaken)

}

\parfun simulate(node: NodeType): Double {

if (mdp.isTerminal(node.state)) {

return mdp.reward(node.parent?.state, node.inducingAction, node.state)

}

var depth = 0

var currentState = node.state

var discount = rewardDiscountFactor

while(true) {

val validActions = mdp.actions(currentState)

val randomAction = validActions.random()

val newState = mdp.transition(currentState, randomAction)

if (mdp.isTerminal(newState)) {

return mdp.reward(currentState, randomAction, newState) * discount

}

currentState = newState

depth++

discount *= rewardDiscountFactor

if (depth > simulationDepthLimit) {

return mdp.reward(currentState, randomAction, newState) * discount

}

}

}

\parfun backpropagate(node: NodeType, reward: Double) {

var currentNode = node

var currentReward = reward

while (true) {

currentStateNode.maxReward = max(currentReward, currentNode.maxReward)

currentStateNode.reward += currentReward

currentStateNode.n++

currentStateNode = currentStateNode.parent ?: break

currentReward *= rewardDiscountFactor

}

}

Figure 6: Expansion, Simulation and Backpropagation pseudo-code.

####  2.3.3 Extensibility and Heuristics

Though the default MCTS implementation described in Section 1.2 works well in
many scenarios, there are situations where knowledge about specific problem
domains can be applied to improve the MCTS performance. Improvements to MCTS,
such as heuristics driven simulation, exploit domain knowledge to improve
solver performance performance. We demonstrate that a Reversi AI that uses
heuristics derived from (Guenther and Klinik, 2004) is able to outperform the
basic MCTS implementation. These heuristics are programmed via extensibility
points in the mctreesearch4j solver implementation, where the key mechanisms
can be altered or augmented. Our heuristic, illustrated in Fig. 2.3.3,
introduces the `heuristicWeight} array, a 2D array storing domain specific
ratings of every position on a Reversi board representing the desirability of
that position on the board. The negative numbers represent a likely loss and
positive numbers representing a likely win, again as represented in Fig.
\ref`fig:reversi-heu. This value is taken into consideration when traversing
down the simulation tree. The `heuristicWeight} array adjusts the propensity
to explore any position for both agents based on the heurisitc’s belief about
the desirability of the position. The effectiveness of this heuristic is later
presented in Section \ref`sec:adversarial-bench. To alter the MCTS simulation
phase we override the `fun simulate()} method and create a new definition for
it. The application of this \mintinline`kotlinheuristicWeight only requires
minor alterations to the `fun simulate()} method, as illustrated from Lines
\ref`code:heu-start until LABEL:code:heu-end in Listing 8.

Figure 7: Reversi `l`ookup table.

The default solver behaviour continues running the MCTS iteration until the
iteration count is reached. This may not be the best criteria and convergence
metrics can be used to better determine when to stop the tree construction.
For example, if no significant improvements in the best action’s score is
made, the algorithm can be terminated early. Additional functionality can also
be added to the solver in the tree construction function. For example, if
additional metrics need to be measured after each MCTS iteration,
mctreesearch4j can be overridden to add this functionality. For example, the
exploration term, $C$, from Eq. 3 can be exported via a class extension that
tracks the exploration term.

⬇

\paroverride fun simulate(node: NodeType): Double {

/*… Original Simulation code …*/

while(true) {

val validActions = mdp.actions(currentState)

var bestActionScore = Int.MIN_VALUE // Begin heuristic $\label{code:heu-
start}$

var bestActions = mutableListOf<Point>()

for (action in validActions) {

val score = heuristicWeight[action.x][action.y]

if (score > bestActionScore) {

bestActionScore = score

bestActions = mutableListOf(action)

}

if (score == bestActionScore) {bestActions.add(action)}

}

val randomAction = bestActions.random() // End heuristic $\label{code:heu-
end}$

val newState = mdp.transition(currentState, randomAction)

/*… Original Simulation code …*/

}

}

Figure 8: Heuristic implementation in Reversi.

##  3 Evaluation & Function

We evaluate our MCTS implementation on its ability to converge to an accurate
solution. In our experiments, the MDP has one or many optimal solutions, and
the solver should accurately converge to these solutions. We also measure the
performance of the implementation by the average time to extract one optimal
action taken from any state, we denote this simply as runtime per decision or
$\Delta_{d}$. $\Delta_{d}$ is an estimate of the time to make a decision
averaged over 100 trials. This can vary from computer to computer, but serves
as a rough estimate. We demonstrate that mctreesearch4j is adaptable across
multiple domains, in addition to the fact that $\Delta_{d}$ can be kept at
manageable levels for operation on a common laptop computer. The exact
hardware specifications are outlined in Appendix A.1, For adversarial search
domains featuring two agents, the terminal state of victory or loss results in
a score of +1 or -1 respectively, from the perspective of the agent when
competing against the opponent. Later in Section 3.3 we demonstrate a
adversarial setup where 2 MCTS solvers with novel characteristics, play
against each other. We examine the performance of the MCTS solver across five
distinct MDP domains. These domains are GridWorld, a probabilistic single
agent MDP illustrated in Fig. 9, the game of 2048 analyzed in Kohler et al.
(2019), Push Your Luck (PYL), a single agent MDP defined in Geißer and Speck
(2018), the game of Connect 4, a deterministic multi-agent game, and the game
of Reversi, a deterministic adversarial multi-agent game.

###  3.1 Solver Runtime per Domain

Domain | No. Agents | Stochastic | Avg. Br. Fac. | Avg. Depth | Solver | $\Delta_{d}$
---|---|---|---|---|---|---
GridWorld | 1 | yes | 4 | 5 | Gen. | 0.1
PYL | 1 | yes | 2 | $\infty$ | Gen. | 0.3
2048 | 1 | yes | 4 | 940 | Gen. | 0.5
Connect4 | 2 | no | 4 | 36 | SF | 0.06
Reversi | 2 | no | 10 | 58 | SF | 0.12
Table 1: MDP domain characteristics, where $\Delta_{d}$ is in seconds.

Furthermore, we select either Generic or Stateful solvers based on the
characteristics of the MDP domain, with the considerations outlined in
Sections 2.3.1 and 2.3. The max tree depth of the MCTS was set to 1000, this
number typically far exceeds the average depth before reaching a terminal
state for most MDP domains, with the exception of 2048. The number of
iterations set to 500 arbitrarily. The MDP domains, where mctreesearch4j was
applied, contain one or two agents, and state action transitions can be
stochastic or deterministic. We also note the average branching factor of the
domain (Avg. Br. Fac.), and average depth (Avg. Depth)†††`i`llustrates Avg.
Br. Fac. and Avg. Depth. of the search tree until a terminal state is reached.
For some games, such as GridWorld, average depth is heavily determined by the
state configuration, we refer to the configuration set out in Fig 9. We record
the average runtime to compute the immediate next optimal action from an
arbitrary state in the state space of the MDP domain in milliseconds‡‡‡The
exact specification of the computer used to run the simulation is contained in
Appendix A.1..

###  3.2 Solver Convergence

To demonstrate the accuracy of mctreesearch4j, we examine the performance of
the solver with respect to convergence of rewards, convergence of exploration
terms, and visiting of the optimal state subspace more than non-optimal state
subspace with increasing iterations. Variables such as the exploration
constant $C$, as denoted in Eq. (3), affect the overall exploration of
mctreesearch4j. If $C$ is too high, there can be over-exploration causing the
UCT function to swing between optimal actions and non-optimal action
selection. Over-exploration affects the smoothness of the exploration term
convergence (James et al., 2017). If $C$ is too low, then it is not able to
sufficiently explore all states to find an optimal action. We provide a simple
example of convergence evaluation in the domain of Gridworld. The grid
displayed in Fig. 9, represents the state space, and each cell demarcates the
state which corresponds to a reward value (unfilled cell indicates a reward of
0). In our example any non-zero state represents a terminal state. The agent
represented by $\Diamond$, has 4 possible actions from its starting point. In
the specific configuration shown by Fig. 9, the MCTS solver should ultimately
select the actions ← or ↓, which are optimal, and mctreesearch4j should
accurately converge to the appropriate values.

+5$\Diamond$-1-1 Figure 9: Illustration of the Gridworld MDP domain. An agent,
is represented by $\Diamond$, lies in a domain with terminal state reward +5,
and terminal reward negative state -1. Figure 10: Convergence of exploration
terms

Our MCTS solver§§§The figures 10 to 12 represent solutions of the Stateful
solver, nevertheless convergence plots using Generic solver yields similar
behaviour., with no additional heuristics, is capable of converging to the
correct solution space. Fig. 10 displays a convergence of the exploration term
$C\sqrt{2\log{n}/n^{\prime}}$, which decreases as $n\rightarrow\infty$, and
$n^{\prime}\leq n$. Provided this, the correct optimal policy will yield
smaller exploration terms for optimal versus non-optimal solutions because the
number of visits to the non-optimal nodes, $n^{\prime}$, will be generally
smaller than the optimal nodes.

Figure 11: Convergence of rewards

Naturally, the reward value associated with each optimal state induced by the
optimal policy action at $t+1$ should yield higher backpropagated rewards. In
Fig. 11 we see that the two optimal actions produce higher reward values than
non-optimal solutions.

Figure 12: Convergence of visits

When the MCTS solver is accurately selecting the optimal solutions, it will
continue to cause the agent to explore in the optimal subset of the state
space, and reduce its exploration in the non-optimal subset of the state space
as evidenced in Fig. 12. The cumulative number of visits corresponding to the
optimal policy is proportionally increasing with respect to the number of MCTS
iterations. Whereas for non-optimal solutions, the cumulative visits are
significantly less because the solver will avoid visiting the non-optimal
state subspace.

###  3.3 Adversarial Game Benchmarking

We demonstrate the possibility of heuristic adaptation to improve
mctreesearch4j in an adversarial game. For this, we create a two-player game
in the deterministic multiplayer domain of Reversi, where our AI will play as
adversaries against each other. The Reversi heuristic is implemented to enable
the search algorithm to compute more realistic estimates of reward, using
specific domain knowledge (Guenther and Klinik, 2004). The intended effect of
this heuristic is to enable a more efficient search of the state action space,
as presented earlier in Section 2.3.3 The heuristic augmented mctreesearch4j
is played against the original mctreesearch4j to prove that the adversarial
MDP solver is capable of improving via domain knowledge. Table 2 demonstrates
that when mctreesearch4j is augmented with heuristics it defeats the original
mctreesearch4j solver up to 75% of the time, under ceteris paribus conditions.
Nevertheless this win rate metric depends on several factors. Firstly, we see
that the heuristic solver is only marginally better than the original solver
when we limit the maximum simulation depth (Max. Sim. Depth), and the number
of simulation iterations (No. Iter). The limitation on these two hyper-
parameters limit the MCTS solver’s ability to explore the entire state action
space to determine accurate rewards, thereby also limiting the effectiveness
of the heuristic. The degree of contrast between mctreesearch4j with heuristic
and without is greatly enhanced when the solver is provided enough simulation
iterations and simulation depth to fully take advantage of the additional
domain information.

No. Iter | Max. Sim. Depth | No. Wins | No. Loss | No. Ties | Win Rate
---|---|---|---|---|---
50 | 40 | 98 | 87 | 15 | 0.49
500 | 40 | 121 | 75 | 4 | 0.605
50 | 1000 | 111 | 75 | 14 | 0.555
500 | 1000 | 151 | 46 | 3 | 0.755
Table 2: Reversi results comparing MCTS solver with heuristics and without.

Via this experiment, we justify that our MCTS solver is capable of being
modified to adapt new heuristics which improve the outcomes of the MDP policy
for an adversarial game. The heuristic presented here actively biases the
random simulation of MCTS to favour actions which induce better outcomes,
based on domain knowledge. We also see that as we adjust hyper-parameters of
the model, such as simulation depth and number of iterations, the heuristic
augmented solver can become more effective.

##  4 Conclusion & Future Work

Due to the extensibility and modularity of mctreesearch4j, many improvements
and experiments could be performed by extending and modifying the capabilities
of the base software. mctreesearch4j is designed to enable researchers to
experiment with various MCTS strategies while standardizing the functionality
of the MCTS solver and ensuring reliability, where the experiments are
reproducible and the solver is compatible with common JVM runtimes ¶¶¶To be
specific mctreesearch4j is fully compatible with Java Runtime Environment
(JRE) 8 and 11..

###  4.1 Future Work

We encourage the effort to enhance mctreesearch4j further. For example, while
the default implementations create a new node and adds it to the node chosen
by the Selection phase, it is possible to rely on domain knowledge to avoid
superfluous game states. For example, in Gridworld, where each unique position
is functionally the same regardless of how it arrived to that position, there
is no need to add a newly created node to the search tree. Instead, a cache of
nodes representing known positions can be used to dramatically reduce the MCTS
search space, yielding more accurate results. Furthermore, creating an mapping
for more expressive and rigorous MDP defining meta-languages such as RDDL
(Sanner, 2010) to bind to mctreesearch4j, could be an important feature in the
near future. This enables complex and rigorous definitions of MDP’s to be
benchmarked using mctreesearch4j, opening many new opportunities for research.
Also, as described in Baier and Winands (2013), some games can be solved more
efficiently if Minimax algorithms can be applied in the Selection phase.
Instead of the default solver which uses UCT to select leaf nodes, a Minimax
algorithm can be used instead to detect shallow wins and losses. This has been
shown to work well for adversarial games to avoid traps set by the opposite
player. For adversarial games, another common strategy is to improve
simulation accuracy by incorporating a Minimax algorithm for the Simulation
phase. This ensures the rewards computed are more realistic than two players
who play randomly. This can significantly improve the MCTS performance. In
addition, the backpropagation step can be augmented with Minimax concepts to
mark known losing positions. This allows subsequent Selection phase to ignore
parts of the search tree and speed up convergence (Baier and Winands, 2013).
Finally, instead of running simulated games to compute a reward, it is
possible to rely on an external source to predict the reward value of a given
state. An example of this is the state-of-the-art Go AI, AlphaGo Silver et al.
(2016), which uses Deep Learning trained on expert positions and via self-play
to compute the expected reward for a given game position. Combining Deep
Learning techniques with mctreesearch4j to provide external intelligence is an
open avenue of research. The phase order of MCTS defined in the base `class
Solver()} can also be modified to explore different avenues. Although the most
common MCTS phase order of $\textit`Selection →Expansion →Simulation
→Backpropagation$workswellinmostscenarios,theMCTSphaseordercanbealteredto$Selection
→Simulation →Expansion
→Backpropagation$asdescribedin\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{Winands:2010}{\@@citephrase{(}}{\@@citephrase{)}}}.Theadvantagesand/ordisadvantagesofalteringtheMCTSphaseorderisanunderexploredtopic.\par$

###  4.2 Summary

In closing, mctreesearch4j presents a framework which enables programmers to
adapt an MCTS solver to a variety of MDP domains. This is important because
software application was a main focus of mctreesearch4j. Furthermore,
mctreesearch4j is fully compatible with JVM, and this design decision was made
due to the excellent support of class structure and generic variable typing in
Kotlin, and other JVM languages, as well as support for mobile applications.
Yet most importantly, mctreesearch4j is modular and extensible, the key
mechanism of MCTS are broken down, and the programmer is able inherit class
characteristics, redefine and/or re-implement certain sections of the
algorithm while maintaining a high degree of MCTS standardization.

###  4.3 Software Availability

• `https://mvnrepository.com/artifact/ca.aqtech/mctreesearch4j} contains the
compiled core library for \textit`mctreesearch4j available via the Maven
Central Repository for the JVM ecosystem. `http://mctreesearch4j.aqtech.ca/}
contains the source code for implementation of \textit`mctreesearch4j core
library, as well as programs for various domains and game controllers.

## Acknowledgements

We would like to acknowledge the kind support of our reviewers, and Maven
Central Repository for repository hosting of our code base.

## A

###  A.1 Simulation Hardware Specifications

All of the benchmarks run in Section 3 were performed on an Apple Macbook Pro,
containing a 2.6GHz dual-core Intel Core i5 processor with 3MB shared L3 cache
with 8GB of 1600MHz DDR3L onboard memory. We expect that a computer with
similar hardware capabilities will yield similar results.

## References

  * Auer et al. (2002) Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Mach. Learn._ , 47(2-3):235–256, May 2002.  ISSN 0885-6125.  doi: 10.1023/A:1013689704352.  URL https://doi.org/10.1023/A:1013689704352.

* Baier and Winands (2013) Hendrik Baier and Mark H. M. Winands.  Monte-carlo tree search and minimax hybrids.  In _2013 IEEE Conference on Computational Inteligence in Games (CIG)_ , pages 1–8, 2013.  doi: 10.1109/CIG.2013.6633630.
* Bellman (1957) Richard Bellman.  A markovian decision process.  _Journal of Mathematics and Mechanics_ , 6(5):679–684, 1957.  URL http://www.jstor.org/stable/24900506.

* Browne et al. (2012) Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter I. Cowling, Stephen Tavener, Diego Perez, Spyridon Samothrakis, Simon Colton, and et al.  A survey of monte carlo tree search methods.  _IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI_ , 2012.
* Chang et al. (2010) Hyeong Soo Chang, Jiaqiao Hu, Michael C. Fu, and Steven I. Marcus.  Adaptive adversarial multi-armed bandit approach to two-person zero-sum markov games.  _IEEE Trans. Autom. Control._ , 55(2):463–468, 2010.  doi: 10.1109/TAC.2009.2036333.  URL https://doi.org/10.1109/TAC.2009.2036333.
* Chatzilygeroudis (2016) Konstantinos Chatzilygeroudis.  Monte carlo tree search - c++.  https://github.com/resibots/mcts, 2016.
* Ciancarini and Favini (2010) Paolo Ciancarini and Gian Piero Favini.  Monte carlo tree search in kriegspiel.  _Artificial Intelligence_ , 174(11):670–684, 2010\.  ISSN 0004-3702.  doi: https://doi.org/10.1016/j.artint.2010.04.017.  URL https://www.sciencedirect.com/science/article/pii/S0004370210000536.
* Coquelin and Munos (2007) Pierre-Arnaud Coquelin and Rémi Munos.  Bandit algorithms for tree search.  _CoRR_ , abs/cs/0703062, 2007.  URL http://arxiv.org/abs/cs/0703062.
* Cowling et al. (2012) Peter Cowling, Edward Powley, and Daniel Whitehouse.  Information set monte carlo tree search.  _IEEE Transactions on Computational Intelligence and Ai in Games_ , 4:120–143, 06 2012.  doi: 10.1109/TCIAIG.2012.2200894.
* Feldman and Domshlak (2014) Zohar Feldman and Carmel Domshlak.  Monte-carlo tree search: To MC or to dp?  In Torsten Schaub, Gerhard Friedrich, and Barry O’Sullivan, editors, _ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic - Including Prestigious Applications of Intelligent Systems (PAIS 2014)_ , volume 263 of _Frontiers in Artificial Intelligence and Applications_ , pages 321–326. IOS Press, 2014.  doi: 10.3233/978-1-61499-419-0-321.  URL https://doi.org/10.3233/978-1-61499-419-0-321.
* Geißer and Speck (2018) Florian Geißer and David Speck.  Prost-dd-utilizing symbolic classical planning in thts.  2018\.
* Guenther and Klinik (2004) Mathias Guenther and Jobas Klinik.  A new experience: O-thell-us – an ai project.  https://courses.cs.washington.edu/courses/cse573/04au/Project/mini1/O-Thell-Us/Othellus.pdf, 2004\.
* James et al. (2017) Steven James, George Konidaris, and Benjamin Rosman.  An analysis of monte carlo tree search, 2017.  URL https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14886.
* Kocsis and Szepesvári (2006) Levente Kocsis and Csaba Szepesvári.  Bandit based monte-carlo planning.  In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou, editors, _Machine Learning: ECML 2006_ , pages 282–293, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.  ISBN 978-3-540-46056-5.
* Kohler et al. (2019) Iris Kohler, Theresa Migler, and Foaad Khosmood.  Composition of basic heuristics for the game 2048.  In _Proceedings of the 14th International Conference on the Foundations of Digital Games_ , FDG ’19, New York, NY, USA, 2019. Association for Computing Machinery.  ISBN 9781450372176.  doi: 10.1145/3337722.3341838.  URL https://doi.org/10.1145/3337722.3341838.
* Liu (2021) Larkin Liu.  Connect 4 implementation in scala.  https://github.com/larkz/connect4-scala, commit = 4549c00398e7987814d83a2bd0760bbaedeb879b, 2021.
* Lucas (2018) Simon Lucas.  Montecarlots - java.  https://github.com/DrumerJoe21/MonteCarloTS, 2018.
* Norvig (1992) Peter Norvig.  _Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp_.  Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition, 1992\.  ISBN 1558601910.
* Puterman (1994) Martin L. Puterman.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  John Wiley & Sons, Inc., USA, 1st edition, 1994.  ISBN 0471619779.
* Sanner (2010) Scott Sanner.  Relational dynamic influence diagram language (rddl): Language description, 2010.
* Silver et al. (2016) David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.  Mastering the game of Go with deep neural networks and tree search.  _Nature_ , 529(7587):484–489, January 2016.  doi: 10.1038/nature16961.
* Winands et al. (2010) M. H. M. Winands, Y. Bjornsson, and J. Saito.  Monte carlo tree search in lines of action.  _IEEE Transactions on Computational Intelligence and AI in Games_ , 2(4):239–250, 2010.  doi: 10.1109/TCIAIG.2010.2061050.


# Classification of 3-GNDB graphs

A. Hosseini, M. Alaeiyan and Z. Aliannejadi∗

###### Abstract.

A nonempty graph $\Gamma$ is called generalized 3-distance-balanced, (3-$GDB$)
whenever for every edge $ab$, $|W_{ab}|=3|W_{ba}|$ or conversely. As well as a
graph $\Gamma$ is called generalized 3-nicely distance-balanced (3-$GNDB$)
whenever for every edge $ab$ of $\Gamma$, there exists a positive integer
$\gamma_{\Gamma}$, such that: $|W_{ba}|=\gamma_{\Gamma}$.
In this paper, we classify 3-$GNDB$ graphs with,
$\gamma_{\Gamma}\in\\{1,2\\}$.

MSC(2010): Primary: 05C12; Secondary: 05C40, 11Y50
Keywords: graphs, generalize 3-distance-balanced graphs, bipartite graphs.
$*$Corresponding author

##  1\. Introduction

Throughout of this paper, let $\Gamma$ be a finite, undirected, connected
graph with diameter $d$, and $V(\Gamma)$ and $E(\Gamma)$ denote the vertex and
edge set of $\Gamma$, respectively. The distance $d(a,b)$ between vertices
$a,b\in V(\Gamma)$ is the length of a shortest path between $a,b\in
V(\Gamma)$. For an edge $ab$ of a graph $\Gamma$, let $W_{ab}$ be the set of
vertices closer to $a$ than to $b$ , that is
$W_{ab}=\\{x\in\Gamma|d(x,a)<d(x,b)\\}$. We call a graph $\Gamma$, distance-
balanced $(DB)$, if $|W_{ab}|=|W_{ba}|$ for every edge $ab\in E(\Gamma)$.
These graphs were studied by Handa [6] who considered $DB$. For recent results
on $DB$ and $EDB$ see [3, 4, 5, 7, 8, 9, 11, 12]. A graph $\Gamma$ is called
nicely distance-balanced, whenever there exists a positive integer
$\gamma_{\Gamma}$, such that for two adjacent vertices $a,b$ of $\Gamma$;
$|W_{ab}|=|W_{ba}|=\gamma_{\Gamma}$. These graphs were studied by Kutnur and
Miklavič in [10].
A graph $\Gamma$ is called generalized 3-distance-balanced (3-$GDB$) if for
every edge $ab\in E(\Gamma)$; $|W_{ab}|=3|W_{ba}|$ or conversely. Throughout
of this paper, we assume that $|W_{ab}|=3|W_{ba}|$. A graph $\Gamma$ is called
generalized 3-nicely distance-balanced (3-$GNDB$), if for every edge $ab$ of
$\Gamma$, there exists a positive integer $\gamma_{\Gamma}$, such that:
$|W_{ba}|=\gamma_{\Gamma}$. For example we can show that $K_{1,3}$ and
$K_{2,6}$ are $3-GNDB$. The aim of this paper is classifying 3-$GNDB$ graphs
with $\gamma_{\Gamma}\in\\{1,2\\}$.

##  2\. Classification

In order to express the problem, it is better to start with parameter 3. In
this section, we classify 3-$GNDB$ graphs with $\gamma_{\Gamma}\in\\{1,2\\}$.
For every two non-negative integers $i,j$, we denote:

$D^{i}_{j}(a,b)=\\{x\in V(\Gamma)|d(x,a)=i$ and $d(x,b)=j\\}.$ $\hskip
36.70386pt(1)$

We now suppose that $\Gamma$ is a 3-$GNDB$ graph with diameter $d$. Since
$|W_{ab}|=3|W_{ba}|$ for every two adjacent vertices $a,b$ and by (1), we have

$|\\{a\\}\bigcup^{d-1}_{i=1}D^{i}_{i+1}(a,b)|=3|\\{b\\}\bigcup^{d-1}_{i=1}D^{i+1}_{i}(a,b)|$.

Therefore,
$\sum^{d-1}_{i=1}|D^{i}_{i+1}(a,b)|=3\sum^{d-1}_{i=1}|D^{i+1}_{i}(a,b)|+2$.$\hskip
71.13188pt(2)$

######  Theorem 2.1.

If $\Gamma$ be a connected $k-GNDB$ graph, then $\Gamma$ is a bipartite graph.

###### Proof.

. Inspired by the proof of Theorem 1.1 in [2], let $\Gamma$ be a $k-GNDB$
graph with diameter $d$, and the vertex set $\\{v_{1},v_{2},...,v_{2l+1}\\}$
form an odd cycle with length $2l+1$ such that $v_{i}v_{i+1}\in E(\Gamma)$.
Set

$A_{ij}=\\{v\in V(\Gamma)|d(v,v_{i+2l})=m_{j}k$,

$m_{j}k=\\{1,2,...,d\\},k=0,1,...,2l,2\leqslant j\leqslant r\\}$,

and

$W^{\Gamma}_{v_{i},v_{i+l}}=(\bigcup^{r}_{j=1}A_{ij})\bigcup\\{v_{i},v_{i+2l}\\}$,

$W^{\Gamma}_{v_{i+1},vi}=(\bigcup^{r}_{j=1}A_{(i+1)j})\bigcup\\{v_{i+1},v_{i+2}\\}$,

where the calculation in indexes $i$ are performed modulo $2l+1$ and some
$r\in N$. Taking $|A_{ij}|=a_{ij}$ for $i=0,1,...,2l$ and $j=1,2,...,r$, by
definition $k-GNDB$ graphs, there exists $e_{i}\in\\{\pm 1\\},i=0,1,...,2l$
such that

$\sum^{r}_{j=1}a_{0j}+2=k^{e_{0}}(\sum^{r}_{j=1}a_{1j}+2),$

$\sum^{r}_{j=1}a_{1j}+2=k^{e_{1}}(\sum^{r}_{j=1}a_{2j}+2),$

$\hskip 165.02606pt.$
$\hskip 165.02606pt.$
$\hskip 165.02606pt.$

$\sum^{r}_{j=1}a_{(2l-1)j}+2=k^{e_{2l-1}}(\sum^{r}_{j=1}a_{2l}+2)$,

$\sum^{r}_{j=1}a_{(2l)j}+2=k^{e_{2l}}(\sum^{r}_{j=1}a_{0j}+2)$.

Now, multipling all $(2l+1)$ equations above imply that
$k^{{\sum^{2i}_{i=0}}e_{i}}=1$, that is, $\sum^{2i}_{i=0}ei=0$. On the other
hand, $e_{i}\in\\{\pm 1\\}\Longrightarrow 1\leqslant|\sum^{2i}_{i}=0e_{i}|$,
which is a contradiction and henes $\Gamma$ has no odd cycle. This completes
the proof. ∎

######  Theorem 2.2.

If $\Gamma$ be a 3-GNDB grpah with $d=2$, then $deg(a)=3deg(b)$ for every edge
$ab$ of $\Gamma$.

###### Proof.

It follows from (1) that for a $3-GNDB$ graph with diameter $2$,
$|D^{1}_{2}(a,b)|=3|D^{2}_{1}(a,b)|+2$, for every edge $ab$ of $\Gamma$. If
$|D^{2}_{1}(a,b)|=t$, then $|D^{1}_{2}(a,b)|=3t+2.$ Therefore, $deg(b)=t+1$
and $deg(a)=3t+3$. So always $deg(a)=3deg(b)$. ∎

######  Lemma 2.3.

Let $\Gamma$ be a $3-GNDB$ graph with diameter 2. Then $\Gamma$ is only
$K_{n,3n}$.

###### Proof.

Let $\Gamma$ be a $3-GNDB$ graph with diameter 2. We claim that $\Gamma$ is a
complete bipartite graph. Otherwise, it does not have diameter 2. It follows
from Theorem 2.2 that $deg(a)=3deg(b)$. Since $\Gamma$ is complete bipartite
graph, $\Gamma$ must be $K_{n,3n}$. ∎

######  Lemma 2.4.

Let $\Gamma$ be a connected $k-GNDB$ graph with diameter $d$. Then $d\leqslant
k\gamma_{\Gamma}$

###### Proof.

Pick vertices $x_{0}$ and $x_{d}$ of $\Gamma$ such that $d(x_{0},x_{d})=d$ and
a shortest path $x_{0},x_{1},x_{2},...,x_{d}$ between $x_{0}$ and $x_{d}$. We
may assume without loss of generality that
$|W_{x_{0},x_{1}}|=k|W_{x_{0},x_{1}}|$. Then $\\{x_{1},x_{2},...,x_{d}\\}\in
W_{x_{1},x_{0}}$. Hence
$|\\{x_{1},x_{2},...,x_{d}\\}|\leqslant|W_{x_{1},x_{0}}|=k|W_{x_{0},x_{1}}|$.
this shows that $d\leqslant k\gamma_{\Gamma}$.

∎

We now classify $3-GNDB$ graphs $\Gamma$ with, $\gamma_{\Gamma}\in\\{1,2\\}$.
First we consider when $\gamma_{\Gamma}=1$. By the Lemma 2.4, $d\leqslant 3$.
If $d=1$, then $\Gamma$ is complete graph.
If $d=2$, by the Lemma 2.3, $\Gamma$ is only $K_{1,3}$.
If $d=3$, then we have only a path of length 2, that it would not be $3-GNDB$.

Now we consider the case $\gamma_{\Gamma}=2$.

######  Theorem 2.5.

A graph $\Gamma$ is $3-GNDB$ with $\gamma_{\Gamma}=2$ if and only if it is
$K_{2,6}$.

###### Proof.

For adjacent vertices $a,b$ of $\Gamma$, we say that the edge ab is consistent
if $|W_{ab}|=3|W_{ba}|$. Let $d$ be the diameter of $\Gamma$. By the Lemma
2.4, $d\leqslant 6$. If $d=1$, then $\Gamma$ is a complete graph. Therefore,
$d\in\\{2,3,4,5,6\\}$. Pick an edge $xy\in E(\Gamma)$ and for non-negative
integers $i,j$ set $D^{i}_{j}=D^{i}_{j}(x,y)$. Note that, by triangle
inequality, $D^{i}_{j}=\phi$ whenever $|i-j|>1$. If $d=2$, then by Lemma 2.3,
$\Gamma$ is only $K_{2,6}$.
Note that $|V(\Gamma)|=8$. Consider that $xy\in E(\Gamma)$ and
$d\in\\{3,4,5,6\\}$. Therefore, $|V(\Gamma)|$ $\setminus$ $\\{x,y\\}=6$. Since
for every $D^{i}_{j}$, in which $i,j\neq 0$, then there must be at least a
neighbour for either vertex $x$ or vertex $y$. Suppose that $|D^{2}_{1}|=1$
for all cases. We now consider all different cases of $|D^{i}_{j}|$, where
$i,j\neq 0$ for the 6 remaining vertices in $\Gamma$ and edge $xy$. Now we
show that, there is no graph for $3\leqslant d\leqslant 6$.
If $d=3$, then we split our proof into the following subcases.

Subcase 1: $|D^{1}_{2}|=1,|D^{2}_{3}|=4$ and $|D^{2}_{1}|=1$.
We will show that this case can not occur. Denote the vertex in $D^{1}_{2}$ by
$x_{1}$, the vertices in $D^{2}_{3}$ by $x_{2},x_{3},x_{4}$ and $x_{5}$, and
also the vertex in $D^{2}_{1}$ by $y_{1}$. The vertices $x_{2}$ up to $x_{5}$
can not be adjacent with $y_{1}$, because which is created an odd cycle.
Therefore, the vertices $x_{2}$ up to $x_{5}$ must be adjacent to each other.
In this case we have an odd cycle.

Subcase 2: $|D^{1}_{2}|=2,|D^{2}_{3}|=3$ and $|D^{2}_{1}|=1$.
Denote the vertices in $D^{1}_{2}$ by $x_{1}$ and $x_{2}$, the vertices in
$D^{2}_{3}$ by $x_{3},x_{4}$ and $x_{5}$, and also the vertex in $D^{2}_{1}$
by $y_{1}$. The vertices $x_{3},x_{4}$ and $x_{5}$ can not be adjacent with
$y_{1}$. The vertices $x_{3},x_{4}$ and $x_{5}$ can only be adjacent with
$x_{2}$. Since the diameter of graph is 3, the vertex $y_{1}$ must be adjacent
with $x_{1}$ or $x_{2}$ or both. In each case, the edges $xx_{1}$ or $yy_{1}$
are not consistent.

Subcase 3: $|D^{1}_{2}|=2,|D^{2}_{3}|=3$ and $|D^{2}_{1}|=1$.
Denote the vertices in $D^{1}_{2}$ by $x_{1}$ and $x_{2}$, the vertices in
$D^{2}_{3}$ by $x_{3},x_{4}$ and $x_{5}$, and also the vertex in $D^{2}_{1}$
by $y_{1}$. The vertices $x_{3},x_{4}$ and $x_{5}$ can not be adjacent with
$y_{1}$. The vertices $x_{3},x_{4}$ and $y_{1}$ can not be adjacent with
$x_{5}$. The vertices $x_{3}$ and $x_{4}$ must be adjacent with $x_{2}$, and
vertex $x_{5}$ must be adjacent with $x_{1}$. The vertex $y_{1}$ can be
adjacent with $x_{1}$ or $x_{2}$ or both. In each case the edge $xx_{1}$ is
not consistent.

Subcase 4: $|D^{1}_{2}|=3,|D^{2}_{3}|=2,|D^{2}_{1}|=1$.
Denote the vertices in $D^{1}_{2}$ by $x_{1},x_{2}$ and $x_{3}$, the vertices
in $D^{2}_{3}$ by $x_{4}$ and $x_{5}$, and also the vertex in $D^{2}_{1}$ by
$y_{1}$. The vertex $y_{1}$ can not be adjacent with $x_{4}$ and $x_{5}$. The
vertex $x_{3}$ can be adjacent with $x_{4},x_{5}$ and $y_{1}$, and also The
vertex $x_{4}$ can be adjacent with $x_{2}$ and $x_{3}$. Since the diameter of
graph is 3, the vertices $y_{1}$ and $x_{4}$ must be adjacent with $x_{2}$ or
the vertices $y_{1}$ and $x_{5}$ must be adjacent with $x_{1}$ or the vertex
$y_{1}$ must be adjacent with $x_{1}$ and $x_{2}$. In each case the edges
$xx_{2}$ and $x_{2}x_{5}$ are not consistent.

Subcase 5: $|D^{1}_{2}|=3,|D^{2}_{3}|=2,|D^{2}_{1}|=1$.
Denote the vertices in $D^{1}_{2}$ by $x_{1},x_{2}$ and $x_{3}$, the vertices
in $D^{2}_{3}$ by $x_{4}$ and $x_{5}$, and also the vertex in $D^{2}_{1}$ by
$y_{1}$. The vertex $y_{1}$ can not be adjacent with $x_{4}$ and $x_{5}$. The
vertices $x_{4}$ and $x_{5}$ can only be adjacent with $x_{2}$ and $x_{3}$.
The vertices $x_{2}$ and $x_{3}$ can be adjacent with $x_{4},x_{5}$ and
$y_{1}$. Since the diameter of graph is 3, the vertices $y_{1}$ must be
adjacent with $x_{1}$. In each case the edges $xx_{1}$ and $yy_{1}$ are not
consistent.

Subcase 6: $|D^{1}_{2}|=4,|D^{2}_{3}|=1,|D^{2}_{1}|=1$.
Denote the vertices in $D^{1}_{2}$ by $x_{1},x_{2},x_{3}$ and $x_{4}$, and the
vertex in $D^{2}_{3}$ and $D^{2}_{1}$ by $x_{5}$ and $y_{1}$ respectively. The
vertex $y_{1}$ can not be adjacent with $x_{5}$. The vertex $y_{1}$ can be
adjacent with $x_{1},x_{2},x_{3}$ and $x_{4}$, and also the vertex $x_{5}$ can
be adjacent with $x_{1},x_{2}$ and $x_{3}$. In each case the edges
$x_{4}x_{5}$ and $yy_{1}$ are not consistent.
If $d=4$ we split our proof into the following subcases.

Subcase 1: $|D^{1}_{2}|=1,|D^{2}_{3}|=2,|D^{3}_{4}|=2,|D^{2}_{1}|=1$.
Denote the vertex in $D^{1}_{2}$ by $x_{1}$, the vertices in $D^{2}_{3}$ by
$x_{2}$ and $x_{3}$, the vertices in $D^{3}_{4}$ by$x_{4}$ and $x_{5}$, and
the vertex in $D^{2}_{1}$ by $y_{1}$. The vertex $y_{1}$ can not be adjacent
with $x_{2}$ and $x_{3}$. The vertex $y_{1}$ can be adjacent with
$x_{1},x_{4}$ and $x_{5}$. The vertex $x_{2}$ can be adjacent with $x_{4}$ and
$x_{5}$, and also the vertices $x_{4}$ and $x_{5}$ can only be adjacent with
$x_{2}$ and $y_{1}$. In each case the edge $x_{1}x_{3}$ is not consistent.

Subcase 2: $|D^{1}_{2}|=1,|D^{2}_{3}|=2,|D^{3}_{4}|=2,|D^{2}_{1}|=1$.
Denote the vertex in $D^{1}_{2}$ by $x_{1}$, the vertices in $D^{2}_{3}$ by
$x_{2}$ and $x_{3}$, the vertices in $D^{3}_{4}$ by $x_{4}$ and $x_{5}$, and
the vertex in $D^{2}_{1}$ by $y_{1}$. The vertex $y_{1}$ can not be adjacent
with $x_{2}$ and $x_{3}$. The vertex $y_{1}$ can be adjacent with
$x_{1},x_{4}$ and $x_{5}$. The vertex $x_{4}$ can be adjacent with $x_{3}$ and
$y_{1}$, and also the vertex $x_{5}$ can be adjacent with $x_{2}$ and $y_{1}$.
In each case the edge $x_{2}x_{4}$ is not consistent.

Subcase 3: $|D^{1}_{2}|=1,|D^{2}_{3}|=1,|D^{3}_{4}|=3,|D^{2}_{1}|=1.$
Denote the vertex in $D^{1}_{2}$ by $x_{1}$, the vertex in $D^{2}_{3}$ by
$x_{2}$ and $x_{3}$, the vertices in $D^{3}_{4}$ by $x_{3},x_{4}$ and $x_{5}$,
and the vertex in $D^{2}_{1}$ by $y_{1}$. The vertex $y_{1}$ can not be
adjacent with $x_{2}$. The vertices $x_{3},x_{4}$ and $x_{5}$ must be adjacent
with $y_{1}$. The vertex $y_{1}$ can be adjacent with $x_{1},x_{3},x_{4}$ and
$x_{5}$. In each case the edge $x_{1}x_{2}$ is not consistent.

Subcase 4: $|D^{1}_{2}|=1,|D^{2}_{3}|=3,|D^{3}_{4}|=1,|D^{2}_{1}|=1.$
Denote the vertex in $D^{1}_{2}$ by $x_{1}$, the vertices in $D^{2}_{3}$ by
$x_{2}$, $x_{3}$ and $x_{4}$, the vertex in $D^{3}_{4}$ by $x_{5}$, and the
vertex in $D^{2}_{1}$ by $y_{1}$. The vertex $y_{1}$ can not be adjacent with
$x_{2},x_{3}$ and $x_{4}$. The vertices $x_{3}$ and $x_{4}$ most be adjacent
with $x_{5}$. The vertex $x_{5}$ can be adjacent with $x_{3},x_{4}$ and
$y_{1}$, and also the vertex $y_{1}$ can be adjacent with $x_{1}$ and $x_{5}$.
In each case the edge $x_{4}x_{5}$ is not consistent.

Subcase 5: $|D^{1}_{2}|=2,|D^{2}_{3}|=1,|D^{3}_{4}|=2,|D^{2}_{1}|=1$.
Denote the vertices in $D^{1}_{2}$ by $x_{1}$ and $x_{2}$, the vertex in
$D^{2}_{3}$ by $x_{3}$, the vertices in $D^{3}_{4}$ by $x_{4}$ and $x_{5}$,
and the vertex in $D^{2}_{1}$ by $y_{1}$. The vertex $y_{1}$ can not be
adjacent with $x_{3}$. The vertices $x_{4}$ and $x_{5}$ must be adjacent with
$y_{1}$. The vertex $y_{1}$ can be adjacent with $x_{2},x_{3},x_{4}$ and
$x_{5}$. The vertex $x_{2}$ can only be adjacent with $x_{3}$ and $y_{1}$. In
each case the edge $x_{1}x_{3}$ is not consistent.

Subcase 6: $|D^{1}_{2}|=2,|D^{2}_{3}|=2,|D^{3}_{4}|=1,|D^{2}_{1}|=1$.
Denote the vertices in $D^{1}_{2}$ by $x_{1}$ and $x_{2}$, the vertices in
$D^{2}_{3}$ by $x_{3}$ and $x_{4}$, the vertex in $D^{3}_{4}$ by $x_{5}$, and
the vertex in $D^{1}_{2}$ by $y_{1}$. The vertex $y_{1}$ can not be adjacent
with $x_{3}$ and $x_{4}$. The vertex $x_{4}$ can be adjacent with $x_{1}$ and
$x_{5}$. The vertex $y_{1}$ can be adjacent with $x_{1},x_{2}$ and $x_{5}$.
The vertex $x_{2}$ can be adjacent with $x_{3}$ and $y_{1}$. The vertex
$x_{3}$ can only be adjacent with $x_{2}$. The vertex $x_{5}$ can be adjacent
with $x_{4}$ and $y_{1}$. In each case the edge $xx_{1}$ is not consistent.

Subcase 7: $|D^{1}_{2}|=3,|D^{2}_{3}|=1,|D^{3}_{4}|=1,|D^{2}_{1}|=1$.
Denote the vertices in $D^{1}_{2}$ by $x_{1},x_{2}$ and $x_{3}$, the vertex in
$D^{2}_{3}$ by $x_{4}$, the vertex in $D^{3}_{4}$ by $x_{5}$ and the vertex in
$D^{2}_{1}$ by $y_{1}$. The vertex $y_{1}$ can not be adjacent with $x_{4}$.
The vertices $x_{2}$ and ?$?x_{3}$ can be adjacent with $y_{1}$ and $x_{4}$.
The vertex $y_{1}$ can be adjacent with $x_{1},x_{2},x_{3}$ and $x_{5}$. The
vertex $x_{4}$ can be adjacent with $x_{2}$ and $x_{3}$. The vertex $x_{5}$
must be adjacent with $y_{1}$. In each case the edge $xx_{1}$ is not
consistent.
If $d=5$ we split our proof into the following subcases.

Subcase 1: $|D^{1}_{2}|=|D^{2}_{3}|=|D^{3}_{4}|=1,|D^{4}_{5}|=2$ and
$|D^{2}_{1}|=1.$
Denote the vertex in $D^{1}_{2},D^{2}_{3}$ and $D^{3}_{4}$ by $x_{1},x_{2}$
and $x_{3}$ respectively, the vertices in $D^{4}_{5}$ by $x_{4}$ and $x_{5}$,
and also the vertex in $D^{2}_{1}$ by $y_{1}$. The vertex $y_{1}$ can not be
adjacent with $x_{2},x_{4}$ and $x_{5}$. In this case the vertices $x_{4}$ and
$x_{5}$ can not be adjacent with other vertices.

Subcase 2: $|D^{1}_{2}|=|D^{2}_{3}|=1,|D^{3}_{4}|=2,|D^{4}_{5}|=1$ and
$|D^{2}_{1}|=1.$
Denote the vertex in $D^{1}_{2},D^{2}_{3}$ by $x_{1}$ and $x_{2}$
respectively, the vertex in $D^{3}_{4}$ by $x_{3}$ and $x_{4}$, the vertex in
$D^{4}_{5}$ by $x_{5}$ and also the vertex in $D^{2}_{1}$ by $y_{1}$. The
vertices $y_{1}$ can not be adjacent with $x_{2}$ and $x_{5}$. The vertex
$x_{4}$ must be adjacent with $x_{5}$. The vertex $y_{1}$ can be adjacent with
$x_{3}$ and $x_{4}$. In each case the edge $x_{1}x_{2}$ is not consistent.

Subcase 3: $|D^{1}_{2}|=1,|D^{2}_{3}|=2,|D^{3}_{4}|=1,|D^{4}_{5}|=1$ and
$|D^{2}_{1}|=1.$
Denote the vertex in $D^{1}_{2}$ by $x_{1}$, the vertices in $D^{2}_{3}$ by
$x_{2}$ and $x_{3}$, the vertex in $D^{3}_{4}$ by $x_{4}$, the vertex in
$D^{4}_{5}$ by $x_{5}$, and also the vertex in $D^{2}_{1}$ by $y_{1}$. The
vertex $y_{1}$ can not be adjacent with $x_{2},x_{3}$ and $x_{5}$. In this
case the vertex $x_{5}$ can not be adjacent with other vertices.
If $d=6$, we have:
$|D^{1}_{2}|=|D^{2}_{3}|=|D^{3}_{4}|=|D^{4}_{5}|=|D^{5}_{6}|=|D^{2}_{1}|=1.$
Denote the vertex in $D^{1}_{2},D^{2}_{3},D^{3}_{4},D^{4}_{5},D^{5}_{6}$ and
$D^{2}_{1}$ by $x_{1},x_{2},x_{3},x_{4},x_{5}$ and $y_{1}$ respectively. The
vertex $y_{1}$ can not be adjacent with $x_{2}$ and $x_{4}$, and also the
vertex $y_{1}$ can be adjacent with $x_{1},x_{3}$ and $x_{5}$. In each case
the edge $x_{1}x_{2}$ is not consistent. ∎

## References

  * [1] A.Abedi, M. Alaeiyan, A. Hujdurović, K. Kutnar, Quasi-$\lambda$-distance-balanced graphs, Discrete Appl. Math. 227 (2017), 21-28.
  * [2] Z. Aliannejadi, A. Gilani, M. Alaeiyan, J. Asadpour, On some properties of edge quasi-distance-balanced graphs, Journal of Mathematical Extension. 16 (2022), 1-13.
  * [3] Z. Aliannejadi, M. Alaeiyan, A. Gilani, Strongly edge distance-balanced graph products, 7th International Conference on Combinatorics, Cryptography, Computer Science and Computing (2022).
  * [4] K. Balakrishman, M. Changat, I. Peterin, ?S.P. Špacapan?, P. Šparal, A. R. Subhamathi, Strongly distance-balanced graph and graph product, European. J. Combin. 30 (2009), 1048-1053.
  * [5] S. Cabello, P. Lukšič, The complexity of obtaining a distance-balanced graph, Electron. J. combin. 18 (1) (2011), Paper 49.
  * [6] K. Handa, Bipartite graphs with balanced (a, b)-partitions, Ars Combin.  51 (1999), 113-119.
  * [7] A. Ilič, S. Klavžar, M. Milanović, On distance-balanced graphs, European. J. Combin. 31 (2010), 733-737.
  * [8] K. Kutnar, A. Malnič, D. Marušič, Š. Miklavič, Distance-balanced graphs:symmetry conditions,Discrete Math. 306 (2006), 1881-1894.
  * [9] K. Kutnar, A. Malnič, D. Marušič, Š. Miklavič, The strongley distance-balanced property of generalized petersen graphs, Ars Math. Contemp. 2 (2009), 41-47.
  * [10] K. Kutnar, Š. Miklavič, Nicely distance-balanced graphs,European. j. Combin. 39 (2014), 57-67.
  * [11] Š. Miklavič, P. Šparl, On the connectivity of bipartite distance-balanced graphs, European. J. Combin. 33 (2012), 237-247.
  * [12] R. Yang, X. Hou, N. Li, W. Zhong, A note on the distance-balanced property of generalized petersen graphs, Electron. J. Combin. 16 (1) (2009), Note 33.

Amir Hosseini
Department of Mathematics, Islamic Azad University, Nazarabad Branch,
Nazarabad, Iran.
Email<EMAIL_ADDRESS>

Mehdi Alaeiyan
Department of Mathematics, Iran University of Science and Technology, Narmak,
Tehran 16844. Iran.
Email<EMAIL_ADDRESS>

Zohreh Aliannejadi
Department of Mathematics, Islamic Azad University, South Tehran Branch,
Tehran, Iran.
Email<EMAIL_ADDRESS>