# Split Moves for Monte-Carlo Tree Search

Jakub Kowalski1, Maksymilian Mika1, Wojciech Pawlik1, Jakub Sutowicz1, Marek
Szykuła1,
Mark H. M. Winands2

###### Abstract

In many games, moves consist of several decisions made by the player. These
decisions can be viewed as separate moves, which is already a common practice
in multi-action games for efficiency reasons. Such division of a player move
into a sequence of simpler / lower level moves is called _splitting_. So far,
split moves have been applied only in forementioned straightforward cases, and
furthermore, there was almost no study revealing its impact on agents’ playing
strength. Taking the knowledge-free perspective, we aim to answer how to
effectively use split moves within Monte-Carlo Tree Search (MCTS) and what is
the practical impact of split design on agents’ strength. This paper proposes
a generalization of MCTS that works with arbitrarily split moves. We design
several variations of the algorithm and try to measure the impact of split
moves separately on efficiency, quality of MCTS, simulations, and action-based
heuristics. The tests are carried out on a set of board games and performed
using the Regular Boardgames General Game Playing formalism, where split
strategies of different granularity can be automatically derived based on an
abstract description of the game. The results give an overview of the behavior
of agents using split design in different ways. We conclude that split design
can be greatly beneficial for single- as well as multi-action games.

## Introduction

The benefits of simulation-based, knowledge-free, open-loop algorithms such as
Monte-Carlo Tree Search (MCTS) (Kocsis and Szepesvári 2006; Browne et al.
2012; Świechowski et al. 2021) and Rolling Horizon Evolutionary Algorithm
(Perez et al. 2013) are especially suited to work within environments with
many unknowns. In particular, they are widely used in General Game Playing
(GGP) (Genesereth, Love, and Pell 2005), a domain focusing on developing
agents that can successfully play any game given its formalized rules, which
was established to promote work in generalized, practically applicable
algorithms (Finnsson and Björnsson 2010; Goldwaser and Thielscher 2020).
Initially based entirely on Stanford’s Game Description Language (GDL) (Love
et al. 2006), GGP expands over time as new game description formalisms are
being developed e.g., Toss (Kaiser and Stafiniak 2011), GVG-AI (Perez et al.
2016), Regular Boardgames (RBG) (Kowalski et al. 2019), and Ludii (Piette et
al. 2020).

Recent advances in search and learning support the trend of generalization,
focusing on methods being as widely applicable as possible. Deep Q-networks
were applied to play classic Atari games and achieved above human-level
performance on most of the 49 games from the test set (Mnih et al. 2015). More
recently, AlphaZero, showed how to utilize a single technique to play Go,
Chess, and Shogi on a level above all other compared AI agents (Silver et al.
2018).

In the trend of developing enhancements for MCTS (Cazenave 2015; Baier and
Winands 2018), we tackle the problem of influencing the quality of the search
by altering the structure of the game tree itself. In many games, a player’s
turn consists of a sequence of choices that can be examined separately. A
straightforward representation is to encode these choices as distinct moves,
obtaining a split game tree, instead of using a single move in orthodox
design. The potential applications go beyond games, as the method can be used
for any kind of problem that is solvable via a simulation-based approach and
its representation of actions can be decomposed. In this paper, we are
interested in the general technique of altering the game tree by introducing
split moves and its possible effects, rather than its application to a
particular game combined with expert knowledge. Hence, we focus on the GGP
setting and MCTS, which is the most well-known and widely applied general
search algorithm working without expert knowledge.

We propose the _semisplit_ algorithm, which is a generalization of MCTS that
effectively works with arbitrary splitting. For the purposes of experiments,
we implement the concept in the Regular Boardgames system (Kowalski et al.
2019) – a universal GGP formalism for the class of finite deterministic games
with perfect information. A few _split strategies_ of different granularity
are developed, which split moves basing on the given general game description.
The experiments are conducted on a set of classic board games, comparing
agents using orthodox and split designs. We test a number of variants of the
algorithm, applying split moves selectively to different phases of MCTS, and
include action-based heuristics (MAST, RAVE (Gelly and Silver 2007)) to
observe the behavior also for enhanced MCTS. From the results, we identify the
most beneficial configurations and conclude that split moves can greatly
improve the player’s strength.

The source code used for the experiments is shared within the RBG
implementation (Kowalski et al. 2021).

### Related Work

The idea of splitting moves is well known, but apparently, it was not given
proper consideration in the literature, being either used naturally in trivial
cases or restrained to follow a human-authored heuristic. Even these cases
were discussed in rather limited aspects, given how general applications of
split technique can be.

For particularly complex environments, split is regarded as natural and
mandatory. This technique is widely used for Arimaa, Hearthstone, and other
multi-action games (Fotland 2006; Justesen et al. 2017; Roelofs 2017). Here,
the reduced branching factor is considered to be the main effect, as
otherwise, programs could not play such games at a proper level. The case of
Amazons is the only one that we have found where agents playing with split and
non-split representations were compared against each other (Kloetzer, Iida,
and Bouzy 2007). For multi-action games such as real-time strategies, where
the ordering of actions is unrestricted, Combinatorial Multi-armed Bandits
algorithms are often employed (Ontañón 2017). Using actions separately as
moves in the MCTS tree was also considered under the name of _hierarchical
expansion_ (Roelofs 2017) and in context of factoring action space for MDPs
(Geißer, Speck, and Keller 2020). So far, splitting was applied only for such
multi-action games, where it is possible and natural to divide a turn into
separate moves and process them like regular ones. Splitting / move
decomposition should not be confused with the game decomposition (Hufschmitt,
Vittaut, and Jouandeau 2019).

A practical application of splitting is found in GGP, where many games are
manually (re)encoded in their split variants just to improve efficiency. For
example, some split versions of games like Amazons, Arimaa, variants of
Draughts, or Pentago exist in GDL. The same approach is taken in other systems
like Ludii. However, it is generally unknown how such versions affect the
agents’ playing strength.

Additionally, splitting via artificial turns causes some repercussions, e.g.,
for game statistics or handling the turn timer. Especially in a competitive
setting, an agent gets the same time for every move, even when they are single
actions, thus making more moves in a turn gives longer computation time.
Although this can be resolved, it requires specific language constructions
that do not exist in any GGP system. Instead of complicating languages, it
would be better and more general to develop split-handling on the agent’s
side.

A related topic is _move groups_ (Saito et al. 2007; Childs, Brodeur, and
Kocsis 2008; Van Eyck and Müller 2011), where during MCTS expansion, children
of every tree node are partitioned into a constant number of classes guided by
a heuristic. The basic idea of move groups is to divide nodes of the MCTS tree
into two levels, creating intermediate nodes that group children belonging to
the same class. There is no reported application of move groups beyond Go,
Settlers of Catan, and artificial single-player game trees for maximizing UCT
payoff. Usually, move groups are understood as introducing artificial tree
nodes unrelated to any move representation nor simplifying computation. They
also require human intervention to encode rules on how to partition the moves.
From the perspective of splitting, (nested) move groups are a side effect, but
not every partition can be obtained by splitting.

As splitting just alters the game tree, it is compatible with any other search
algorithm that uses this game tree as the underlying structure. In particular,
it affects action-based heuristics operating on moves such as MAST and RAVE
(Gelly and Silver 2007). But unlike usual techniques, splitting often improves
efficiency, so it would be beneficial assuming that it leaves the behavior of
algorithms unchanged.

## Semisplitting in MCTS

### Abstract Game

We adapt a standard definition of an abstract turn-based game (Rasmusen 2007)
to our goals. A _finite deterministic turn-based game with perfect
information_ (simply called _game_) $\mathcal{G}$ is a tuple
$(\mathit{players}_{\mathcal{G}},\mathcal{T}_{\mathcal{G}},\mathit{control}_{\mathcal{G}},\mathit{out}_{\mathcal{G}})$,
where: $\mathit{players}_{\mathcal{G}}$ is a finite non-empty set of _players_
; $\mathcal{T}_{\mathcal{G}}=(V,E)$ is a finite directed tree called the _game
tree_ , where $V$ is the set of nodes called _game states_ and $E$ is the set
of edges called _moves_ , $V_{\mathrm{n}}\subset V$ is the set of inner nodes
called _non-terminal_ states, and $V_{\mathrm{t}}\subseteq V$ is the set of
leaves called _terminal_ states; $\mathit{control}_{\mathcal{G}}\colon
V_{\mathrm{n}}\to\mathit{players}_{\mathcal{G}}$ is a function assigning the
_current player_ to non-terminal states; $\mathit{out}_{\mathcal{G}}\colon
V_{\mathrm{t}}\times\mathit{players}_{\mathcal{G}}\to\mathbb{R}$ is a function
assigning the final _score_ of each player at terminal states. For a non-
terminal state $s\in V_{\mathrm{n}}$, the set of _legal moves_ is the set of
outgoing edges $\\{(s,t)\in E\mid t\in V\\}$. During a play, the current
player $\mathit{control}_{\mathcal{G}}(s)$ chooses one of its legal moves. The
game tree is directed outwards its root $s_{0}\in V$, which is called the
_initial state_. Hence, all states are reachable from $s_{0}$. Each play
starts from $s_{0}$ and ends at a terminal state (leaf).

Two games are _isomorphic_ if there exists a bijection between the states that
preserve the edges of the game tree and the current player (if the state is
non-terminal) or the scores (if the state is terminal). For a state $s\in V$,
the _subgame_ $\mathcal{G}_{s}$ is the game with the tree obtained from
$\mathcal{T}_{\mathcal{G}}$ by rooting at $s$ and removing all states
unreachable from $s$.

### Semisplit Game

Going deeper into a particular representation of a move, it usually can be
partitioned into a sequence of smaller pieces, which we call _semimoves_. For
example, depending on a particular implementation, they could correspond to
atomic actions, move groups, or, in the extreme case, even single bits of a
technical move representation. Computing semimoves can be, but not always is,
computationally easier than full moves and sometimes may reveal structural
information desirable in a knowledge-based analysis.

However, often a natural and the most effective splitting does not lead to a
proper variant of the game, i.e., we cannot treat semimoves as usual moves. It
is because not every available sequence of easily computed semimoves can be
completed up to a legal move. This especially concerns single-action games,
but also splits inferred automatically in general, where without prior
knowledge it is difficult to determine if we obtain a proper game.

###### Example 1

In Chess, a typical move consists of picking up a piece and choosing its
destination square. It would be much more efficient first to select a piece
from the list of pieces and then a square from the list of available
destinations computed just for this piece, than to select a move from the list
of all legal ones, which is usually much longer. However, sometimes we may not
be able to make a legal move with a selected piece, e.g., because the piece is
blocked or the king will be left under check.

A remedy could be checking if each available semimove is a prefix of at least
one legal move. However, in many cases, this can be as costly as computing all
legal moves, losing performance benefits, or even decreasing efficiency.
Instead, we can work on semisplit games directly.

To provide an abstract model, we require a different game definition,
including additional information about intermediate states. We extend the
definition of a game to a _semisplit game_ as follows. Let $V$ be now the
disjoint union of non-terminal states $V_{\mathrm{n}}$, terminal states
$V_{\mathrm{t}}$, and the _intermediate states_ $V_{\mathrm{i}}$. Then,
$V_{\mathrm{n}}$ is a subset of inner vertices of the game tree, terminal
states $V_{\mathrm{t}}$ is a subset of leaves, and $V_{\mathrm{i}}$ can
contain states of both types. The states in $V_{\mathrm{n}}$ and
$V_{\mathrm{t}}$ are called _nodal_. A semisplit game must satisfy that the
initial state $s_{0}$ is nodal, and for every non-terminal state $s\in
V_{\mathrm{n}}$, the subgame $\mathcal{G}_{s}$ contains at least one terminal
state. The second condition ensures that from each nodal state, a terminal
state is reachable. Yet, for an intermediate state, there may be no nodal
state in its subgame; then this state is called _dead_. An edge is now called
a _semimove_. A _submove_ is a directed path where nodal states can occur only
at the beginning or at the end, and there are only intermediate states in the
middle. Then, a _move_ is a submove between two nodal states.

There is a correspondence between a semisplit game and an (ordinary) game. The
_rolled-up_ game of a semisplit game is obtained by removing all dead states,
and then by replacing each maximal connected component rooted at a non-
terminal state with only intermediate states below with one non-terminal
state; then all the edges become moves. A semisplit game
$\mathcal{G}^{\prime}$ is _equivalent_ to a game $\mathcal{G}$ if the rolled-
up game of $\mathcal{G}^{\prime}$ is isomorphic to $\mathcal{G}$. So
generally, splitting moves in a game means deriving its equivalent semisplit
game.

Figure 1: A Chess position (left) and the corresponding fragments of two
semisplit games of a smaller (middle) and a larger (right) granularity. There
are $8$ legal moves in total ($\text{a7-a8Q},\ldots,\text{Kh3-g2}$ in the long
algebraic notation), which form $8$ edges in the standard game tree. Nodal
states are marked with a double circle; ~~+~~ indicates passed non-check king
test. In the right semisplit game fragment, there are drawn 3 nodal, 9
intermediate, and 5 dead states.

An example of two distinct semisplit versions of Chess is shown in Fig. 1.

### The Semisplit Algorithm

We describe a generalization of MCTS that works on an underlying semisplit
game. To distinguish from the standard MCTS algorithm that operates on an
ordinary game, the latter is called _orthodox MCTS_. In the following
description, we use standard terminology (Browne et al. 2012) and focus on the
differences with orthodox MCTS.

The simulation phase is shown in Alg. 1, lines 1–13. Drawing a move at random
is realized through backtracking (SemisplitRandomMove). Given a game state, we
choose and apply semimoves in the same way as moves in orthodox MCTS, but we
keep the list of legal semimoves computed at each level. When it happens that
the current intermediate state does not have a legal semimove (it is dead), we
backtrack and try another semimove. Thus, a move is always found if it exists,
and every legal move has a positive chance to be chosen, although the
probability distribution (on legal moves) may be not uniform (in the worst
case, the probability of choosing a move can be exponentially smaller in the
number of introduced intermediate states). A single simulation
(SemisplitSimulation) just uses the modified random move selection. Note that
this function can fail (line 4), which happens if and only if called for a
dead state.

1:$s$ – game state

2:function SemisplitSimulation($s$)

3: while $\mathbf{not}\>s.\textsc{IsTerminal}()$ do

4: $m\leftarrow\textsc{SemisplitRandomMove}(s)$

5: if $m=\textbf{None}$ then return None $\triangleright$ $s$ is dead

6: $s\leftarrow s.\textsc{Apply}(m)$

7: return $s.\textsc{Scores}()$

8:function SemisplitRandomMove($s$)

9: for all $a\in\textsc{Shuffle}(s.\textsc{GetAllSemimoves}())$ do

10: $s^{\prime}\leftarrow s.\textsc{apply}(a)$

11: if $s^{\prime}.\textsc{IsNodal}()$ then return $a$

12: $m\leftarrow\textsc{SemisplitRandomMove}(s^{\prime})$

13: if $m\neq\mathbf{None}$ then return Concatenate($a,m$)

14: return $\mathbf{None}$ $\triangleright$ No legal move

15:function MCTSIteration( )

16: $v\leftarrow\textsc{TreeRoot}()$

17: while $\mathbf{not}\>v.\textsc{State}().\textsc{IsTerminal}()$ do

18: if $v.\textsc{FullyExpanded}()$ then

19: $v\leftarrow v.\textsc{UCT}()$

20: else

21: $a_{1}\leftarrow\textsc{RandomElement}(v.\textsc{UntriedSemimoves}())$

22: $(v^{\prime},\mathit{scores})\leftarrow\textsc{Expand}(v,a_{1})$

23: if $\mathit{scores}=\mathbf{None}$ then continue

24: $\textsc{Backpropagation}(v^{\prime},\mathit{scores})$

25: return

26: $\textsc{Backpropagation}(v,v.\textsc{State}().\textsc{Scores}())$

27:$v$ – leaf node; $a_{1}$ – selected untried semimove

28:function Expand($v,a_{1}$)

29: $s\leftarrow v.\textsc{State}().\textsc{Apply}(a_{1})$

30: $\mathit{scores}\leftarrow\textsc{SemisplitSimulation}(s)$

31: if $\mathit{scores}=\mathbf{None}$ then

32: $v.\textsc{RemoveSemimove}(a_{1})$

33: return $\mathbf{None}$

34: $c\leftarrow\textsc{CreateNode}(s)$

35: $v.\textsc{AddChild}(c,a_{1})$

36: return $(c,\mathit{scores})$

37:$v$ – leaf node; $\mathit{scores}$ – players’ final scores

38:function Backpropagation($v,\mathit{scores}$)

39: while $v\neq\textsc{TreeRoot}()$ do

40: $v.\mathit{scoreSum}\leftarrow
v.\mathit{scoreSum}+\mathit{scores}[v.\mathit{Player}]$

41: $v.\mathit{iterations}\leftarrow v.\mathit{iterations}+1$

42: $v\leftarrow v.\textsc{Parent}()$

43: v.$\mathit{iterations}\leftarrow v.\mathit{iterations}+1$

Algorithm 1 Vanilla semisplit MCTS.

The vanilla variant of semisplit MCTS is shown in Alg. 1. As orthodox MCTS, it
uses the UCT policy in the selection phase (Kocsis and Szepesvári 2006). But
in contrast, semisplit MCTS uses both nodal and intermediate states as tree
nodes. The expansion begins with the selection of an untried semimove (line
20). Dead states are never added to the MCTS tree. If the next state turns out
to be dead, that semimove is removed from the list in the node, and the search
goes back to the MCTS tree, so other untried semimoves are chosen (line 22).
It can happen that all untried semimoves lead to dead states and the node
becomes fully expanded; then the search continues according to the UCT policy.

Raw and nodal variants. There are two expansion variants, _raw_ and _nodal_.
The _raw_ variant, given in Alg. 1, adds just one tree node as usual, either
intermediate or nodal. However, this can leave semisplit MCTS behind orthodox
MCTS in terms of expansion speed, as a single node in the latter corresponds
to a path between nodal states in the former. In other words, when counting
nodal states, orthodox MCTS expands faster. The _nodal_ variant compensates
this risk by adding the whole move (path) during a single expansion (see
Appendix, Alg. 2 for pseudocode). This may slightly increase the quality of
the search when these paths are long and, in particular, cannot be exploited
due to slower expansion. However, the nodal variant may be slightly slower.

Final selection. There are several policies to select the final move to play.
A common policy is to choose the one with the best average score (Winands
2017) among tried moves. When it comes to selecting the final move to play,
semisplit MCTS greedily chooses the best semimove till the first next nodal
state. If the move goes outside of the MCTS tree constructed so far, the raw
variant chooses the remaining semimoves uniformly at random. This can happen
when the branching factor is very large compared to the number of iterations.
In the nodal variant this cannot occur, as all leaves added to the MCTS tree
are nodal states.

Combined variants and roll-up. Possible variants of semisplit MCTS involve
combining both designs and using them selectively in different phases. There
are two natural variants: orthodox design in the MCTS tree phases (selection
and expansion) combined with semisplit design in the simulation phase, and the
opposite variant.

Another proposed variant is adaptive, applied in the MCTS tree phases. The
idea is to use semisplit design at first, to improve efficiency and deal with
potentially large branching factor, and then switch to orthodox design to
provide more conservative evaluation. The _roll-up_ variant uses semisplit
design in the MCTS tree with the modification as follows (see Appendix, Alg. 3
for pseudocode). Whenever a node $v$ of an intermediate state in the MCTS tree
is fully expanded, i.e., all its children $v_{1},\ldots,v_{k}$ were tried, the
algorithm removes $v$ and connects $v_{1},\ldots,v_{k}$ directly to its parent
$v^{\prime}$. Then, the edges to them are submoves obtained from concatenating
the submove from $v^{\prime}$ to $v$ and the submoves from $v$ to $v_{i}$. In
this way, semisplit design is limited to the expansion phase, as the algorithm
switches to orthodox design in the parts of the MCTS tree that become fully
expanded. The roll-up variant can be used to test the impact of semisplit
design in this phase alone.

Action-based heuristics. Common general knowledge-free enhancements of MCTS
are online learning heuristics, which estimate the values of moves by
gathering statistics. We test the two most fundamental methods, MAST and RAVE
(Finnsson and Björnsson 2008; Gelly and Silver 2011; Winands 2017). MAST
globally stores for every move (actually, for every set of moves with the same
representation) the average result of all iterations containing this move; it
is used in simulations in place of a uniformly random choice. RAVE stores
similar statistics locally in each MCTS node for available moves and uses them
to bias the choice in UCT. For both techniques, there are many policies
proposed that differ in details.

Table 1: Flat Monte-Carlo results (random simulations with gathering scores). The 2st and 3rd column show the speed measured in the number of computed respective nodal states and simulations per second. The 4th and 5th columns show the mean simulation depth measured resp. in nodal states and all states (computed dead states are also included). The last 6th column shows the branching factor calculated as the number computed (semi)moves divided by the number of states.  Game | Nodal states/sec. | Sim./sec. | Mean nodal states/sim. | Mean all states/sim. | Mean br. factor (all states)
---|---|---|---|---|---
Breakthrough (orthodox) | 2,388,827 (100%) | 37,272 | 64 | 64 | 25.69
Breakthrough (@Mod) | 5,717,972 (239%) | 78,120 | 73 | 157 | 7.71
Breakthrough (@ModShift) | 7,558,711 (316%) | 220,074 | 34 | 164 | 3.12
Chess (orthodox) | 308,157 (100%) | 976 | 316 | 316 | 22.83
Chess (@Mod) | 1,556,036 (505%) | 5,971 | 261 | 1,494 | 2.96
Chess (@ModPlus) | 1,390,428 (451%) | 5,341 | 260 | 2,194 | 2.31

MAST and RAVE can be adapted to semisplit in a straightforward way if
semisplit design is used both in the MCTS tree and simulation. In combined
variants, they require some adjustments, which rely on dividing (sub)moves
into semimoves or merging semimoves into moves.

$\bullet$  _MAST-split_ and _RAVE-split_ : The basic modification of MAST
adapted to semisplit simply stores separate statistics for each semimove.
Then, when evaluating the score of a longer submove, we have to somehow
combine the result from the scores of the included semimoves. Here, we propose
the arithmetic mean of the scores of the semimoves. However, if a semimove has
not been tried, then the maximum reward is returned as the final score of the
whole submove. MAST-split can be applied to any variant of MCTS.

_RAVE-split_ works analogously, i.e., it splits every submove into single
semimoves. Statistics for a semimove in a tree node are updated if this
semimove was used explicitly at the node or later in the iteration, either
directly or possibly as a part of a submove. RAVE-split is easily enabled only
in the combinations using semisplit design in the selection and expansion
phases, i.e. when the domain of semimoves in these phases correspond to the
stored statistics.

Depending on the implementation, split variants can be much faster than
regular heuristics due to a much smaller domain of semimoves (i.e., we can use
faster data structures for storing statistics). However, obtained samples are
less reliable, as semimoves carry less information than full moves.

$\bullet$  _MAST-join_ and _RAVE-join_ : These variants merge semimoves into
full moves. MAST-join and RAVE-join store statistics only for whole moves. Of
course, they are available only in the cases where we evaluate only moves in
the corresponding MCTS phases.

$\bullet$  _MAST-context_ and _RAVE-context_ : To partially overcome the
weakness of less reliable samples, we also propose _context_ variants. They
lead to storing sample values closer to those used in orthodox design. The
main idea of MAST-context is entwined with _N-gram-Average Sampling Technique_
(_NST_) (Tak, Winands, and Björnsson 2012), which gathers statistics for
fixed-size sequences of moves. MAST-context maintains statistics for submoves
of different lengths. When the iteration is over, for each move applied in the
iteration, the statistics are updated not only for that move but also for each
of its prefixes. The _context_ of a state is the submove from the last
preceding nodal state to this state. Thus, a context is a submove that is a
prefix of some move. While selecting the best submove in the simulation phase,
we use the statistics of the submoves concatenated to the current context. In
RAVE-context, MCTS nodes store statistics for each child just as in the
regular RAVE. The difference is in updating them; the statistic of a semimove
is updated only if the iteration contains the same semimove played in the same
context. The context variants are available for every variant of MCTS (in
particular, for roll-up) because they store statistics for all submoves that
may be ever needed.

$\bullet$  _MAST-mix_ and _RAVE-mix_ : For most MCTS variants, we have more
than one choice for variants of action-based heuristics. This leads to the
possibility of using more than one simultaneously. The variants of the
heuristics differ in speed of gathering samples but also in their quality,
e.g., MAST-split gathers samples faster than MAST-context, but they are less
reliable. Hence, MAST-mix combines MAST-split with MAST-context, and RAVE-mix
combines RAVE-split with RAVE-context. All statistics are updated separately
according to both split and context strategies. For both heuristics, we have
an additional parameter – the _mix-threshold_. During the evaluation, when the
number (weight) of samples in the context heuristic is smaller than the mix-
threshold, the score is evaluated according to the split variant; otherwise,
the context statistics are used.

An extended discussion on these heuristics and their available combinations
can be found in Appendix, Sec. 1.

## Implementation and Experiments

Our test set consists of 12 board games, well known in GGP (Amazons,
Breakthrough, Breakthru, Chess, Chess without check, English Draughts, Fox And
Hounds, Go, Knightthrough, Pentago, Skirmish, and The Mill Game). Appendix,
Sec. 3 contains the precise rules of the used versions.

Split Strategies. For a given game, there are many equivalent split versions.
Usually, they are derived through a manual implementation of the algorithm
computing legal moves and states. For the purposes of experiments, we use
abstract game descriptions in the Regular Boardgames and derive semisplit
games through _split strategies_ , which are algorithms taking as the input a
pure definition of the game rules (without any heuristic information for good
playing). Thus, they can be considered knowledge-free and derive splittings
automatically in a systematic way across different games.

Although split strategies might be interesting by themselves, they are
developed here for the purposes of experiments. This part is to create an
example environment for testing semisplit MCTS, and thus it is not the focus
of the current paper. We note that using such split strategies would not be
possible effectively without semisplit MCTS, as they introduce dead states.
Similar effects could be obtained via other approaches; in particular, one
could manually implement each semisplit game, apart from any GGP system.

The omitted technical details of RBG language, split strategies, and how they
affect each particular game are given in Appendix Sec. 2 and 3. Below, we
describe the intuitive meaning of split strategies. Each split strategy is
defined via a subset of three components.

$\bullet$  _Mod_ : This is a basic component of relatively low granularity.
Every semimove corresponds to an action modifying either a single square on
the board or a variable; thus there is introduced a semimove for each
elementary modification of the game state. A move in a chess-like game is
split into two semimoves: one for selecting and grabbing a piece from the
board and one for dropping it on the destination square. For modifying more
squares, more semimoves are introduced accordingly (e.g., Amazons). Also, it
separates the final decision in a move, e.g., in Chess, the king check is
performed in a final semimove; in Go, the player first chooses whether to pass
or to put a stone. An example of the resulting semisplit game tree is shown in
Fig. 1(middle).

$\bullet$  _Plus_ : This component introduces a semimove for every single
decision (branch) specified by the rules except those made iteratively. It
commonly involves choosing the direction of the movement (Amazons, Chess,
English Draughts) and move type (capture or two movements in Breakthru). It
does not split decisions that are repeated, such as stopping on a square while
moving in a chosen direction (e.g., rook upwards move). An example of the
resulting semisplit game tree is shown in Fig. 1(right).

$\bullet$  _Shift_ : This component splits square selection when it consists
of more than one decision. It commonly separates the selection of a column and
a row of the board (all games) and also divides movements of some pieces
(e.g., knight – first long and then short hop).

By combining these components, we can build split strategies such as Mod,
ModShift, or ModPlusShift. Additionally, the algorithm optimizes the semisplit
game by removing some indecisive splits (i.e., semimoves that are always the
only available choice) when possible.

### Results

Table 2: Win rates of semisplit agents. The bars show the grand average in timed (upper, red) and fixed (lower, blue) settings. Timed results are also given separately for each game; green, yellow, and red indicate statistically significant _better_ , _same_ , and _worse_ performance, respectively. A game is counted for better performance if the whole 95% confidence interval is above 50%; worse is symmetrical.  Agent | Win rates vs. $\mathbb{O}$X
---|---
$\mathbb{S}^{\text{tree:S-raw}}_{\text{sim:S}}$ @Mod - |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}$ @Mod - |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:O}}$ @Mod - |
$\mathbb{S}^{\text{tree:O}}_{\text{sim:S}}$ @Mod - |
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:S}}$ @Mod - |
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:O}}$ @Mod - |
|
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}$ @ModPlus - |
$\mathbb{S}^{\text{tree:S-raw}}_{\text{sim:S}}$ @ModPlus - |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}$ @ModShift - |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}$ @ModPlusShift - |
$\mathbb{S}^{\text{tree:O}}_{\text{sim:S}}$ @ModPlus - |
Agent | Winrates vs. $\mathbb{O}^{\text{tree:RAVE}}_{\text{sim:MAST}}$ X
$\mathbb{S}^{\text{tree:S-nodal,{RAVE-split}}}_{\text{sim:S,{MAST-split}}}$ @Mod - |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S,{MAST-split}}}$ @Mod - |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S,{MAST-mix}}}$ @Mod - |
$\mathbb{S}^{\text{tree:O,RAVE-join}}_{\text{sim:S,MAST-split}}$ @Mod - |
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:S,{MAST-split}}}$ @Mod - |
Figure 2: The results of
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}\text{@Mod}$ versus
$\mathbb{O}$ for different time limits (circle) and for equivalent states
budgets (square).

Setup and notation. The full technical setup and methodological details are
given in Appendix, Sec. 4. All parameters (e.g., the exploration factor, MAST
and RAVE policies) were set according to the recommendations in the literature
(Finnsson and Björnsson 2010; Sironi and Winands 2016) and keep the same for
every agent. Semisplit agents were tested against the orthodox ones: both the
vanilla MCTS agent (denoted by $\mathbb{O}$) and the enhanced MCTS agent
($\mathbb{O}^{\text{tree:RAVE}}_{\text{sim:MAST}}$) were used as baselines.
Our semisplit agents are denoted by $\mathbb{S}$ with indices describing the
variant: “S” means semisplit design and “O” means orthodox design, which can
be independently used in the MCTS tree or in simulations; “R” is the roll-up
variant. Raw and nodal variants and which variants of MAST and RAVE are used,
if applied, are also indicated. Finally, the used split strategy is denoted
after “@”.

We tested agents in two settings: the _timed setting_ , where agents have the
same amount of time (0.5s) per turn, and the _fixed setting_ , where agents
have a limited number of nodal states to compute. These settings are
correlated by letting the states limit equal to the number of states computed
by the baseline orthodox agent performing within the given time limit. Hence,
the fixed setting is used to observe the impact of semisplit design apart from
efficiency benefits. Note that this is different than the common measurement
with a fixed number of simulations and gives a better correspondence with the
timed setting, as splitting alters simulation length.

Statistics. Tab. 1 shows illustratively how simulation statistics change under
semisplit design. We observe a significant speed-up in terms of the number of
traversed states, and thus of simulations in a given time limit. Obviously,
semisplit design increases the depth of a simulation and reduces the mean
branching factor. When the branching factor is already small, introducing more
splits slows down. The real threshold strongly depends on the game and the
implementation. Note that the mean depth of a simulation measured in nodal
states is also altered, which can independently influence the number of
simulations.

Comparison of agents. Table 2 contains three parts. The first part shows the
results of variants of semisplit MCTS without action-based heuristics and
using the Mod split strategy (one of the least granularity). All variants get
better results than orthodox MCTS, except for
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:O}}\text{@Mod}$. There is no
visible difference between the raw and nodal variants. The efficiency benefits
alone are most significant when the agent uses semisplit in simulations. We
also see an advantage in the fixed setting when semisplit is applied in the
MCTS tree. While $\mathbb{S}^{\text{tree:S-raw}}_{\text{sim:S}}\text{@Mod}$
gets the largest mean, $\mathbb{S}^{\text{tree:O}}_{\text{sim:S}}\text{@Mod}$
is the most robust, winning in ten games and losing only in one. The
particular case of
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:O}}\text{@Mod}$ shows the effect
of semisplit applied only to the expansion phase, which results in a kind of
an unprunning method (Chaslot et al. 2008) – this is beneficial only for
Breakthru, which has a very large branching factor.

The second part shows four representative combinations with split strategies
of a larger granularity. Here, the nodal variant has a slight advantage over
raw. The results follow the same pattern, yet ModPlus seems to be slightly
better than Mod, but ModShift already worsens the results.

The third part shows selected combinations of agents equipped with RAVE and
MAST against $\mathbb{O}^{\text{tree:RAVE}}_{\text{sim:MAST}}$.
$\mathbb{S}^{\text{tree:S-nodal,RAVE-split}}_{\text{sim:S,MAST-
split}}\text{@Mod}$ is the simplest variant; it gives positive results but is
not that strong as previously. Surprisingly, RAVE does not perform that well
here; thus it is better to omit it.
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S,MAST-mix}}\text{@Mod}$ gives
the best results in the fixed setting, but the computation cost of MAST-mix
does not overcome the benefits. The best and most robust agent among tested
ones is the roll-up variant with semisplit simulations and MAST-split.

Fig. 2 shows how the win rate changes for different time limits and in
relation to the fixed setting. In most cases, the results are kept consistent
for different limits, especially in the games where semisplit is clearly
beneficial.

## Conclusions

We have introduced a family of Monte-Carlo Tree Search variants that work on
semimoves – arbitrarily split game moves. The algorithm is based on the idea
of lazy move computation, yet it has many possible variants. We applied split
design for single-action games for the first time and revealed the impact on
agents’ results on a wider set of games (as previously, only Amazons was
tested). Furthermore, we tested different configurations concerning the
selective application in MCTS phases, split granularity, and variants of
action-based heuristics. The developed framework allows testing the effects of
(semi)splitting for more than 600 combined variants of semisplit, action-based
heuristics, and split strategies, for any game described in RBG.

The impact of using semisplit is generally beneficial. First, it greatly
improves search efficiency (typically, 3–5 times more nodal states/sec.).
Moreover, for many games, the playing strength is improved over its orthodox
counterpart, also when both algorithms are capped to the same performance.
Even with general and blind split strategies, we were able to obtain win rates
larger than 70% on about half of the test set (e.g.,
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}\text{@Mod}$ or
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:S,MAST-split}}\text{@Mod}$). For
comparison, the benefits are larger than those from adding action-based
heuristics to the vanilla orthodox agent (the mean win rate of
$\mathbb{O}^{\text{tree:RAVE}}_{\text{sim:MAST}}$ vs. $\mathbb{O}$ on our test
set is 53% in timed and 65% in fixed setting).

More detailed results show that using semisplit in simulations gives a large
efficiency boost and generally is not harmful in terms of their quality. This
may be useful also apart from game playing, as simulations are applied to many
single-player problems (Wang et al. 2020). On the other hand, using semisplit
in the MCTS tree gives some benefits in the quality of iterations, yet it is
riskier, as sometimes it is consistently harmful (e.g., The Mill Game).
However, on average, almost none of the tested variants is worse in the fixed
setting than the orthodox baseline.

The conducted research can be seen as pioneering, as there are many directions
for future research, e.g.:
$\bullet$ There should be developed methods for choosing the most suitable
semisplit variant and split strategy for a given game.
$\bullet$ The used parameters were the same for both agent types and were
tuned rather for orthodox agents according to the literature. This indicates
that after a tuning, semisplit should achieve even better results.
$\bullet$ We focused on the practical aspect, yet there are interesting
theoretical questions as to how strongly splitting the game can distort the
agent’s results, and how hard is the problem? to determine whether splitting
will be beneficial.
$\bullet$ Semisplit can be combined with prior knowledge (Gelly and Silver
2007) or neural networks. It can reduce action space and improve efficiency,
especially when simulations are combined with neural networks (Cotarelo et al.
2021).

## Acknowledgements

This work was supported in part by the National Science Centre, Poland under
project number 2021/41/B/ST6/03691 (Jakub Kowalski, Marek Szykuła).

## References

  * Baier and Winands (2018) Baier, H.; and Winands, M. H. M. 2018.  MCTS-minimax hybrids with state evaluations.  _JAIR_ , 62: 193–231.
  * Browne et al. (2012) Browne, C. B.; Powley, E.; Whitehouse, D.; Lucas, S. M.; Cowling, P. I.; Rohlfshagen, P.; Tavener, S.; Perez, D.; Samothrakis, S.; and Colton, S. 2012\.  A Survey of Monte Carlo Tree Search Methods.  _IEEE TCIAIG_ , 4(1): 1–43.
  * Cazenave (2015) Cazenave, T. 2015.  Generalized rapid action value estimation.  In _IJCAI_ , 754–760.
  * Chaslot et al. (2008) Chaslot, G.; Winands, M. H. M.; van den Herik, H. J.; Uiterwijk, J.; and Bouzy, B. 2008.  Progressive strategies for Monte-Carlo tree search.  _New Mathematics and Natural Computation_ , 4(3): 343–357.
  * Childs, Brodeur, and Kocsis (2008) Childs, B. E.; Brodeur, J. H.; and Kocsis, L. 2008.  Transpositions and move groups in Monte Carlo tree search.  In _IEEE Symposium On Computational Intelligence and Games_ , 389–395.
  * Cotarelo et al. (2021) Cotarelo, A.; García-Díaz, V.; Núñez-Valdez, E. R.; González García, C.; Gómez, A.; and Chun-Wei Lin, J. 2021.  Improving Monte Carlo Tree Search with Artificial Neural Networks without Heuristics.  _Applied Sciences_ , 11(5).
  * Finnsson and Björnsson (2008) Finnsson, H.; and Björnsson, Y. 2008.  Simulation-Based Approach to General Game Playing.  In _AAAI_ , volume 8, 259–264.
  * Finnsson and Björnsson (2010) Finnsson, H.; and Björnsson, Y. 2010.  Learning Simulation Control in General Game Playing Agents.  In _AAAI_ , 954–959.
  * Fotland (2006) Fotland, D. 2006.  Building a World-Champion Arimaa Program.  In _Computers and Games_ , volume 3846 of _LNCS_ , 175–186.
  * Geißer, Speck, and Keller (2020) Geißer, F.; Speck, D.; and Keller, T. 2020.  Trial-based Heuristic Tree Search for MDPs with Factored Action Spaces.  In _Thirteenth Annual Symposium on Combinatorial Search_.
  * Gelly and Silver (2007) Gelly, S.; and Silver, D. 2007.  Combining online and offline knowledge in UCT.  In _Proceedings of the 24th International Conference on Machine Learning_ , 273–280.
  * Gelly and Silver (2011) Gelly, S.; and Silver, D. 2011.  Monte-Carlo tree search and rapid action value estimation in computer Go.  _Artificial Intelligence_ , 175(11): 1856–1875.
  * Genesereth, Love, and Pell (2005) Genesereth, M.; Love, N.; and Pell, B. 2005.  General Game Playing: Overview of the AAAI Competition.  _AI Magazine_ , 26: 62–72.
  * Goldwaser and Thielscher (2020) Goldwaser, A.; and Thielscher, M. 2020.  Deep Reinforcement Learning for General Game Playing.  In _AAAI_.
  * Haworth (2003) Haworth, G. M. C. 2003.  Self-play: statistical significance.  _ICGA journal_ , 26(2): 115–118.
  * Hufschmitt, Vittaut, and Jouandeau (2019) Hufschmitt, A.; Vittaut, J.-N.; and Jouandeau, N. 2019.  Exploiting Game Decompositions in Monte Carlo Tree Search.  In _Advances in Computer Games_ , 106–118. Springer.
  * Justesen et al. (2017) Justesen, N.; Mahlmann, T.; Risi, S.; and Togelius, J. 2017.  Playing Multiaction Adversarial Games: Online Evolutionary Planning Versus Tree Search.  _IEEE Transactions on Games_ , 10(3): 281–291.
  * Kaiser and Stafiniak (2011) Kaiser, Ł.; and Stafiniak, Ł. 2011.  First-Order Logic with Counting for General Game Playing.  In _AAAI_ , 791–796.
  * Kloetzer, Iida, and Bouzy (2007) Kloetzer, J.; Iida, H.; and Bouzy, B. 2007.  The Monte-Carlo approach in Amazons.  In _Proceedings of the Computer Games Workshop_ , 185–192.
  * Kocsis and Szepesvári (2006) Kocsis, L.; and Szepesvári, C. 2006.  Bandit Based Monte-carlo Planning.  In _European Conference on Machine Learning_ , 282–293.
  * Kowalski et al. (2020) Kowalski, J.; Miernik, R.; Mika, M.; Pawlik, W.; Sutowicz, J.; Szykuła, M.; and Tkaczyk, A. 2020.  Efficient Reasoning in Regular Boardgames.  In _IEEE Conference on Games_ , 455–462.
  * Kowalski et al. (2021) Kowalski, J.; Mika, M.; Pawlik, W.; Sutowicz, J.; and Szykuła, M. 2021.  Regular Boardgames – source code (version 1.3).  https://github.com/marekesz/rbg.
  * Kowalski et al. (2019) Kowalski, J.; Mika, M.; Sutowicz, J.; and Szykuła, M. 2019.  Regular Boardgames.  In _AAAI_ , 1699–1706.  https://arxiv.org/abs/1706.02462.
  * Lemire (2019) Lemire, D. 2019.  Fast random integer generation in an interval.  _ACM Transactions on Modeling and Computer Simulation (TOMACS)_ , 29(1): 1–12.
  * Love et al. (2006) Love, N.; Hinrichs, T.; Haley, D.; Schkufza, E.; and Genesereth, M. 2006.  General Game Playing: Game Description Language Specification.  Technical report, Stanford Logic Group.
  * Mnih et al. (2015) Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M. G.; Graves, A.; Riedmiller, M.; Fidjeland, A. K.; Ostrovski, G.; et al. 2015\.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540): 529–533.
  * Ontañón (2017) Ontañón, S. 2017.  Combinatorial Multi-armed Bandits for Real-Time Strategy Games.  _J. Artif. Intell. Res._ , 58: 665–702.
  * Perez et al. (2013) Perez, D.; Samothrakis, S.; Lucas, S.; and Rohlfshagen, P. 2013.  Rolling horizon evolution versus tree search for navigation in single-player real-time games.  In _GECCO_ , 351–358.
  * Perez et al. (2016) Perez, D.; Samothrakis, S.; Togelius, J.; Schaul, T.; and Lucas, S. M. 2016.  General Video Game AI: Competition, Challenges and Opportunities.  In _AAAI_ , 4335–4337.
  * Piette et al. (2020) Piette, E.; Soemers, D. J.; Stephenson, M.; Sironi, C. F.; Winands, M. H. M.; and Browne, C. 2020.  Ludii - The ludemic general game system.  In _ECAI 2020_ , 411 – 418.
  * Powley, Whitehouse, and Cowling (2013) Powley, E.; Whitehouse, D.; and Cowling, P. 2013.  Bandits all the way down: UCB1 as a simulation policy in Monte Carlo Tree Search.  In _Proc. IEEE Conf. Comput. Intell. Games_ , 1–8.
  * Rasmusen (2007) Rasmusen, E. 2007.  _Games and Information: An Introduction to Game Theory_.  Blackwell, 4th ed.
  * Roelofs (2017) Roelofs, G.-J. 2017.  Pitfalls and Solutions When Using Monte Carlo Tree Search for Strategy and Tactical Games.  _Game AI Pro 3: Collected Wisdom of Game AI Professionals_ , 343––354.
  * Saito et al. (2007) Saito, J.-T.; Winands, M. H. M.; Uiterwijk, J. W.; and van den Herik, H. J. 2007\.  Grouping nodes for Monte-Carlo tree search.  In _Computer Games Workshop_ , 276–283.
  * Silver et al. (2018) Silver, D.; Hubert, T.; Schrittwieser, J.; Antonoglou, I.; Lai, M.; Guez, A.; Lanctot, M.; Sifre, L.; Kumaran, D.; Graepel, T.; et al. 2018.  A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.  _Science_ , 362(6419): 1140–1144.
  * Sironi and Winands (2016) Sironi, C. F.; and Winands, M. H. M. 2016.  Comparison of rapid action value estimation variants for general game playing.  In _2016 IEEE Conference on Computational Intelligence and Games (CIG)_ , 1–8.
  * Świechowski et al. (2021) Świechowski, M.; Godlewski, K.; Sawicki, B.; and Mańdziuk, J. 2021.  Monte Carlo Tree Search: A Review of Recent Modifications and Applications.  _arXiv preprint arXiv:2103.04931_.
  * Tak, Winands, and Björnsson (2012) Tak, M. J.; Winands, M. H. M.; and Björnsson, Y. 2012.  N-grams and the last-good-reply policy applied in general game playing.  _IEEE Transactions on Computational Intelligence and AI in Games_ , 4(2): 73–83.
  * Tak, Winands, and Björnsson (2014) Tak, M. J. W.; Winands, M. H. M.; and Björnsson, Y. 2014.  Decaying simulation strategies.  _IEEE Transactions on Computational Intelligence and AI in Games_ , 6(4): 395–406.
  * Van Eyck and Müller (2011) Van Eyck, G.; and Müller, M. 2011.  Revisiting move groups in monte-carlo tree search.  In _Advances in Computer Games_ , 13–23.
  * Wang et al. (2020) Wang, H.; Preuss, M.; Emmerich, M.; and Plaat, A. 2020.  Tackling Morpion Solitaire with AlphaZero-like Ranked Reward Reinforcement Learning.  In _2020 22nd International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)_ , 149–152. IEEE.
  * Winands (2017) Winands, M. H. M. 2017.  Monte-Carlo Tree Search in Board Games.  In _Handbook of Digital Games and Entertainment Technologies_ , 47–76.

## Appendix

##  1 Details of Semisplit MCTS

Alg. 2 shows the expansion function in the nodal variant, which is called in
Alg. 1 line 21 in the main text.

Alg. 3 shows the roll-up function, which checks and removes a given node of an
intermediate (non-nodal) state. It is called during the backpropagation phase
for all MCTS nodes involved in the iteration, in bottom-up order (Alg. 5 line
15).

1:$v$ – leaf node in MCTS tree

2:$a_{1}$ – selected untried semimove

3:function ExpandNodal($v,a_{1}$)

4: $s\leftarrow v.\textsc{State}()$

5: $m\leftarrow\textsc{SemisplitRandomMove}(s.\textsc{Apply}(a_{1}))$

6: if $m=\mathbf{None}$ then

7: $v.\textsc{RemoveSemimove}(a_{1})$

8: return $\mathbf{None}$

9: $m^{\prime}\leftarrow\textsc{Concatenate}(a_{1},m)$

10: for all $a\in m^{\prime}$ do $\triangleright$ For all semimoves $a$ in
$m^{\prime}$ in the order

11: $s\leftarrow s.\textsc{Apply}(a)$

12: $c\leftarrow\textsc{CreateNode}(s)$

13: $v.\textsc{AddNode}(c,a)$

14: $v\leftarrow c$

15:
$\mathit{scores}\leftarrow\textsc{SemisplitSimulation}(v.\textsc{State}())$

16: return $(v,\mathit{scores})$

Algorithm 2 The nodal expansion variant.

1:$v$ – node (of intermediate state) to roll-up

2:function RollUp($v$)

3: if $v.\textsc{FullyExpanded}()$ then

4: $\mathit{childrenCount}\leftarrow v.\textsc{Children}().\textsc{Length}()$

5: if $v.\mathit{iterationCount}\geq\mathit{childrenCount}$ then

6: $v^{\prime}\leftarrow v.\textsc{Parent}()$

7: $m\leftarrow v^{\prime}.\textsc{Submove}(v)$ $\triangleright$ Get the
submove from $v^{\prime}$ to $v$

8: $v^{\prime}.\textsc{RemoveChild}(v)$

9: for all $(c,a)\in v.\textsc{Children}()$ do

10: $m^{\prime}\leftarrow\textsc{Concatenate}(m,a)$

11: $v^{\prime}.\textsc{AddChild}(c,m^{\prime})$

12: $v^{\prime}.\mathit{AMAF}[m^{\prime}]\leftarrow c.\mathit{AMAF}[a]$
$\triangleright$ If RAVE is used

Algorithm 3 The roll-up procedure.

###  1.1 MAST and RAVE

Commonly used general knowledge-free enhancements of MCTS are online-learning
heuristics, which estimate the values of moves by gathering statistics. Two
general methods are Move-Average Sampling Technique (MAST) and Rapid Action
Value Estimation (RAVE) (Finnsson and Björnsson 2008; Gelly and Silver 2011;
Winands 2017). For both techniques, there are many policies proposed that
differ in detail.

MAST globally stores for every move the average result of all iterations
(samples) involving this move. Those values are updated after each iteration,
and the score of each move is updated as many times as the move was applied in
the iteration. The statistics are stored for each player separately. They are
later used in the simulation and (optionally) expansion phases in place of the
random selection. For each move from the set of all legal moves at some state,
MAST defines the probability that this move will be selected. This probability
distribution is defined depending on a particular policy, e.g., Gibb’s
distribution (Finnsson and Björnsson 2008), Roulette wheel (Powley,
Whitehouse, and Cowling 2013) or $\epsilon$-greedy (Tak, Winands, and
Björnsson 2012). According to the previous research, $\epsilon$-greedy is
universally considered to be the best policy (Powley, Whitehouse, and Cowling
2013; Tak, Winands, and Björnsson 2012). It is also common to assume that if
the move was not tried any time before, then its score is the maximum
available reward, so it will be preferred to play as soon as possible.

An improvement for MAST is the _decaying_ technique (Tak, Winands, and
Björnsson 2014). It comes from the insight that certain moves that are good
globally in the game may not be so strong in latter phases. In other words,
that the global average may be not equally adequate for all stages (subgames)
of the game. Decaying means that the weights of all the collected samples are
multiplied by the _decay factor_ , hence new samples gathered will have more
impact on the average score. A few methods of decaying are known and proposed
in (Tak, Winands, and Björnsson 2014): _move decay_ takes place after the
effective move is applied in the game, _batch decay_ applies decaying after a
fixed number of simulations, and _simulation decay_ applies decaying after
each played move (of either the agent or the opponent). The last option was
considered to be possibly the best.

Monte Carlo Tree Search needs many iterations to gather enough samples to
differentiate the most promising moves. At the beginning, many choices are
made randomly. RAVE tries to shorten this phase by storing additional
statistics in nodes. Similarly to MAST, it stores the average reward for
moves, but locally in MCTS nodes. These statistics are called _All Moves As
First_ (_AMAF_). For each node, each child with move $m$ stores the average
score (for the player of the node) from all iterations that passed through the
node and that include $m$ played at the node or at any place below. This is in
contrast with the regular statistic of $m$ in UCT, which is gathered only from
iterations that play $m$ at the current node. In this way, AMAF collects much
more samples, which are less reliable, however.

The AMAF statistics are used to bias the choice in the selection phase by
modifying the UCB formula. The priority for each node is calculated as the
weighted mean of the regular average score and the average stored for all
simulations. There are many different formulas to calculate such weights
(Cazenave 2015; Finnsson and Björnsson 2008; Gelly and Silver 2011; Sironi and
Winands 2016). The general rule is that for fewer iterations the statistics
gathered by RAVE are more relevant due to a larger number of samples than the
MCTS score, but then they lose significance as they do not distinguish between
the situations where moves are played.

1:$\mathit{semimoves}$ – list of semimoves to choose from

2:$\mathit{player}$ – current player

3:function ChooseSemimoveWithMAST($\mathit{semimoves},\mathit{player}$)

4: if $\textsc{RandomRealNumber}(0,1)\geq\epsilon$ then

5:
$\mathit{bestSemimoves}=\operatorname*{arg\,max}_{m\in\mathit{semimoves}}(\mathit{MASTstatistics}[\mathit{player}].\textsc{Score}(m))$

6: return $\textsc{RandomElement}(\mathit{bestSemimoves})$

7: else

8: return $\textsc{RandomElement}(\mathit{semimoves})$

9:$s$ – game state

10:function SemisplitMASTMove($s$)

11: $semimoves\leftarrow s.\textsc{GetAllSemimoves}()$

12: while $\mathbf{not}\>\mathit{semimoves}.\textsc{Empty}()$ do

13:
$a\leftarrow\textsc{ChooseSemimoveWithMAST}(\mathit{semimoves},s.\textsc{Player}())$

14: $s^{\prime}\leftarrow s.\textsc{Apply}(a)$

15: if $s.\textsc{IsNodal}()$ then return $a$

16: $m\leftarrow\textsc{SemisplitMASTMove}(s^{\prime})$

17: if $m\neq\mathbf{None}$ then return $\textsc{Concatenate}(a,m)$

18: return $\mathbf{None}$

Algorithm 4 MAST working on semimoves.

Both MAST and RAVE can be adapted to semisplit game trees and work in the pure
semisplit design in a straightforward way, i.e., in the same manner as in the
orthodox design. Alg. 4 shows the modified move selection in the simulation
phase, where a move is selected with the $\epsilon$-greedy policy. We use
SemisplitMASTMove in place of SemimoveRandomMove that is called in Alg. 1,
line 3. If statistics are used to select move in expansion phase, then line 20
of Alg. 1 is also replaced with $a_{1}\leftarrow$
ChooseSemimoveWithMAST($v.\textsc{UntriedSemimoves}(),v.\textsc{Player}()$).
RAVE just modifies the UCT selection (Alg. 1, line 18) and backpropagation
(Alg. 5), and includes transferring AMAF values in the case of the roll-up
variant (Alg. 3, line 11).

1:$v$ – last node of iteration in MCTS tree

2:$\mathit{scores}$ – final scores for each player of iteration

3:$\mathit{appliedSubmoves}$ – list of submoves applied in simulation phase

4:function Backpropagation($v,\mathit{scores},\mathit{appliedSubmoves}$)

5: $\mathit{scores}\leftarrow\mathit{state}.\textsc{Scores}()$

6: for all $(m,\mathit{player})\in\mathit{appliedSubmoves}$ do
$\triangleright$ with MAST

7:
$\mathit{MASTstatistics}[\mathit{player}].\textsc{Update}(m,\mathit{scores})$
$\triangleright$ with MAST

8: while $v\neq\textsc{TreeRoot}()$ do

9: $v.\mathit{scoreSum}\leftarrow
v.\mathit{scoreSum}+\mathit{scores}[v.\mathit{Player}]$

10: $v.\mathit{iterations}\leftarrow v.\mathit{iterations}+1$

11: $v^{\prime}\leftarrow v.\textsc{Parent}()$

12: $m\leftarrow v^{\prime}.\textsc{Submove}(v)$ $\triangleright$ with MAST or
RAVE

13:
$\mathit{MASTstatistics}.\textsc{Update}(m,\mathit{scores},v^{\prime}.\textsc{Player}())$
$\triangleright$ with MAST

14:
$\mathit{appliedSubmoves}[v^{\prime}.\textsc{Player}()].\textsc{Append}(m)$
$\triangleright$ with RAVE

15: for all $(c,a)\in v.\textsc{Children}()$ do $\triangleright$ with RAVE

16: if $a\in\mathit{appliedSubmoves[v^{\prime}.\textsc{Player}()]}$ then
$\triangleright$ with RAVE

17:
$v^{\prime}.\mathit{AMAF}[a].\textsc{Update}(\mathit{score}[v^{\prime}.\textsc{Player}()])$
$\triangleright$ with RAVE

18: RollUp($v$) $\triangleright$ with roll-up

19: $v\leftarrow v^{\prime}$

20:
$\textsc{TreeRoot}().\mathit{iterations}\leftarrow\textsc{TreeRoot}().\mathit{iterations}+1$

Algorithm 5 Variants of backpropagation, depending on whether MAST, RAVE, or
roll-up is used, respectively.

###  1.2 Available Combinations

Table 3: Available combinations of the variants of MCTS and action-based
heuristics.

MCTS variant | Standard | Split | Join | Context
---|---|---|---|---
Tree | Sim. | MAST | RAVE | MAST | RAVE | MAST | RAVE | MAST | RAVE
orthodox | orthodox | ✓J | ✓J | ✓ | – | ✓ | ✓ | ~~✓ J~~ | ~~✓ J~~
orthodox | semisplit | – | – | ✓ | – | – | ✓ | ✓ | ~~✓ J~~
semisplit | orthodox | – | – | ✓ | ✓ | ✓* | – | ✓ | ✓
semisplit | semisplit | ✓S | ✓S | ✓ | ✓ | – | – | ✓ | ✓
roll-up | orthodox | – | – | ✓ | – | ✓* | – | ✓ | ✓
roll-up | semisplit | – | – | ✓ | – | – | – | ✓ | ✓

S – equivalent to _split_ variant

J – equivalent to _join_ variant

~~✓~~ – equivalent to another variant but less efficient, so this variant is
useless

* – works without using MAST in the expansion phase

Table 3 summarizes possible variants of action-based heuristics depending on
the MCTS semisplit combination. As a general rule, a variant is available if
it gathers statistics required for the main MCTS phase where it is used (i.e.,
simulation phase for MAST and tree phase for RAVE).

The standard variants represent a straightforward application of the
heuristics, i.e. when they operate exactly on the same (sub)moves as computed
in MCTS. They are available only when the domain of moves is the same in both
the MCTS tree phases and the simulation phase, and they are always equivalent
either to join or split variants. Hence, we use the latter naming.

MAST-split can work in all cases, as it can divide a move or its factor into a
set of semimoves and supports evaluation of such a factor basing on the
statistics of semimoves. RAVE-split works only when the MCTS tree uses
semisplit, as in other cases it could not easily evaluate submoves that are
not single semimoves (due to technical difficulties and only small benefits
expected, we do not propose such a solution). MAST-join and RAVE-join can work
whenever the simulation phase and the tree phase, respectively, use the
orthodox design. MAST-join can work when the MCTS tree phase is not orthodox,
but then it is not applied for the expansion phase. Finally, MAST-context and
RAVE-context can work in all cases, as they gather all statistics that may be
required. However, in some orthodox cases, they are fully equivalent to the
corresponding join variants and thus are inefficient due to gathering some
useless statistics (i.e., for semimoves). Of course, the mix variants are
available precisely in the combinations where both the split and the context
variants are available, and where the context variant is non-optimal, they can
also use the join variant instead (i.e., in the case of orthodox MCTS).

##  2 Implementation in Regular Boardgames

To test the concept in a practical setting and explain more issues in the
context of a particular representation, we applied it to the Regular
Boardgames (RBG) game description language. It offers a simple way of
partitioning a move, and furthermore, we can get significant efficiency
benefits from it, resembling those that could be gained from a manual
implementation of the reasoner. Using a GGP language also allows us to split
games in a more systematic way, without the need to take manual split
decisions for each game.

###  2.1 Regular Boardgames

We give a short description of the language, which is necessary for
understanding how exactly split strategies divide moves. For the full language
definition, we refer to (Kowalski et al. 2019).

To describe a game in RBG we need to define a _board_ , _variables_ , _player
roles_ , and _rules_. The _game state_ contains a placement of pieces on the
board, values of the variables, information who is the current player, the
current position (the one we are “looking at”) on the board, and the current
index (position) in the rules. The _board_ is a directed graph with labeled
edges, called _directions_. (Thus, as any such graph is accepted, it is much
more general than what is usually understood as a “board”.) The current
player, in his turn, performs a sequence of elementary _actions_. When applied
sequentially, they modify the game state in a specific way. An action is
_legal_ when it is: _valid_ for the current game state when it is applied; and
permitted by the rules. There are seven distinct types of actions:

  1. 1.

_Shift_ , e.g., left or up. Changes the current position (the one we are
looking at) on the board following the specified direction. The action is
invalid when the edge specified is not defined in the board graph.

  2. 2.

_On_ , e.g., {whiteQueen}. Checks if the specified piece occupies the current
position on the board. Does not modify the game state.

  3. 3.

_Off_ , e.g., [whiteQueen]. Puts the specified piece at the current position
on the board. The action is always valid and overrides the previous content of
the square.

  4. 4.

_Comparison_ , e.g., {$ turn==100}. Compares two arithmetic expressions
involving variables.

  5. 5.

_Assignment_ , e.g., [$ turn=turn+1]. Assigns the value of an arithmetic
expression to a given variable.

  6. 6.

_Switch_ , e.g.,  –${>}$white. Ends a move and changes the current player to
the one specified.

  7. 7.

_Pattern_ , e.g., {? left up}. A conditional valid only if there exists a
legal sequence of actions under the specified rules. In this example, the
action is valid if from the current square there is a path going on two edges
labeled by left and up.

A _move_ is defined as a sequence of actions ending with a switch.

###### Example 2

This sequence of actions originates from Amazons. It defines a move where a
white queen is moving two squares up and then it shoots an arrow one square
right.

⬇

{wQueen} [empty] up up [wQueen] right [arrow] –${>}$black

A _move_ is the subsequence of (indexed) actions (offs, assignments, and
switches), paired with the positions in rules (i.e., regular expression) where
they are applied. These are precisely the actions that modify the game state,
not counting the changes in the board position and the rules index. Thus, the
move given in the example above has length $4$ (caused by three offs and one
switch).

A playout ends when the current player has no legal moves. Then, each player
has assigned a _score_ , which is a value stored in a dedicated variable
(named the same as the player’s role). The rules are encoded as a regular
expression over the alphabet of the actions defined above. The language
defined by this expression encodes a game tree by containing all potentially
legal sequences of actions. To simplify the encoding of the regular
expression, RBG descriptions may contain C-like macros that are instantiated
for given parameters.

###  2.2 Split Strategies

The split strategies directly refer to the elements of the language. The Mod
component ends a semimove at every Off and Switch. The Plus component
additionally ends a semimove after entering an alternative of regular
expressions. This, however, does not break consistent subexpressions with
shifts only, which define the selection of a square. The Shift component
additionally provides a split point within such subexpressions after entering
an alternative (similarly as Plus).

Split points in the generated game code rules are indicated with a dot (.),
whereas an Off and a Switch is always assumed to be a split point when
semisplit is used. Patterns are never split.

#### Legality Check

After the initial placement, we check whether the introduced split points do
not potentially cause duplication of legal moves, i.e., whether we obtain a
proper semisplit game. It could happen that two distinct semimoves lead to the
same legal move in the original rules. For example, in (left* . + right* .)
[e], if we stay at the same square, we could choose either the left branch or
the right branch and end at different dots, but in the original rules the
square of $[e]$ is the same, so it will lead to the same legal move.

Such illegal dots are postponed to the right until they become safe. Thus, the
above example will be turned into (left* + right* ).[e].

#### Removing Indecisive Splits

The third phase is optimization. We try to remove as many indecisive semimoves
as possible. An indecisive semimove is when it is the only outgoing semimove
from a state. In the above example, if we use the Mod component, the dot can
be removed, as $[e]$ also ends a semimove.

Sometimes, we could remove either previous or the latter split point, but not
both. In this case, we remove split points starting from the right, thus
making the first semimove shorter. When it is impossible, because we cannot
remove split points related to Offs and Switches when using Mod, we then
remove other split points on the left.

Of course, not all indecisive semimoves are removed in this way, as whether a
semimove is indecisive depends on the whole rules and is a computationally
hard problem in general.

###  2.3 Example of Amazons

A complete example of game Amazons is given in Fig. 2. Its underlying
nondeterministic finite automaton, processed by the game compiler, is shown in
Fig.3. Split points introduced by each of the Mod, Plus, and Shift components
are shown. A semimove ends when the current index in the rules reaches such a
point.

At the beginning of the game description (Fig. 2, lines 1–14), we define the
players, pieces, variables, and the game board. For the player, we also
provide their maximal achievable scores. In our example we need four pieces: e
for encoding an empty square, w for a white queen, b for a black one, and x
for an arrow. There are no variables here, as the variables for players
containing their current scores are created automatically. To define the board
graph with its initial state, we use a predefined helper macro. We create a
rectangular board with four possible movement directions.

Then, we introduce some helpful, user-defined macros to simplify further game
definition. anySquare is responsible for changing the current position to any
square on board by first jumping an arbitrary number of squares vertically and
then horizontally. Split strategies with the Shift component insert a split
point after the first such decision, whereas the second is skipped as it ends
the shift subexpression. The goal of directedShift is to encode movement in
direction dir given as a parameter as long as the squares on the way are
empty. It requires that at least one step has to be made. queenShift encodes
all possible queen-like moves as an alternative to directed shifts. For
diagonal movements, two consecutive directions are passed as a single macro
argument.

The turn macro (lines 23–28), describes a single turn for player me, whose
queen pieces are encoded as piece. First, we switch the player to ourselves.
Then, we switch the current square to any that contains our queen. Next, we
pick up the queen – putting down the “empty” piece, which introduces split
under the Mod component. Now, we select a direction, which forms a separate
semimove under the Plus component. Then, we move to the desired square and put
down the queen (the second Mod split point). This procedure is repeated for an
arrow, as its placement follows the same rules as for moving a queen. The
switch action  –${>}{>}$ gives control to the manager (special role named
_keeper_). Keeper moves are never split; if there are split points inserted,
they are ignored. A keeper switch indicates that the player has no more
decisions to make, and the remaining steps are deterministic in this sense.
These steps are: putting down the arrow and setting the winning score for the
last player. When the playout ends because the current player has no legal
moves, this stage will not be reached; thus the previous current player will
win the game. Finally, we can define the macro for the game rules. We encode
the overall rules as a repetition of the sequence of the white and the black
player turns (line 29).

⬇

1#players = white(100), black(100)

2#pieces = e, w, b, x

3#variables = // no variables

4#board = rectangle(up,down,left,right,

5 [e, e, e, b, e, e, b, e, e, e]

6 [e, e, e, e, e, e, e, e, e, e]

7 [e, e, e, e, e, e, e, e, e, e]

8 [b, e, e, e, e, e, e, e, e, b]

9 [e, e, e, e, e, e, e, e, e, e]

10 [e, e, e, e, e, e, e, e, e, e]

11 [w, e, e, e, e, e, e, e, e, w]

12 [e, e, e, e, e, e, e, e, e, e]

13 [e, e, e, e, e, e, e, e, e, e]

14 [e, e, e, w, e, e, w, e, e, e])

15#anySquare = ((up* + down*)(left* + right*))

16#directedShift(dir) = (dir {e} (dir {e})*)

17#queenShift = (

18 directedShift(up left) + directedShift(up) +

19 directedShift(up right) + directedShift(left) +

20 directedShift(right) + directedShift(down left) +

21 directedShift(down) + directedShift(down right)

22 )

23#turn(piece; me; opp) = (

24 –${>}$me anySquare {piece} [e]

25 queenShift [piece]

26 queenShift

27 –${>}{>}$ [x] [$ me=100, opp=0]

28 )

29#rules = (turn(w; white; black) turn(b; black; white))*

Figure 2: RBG encoding of Amazons (non-split).

ShiftMod…Mod$\mathrm{queenShift}$$\mathrm{queenShift}$PlusPlus$\mathrm{turn(w;white;black)}$$\mathrm{turn(b;black;white)}$$\mathit{{\to}white}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{\\{w\\}}$$\mathit{[e]}$$\mathit{[w]}$$\mathit{\to\mathrel{\mkern-13.0mu}\to}$$\mathit{[x]}$$\mathit{[\$white{=}100]}$$\mathit{[\$black{=}0]}$$\mathit{{\to}black}$$\mathit{{\to}white}$$\mathit{\varepsilon}$$\mathit{up}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{down}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{left}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{right}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{up}$$\mathit{left}$$\mathit{\\{e\\}}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{up}$$\mathit{left}$$\mathit{\\{e\\}}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{up}$$\mathit{\\{e\\}}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$$\mathit{up}$$\mathit{\\{e\\}}$$\mathit{\varepsilon}$$\mathit{\varepsilon}$
Figure 3: NFA represented by the Amazons description from Fig. 2.

##  3 Description of Games in the Test Set

We describe the rules of all games used in our experiments and how they are
split according to the three considered components of our split strategies.
All these games are two-player, perfect-information, and deterministic.

For all games, the Shift component separates choosing a column (first) and a
row (second) when selecting any square, which usually takes place at the
beginning of a turn. All the strategies sometimes introduce some indecisive
semimoves, which we do not describe in detail. They can slightly affect
efficiency, but generally are irrelevant for the quality of MCTS iterations.
They come from the fact that the splitting algorithm cannot know whether a
split point is decisive, as it only splits moves basing on syntactic game
rules.

For each game, it is given the name of the game file in the provided Code
Appendix.

_$\bullet$ Amazons_ (amazons.rbg): It is played on a $10\times 10$ chessboard.
The initial position contains four pieces called _amazons_ for each player.
The move consists of shifting an own amazon, which moves as a Chess queen, to
a valid empty square, and then, from its final position, spawning a new piece
called an arrow that has to be shifted under the same conditions. Arrows block
the squares where they are put for the remaining part of the play. Neither an
amazon nor an arrow can be shifted through a square with an arrow or another
amazon. No captures are possible, and the player without a legal move loses.
Draws are impossible.

Amazons is considered to be multi-action because moving a queen and shooting
an arrow can be performed in separate moves. In particular, a moved queen
always has a possibility to shot an arrow; thus this would yield a proper
split-equivalent game.

The Mod component divides a move into three choices ending by modifying a
square: taking an amazon, putting it on a destination square, and putting an
arrow. The Plus component additionally separates the choice of the eight
directions for both an amazon and an arrow.

_$\bullet$ Breakthrough_ (breakthrough.rbg): The game is played on the
standard chessboard, starting with two rows of pawns on each side of the
board. Pawns can capture diagonally and go forward either vertically or
diagonally. The goal of the game is to reach the opposite row. Draws are
impossible.

The Mod component simply separates piece selection and its destination square
(maximum three possibilities). Here, the Plus component does not introduce any
additional decisive semimoves.

_$\bullet$ Breakthru_ (breakthru.rbg): This is a game of evasion or capture,
played on $11\times 11$ board featuring unevenly matched teams with different
objectives. In the initial phase, the _gold_ player puts his pieces in the
central part of the board with the goal of escorting a distinguished piece
called flagship to the perimeter of the board. The other _silver_ player puts
his ships on predefined positions in the outward part of the board and tries
to capture the flagship. In one turn, a player may perform two moves of a
standard unit or one move with a flagship (both behave like Chess rook without
capture), or one capture. When capturing, a piece behaves like a Chess bishop
limited to one square.

The Mod component works as usual, yet the player already decides together with
grabbing the first piece whether to capture or not. With the Plus component,
this decision of capturing takes place separately after selecting the square,
since there is an alternative on these choices. Furthermore, choosing one of
the four directions is also performed separately. With Shift, besides separate
selection of a column and a row, a diagonal shift is also split into up-down
and left-right decisions. The initial phase of the gold player’s setup is
split only under the Shift component.

_$\bullet$ Chess_ (chess.rbg): The Chess version with the fifty-move rule for
a draw. It contains all the standard rules (check, castling, en-passant,
etc.), except the threefold position repetition checking.

Chess follows the standard pattern for splitting. Thus, the Mod component
separates choosing the piece and its destination square. There are two
exceptions for rare moves: castling, which is decided after picking the king;
and en-passant, which is decided at the beginning of a move if available. An
additional notable efficiency improvement comes from postponed verification of
whether the move is legal, i.e., whether after the move, the king is not under
check. With Plus, picking a direction for Bishop, Rook, and Queen is also
separated, together with castling direction. Shift also divides King and
Knight moves (e.g., a knight first decides about the 2-squares hop direction,
then the 1-square hop).

_$\bullet$ Chess without check_ (chess_kingCapture.rbg): This is a simplified
version of Chess, commonly used in GGP (its GDL counterpart is called
speedchess). There is no check, i.e., it is ignored in all cases, and the game
ends with capturing the king. Strategically, it is the same as Chess, except
that there is no stalemate.

Splitting is the same as for Chess, but of course, we do not have any
postponed check checking.

_$\bullet$ English draughts_ (englishDraughts.rbg): It is one of the most
popular versions of draughts played on an $8\times 8$ board. A crowned man
(promoted after reaching the opposite row) can move one square both forward or
backward. Performing capturing moves are mandatory whenever possible, but the
player is not forced to perform a longest sequence of captures as in other
draughts versions. The game ends in a draw after 20 moves without capturing or
moving a (non-crowned) man.

The Mod component divides a capture into picking a piece, removing the
opponent (indecisive semimove), and putting a piece. Similarly, a non-
capturing move is separated into two semimoves. The Plus component
additionally separates picking a direction, but, as this already determines
the destination square, this is only an indecisive semimove. Shift works as
usual, yet due to a different shape of the board (black squares only), columns
and rows are perceived as diagonals.

_$\bullet$ Fox and Hounds_ (foxAndHounds.rbg): Also known as _Wolf and Sheep_
, the game is played on an $8\times 8$ draughts-like board (i.e., only black
squares are used). Initially, four hounds occupy one row of the board, and the
fox player places his piece on any black square of the opposite row. The
hounds move like a draughts man (diagonally forward one square) while the fox
moves like a draughts king (diagonally forward or backward one square). The
fox moves first and chooses its initial square. The players move one of their
pieces alternatingly. The winning condition for the fox is to reach the
hounds’ back rank, and the player that is unable to move loses.

Splitting here follows the standard pattern. Since there is just one fox, Mod
affects only hound moves. Plus does not introduce any more decisive moves.

_$\bullet$ Go_ (go_constsum.rbg): This is a $19\times 19$ Go implementation
using Tromp-Taylor rules with area scoring, suicide prohibition, no ko rule,
and turn limit set to 722. This is a constant-sum version with win/draw/loss
results based on area scoring.

Here, a move is split into the decision whether to pass (set pass variable)
and then, if not passing, the selection of a square. This game is a
distinguished case demonstrating how a particular encoding significantly
decides about splits. The Mod component separates the decision about the
passing and selecting a square. Plus does not add any more decisive semimoves,
and Shift separates column and row selection as usual.

_$\bullet$ Knightthrough_ (knightthrough.rbg): The game, originated from
Stanford’s GGP competition, is very similar to Breakthrough. The pawns are
replaced by Chess knights that can only move forward.

Splitting is the same as for Breakthrough.

_$\bullet$ Pentago_ (pentago.rbg): This is a five-in-a-row game played on a
$6\times 6$ board with the additional rule that after every move the current
player has to rotate by 90 degrees on of the four $3\times 3$ subboards. The
winning condition is checked twice per turn: before and after the rotation.

The Mod component separates putting a ball and rotating a subboard. Plus
additionally separates the decision of the rotation direction (thus in
ModPlus, there are three semimoves in a turn). Shift just separates column and
row selection, which affects both putting a ball and selecting one of the
subboards (i.e., first up-down, then left-right subboard).

_$\bullet$ Skirmish_ (skirmish.rbg): Yet another simplified version of Chess,
also introduced by Stanford’s GGP competition. The initial position and
movement rules are the same as in Chess (including promotion, castling, and
en-passant), but the king is treated as a regular piece, which can be captured
as the others. The game ends when a player does not have a legal move, or 100
turn limit is reached. The player with more pieces left wins (each piece
counts as 1).

Splitting is the same as for Chess without check.

_$\bullet$ The Mill Game_ (theMillGame.rbg): Also known as _Nine men’s
morris_. The game is played on a grid with twenty-four intersections. Each
player has nine pieces called men. Their goal is to form mills: three own men
lined horizontally or vertically, which allows removing the opponent’s men.

The game has three phases: placing men on vacant points, moving men to
adjacent points, and optionally, moving men to any vacant point when the
player already has three men only. A player loses when it is left with less
than three pieces or has no legal moves. The game ends with a draw after 20
moves without forming a mill after the first phase.

The Mod component separates a pawn movement as usual, and also capturing; thus
a turn consists of either two or three semimoves. Plus separates choosing a
direction in a standard way. Due to a non-standard board, the square selection
with Shift also works differently: first one of the three rings is chosen,
then a square on this ring. This affects both own pawn selection and
capturing.

##  4 Experimental Setup

###  4.1 Parameters

All parameters of the tested agents were turned according to the
recommendations in the literature. Both orthodox and semisplit agents were
using exactly the same parameters set. This means that they may not
necessarily be tuned for semisplit agents, as they are originally recommended
for orthodox agents in the literature.

The exploration constant in the UCT formula (Sironi and Winands 2016, (1)) was
set to $C=0.4$ (Finnsson and Björnsson 2010). We have also tried the second
popular value $C=0.7$, but it turned out to give worse results than $C=0.4$
for our setting and game set.

MAST uses the $\varepsilon$-greedy policy with $\varepsilon=0.4$, i.e., with
probability $0.6$ it chooses a (sub)move with the best average score. The
decaying parameter was set to $0.2$ (Tak, Winands, and Björnsson 2014).

In the case of MAST-mix, the mix-threshold was set to $7$, as this value was
proposed for NST (Tak, Winands, and Björnsson 2012).

RAVE had its equivalence parameter set to $250$ (Sironi and Winands 2016).
According to recommendations, whenever RAVE was used (in all agent types), the
exploration constant was also set to $C=0.2$.

An agent does not compute (it sleeps) during the opponent’s turn.

All ties (e.g., moves with the same UCT score or MAST score) are broken
uniformly at random. In the final selection, an agent selects the
move/semimove with the largest average score, and in the case of ties, with
the largest number of iterations (and then ties are resolved randomly).

###  4.2 Algorithmic Details

MAST stores global statistics for each move. Updating and, in particular,
reading those statistics should be as fast as possible to avoid the situation
in which the time overhead from using MAST causes losings greater than
benefits.

Probably the best general choice is a dictionary based on a hashtable. We use
a custom implementation of a hashtable with closed hashing, taking into
account its global character (adjusting the initial size and growth) and the
domain of the integers in actions. However, in particular in the case of MAST-
split, when we know that the domain of all possible semimoves is small, the
hashtable can be replaced with a raw array.

MAST-context could be implemented with the same hashtable as is used for full
moves. However, it can be optimized, taking advantage of our specific
application. We use the fact that whenever a submove is stored in the
hashtable, also all its prefixes must have been already stored there since
they have been applied earlier. Furthermore, we have queried these prefixes
right before processing the submove. Thus, instead of the full submove, we
store pairs of the context and the semimove. The context is represented by the
bucket id in the hashtable, which uniquely represents a stored submove and is
returned directly from the preceding query. In this way, elements in the
hashtable have a fixed length, and their hashing and comparisons (in the case
of conflicts) are cheaper.

RAVE uses similar structures, but it is enough to use a hash set instead of a
hash map, as we only need to query if a given move occurs at the bottom of the
iteration. In the case of RAVE-split, we use bit sets to encode this, taking
advantage of a relatively small domain of semimoves.

When MAST is used in a semisplit simulation, we compute all values of
semimoves only once, using a heap (priority queue) for picking up the best
value. This reduces the worst-case time from quadratic to linear-logarithmic
in the number of available semimoves, when all semimoves turn out to be dead.

###  4.3 The Setting

There are 300 plays in each test, where 150 plays are played with swapped
agents. The final win ratio is computed by assigning $1$ point for a win,
$0.5$ for a draw, and $0$ for a loss. Win ratios are given in percents.

The confidence intervals are given for $95\%$ confidence based using a
standard method (Haworth 2003). They are used to count games where an agent
has a clear advantage or a disadvantage, as described in the next section.
(The confidence interval is not given in the case of winning all the plays by
one side, which sometimes happens for Breakthru.)

In the timed experiments (_timed setting_), the time limit is set to $0.5$s
per turn, unless otherwise stated. The buffer time is not included, i.e., this
is the time limit for pure computation; the real limit sent by the manager is
$0.6s$. In view of computational power, this roughly corresponds to the
setting with $10$s limit based on GDL reasoning (Kowalski et al. 2020), which
is often used for comparisons of agents (Sironi and Winands 2016).

There are also experiments with a fixed budget limit (_fixed setting_). We
limit the number of states that an agent can compute in its own turn. Only
nodal states are counted. The limits for each game are computed by
benchmarking the corresponding orthodox agent, measuring the number of states
computed in the first turn over $10$s. In contrast with limiting the number of
simulations, this better corresponds to the timed setting, because of two
reasons. First, the average length of simulations may vary depending on
whether the semisplit or orthodox design is used. Second, the average length
of simulations decreases as gameplay advances, since terminal states are
closer.

###  4.4 Environment

The hardware used for the timed experiments was a computer with AMD Ryzen
Threadripper 3970X 32-Core Processor and 64GBi. The system was Ubuntu 20.04.2
LTS (GNU/Linux 5.4.0-80-generic x86_64). The relevant software was gcc 9.3.0,
boost 1.75.0, and Python 3.8.10.

The tests of agents were performed with 30 plays in parallel (one process
computes 5 plays, giving 150 in total for one side).

Because the experiments with fixed states limit do not depend on hardware
efficiency (i.e., are deterministic up to the random seed), they were
performed on other computers belonging to the same grid.

The random generator used was the default used in the RBG system: std::mt19937
together with the Lemire’s selection method (Lemire 2019; Kowalski et al.
2020).

##  5 Extended Results

We present extended results in addition to those given in the main text.

In all tables, the bars show the grand average in timed (upper, red) and fixed
(lower, blue) settings. Timed results are also given separately for each game
with 95% confidence intervals. Green, yellow, and red indicate statistically
significant _better_ , _same_ , and _worse_ performance, respectively. A game
is counted for better performance if the whole 95% confidence interval is
above 50%. Worse performance is symmetrical (i.e., the confidence interval is
below 50%), and the draw means that 50% is included within the confidence
interval.

###  5.1 Vanilla Agents

Tables 4, 5, and 6 show the results for different split strategies. We have
three types of agents combined with three split strategies of different
granularity, all larger than that of Mod alone. As general observation, we
conclude that the Shift component, which commonly separates board’s column and
row selection, tends to decrease the results, but the Plus component has a
small positive effect.

Table 4: Win rates of semisplit agents with different split strategies.  Agent | Win rates vs. $\mathbb{O}$X
---|---
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}$ @ModPlus a |
$\mathbb{S}^{\text{tree:S-raw}}_{\text{sim:S}}$ @ModPlus a |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}$ @ModShift a |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}$ @ModPlusShift a |
|
Table 5: Win rates of semisplit orthodox-tree design agents with different split strategies.  Agent | Win rates vs. $\mathbb{O}$X
---|---
$\mathbb{S}^{\text{tree:O}}_{\text{sim:S}}$ @ModPlus a |
$\mathbb{S}^{\text{tree:O}}_{\text{sim:S}}$ @ModShift a |
$\mathbb{S}^{\text{tree:O}}_{\text{sim:S}}$ @ModPlusShift a |
|
Table 6: Win rates of semisplit roll-up agents with different split strategies.  Agent | Win rates vs. $\mathbb{O}$X
---|---
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:S}}$ @ModPlus a |
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:S}}$ @ModShift a |
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:S}}$ @ModPlusShift a |
|

###  5.2 Enhanced Agents

Table 7 shows the results from sanity tests concerning how beneficial is
adding the action-based heuristics to the vanilla orthodox agent in our
setting. We observe that both heuristics give some advantage on average, yet
MAST yields a larger improvement. However, the results are diminished by the
time overhead, which is not surprising as both heuristics involve noticeable
computational cost (especially when computing moves and states is fast).

Table 7: Win rates of orthodox agents with action-based heuristics vs. vanilla orthodox agent. Agent | Win rates vs. $\mathbb{O}$X
---|---
$\mathbb{O}_{\text{sim:MAST}}$ |
$\mathbb{O}^{\text{tree:RAVE}}$ |
$\mathbb{O}^{\text{tree:RAVE}}_{\text{sim:MAST}}$ |
|

Figure 4 is the counterpart to the Figure 1 from the main text but with
enhanced MCTS agents. Here, we show the results for the most straightforward
(except that this is nodal) semisplit variant. The tendencies are generally
similar, and we get comparable results across different time limits, yet in a
few cases (Amazons, Breakthrough, and Chess (no check)) they drop as the time
limit grows. The differences between the results in timed and fixed settings
are also smaller, except for Chess, where computing legal moves is costly. It
is because action-based heuristics are expensive relatively to semisplit’s
MCTS computation. This should motivate us to consider more involved variants
when semisplit is combined with these heuristics.

Figure 4: The results of $\mathbb{S}^{\text{tree:S-nodal,RAVE-
split}}_{\text{sim:S,MAST-split}}\text{@Mod}$ versus
$\mathbb{O}^{\text{tree:RAVE}}_{\text{sim:MAST}}$ for different time limits
(circle, red) and for equivalent states budgets (square, blue).

Tables 8, 9, and 10 show different variants of semisplit agents together with
some combinations of action-based heuristics. Due to the number of all
possible combinations, we had to make some selection. We tested agents that
performed best/most robust in the vanilla case, i.e.,
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}\text{@Mod}$,
$\mathbb{S}^{\text{tree:O}}_{\text{sim:S}}\text{@Mod}$, and
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:S}}\text{@Mod}$, which are shown
in the three tables, respectively. We also kept Mod split strategy as the
simplest choice, since adding the Shift component seems to give worse results
and adding Plus does not change much.

First, we observe that the split variants of the heuristics give the best
results in the timed setting. MAST-mix gives a slight improvement in quality,
but this benefit is discounted by time overhead. It is clearly better than
MAST-context (compare $\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S,MAST-
context}}\text{@Mod}$ with
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S,MAST-mix}}\text{@Mod}$, and
$\mathbb{S}^{\text{tree:O,RAVE-join}}_{\text{sim:S,MAST-context}}\text{@Mod}$
with $\mathbb{S}^{\text{tree:O,RAVE-join}}_{\text{sim:S,MAST-mix}}\text{@)}$,
whereas MAST-split is faster enough to get better results in the timed
setting.

When semisplit design is applied in the MCTS tree, RAVE gives worse results,
also in the fixed setting. A reason for that could be that semimoves carry too
little information, so the hints gave by RAVE are too random. We should take
into account that RAVE gives only little benefits also for orthodox agents.
Using RAVE also means setting the exploration constant $C$ to $0.2$ instead of
$0.4$ (Subsection 4.1), and since semisplit also reduces exploration, this can
be too much. Further experiments concerning this particular case may be
required, and this is a topic for future work. However, RAVE still gives a
slight advantage in the fixed setting when applied in MCTS tree under orthodox
design (compare $\mathbb{S}^{\text{tree:O}}_{\text{sim:S,MAST-
split}}\text{@Mod}$ and $\mathbb{S}^{\text{tree:O,RAVE-
join}}_{\text{sim:S,MAST-split}}\text{@Mod}$).

The best performing and most robust variants are
$\mathbb{S}^{\text{tree:O}}_{\text{sim:S,MAST-split}}\text{@Mod}$ and
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:S,MAST-split}}\text{@Mod}$. The
latter with RAVE added gets slightly better results in the fixed setting.
Recall here that RAVE-context is the only available variant that works with
the roll-up MCTS variant.

Table 8: Win rates of semisplit agents based on $\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}\text{@Mod}$ with variants of action-based heuristics. Agent | Winrates vs. $\mathbb{O}^{\text{tree:RAVE}}_{\text{sim:MAST}}$ X
---|---
$\mathbb{S}^{\text{tree:S-nodal,RAVE-split}}_{\text{sim:S,MAST-split}}$ @Mod a |
$\mathbb{S}^{\text{tree:S-nodal,RAVE-context}}_{\text{sim:S,MAST-context}}$ @Mod a |
$\mathbb{S}^{\text{tree:S-nodal,RAVE-mix}}_{\text{sim:S,MAST-mix}}$ @Mod a |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S,MAST-split}}$ @Mod a |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S,MAST-context}}$ @Mod a |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S,MAST-mix}}$ @Mod a |
$\mathbb{S}^{\text{tree:S-nodal}}_{\text{sim:S}}$ @Mod a |
|
Table 9: Win rates of semisplit agents based on $\mathbb{S}^{\text{tree:O}}_{\text{sim:S}}\text{@Mod}$ with variants of action-based heuristics. Agent | Winrates vs. $\mathbb{O}^{\text{tree:RAVE}}_{\text{sim:MAST}}$ X
---|---
$\mathbb{S}^{\text{tree:O}}_{\text{sim:S,MAST-split}}$ @Mod a |
$\mathbb{S}^{\text{tree:O,RAVE-join}}_{\text{sim:S,MAST-split}}$ @Mod a |
$\mathbb{S}^{\text{tree:O,RAVE-join}}_{\text{sim:S,MAST-context}}$ @Mod a |
$\mathbb{S}^{\text{tree:O,RAVE-join}}_{\text{sim:S,MAST-mix}}$ @Mod a |
|
Table 10: Win rates of semisplit agents based on $\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:S}}\text{@Mod}$ with variants of action-based heuristics. Agent | Winrates vs. $\mathbb{O}^{\text{tree:RAVE}}_{\text{sim:MAST}}$ X
---|---
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:S,MAST-split}}$ @Mod a |
$\mathbb{S}^{\text{tree:R-nodal}}_{\text{sim:S,MAST-mix}}$ @Mod a |
$\mathbb{S}^{\text{tree:R-nodal,RAVE-context}}_{\text{sim:S,MAST-split}}$ @Mod a |
|