# Impartial Games: A Challenge for Reinforcement Learning

Bei Zhou
Queen Mary University of London
<EMAIL_ADDRESS>
&Søren Riis
Queen Mary University of London
<EMAIL_ADDRESS>

###### Abstract

The AlphaZero algorithm and its successor MuZero have revolutionised several
competitive strategy games, including chess, Go, and shogi and video games
like Atari, by learning to play these games better than any human and any
specialised computer program. Aside from knowing the rules, AlphaZero had no
prior knowledge of each game. This dramatically advanced progress on a long-
standing AI challenge to create programs that can learn for themselves from
first principles.

Theoretically, there are well-known limits to the power of deep learning for
strategy games like chess, Go, and shogi, as they are known to be NEXPTIME
hard. Some papers have argued that the AlphaZero methodology has limitations
and is unsuitable for general AI. However, none of these works has suggested
any specific limits for any particular game.

In this paper, we provide more powerful bottlenecks than previously suggested.
We present the first concrete example of a game - namely the (children) game
of nim - and other impartial games that seem to be a stumbling block for
AlphaZero and similar reinforcement learning algorithms. We show
experimentally that the bottlenecks apply to both the policy and value
networks. Since solving nim can be done in linear time using logarithmic space
i.e. has very low-complexity, our experimental results supersede known
theoretical limits based on many games’ PSPACE (and NEXPTIME) completeness.

We show that nim can be learned on small boards, but when the board size
increases, AlphaZero style algorithms rapidly fails to improve. Intuitively,
this can be explained by the fact that if a tiny amount of noise is added to
the system e.g. if a small part of the board is covered, it is typically not
possible to predict whether the position is good or bad (won or lost). There
is often zero correlation between the visible part of a partly blanked out
position and its correct evaluation. This situation is in stark contrast to
partisan games like chess, Go, and shogi, where a partly blanked out
configuration typically provides abundant (or at least non-trifle) information
about the value of the fully uncovered position.

We quantify the difficulties for various setups, parameter settings and
computational resources. Our results might help expand the AlphaZero self-play
paradigm by allowing it to use meta-actions during training and/or actual game
play like applying abstract transformations, or reading and writing to an
external memory.

_K_ eywords AlphaZero $\cdot$ Reinforcement learning $\cdot$ Neural networks
$\cdot$ Parity problem $\cdot$ Impartial games

##  1 Introduction

The AlphaZero algorithm and its variations have been highly successful in
producing high-quality moves in complex strategy games, including chess, Go,
and shogi [47, 45, 43]. Here "high quality" is measured in terms of playing
against the best human players and the best available computer software.
AlphaZero’s self-play algorithm was trained on powerful computer hardware and
achieved superhuman performance in less than 24 hours.

AlphaZero’s groundbreaking strategies in chess and Go have taken the game
playing communities by storm [41]. This sentiment is expressed by former chess
world champion Garry Kasparov who wrote chess has been shaken to its roots by
AlphaZero, but this is only a tiny example of what is to come. Or as Matthew
Sadler and Natasha Regen write in [41] It is momentous for chess players
because, for the first time, we can learn from a powerful inteligence which
build its chess strategy independently of our own rich history of chess
development.

AlphaZero has not been made generally available; however, the open-sourced
projects LC0 for chess, Leela Zero for Go, and AobaZero for shogi, game
playing agents have, in essence, replicated AlphaZero [10]. These projects
outsourced the demanding computational task of training the game playing
agents to communities of computer strategy game enthusiasts. The participants
would typically lend the project computer power directly by contributing
hardware resources or running a script provided on the google colab cloud
platform. Recently, a variant of AlphaZero has been proposed and published as
open-source [55]. The open-source Go project Elf is also worth mentioning
[51].

Impartial games are games in which the allowable moves depend only on the
position and not on which of the two players is currently moving. The class of
impartial games is an important subclass of combinatorial games [5, 6, 7, 8].
Impartial games include take-and-break games, subtraction games, heap games,
and poset games. It includes children’s games as well as mathematical games,
including sprout, treblecross, cutcake, guiles, wyt queens, kayles, guiles,
grundy’s game, quarto, cram, chomp, subtract a square, notakto, and nim [5,
6]. Many impartial games have multiple variants. The analysis of impartial
games is called nimber theory, and the Sprague–Grundy theorem states that
every impartial game is equivalent to a nim-heap [5]. Thus the game nim plays
a central role in the theory of impartial games, and a large class of
impartial games can mimic nim (or parts of nim). From an AI point of view, it
turns out that many impartial games are as hard (or much harder e.g. node
kayles and geography that are PSPACE complete [42]), than nim. Nim is a game
often played by children.

Despite AlphaZero’s groundbreaking advance for complex games, it turns out
that there are games like nim that, from a human point of view, as well as
from a complexity point of view, are simple, where AlphaZero style algorithms
essentially seems to be unable to learn to play better than a randomly playing
agent. On specific boards or towards the end of the game, the algorithm have
enough resources to play well by essentially using exhaustive search. However,
on larger nontrivial positions the policy network generally fails to provide
any valuable information to guide the Monto Carlo Three Search (MCTS)
algorithm, and the value network fails to evaluate the board positions any
better than random.

Nim is played by two players who take turns removing counters from distinct
heaps [9, 32]. A player must remove at least one counter on each turn and may
remove any number of counters, provided they all belong to the same heap. The
goal of the game is to be the player who removes the last counter i.e. leaves
the empty position to the opponent.

Nim is often classified as a mathematical game, and it has a well defined
mathematical solution. Formally, the initial board of nim can be represented
as an array:

$[n_{1},n_{2},....,n_{k}]$

where $n_{j}\in\\{0,1,2,\dots\\}$ and $j=1,2,\ldots,k$. A position in a game
using that board can be represented as an array

$[v_{1},v_{2},....,v_{k}]$

where $v_{j}\in\\{0,1,2,\dots\\}$ and $v_{j}\leq n_{j}$ for
$j\in\\{1,2,\ldots,k\\}$. Often a nim position is specified without reference
to a board, however, we always specify the intial position of the board since
the algorithm requires a fixed board size, and each self-play game starts with
the initial position of the board. Fig. 1 demonstrates an example of an
initial nim board, a board positions during play and the final board position.

Figure 1:  The initial board consists of a series of heaps (aka rows or piles)
of counters (aka lines or matches). The initial board, as shown in the left
graph, is $[n_{1},n_{2},....,n_{k}]=[1,3,5,7,9]$. The two players take turns
in removing counters, resulting in one of the positions in the game play that
is $[v_{1},v_{2},....,v_{k}]=[1,2,4,4,3]$, as shown in the middle graph. In
the usual version of the game, the player who removes the last counter(s)
wins, as shown in the right graph where all the heaps are cleared.

There are $n=\sum_{j}v_{j}$ legal moves from the position
$[v_{1},v_{2},....,v_{k}]$. For example, the number of legal moves from the
initial position of nim played on the board

$A=[1,2,3,\ldots,9]$

is $45$. The number of legal moves from the initial position of nim played on
the board

$B=[1,2,3,\ldots,25]$

is $325$. This exceeds the number of legal moves in any Go position on the
standard $19\times 19$ board.

The maximal number of moves in nim on the initial board
$[n_{1},n_{2},....,n_{k}]$ is $m=\sum_{j}n_{j}$ as each player needs to remove
at least one counter for each move. Games of chess and Go typical last less
than 300 moves 111In chess a move usually include a move by each player, and
thus a typical chess game lasting $n$ chess moves, in fact last $2n$ moves.
Thus, nim on the board $B$ has a branching factor and game length compatible
to Go and exceeding the branching factor and length of a typical chess game.
Notice that size of the game tree of nim typically hugely exceeds that of the
number of possible positions (states) which is given by

$\Pi_{j}(1+n_{j})$

For any nim position it is (mathematically) easy to determine which player
will win and which winning moves are available to that player. The value (won
or lost) of a nim position can be determined by calculating the binary digital
sum of the number of counters in the heaps, i.e., the sum (in binary),
neglecting all carries from one digit to another [9]. Within combinatorial
game theory this is commonly referred to the nim-sum (see 3.1 for more
details). The complexity of this calculation can be shown to be linear time
and with the use of only logarithmic space memory.

Based on theoretical considerations related to the statistical neutrality of
the parity function [50] as well as some subtle and heuristic arguments that
the defense has the ability to keep preventing the attacking player from
forcing the game into readily predictable patterns, we conjectured that
AlphaZero style learning (without any addition of special customised trick and
features) in practice would not be able to learn nim (and consequently also
numerously other impartial games) on large boards.

Based on our preliminary experimental results from supervised learning we
expected that the policy network in AlphaZero style nim would be unable to
properly learn to play high quality nim on asymptotically large boards like
e.g. $[1,2,3,\ldots,n]$ for $n>100$. To our great surprise we discovered that
the difficulty was much larger than anticipated and that the policy network
and evaluation networks consistently failed to converge even on small boards
e.g. $[1,3,5,7,9,11,13]$.

In games like chess, AlphaZero’s value network fails to be perfect, which is
typically not a serious issue as it is compensated by the search guided by the
policy network. It turns out that imperfection is not necessarily a problem on
some nim boards since the policy network essentially can help the winning
player to force the game into positions that do not require any accurate
evaluations. However, there is no such luck in general as there are two
difficulties:

  1. (1)

The policy network is unable to guide the MCTS better than random

  2. (2)

The value network is unable to evaluate a position better than random

According to (1), the network essentially cannot learn to select relevant
candidate moves necessary to identify winning or high-quality moves. According
to (2), even if the search is able to look many moves ahead, any evaluation is
meaningless as it in general does not perform better than random.

We investigated the difficulties in (1) and (2) and found that if a small part
of a position in an impartial game is blanked out, the prediction of the
policy network and the evaluation of the value network can typically not be
better than pure random guessing.

As a comparison, the general evaluation of the networks might be wrong if we
cover part of a Go, chess or shogi board. However in general the visible part
of the board contains information that is positively correlated with the
correct evaluation of the full board. However, for impartial games like nim,
any board covering where a small but unknown number of counters is covered
makes it impossible to evaluate the resulting position correctly. It is
typically impossible to predict whether the position is good or bad (won or
lost) as there is typically zero correlation between the visible part of a
partly blanked out position and its correct evaluation. This type of heuristic
argument shows that even a small level of noise typically erase the
correlations needed to bootstrap the positive feedback mechanism of an
AlphaZero style algorithm.

The subclass of combinatorial games of so-called partisan games can
occationally pose issues similar to that of impartial games e.g. Dawson’s
chess that in effect is a impartial game in disguise [5].

To better understand the difficulties of learning nim-like games, we decided
to revisit the AlphaZero for chess, Go and shogi projects and consider
positions where simple parity-like problems are needed to correctly evaluate a
position. Since chess is probably the most commonly known game in the English
speaking world, and the official AlphaZero program is unavailable, we mainly
used a highly trained the Leela Chess Zero (LC0) engine.

We investigated and discussed many theoretical and practical issues and
limitations in this paper. To summarize, our main contributions are:

  * •

Identify a class of strategic games that require nontrivial modifications of
AlphaZero style algorithms or in general current RL algorithms to work.

  * •

Discovery that the difficulty for RL algorithms to learn impartial games is
much more dramatic than theoretical analysis of the individual components, the
value network (see section 5.1), the policy network (see example 3 in section
5.2) or the parity-related issue (see section 3.3) would suggest. Noise
brought by these issues has a dramatically compounding negative effect,
showing learning difficulties with less than ten piles instead of 50+ piles
(see section 7).

  * •

Propose two levels of mastery of a RL agent, champion and expert, which are
essential in evaluating the performance of an agent (see section 4). To the
best of our knowledge these concepts are not mentioned in the literature.

  * •

Experimentally demonstrate the robustness of the problems through an extensive
list of experiments and show that fiddling with the hyperparameters does not
have much effect on alleviating the difficulties.

  * •

Briefly outlining of how one might expand the AlphaZero paradigm approach for
future algorithms.

The paper is structured as follows. In section 2 we revisit AlphaZero and
LCZero and look behind some of the fantastic magic moves these chess programs
have produced. The main point of this analysis is to identify the strength and
weaknesses of LCZero. LCZero’s defects often are hidden and mainly appear
behind the scene and only occurs when we look under the hood. However, we will
see that the weaknesses include issues impacting both the value and policy
networks.

Section 3 shows how many impartial games can be boiled down to the nim and
concerns theoretical bottlenecks and general limitations for AI solving
various two-player games with full information. We show that these results all
follow well-known results in complexity theory. The section also includes
reference to our experimental results on modelling the parity function with
neural networks (NNs).

In section 4, we propose two types of optimality that lead to two levels
mastery, namely champion and expert. We illustrate the distinction with one
analogy and one special nim example we also tested experimentally.

In section 5, we present the empirical results of the performance of the value
network on modelling parity function and the inability of the policy network
to modelling nim-sum. In section 6, we give an overview of the AlphaZero
algorithms and the changes we made tailored to nim and demonstrate the
difficulty of our AlphaZero style nim algorithm have in becoming an expert
agent on large boards. We finish the paper with some general remarks,
conjectures, and directions for further research.222The code for the
experiments in this paper is publicly available at:
https://github.com/sagebei/Impartial-Games-a-Chanllenge-for-Reinforcement-
Learning

##  2 Revisiting AlphaZero and LCZero

AlphaZero, which astonished the chess world, has essentially been replicated
by LCZero. This section focuses on a highly trained version of LCZero. In
general, LCZero can access the computational resources that the programs need
to run Monte Carlo Tree Search (MCTS) simulations and replicate the moves made
by AlphaZero chess. LCZero333version: Last T60: 611246 (384 $\times$ 30) uses
the neural network composed of $30$ blocks $\times$ $384$ filters which are
beyond the initial $20\times 256$ architecture of AlphaZero, and LCZero
additionally employs the Squeeze-and-Excitation layers to the residual block
and supports endgame tablebases [28], enabling it to possibly surpass the
original AlphaZero algorithm. The older versions of LCZero running on a
$20\times 256$ architecture are somewhat weaker than the later versions
running on the $30\times 384$ architecture.

For comparing the moves, we also gained access to open-source Stockfish 14,
which, like Stockfish 8 developed initially by Tord Romstad, Marco Costalba,
and Joona Kiiski, and have been further developed and maintained by the
Stockfish community. Unlike Stockfish 8, stockfish 14 also comes with an NNUE
(Efficiently Updatable Neural Network) [31] for its evaluation and thus
combines features of deep neural networks with traditionally handcrafted chess
engines. Game playing strength is usually measured by Elo rating (see section
6.2 for the detailed description). There has been an attempt to measure
playing strength based on the quality of the played chess moves rather than on
the results [37]. On the chess engine rating list rating (August 7, 2021) the
latest iteration of Stockfish 14 has 3555, Stockfish 8 has 3375 and LCZero
3336. LCZero running on hardware similar to AlphaZero against a special fixed
time (1 minute) for each move version of Stockfish 8 has been shown to lead to
a similar dramatic achievement as AlphaZero.

The revolutionary and outstanding evaluations and moves have taken the chess
world by storm. Often AlphaZero and LC0 would evaluate positions quite
differently from human players or traditionally hand-coded chess engines.

Although AlphaZero is not generally available, its detailed evaluation of some
chess positions has been made public [41]. AlphaZero’s use of its policy
network, its evaluation networks and MCTS were explained by a detailed
analysis of the position in Fig. 2. A highly trained LC0 using the net T60:
611246 (384x30) straight away thought that d5 was the move to give the most
attention, which can be seen from the table of the policy network’s prior
probabilities. AlphaZero had a different training history, so the prior
probabilities differed, but AlphaZero agrees that d5 is a promising move.
After investigating 64 and 256 nodes 444More specifically, the number of new
nodes visited, which corresponds to the number of MCTS simulations, AlphaZero
is highly optimistic about the move, while LC0 is somewhat less happy but
agrees that white is better.

r1b2qk1/1pp3rp/4pnp1/1PP5/p2PBp2/P7/1BQ2P2/K1R1R3 w - - 0 1

(a)

Move |  d3 |  f3 | c6 | d5 |  g2 | f3 |  h1 |  c4
---|---|---|---|---|---|---|---|---
Prior prob (AlphaZero) | 29.77% | 18.82% | 16.15% | 10.21% | 4.75% | 3.5% | 4.75% | 1.2%
Prior prob (LCZero) | 6.01% | 12.36% | 16.27% | 23.13% | 1.74% | 3.73% | 1.41% | 8.68%
(b)

Move |  d3 |  f3 | c6 | d5 |  g2 | f3 |  h1
---|---|---|---|---|---|---|---
Win prob (AlphaZero 64 nodes) | 60.1% | 64.5% | 77.3% | 87.1% | 61.6% | 67.3% | 61.6%
Win prob (AlphaZero 256 nodes) | 60.1% | 64.5% | 77.7% | 83.1% | 61.6% | 67.3% | 61.6%
Win prob (LCZero 64 nodes) | 62.8% | 62.8% | 71.2% | 71.6% | 55.7% | 55.7% | 55.7%
Win prob (LCZero 256 nodes) | 59.0% | 62.2% | 63.3% | 67.8% | 50.0% | 58.2% | 50.0%
(c)

Nodes visited | 64 | 256 | 1024 | 65536 | 4194304
---|---|---|---|---|---
AlphaZero eval | 65.7% | 74.1% | 71.6% | 67.9% | 73.5%
LCZero eval | 70.1% | 65.0% | 67.4% | 68.3% | 73.1%
(d)

Figure 2:  LCZero and AlphaZero very fast agree that d5 is the best move, and
though both engines discover various defensive resources, they reach similar
evaluations.

At deeper MCTS, AlphaZero begins to discover various defensive resources, so
its win probability begins to drop. The win probability for a position $s$ is
calculated by $(0.5+v/2)$% where the $v$ is a scalar output from the value
network with position $s$ as its input. When more nodes are examined, the win
probabilities climb up again. Eventually, after 4194304 nodes, the two engines
had almost identical evaluations with win probabilities of 73.5% resp. 73.1%.
In general, LC0 plays very similar to AlphaZero, and it is fair to say
AlphaZero’s play fully have been replicated by LC0.

The quality of evaluation of AlphaZero for chess is discussed in great detail
in [41]. The moves selected by LC0 without search (i.e. when only one node is
visited by the MCTS algorithm) plays remarkably well and is occasionally able
to win games against strong chess players.

When we compare a move made by a human with the one selected by LCZero, the
human typically looks at far fewer positions but humans pattern recognition
sometimes spots features that are missed by LCZero’s value network. A human
grandmaster maximally considers a few hundred moves, i.e. significantly fewer
moves than LCZero, that in turn considers dramatically fewer moves than
conventional chess programs. As an example to illustrate the human superiority
but also to understand limitations that becomes relevant for judging impartial
games, consider the position in Fig. 3. Any decent chess player can "see"
intuitively - essentially without any calculation - that white has a won
position leading to mate (1.g8+,g8 and 2.f7+ mate). But the policy network
typically (it is a stochastic process) first lead the program slightly astray
and spend time investigating the positions arising after 1.f7+. It is
important to stress that LCZero finds the winning sequence in less than a
millisecond. The point made here is that neither the value network nor the
policy network in general evaluates positions completely accurately. This fact
is crucial for understanding the limitations for impartial games where even
the slightest change in position (or noise) completely wipe out any positive
correlation between the policy and position evaluations and the correct ones.

1rr4k/6pp/7N/3Q4/8/qPp5/P1P5/1K6 w - - 0 1

(a)

Move |  f7 |  g8 |  d8
---|---|---|---
Prior Prob | 60.69% | 15.96% | 2.50%
V-value | -0.276 | 0.588 | -0.968
Win prob | 36.2% | 79.4% | 1.6%
Q-value (15 nodes) | -0.075% | 1 | 0
Win prob (15 nodes) | 48.5% | 100% | 0%
(b)

Figure 3:  White has a forced win in two moves where he sacrifices the queen
before mating with his knight. It is not surprising LCZero evaluation with no
search (i.e. with just one node visited) is unable to reach the conclusion
that white has a forced win. Only after 11 nodes does the program jump away
from investigating lines beginning with f7, and switch to investigate the
winning move g8. And only while at node 15 does the program find the forced
mate.

The next example Fig. 4 illustrate the difficulty in handling parity related
problems. On the right part of the position, any player who moves would lose
the game. The situation on the left side of the board is equivalent to the nim
position $[3,2]$ consisting of two heaps with three and two counters,
respectively and where it is only possible to remove one or two counters from
a heap. This version of nim is sometime referred to as bogus nim. The winning
move is to remove one counter from the heap with three counters. Analogously,
the winning move for the white is making the move c3-c4. But LCZero’s policy
network suggests a2-a4, which disastrously leads to a losing position. Like in
the previous example it is important to stress that LCZero finds the winning
sequence almost immediately, and the point is that neither the value network
nor the policy network in general are able to evaluate positions completely
accurately.

6k1/2p5/5P1P/p7/8/2P2p1p/P7/6K1 w - - 0 1

(a)

Move | a4 | c4 | a3 | f7
---|---|---|---|---
Prior prob | 50.4% | 20.7% | 15.4% | 4.4%
V-value | -0.632 | 0.806 | -0.817 | -0.88
Win prob | 18.4% | 90.3% | 9.2% | 6%
Q-value (3 nodes) | -0.632% | 0.806 | -0.248 | -0.248
Win prob (3 nodes) | 18.4% | 90.3% | 37.6% | 37.6%
(b)

Figure 4:  A chess position that mimics a nim position $[3,2]$. Neither black
or white would like to move on the right hand side of the board. A simple
analysis conclude that white has to play c3-c4 which is winning. Any other
move leads to a loss. The LC0 policy network gives the move a2-a4 a score of
50.4%. The second most promising move is c3-c4 which scores 20.7%. The
positions Q-value is -0.083 which corresponds to a win probability of 45.5%
indicates a slight advantage to black while in fact white is winning. Notice
that LC0’s value network already judge the position after c4 very favorable
for white (which we find this quite impressive). Though it is a stochastic
process LC0’s MCTS typically needs only to investigate few nodes before it
considers c3-c4 which it then likes straight away

Despite that LCZero is equipped with rather incredible policy and value
networks, in general, it cannot accurately evaluate positions related to
parity issues, including "zugzwang", "waiting moves", and "triangle
manoeuvres", etc. that are common themes in chess. This, however, is not an
issue for AlphaZero or LCZero as the issues effectively are handled by the
MCTS. However, some examples show that the policy network occasionally might
fail to properly consider crucial key moves.

As an example consider the board position in Fig. 5 that occured in a game
between Stockfish 12 and LCZero. The white player can force checkmate in a
sequence of 5 moves, starting with c2. However, the policy network give the
move of a5+ the highest prior probability. The serious problem is that LC0’s
policy network fails to guide the MCTS propertly, and after more than 1
million nodes LC0 were unable to find the winning sequence. The failure to
find the winning sequence is partly a drawback of using MCTS, while alpha-beta
search that almost universally is used in conventional chess engines,
typically finds the forced mate almost instantly.

6r1/5p2/1r6/2kpPb2/Rp1p4/3P2P1/1R3PK1/3B4 w - - 0 1

(a)

Move |  a5 |  c2 |  e2 |  b3
---|---|---|---|---
Prior prob | 35.9% | 16.5% | 10.3% | 4.7%
V-value | 0.29 | 0.27 | -0.005 | 0.06
Win prob | 64.5% | 63.5% | 49.8% | 53.0%
(b)

Figure 5:  LCZero chess played Bf5 which is a blunder. LCZero fails to realize
that white has a forced mate in 5 moves. In the diagram position the highly
trained LCZero fails to find (even after have looked at more than a million
nodes) the forced mate: 1.c2+,b5 2.a5+!! 2.- a5 3. a2+,b5 4.a4+, and now 4.-c5
5. c2+mate, or 4.-a5 or 4.-a6 followed by 5.c6+ mate.

##  3 Background and related work

###  3.1 Impartial games and nim

An impartial game is a two-player game in which players take turns to make
moves, and the actions available from a given position do not rely on whose
turn it is. A player lose if they cannot make a move on their turn (i.e. a
player wins if they move to a position from which no action is possible).

In impartial games, all the positions can be classified into losing or winning
positions, in which the player to move have no winning move or has at least
one winning move.

Sprague-Grundy theorem states that every (finite) impartial game is equivalent
to a one-heap game of nim. More specifically each board position in impartial
games has a nimber, which is also called the Sprague-Grundy value. For every
position the nimber $G(s)$ is defined as

$G(s)=\text{mex}(\\{G(s^{\prime})\\}:s^{\prime}\in N(s))$ (1)

where $s^{\prime}\in N(s)$ denotes all the state $s^{\prime}$ that can be
reached by from $s$ in one legal play and the output of a mex function is the
minimum excluded value from a set, which is the least non-negative integer not
in the set [4]. A position with Sprague-Grundy value $G(s)$ is equivalent with
nim heap with $G(s)$ counters. A position is lost exactly when its Sprague-
Grundy value is $0$.

The Sprague-Grundy value of a nim position $[v_{1},v_{2},\ldots,v_{k}]$ is
given as is the binary digital sum of the heap sizes
$v_{1},v_{2},\ldots,v_{k}$ , (in binary) neglecting all carries. In
combinatorial game theory this sum is often called the nim-sum. Thus it is
computationally easy to decide if a given nim position is won or lost.

The analysis of impartial games are closely linked to the nim-sum which in
turn is linked to the parity function. Thus the parity function plays
implicitly (or explicitly) a central role in the theory of impartial games as
such games often are able to mimic nim or parts of nim. To illustrate this
consider the impartial game called sprout [5, 18] invented by John Conway and
Michael Paterson.

Positions in sprout typically have nimber values $0,1,2$ and $3$ [7]. The
position in Fig. 6(a) has nimber value 3. The Sprout position in Fig. 6(b)
also has nimber value $3$, but it has been modified so it becomes an "isolated
land" that cannot interact with anything on the outside. It follows that a
sprout starting position consisting of $n$ copies of the gadget in 6(b) can
mimic any nim position that can arrive from a staring positions with $n$ heaps
with $3$ counters.

(a) sprout position

(b) sprout position serving as a gadget

Figure 6:  nim played on a board $[3,3,3,\ldots,3]$ with $n$ heaps, is
equivalent to sprout with $n$ copies of the sprout position (gadget) in (b) in
the Figure (see the diagram on p599 in [7] for details).

Unlike nim, some impartial games cannot be solved by a simple calculation.
This follows from the fact that the complexity of some impartial games is
PSPACE complete (see 3.2 for more details).

So far algorithms for impartial games have used handcrafted programs that use
ideas akin to the alpha-beta search but are specially designed for the mex
operation [53]. Recently [4] proposed a novel method that prunes the search
tree according to the node values calculated by the mex function on short
impartial games, like nim, chomp, and cram, but this approach does not in
general scale to large board sizes.

These conventional programs that utilise that mex operation and the Sprague-
Grundy values could be used as benchmarks to test whether new RL based
algorithms can outperform conventional algorithms.

###  3.2 Intrinsic complexity bottlenecks

Computational Complexity deals with fundamental limits and bounds of
algorithmic tasks. In this section we review classical complexity classes,
results and conjectures related the asymptotic complexity of games.

The time complexity of an algorithm is the amount of time it takes a computer
to run it, and it is commonly estimated by counting how the algorithm performs
many elementary operations. An algorithm is said to be of $T(n)$ time if its
running time is upper bounded by $T(n)$ in the size n of the input for the
algorithm. Since we are not interested in actual hardware and the complexity
is commonly expressed using big O-notation. This way, the complexity of an
algorithm becomes independent of the actual speed of the computer and is
frequently measured as the number of steps needed by the algorithm. An
algorithm is said to be polynomial-time (belongs to $P$) if its running time
is upper bounded by a polynomial expression in the size of the input for the
algorithm, that is, $T(n)=O(n^{k})$ for some positive constant k.

An algorithm is said to be exponential time (belong to EXPTIME) if $T(n)$ is
upper bounded by $O(2^{nk})$ for some constant $k$.

It is essential to keep in mind that complexity classes like P and EXPTIME are
asymptotic notations. Problems in P are often considered tractable, while
problems that requires exponential time are considered intractable.

A non-deterministic algorithm is an algorithm that it can make certain guesses
at certain points during its computation. Such algorithms are designed so that
if they make the right guesses at all the choice points, then they can solve
the problem within the required time bound. We can think of a non-
deterministic computation as and algorithm with access to a perfect AI module
that at each choice point always would return the optimal choice.‘

NP is the class of decision problems that can be solved in polynomial time by
a non-deterministic algorithm. So we can consider NP as the class of problems
that can be solved in polynomial time when given access to a perfect
(idealised) build-in AI that as each branch point always recommend the most
economical choice. NEXPTIME denotes the class of problems that can be solved
in exponential time by a non-deterministic algorithm.

A complexity class might be based on space rather than time. PSPACE is the
class of decision problems that can be solved by an algorithm using memory
bounded by a polynomial expression in the size of the input.

A decision problem $A$ is said to be complete for a set of decision problems
$\mathbf{B}$ if $A$ is a member of $\mathbf{B}$ and every problem in
$\mathbf{B}$ can be reduced to $A$. Thus if the problem $A$ can be solved by
an algorithm using certain computational resources, it would essentially make
it possible to solve any problem in $\mathbf{B}$ by use of the same
computational resources.

Runtime bounds apply to algorithms including AlphaZero style learning
algorithms, that use neural networks. The computational time bounds apply to
such algorithms, however here the training process needs to be considered as a
part of the algorithm. Learning algorithms are typically probabilistic, and
the criteria for success is typically not measured against 100% accuracy.

In practice we might want to disregard the training time and ask for the
algorithms asymptotic run-time, given access to perfectly trained (or pre-
trained) neural networks. In computational complexity theory, an advice string
(advice function) is an extra input that is allowed to depend on the length
$n$ of the input, but not on the input itself. A decision problem is in the
complexity class $P/f(n)$ if there is a polynomial time algorithm (Turing
Machine) with the following property: for any $n$, there is an advice string A
of length $f(n)$ such that, for any input $x$ of length $n$, the machine M
correctly decides the problem on the input $x$, given $x$ and A. The class
P/poly consists of decision problems (classification problems) that can be
solved in polynomial time, by use of polynomial advice functions. A (pre-
trained) neural network can serve as advice function, as there is no
requirement on the quality of the advice given. For the algorithm to be able
to run in polynomial time, it need to be able to evaluate the NN in polynomial
time, so all NNs used by the algorithm need to have polynomial size. Thus, the
class P/poly include problems that can be solved in polynomial time using pre-
trained (polynomial size) neural networks for free.

Chess, Go and shogi on $n\times n$ boards have all been shown to be NEXPTIME
hard. More specifically, the decision problem of determining if a given
positions is a forced win (i.e.guarantees the player who moves from the
position a win with optimal play) is NEXPTIME complete for chess, Go and shogi
[16, 40, 1]. Thus Chess, Go or shogi on $n\times n$ game positions cannot be
correctly evaluated by any sub-exponential time algorithm. And thus
particularly the required computational time needed for an algorithm to learn
to play generalised chess (Go or shogi) to a level of perfection would be
exponential. Therefore from a theoretical point of view there is no hope that
AI algorithms in practise will be able to learn to perfectly master
generalised versions of complex games like chess, Go or shogi on large boards.
In fact, given the widely believed but unproven conjecture that NEXPTIME
$\not\subseteq$ P/poly it would be impossible for any polynomial time
algorithm is solve a NEXPTIME complete decision problem (like generalised
chess, Go or shogi) even when given access to polynomial size advice functions
e.g. polynomial size pre-trained networks [49]. But these theoretical results
are asymptotic and does not say anything about the possibility for AI systems
to learn to play the games with perfection on boards of standard size e.g.
$8\times 8$ for chess, $19\times 19$ for Go, and $9\times 9$ for shogi.

Determining if positions in impartial games like geography and node kayles is
a win is PSPACE complete [42]. So unless PSPACE $\subseteq$ P/poly or
something to that effect, from a theoretical point of view, there is no hope
that AI algorithms, in general, will be able to master (in polynomial time)
impartial games perfectly even if allowed unlimited time for training [49].

###  3.3 Low complexity bottlenecks: Parity and low-level thinking

Issues related to the parity function has a long history in AI. In [29]
McCarty suggested that the multilated chess board problem is a tough nut for
proof procedures. The problem is given an $2n\times 2n$ chessboard with two
diagonally opposite squares missing. Show that this board cannot be covered
with non-overlapping dominoes.

Figure 7:  Consider an $8\times 8$ chessboard, where the top-right and bottom-
left squares have been removed. Is it possible to tile this mutilated
chessboard with $2\times 1$ dominoes?

Humans, using high level thinking, typically manege to solve this problem -
after some trial and error - by noticing that the number of white squares and
black squares differs (in fact have different parity). McCarthy conjectured
that this problem is challenging when using low level non-abstract reasoning.
It was only 35 years later that was formally proved by Danchev and Riis with
regards to the so-call resolution proof system [14].

The issue underlying the mutilated chess board problem is directly related to
the principles based on simple counting like the parity principle. Basic
counting principles have played a prominent role in propositional proof
complexity and more abstract formal systems that captures "low complexity"
reasoning [39, 3]. For humans, counting is a straightforward process. Even
young children understand that the number of objects is an invariant, so
recounting should (in principle) lead to the same number. In mathematics, this
principle is referred to as the pigeon-hole principle. In [38] it was shown
that combinatorial principles in a technical sense that can be formalised,
either are easy and have polynomial size proofs (so-called tree-like
resolution proofs), or are very hard (like the parity principle) and require
exponential size proofs. The exponentially hard principles are exactly those
principles that fails in infinite structures (all in a sense that can be made
precise). The pigeon-hole principle fails for infinite sets as its possible to
map bijectively an infinite set to a proper subset of itself. Thus according
to the main results in [38] it follows that this principle require
exponentially large (tree-like) resolution proofs. The intractability of the
pigeon-hole principle (for the resolution proof system) had already been
established in [20]. For an AI that is unable to grasp principles like the
pigeon-hole principle (without human help), its seems hard to be able "solve"
the mutilated chess board problem. Maybe, this was already part of McCarthy
intuition when he originally posed his conjecture in 1964.

Boolean circuits are very similar to neural networks, but can only handle
Boolean 0/1 values. In this setting the parity function is defined as:

$f({x_{1},\ldots,x_{n}})=\sum_{i=1}^{n}x_{i}\ mod\ 2$ (2)

where $x_{1},x_{2},...x_{n}\in\\{0,1\\}$. In [21] it was shown that the parity
function cannot be computed by so-called constant depth, sub-exponential
Boolean circuits. There is also a long list of theoretical work related to
Boolean circuit complexity that support of the view that the parity function
is hard to learn and correctly generalise to unseen data [26].

Many types of neural networks can in principle compute the parity function. It
is possible to handcraft and artificially tune weight, so the NN can compute
the parity function (see section 3.4 for details). To better understand the
issue, it is essential to keep a few facts in mind:

If we pick a random Boolean function $f$ uniformly from the set of $2^{2^{n}}$
Boolean functions, that function can in general not be learned. To illustrate
this assume we are given an array of (distinct) inputs
$\bm{X}=(\bar{x}_{1},\bar{x}_{2},\ldots,\bar{x}_{s})$ with the corresponding
list $\bm{y}=(y_{1},y_{2},\ldots,y_{s})$ of function values where
$\bar{y_{j}}=f(\bar{x_{j}}),\quad j=1,2,\ldots,s$. For any new unseen input
$\bar{x}\not\in\bm{X}$ there is no relation between the already seen data
$(\bm{X},\bm{y})$ and $f(\bar{x})$. To see this, notice that there are exactly
$2^{2^{n}-s}$ Boolean functions that fit the observations $(\bm{X},\bm{y})$,
and exactly half i.e. $2^{2^{n}-s-1}$ have $f(\bar{x})=0$ and while the
remaining $2^{2^{n}-s-1}$ have $f(\bar{x})=1$. Thus if we are given data that
agree with the parity function for $s$ inputs, there is precisely the same
number of Boolean functions with the correct generalisation as there are with
the wrong generalisation.

Why do we believe that the parity function is the correct way to generalise
data $(\bm{X},\bm{y})$ that happens to fit the parity function? There is no
doubt that a human investigating the data $(\bm{X},\bm{y})$ after some time
will spot the pattern and then be in no doubt about how to generalise the
data. That is essential because we naturally apply Occam’s razor, and the
phenomenon is also related to the concept of Kolmogorov complexity. We feel
the parity function is a better guess as it has a short description. According
to Kolmogorov’s philosophy, it is a less "random" function as it has a short
description. However, if the underlying prior probability distribution is
uniform, though it might feel counter intuitive, there is no logical
mathematical reason to apply Occam’s razor, as no generalisation of the
partial data matching those of the parity function is more likely than any
other.

Humans find it easy to generalise the parity pattern due to its elementary
description. To some extent, neural networks apply Occam’s razor automatically
as they favour functions that can be computed by NNs with certain size and
depth bounds. Given training data $(\bm{X},\bm{y})$, a new data point is not
equally likely to have output 0 or 1. Humans find it easy to generalise the
parity pattern due to its elementary description. However, most NN models do
not take take this into account. Even if the NN happens to train a NN to
compute all training data correctly (e.g. obtain 100% accuracy), the NN might
still overfit and not generalise "correctly" to unseen data.

Some researchers have argued that the parity function is a mathematical
function rather than a natural occurring function, and they use this to
explain why it is so hard to generalise. This kind of argument has sparked of
some debate among AI researchers [50, 12].

Any Boolean function, including the parity function, can be computed by a NN
with only two layers. This result requires exponentially large neural networks
as the number $n$ of variables goes to infinity. Our arguments and experiments
would break down if we allowed exponentially large NN and exponentially large
training sets.

One heuristic way we have been thinking about parity, nim and impartial games
in general, can be expressed as an informal non-rigious argument that have
been guiding our intuition. It falls outside the scope of this paper, but it
might be possible to make the argument more rigorous by for example replacing
the notion of continuity with a suitable approximate notion.

Informal argument: In mathematics, a continuous function has the property that
if we keep the inputs in a small neighbourhood of a point, the output values
will stay in a small neighbourhood of the original output. Neural Networks
are, in essence, continuous (even for discrete classification problems) as the
probabilities they return are stable, so small input changes only lead to
small changes in the output. Back-propagation, the calculation of the
derivative of weights with respect to the loss in a neural network, is
essentially a differentiable (and thus continuous) process. Many learning
tasks are continuous because small changes to the input lead to small changes
in the output. Such learning tasks might be well suited for neural networks.
Intuitively, Games like chess, Go, and shogi are mainly continuous, but there
are typically some points of discontinuity where the correct evaluation of a
position might jump with a slight change in input. The discontinuity is not a
serious issue as the policy and value networks can still provide sufficient
guidance to the MCTS. However, many impartial games - and certainly nim - are
in some sense ubiquitously discontinuous as a slight change of the position
might dramatically change the corresponding correct evaluation.

###  3.4 Practical challenge: Parity and neural networks

The nim board positions can be represented by a list of bits, being 1, 0 or -1
where 1 denotes the counters on the board, 0 denotes the counters that have
been removed from the board, and -1 is a token separating the heaps. To
accommodate nim board representation, we define a version of the parity
function (sometimes called parity with noise) as the following. Let $n$ be any
positive integer. Given input
$\chi=\\{0,1,-1\\}^{n}=\\{x_{1},\ldots,x_{n}\\}$, the function is defined as
[2]:

$f({x_{1},\ldots,x_{n}})=\left(\sum_{i=1}^{n}x_{i}\;\textbf{{if}}\;x_{i}==1\right)\
mod\ 2$ (3)

where $n$ is the length of the input. Thus, the function output is either 0 or
1, indicating whether it contains even or odd numbers of 1s.

Neural networks are the pillars of modern artificial intelligence (AI).
However, parity function has turned out to be difficult to learn and
generalise for a variety of neural network models. [36] shows MLP and simple
RNNs trained with gradient descent can learn to modelling training data, but
fail to generalise on unseen data.

The majority of prior works focused on constructing specify neural networks
with fixed weight parameters, mainly Multilayer Perception (MLP) or RNN,
dedicated to solve the parity problem [23, 27, 17, 54, 17]. A RNN with 3
neurons and 12 frozen parameters can approximate perfectly a XOR function.
These artificially hard-wired neural networks can generalize to all seen and
unseen patterns without training or adaptation [36]. However, it is improbable
to artificially setup the weight parameters for neural networks modelling the
unknown data distributions.

As, to our best knowledge, no prior experiments systematically investigating
and comparing the performance of different neural networks trained on the
bitstring of varying length to model parity function are available in the
literature, we performed our own experiments whose results also show that that
neural networks, like simple Recurrent Neural Networks (RNNs) or Long Short-
Term Memory (LSTM), are capable of modelling parity function perfectly on
short bitstrings where the number of bits are less than 100, but it is
intractable for them to learn the parity function when the length of the
bitstrings is generally more than 100 (see section 5.1).

RNN is an umbrella term that incorporates vanilla (simple) RNN, Bidirectional
RNN (BRNN), Gated Recurrent Unit (GRU), LSTM and a wide range of their
variations like the Memory-Augmented RNN (MRNN) that enhances RNNs’ ability on
handling on sequential data with long dependencies [56]. In [56] it was argued
that RNN and LSTM are incapable of processing long time series data that
requires persistent memorization, which is a disadvantage to process long
bitstrings as flipping any single bit alters the parity and furthermore a tiny
error in the memory might incur disastrous repercussion. This discovery aligns
with our results that the longer bitstrings on which the neural networks are
trained, the harder it is for them to learn to model the parity function.

The parity of bitstrings is permutation invariant by its nature, as changing
the order of the bits does not affect the parity. RNNs, despite dependent on
the order of the input, can be regularized towards permutation invariant. [11]
shows that RNNs with regularization applied towards permutation invariance can
simulate correct parity function for the bitstrings whose length is up to 100.
However, our results (see section 5.1) demonstrate that RNN trained on
bitstrings of length 20 can model parity function for the bitstring of any
length, without applying any regularization.

RNN architectures are in theory able to simulate any Turing Machine (TM) [36,
44] given the suitable weights and biases, however the results depend on
unrealistic assumptions such as unlimited computation time and infinite
precision representation of states. In practice finding proper parameters
thought gradient descent algorithms for RNNs is a demanding task due to the
notoriously hard vanishing gradient problem [22]. With the number of bitstring
increasing, the difficulty of the RNN modelling the parity function also
escalates drastically.

Self-Attention network (a.k.a Transformer architectures) [52] underpins many
Natural Language Processing (NLP) applications since its emergence in 2017.
However, [19] has shown strong theoretical limitations of the abilities of the
Self-Attention network on evaluating logical formulas, which is equivalent to
evaluating the parity of bitstrings, and draw an conclusion from asymptotic
results that any transformers will make mistakes on modelling the parity when
the input is sufficiently long.

Recently, researchers from DeepMind considered PonderNet [2] and showed its
ability to modelling the parity function by adaptive computation where the
computation needed is proportional to the complexity of the problem. In their
experiments, the bitstrings contained 96 bits, of which a random number from 1
to 48 are set to 1 or -1s and the remaining bits are set to 0 for training,
and of which a random number from 49 to 96 are set to 1 and the rest are set
to 0 for evaluation. The PonderNet achieved almost perfect accuracy on this
hard extrapolation task, but unlike RNNs that can process the input vectors of
any length through unrolling, it can only be evaluated on the same length of
the input vectors as that of the ones it was trained on. Their experiments
were intended to demonstrate the computational adaptability of the PonderNet
using the parity function as a testbed, rather exhibiting its power on
modelling parity function. But it shows that as the bitstrings become
increasingly complicated, i.e. more 1s or -1s in the bitstring, the
computational resources required to learn the parity increases to the extend
where when the bitstring is sufficiently long, the required resources are
astronomical, if not unobtainable.

Modern computer vision models are capable of classifying images with super
high resolutions [15]. It is a common misbelief that they can also classify
long bitstrings represented by image format as well. There is typically a
robustness inherited in image classification, as the result of the
classification does not vary by slight changes in the input image. However,
flipping a bit completely changes the parity of a bitstring. Thus they are
fundamentally different tasks.

##  4 Different levels of mastery

The goal of an RL agent during training is to cultivate the ability of gaining
maximum rewards in a Markov decision process (MDP) [48]. The performance of an
RL agent is commonly measured in terms of the averaged accumulated rewards it
obtained over a number of episodes or the Elo rating score attached to it,
measuring its competitiveness against other agents. To complement these score-
based measurements, we propose and consider two fundamentally different ways
to assess the extend to which a RL algorithm has learnt to master a game, as
shown in table 1.

Table 1: Two types of optimality Type of Optimality | Description
---|---
Type 1 |  To what extend have the algorithm learnt to make a sequence of good moves in actual game play that lead to winning the game when played from initial position
Type 2 |  To what extend have the algorithm learnt to make good moves in all possible game positions arising from play from the initial position

This leads to two notions of an optimal agent, namely champion and expert,
which are distinguished by their level of mastery on the game, as shown in
table 2. The general complexity results for chess, Go and shogi might only
concern the type 2 notion of optimality.

Table 2: Two Levels of Mastery Mastery Level | Description
---|---
Champion |  A player who is able to always get optimal result against any opponent, when the game is started from the initial position
Expert |  A player who is able to always play the optimal move in any position that can arise by legal play from the initial position

This distinction is vital. The champion might have developed a skill to steer
the game into its comfort zone where it masters the game. The expert agent
always takes the best move on any positions. But in some games it is
essentially impossible to become a champion without also becoming an expert.
It is outside the scope of this paper to systematically prove this claim.
Intuitively, this is because the winning side cannot control the game enough
to steer the game into well know territory. A more rigorous and theoretical
analysis of this issue is left open.

In chess, there is a special discipline called problem chess, where the task
is to solve composed chess problems artificially created, rather than problems
arising from actual competitive play. LCZero is not trained to solve specially
artificial problems and it is not surprising that the program has difficulty
dealing with them [28]. AlphaZero’s successes in chess, shogi and Go were its
ability to learn to play and win games. The task was not to solve problem
positions i.e. find good moves in artificial situations. Thus, AlphaZero
learnability of a game was measured by a champion notion instead of applying
an expert measure.

The champion and expert concepts will be discussed in conjunction with
experimental results in Section 6. We also use an analogy and a crafted nim
board below to expound the distinction between them.

Example 1: Imagine a fighting game where one of the agents can force the
opponent to fight on either the savanna or in the jungle. A champion might be
an expert in savanna fight, but pretty hopeless in the jungle (or visa versa).
Regardless, the champion can win by compelling the combat into the savanna. To
be an expert, the agent needs to master both savanna and jungle fights to win
in any situation it could possibly encounter.

Here is another simple (and rather extreme) example of the relevance of the
two notions from the game of nim.

Example 2: Let $n\in N$ and consider the nim board $[2,1,1,\ldots 1]$ with one
pile with 2 counters, and $n$ piles with $1$ counter where $n$ is large
number, for instance, 100. An agent - even after relatively little training -
become a champion in this game. The agent very fast learns that if their are
two counters in the first pile, it always have to remove either $1$ or $2$
counters from that pile. Thus with only relatively little self play training
the agent becomes an optimal agent of type 1 i.e. a champion, that essentially
learns and memorises the initial two first "opening" moves. But the task of
selecting the best move in a general position $[2,v_{2},v_{3},\ldots,v_{n}]$
with $v_{j}\in\\{0,1\\},j\in\\{2,3,\ldots,n\\}$ is equivalent to evaluating
the parity of $[v_{2},v_{3},\ldots,v_{n}]$. Thus due to difficulty for the
neural network to model the parity function, especially without any serious
incentive to learn to do so, a champion agent for this nim board is not
expected to become an expert agent. Our experiments show that for nim with a
small number of heaps like $n=15$, an agent becomes champion after just 200
epochs of training.

Yet, despite fast becoming a champion it fails to become an expert even after
extensive training with thousands of epochs. The experimental setup and
configuration is shown in section 6.1.

##  5 Preliminary experimental results

Among various types of neural networks we investigated and surveyed in the
section 3 including MLP, RNNs, Self-Attention, PonderNet, RNNs are the only
ones that seem to possess the potential to model perfectly the parity function
through learning by gradient descent and could process the bitstrings of any
length ascribing to its unrolling mechanism. Thus, we designed a range of
experiments aimed to investigate empirically if or to what extend RNNs could
model the parity function from bitstrings and the nimsum function from nim
positions that could possibly arise during actual game play.

###  5.1 Model parity function using value network

We used LSTM as the main component of the value network and discovered that
the single layer LSTM with 128 hidden size trained on the bitstrings of length
20 can simulate a parity function, indicating that there exists a set of
parameters for this LSTM model that enables it to model the parity function.
The architecture of the value network we used is shown below. The bitstrings
are processed by a LSTM layer, followed by a linear layer whose output is then
squeezed to the range between (0, 1) by a sigmoid function.

  1. (1)

Single LSTM layer with 128 nodes

  2. (2)

Linear layer with 1 node

  3. (3)

Sigmoid function

The batch normalization layers [24] are not used in the value network as in
[47] because we found it adversely impacts the performance of the model. We
use Adam [25] optimizer to apply the gradients to the weights of the neural
networks and each gradient calculation consumes 128 bitstrings. All our
experiments in this paper ran on the NVIDIA A100 GPU in High Performance
Computer Cluster 555https://docs.hpc.qmul.ac.uk/.

We conducted a series of experiments investigating the impact of the length of
the bitstrings on the difficulty of value networks to find the right
parameters to model the parity function through gradient descent. All the
training and testing data were generated randomly as in [2]. The value
networks were evaluated on the bitstrings with 10 more bits than these it was
trained on to test its ability on extrapolation tasks and to ensure that the
test data do not overlap with data it has seen in the training. The results
are shown in the Fig. 8. The left graph shows the performance of the model
trained on bitstrings whose length is $h\in\\{20,40,60,80,120\\}$. It is
obvious to see that the difficulty in modelling the parity function rises as
the length of the bitstrings grows.

We also found that the model trained on longer bitstring is more sensitive to
the changes in hyperparamters, like learning rate. As shown in the right graph
in Fig. 8, the value network trained on the bitstrings of length 20 is immune
to varying learning rates, evidenced by the three overlapping lines each of
which shows the prediction accuracy on the bitstrings of length 20. The value
network trained on bitstrings of length 40 is not as impervious to the changes
of the hyper-parameters as these of length 20. The model trained on bitstrings
of length 80 requires significantly higher number of training steps to
converge to the parity function, and the one trained using the learning rate
of 0.0003 and 0.0005 failed at making prediction better than random guess.

It is necessary to note that the amount of data used in the training and the
way they are sampled impinge on the convergence of the model, but the impacts
of these stochasticities and factors are of no significance due to the fact
that we did myriads of experiments with a range of configurations, i.e.
various combinations of different number of LSTM layers and learning rates,
using thousands of GPU hours, out of which the statistically stable properties
emerged. The results shown in these graphs are some of the exemplary among
them. We did not discover any apparent patterns pertaining to the effects of
the size of the training dataset or the impact of learning rates on the
convergence of the model.

Figure 8:  The accuracy of the value network on extrapolation task as the
training progresses. The model was training by 1 million steps in every
experiment, each step consuming 128 bitstrings. The training and testing time
each run takes ranged from 90 to 165 minutes for the bitstrings whose length
ranges from 20 to 120.

As observed from these steep learning curves, the polarity of the performance
of value networks during the training process might indicate that they are not
learning incrementally to simulate the parity function, but in a way likening
epiphany. During training, the neural networks that end up converging to the
parity function experienced two states and the transition is transient, being
either cannot model the parity function at all or can model the parity
function perfectly, resembling how we human learn the parity function. We
suggest that the neural networks before generalization were in the incubation
period in which they were ruling out the incorrect sets of parameters and were
steering the update direction towards uncovering the right one that enables it
to model the parity function. A recent study on generalization of neural
networks over small algorithmic datasets discovered a similar phenomenon and
they dubbed it as "grokking" where the generalization performance of the
neural networks suddenly shoots from random guessing to perfect
generalization, which could also occur long after the presence of overfitting
[35]. We have made some remarks on this phenomenon in section 7.

###  5.2 Learn winning moves using policy networks

AlphaGo, the precursor of AlphaZero, employed a mixed training strategy where
the policy networks were trained in supervised learning from 30 million board
positions obtained from the KGS Go Server, preceding further training by
reinforcement learning (RL) [46]. The policy network was trained on randomly
sampled state-action pairs $(s,a)$ where $s$ is a board state and $a$ is an
action that the experts took on that board position.

An agent might be excellent in evaluating positions that naturally occur in
actual game-play, but might be poor at evaluating “artificial” positions that
cannot arise in practice. One reason could be that the agent follows a policy
that prevents the position to occur. Although applying temperature setting and
the Dirichlet noise to boost the exploration of all the possible legal moves,
some moves might still get lower chance to be tried [47]. Thus the role of the
policy network in nim becomes important for our analysis. When AlphaZero after
being trained plays chess (Go or shogi) it typically garners a collection of
sample trajectories and returns heuristics of the search guided by policy and
value networks. If the search tree fails to branch enough, resulting in that
the critical moves are not explored,(see example 5) in which case we cannot
expect the quality of the search to be reliable. To illustrate the issue,
consider the following example in which the nim positions can be categorized
into 4 classes.

Example 3: Let $n\in N$ be a large number and consider nim positions
$[v_{1},v_{2},v_{3},\ldots v_{n}]$ with $n$ rows, each containing either 0,1
or 2 items. Such positions fall into the following 4 different categories, as
shown in the Table 3.

Table 3: Winning Moves on nim Board Positions Winning Move | Nim Board Positions
---|---
Not exist | even number of heaps with 1, and even number of heaps with 2
remove 2 from heap with 2 | even number of heaps with 1, and odd number of heaps with 2
remove 1 from heap with 1 | odd number of heaps with 1, and even number of heaps with 2
remove 1 from head with 2 | odd number of heaps with 1, and odd number of heaps with 2

The number of search paths through the game tree from such a initial position
is given by $\prod_{j=1}^{n}v_{j}$, which for large values of $n$ becomes
compatibly unfeasible to traverse every path. However, after training the
policy network might have learned to reduce the branching factor, so it mainly
selects one move that has a better chance leading to a winning position out of
the 3 move types at given steps.

In order to investigate if the policy network could output the probability
distribution that is in favor of the winning move on the boards shown in the
example, we considered a supervised classification problem of 3 classes
corresponding to the three classes of nim positions with winning moves
available in the example. The input to the policy network is a won position
$[v_{1},v_{2},…v_{n}]$ i.e. the position is of type 2, 3 or 4 as described in
the above example. Type 1 board positions are not being taken into
consideration as they do not have winning moves. The output would be the type
of the winning move derived from the nim-sum (which is equivalently one of the
type 2, 3 or 4) labelled as 0, 1 or 2. The training and testing data are
randomly generated nim positions that could possibly arise during actual game
play. The architecture of the policy networks consists of one or multiple LSTM
layer(s), a batch normalization layer, a ReLU function, a linear layer with 3
nodes corresponding to the 3 legal moves, and a softmax function, as shown
below.

  1. (1)

LSTM layer(s), each of which contains 128 nodes

  2. (2)

Batch normalization

  3. (3)

A rectifier nonlinearity

  4. (4)

Linear layer with 3 nodes

  5. (5)

Softmax function

Our experiments tested the board positions of the nim with different number of
heaps ($h$), ranging from 7 to 9 and use the policy network with different
number layers ($l$) from 1 to 5, and up to 10 for 9 heaps nim. The training
and testing datasets are evenly balanced across three labels. The results are
shown in the Fig. 10 in which the top 3 plots are the results on training data
and the bottom 3 plots on testing data.

We discovered that in none of the experiments do the policy networks predict
the correct winning moves with more than 80 percent accuracy, showing that the
policy networks fail to model the nim-sum accurately. The performance of
policy networks trained on board positions from 7 heaps nim is consistent,
while the testing accuracy of the policy networks trained on these from 8
heaps is more volatile. The policy network trained on board position of 9
heaps nim cannot predict the winning moves better than a random policy,
showing the difficulty for the policy to model the nim-sum also grows as the
length of the bitstrings increases, which is similar to our findings on value
network.

We did extensive experiments using different number of LSTM layers in attempts
to find a architecture that is capable of modelling the nim-sum, like the LSTM
model that can model perfect parity function in section 5.1, but of no avail.
Thus, we present the results on the policy networks consisting of varying
layers to illustrate this discovery and to show that it occurs among various
network architectures.

(a) $h=7$ heaps

(b) $h=8$ heaps

(c) $h=9$ heaps

(a) $h=7$ heaps

(b) $h=8$ heaps

(c) $h=9$ heaps

Figure 10:  The training and testing performance of the policy network on
$h\in\\{7,8,9\\}$ heaps of nim. $h$ denotes the number of heaps in the game
and $l$ the number of LSTM layers in the policy network. The top 3 plots are
the model accuracy on the training data, and the bottom 3 plots the accuracy
on the testing data. Every policy network was trained one hundred thousand
steps with each step consuming 128 bitstrings. Each run finished within 30
minutes.

The size of the dataset and how the data are generated affect the performance
of the value network, so do they on that of the policy network. It is possible
that using a larger dataset would help the policy network to learn the nimsum
function. However, the state space (i.e. the size of the dataset) in our
experiments was relatively small, and positions were visited many times during
training iterations. One crucial point is to understand that learning nimsum
or parity function - even on smaller boards - is non-monotone. Thus it is not
the case that the policy network gradually increases its knowledge and
steadily improves. Instead, the non-convergence typically manifests itself in
random fluctuations where the performance of the policy network fails to
improve on certain positions, as shown in the learning curves.

##  6 Reinforcement Learning for nim

There exist some open-source implementations of AlphaZero on the GitHub, but
due to the fact that we need some additional functionalities that are not
provided in any of them, for instance calculating the Elo rating of the agent
being trained against its ancestors, evaluating the accuracy of output of the
policy network as the training progresses against the winning move derived
from the nim-sum formula, etc., we implemented the AlphaZero algorithm by our
own in PyTorch [33] for neural network training and Ray [30] for running
simulations in parallel. We made considerable efforts on ensuring our
implementation is in close proximity to the algorithms at granular details as
described in [47, 45], while necessary changes to neural network architectures
tailored to the nim were made, which will be specified in the section 6.1.

###  6.1 Implementing an AlphaZero style algorithm for nim

The AlphaZero algorithm starts training from a clean slate with no specific
game knowledge, besides knowing the rules of the games [45]. Policy network,
value network and MCTS are three pillars of the AlphaZero algorithm. The
policy network outputs a probability distribution over all the actions
$\mathcal{A}$. $P(s,a)$ stands for the prior probability associated with
action $a\in\mathcal{A}$ at state $s$. The probabilities of the illegal
actions are set to zero and the remaining probabilities are re-normalized so
that the summation of all the probabilities remains one. The policy network
narrows down the search to the actions with high probability of leading to a
win position, hence reducing the breath of the search tree. The value network
outputs a scalar value $v\in[-1,1]$ estimating the expected outcome from
position $s$ if following the actions suggested by the policy network. Higher
value of $v$ indicates the current player who is taking move at position $s$
has a higher change to win, and vice versa. The value of the leaf node is
predicted by the value network, without which it can only be known at the end
of the game where it is 1 when the current play won the game or -1 when lost,
whereby effectively reducing the depth the search tree.

The policy and value networks share the LSTM layer, but use two separate
heads, policy head and the value head. We did the experiments on nim of 5, 6
and 7 heaps and tweaked the network architectures and configuration to adapt
to different board sizes. The shared layers of the policy and value network
are one LSTM layer with hidden size of 128 for all three nim games. It is
natural to increase the number of layers as the board size grow, however we
found that larger model is detrimental to the performance and tends to
destabilize the training process. The output of the LSTM layer is then passed
into two heads. The policy head consists of 25, 36 and 48 nodes for 5, 6 and 7
heaps nim respectively, the output of policy head goes into a softmax function
converting these logits into probabilities that sum to 1. The policy head
contains a single node that outputs a scalar value, which goes into a tanh
activation function squeezing it to the range of [-1, 1].

The MCTS starts with the root node of the search tree corresponding to the
current state the player is taking action on. Each node represents a state
encountered in the game play and each edge an action. The tree is constructed
in the course of running a predefined number of simulations, each of which
starts with the root node and ends with a leaf node, following a sequence of
actions selected using the Formula 4 666See the python scripts in the
reinforcement learning folder in our GitHub repository for the implementations
of all the formula used in this section.. We ran a predefined simulations for
each move, and during training we collect 100 episodes of interaction data in
the form of $(s,\pi,r)$ to train the policy network with cross entropy loss
and to train the value network with mean square error.

$a_{t}=\operatorname*{arg\,max}_{a}(Q(s,a)+U(s,a))$ (4)

where $Q(s,a)$ is the averaged action value across simulations calculated by

$Q(s,a)=\frac{1}{N(s,a)}\sum_{s^{\prime}|s,a\rightarrow
s^{\prime}}V(s^{\prime})$ (5)

in which $N(s,a)$ is a counter that records the number of times action $a$ has
been taken from state $s$, $s^{\prime}|s,a\rightarrow s^{\prime}$ denotes that
action $a$ is taken at state $s$ and this simulation terminates at state
$s^{\prime}$, and $V(s^{\prime})$ represents the value of the end state of a
simulation for the perspective of the current player, obtained from either the
value network if $s^{\prime}$ is an intermediate state or the game itself as a
reward if it is a terminal state. The $U(s,a)$ is calculated using

$U(s,a)=c_{put}P(s,a)\dfrac{\sqrt{\sum_{b}{N(s,b)}}}{1+N(s,a)}$ (6)

where the $c_{put}$ is a constant controlling the level of exploration.
AlphaGo [46], AlphaGo Zero [47] and AlphaZero [45] all leave $c_{put}$
unspecified. We found that $c_{put}$ value affects the performance of
AlphaZero on nim significantly because setting it too low discourages the
exploration, while setting it too high weights down the action value,
impairing the effectiveness of the search depth. [51] found setting
$c_{put}=1.5$ yields satisfactory results, but this value along with other
sensible ones like $c_{put}=\\{1,1.5,2,3\\}$ works poorly for nim. We thus
adopted another formula [43] to calculate the $U(s,a)$, as shown below.

$U(s,a)=P(s,a)\cdot\dfrac{\sqrt{\sum_{b}{N(s,b)}}}{1+N(s,a)}\left(c_{1}+\log\left(\dfrac{\sum_{b}{N(s,b)}+c_{2}+1}{c_{2}}\right)\right)$
(7)

where $c_{1}=0.25$ and $c_{2}=19652$. To further encourage the exploration,
Dirichlet noise was added to the prior probability $P(s,a)$ of the root node
where the search begins. The Dirichlet noise is indispensable as it ensures
that the search tree is widely branched, thus avoiding always visiting the
moves with high prior probability.

$P(s,a)\leftarrow(1-\epsilon)\cdot P(s,a)+\epsilon\cdot\eta_{a}$ (8)

where $\eta_{a}$ is sampled from the Dirichlet distribution Dir($\alpha$) in
which $\alpha$ is set to 0.35. $\epsilon$ is constant set to 0.25 during
training. But it is set to 0 during the evaluation to negate the effect of the
Dirichlet noise. The values of $\alpha$ used for chess, shogi and Go are 0.3,
0.15, 0.003 respectively. The alpha value should be in inverse proportion to
the approximate number of legal moves at given positions, as the average
number of legal moves in the nim we run experiments on are less than that of
chess, we opted for higher $\alpha$ value 0.35. Although in theory $\alpha$
should be set to 0.5, but in practice setting $\alpha$ to 0.35 yields better
outcome. The left arrow denotes that the prior probability is reassigned to
the value on the right.

$U(s,a)\propto\dfrac{P(s,a)}{1+N(s,a)}$ (9)

As shown in the equation 9, the $U(s,a)$ is proportional to the prior
probability $P(s,a)$. The visit count $N(s,a)$ in the denominator relatively
enlarges the prior probability on nodes being visited with less frequency in
order to boost exploration. At each state $s$, the action selection is jointly
determined by the action value $Q(s,a)$, the visit count $N(s,a)$ and the
prior probability $P(s,a)$ obtained from the policy network. The action with
lower visit count, higher prior probability and higher value has better chance
to be chosen. Thus, when the policy network fails to assign higher probability
to winning moves, the search is directed to the nodes with less chance of
leading to a winning state, making the search less effective. The problem also
exists for the value network that fails to estimate the correct expected
outcome of the game, resulting in prematurely cutting off the depth of the
search that results in winning state.

After the simulations are finished, the search returns a probability
distribution over all the actions according to the formula 10, from which an
action is sampled to take at board state $s$.

$\bm{\pi}(\textbf{a}|s)=\dfrac{N(s,\textbf{a})^{1/\tau}}{\sum_{b}N(s,b)^{1/\tau}}$
(10)

where $\tau$ is the temperature that changes according to the number of moves
that have been made during game play. We call the $\bm{\pi}(\textbf{a}|s)$
posterior probabilities which are related to the prior probabilities as they
are derived from MCTS simulation partially guided by prior probability from
the policy network. For the first 3 moves, we set the temperature to $\tau=1$
so that the chance of each action being sampled is proportional to its visit
count. For the rest moves of the game, the temperature is set to $\tau=0$,
making the action being taken is the one with the highest visit count. Note
that during the evaluation, the temperature is set to $\tau=0$ for all the
moves.

The policy network serves as the lighthouse that guides the search to moves
with higher chances of winning the game. If it fails to work as intended, the
search is misguided, immensely impacting the effectiveness of the search to
the extent where when the search space is sufficiently large, the MCTS is
equivalent to or worse than brute force search if the policy is skewed towards
lost moves. In addition, the improvement of the policy network relies
completely on the heuristics from the search. Thus, if the policy network is
weak, a vicious cycle is formed where the poor policy misleads the search and
the ineffective search leads to poor improvement of the policy, as will be
shown in section 6.2.2. [13] came up with a policy improvement algorithm in
Gumbel AlphaZero which ensures the heuristic improves the policy network
consistently. However, in that approach the target of the policy improvement
entails the approximation from the value network (see the Section 4: Learning
an Improved Policy in [13] for the details), and due to the parity-related
problems that incapacitate the policy and value network, they still might not
be able to handle nim with large board size.

So far we have argued that various parts of the Alphazero algorithm (e.g.
policy network and value network) have problems learning what would be
required for overall success to master nim. In the next section we present
experiment design and results from the AlphaZero algorithm on nim of varying
board sizes, and the method to evaluate its performance.

###  6.2 Experimental setup and results

In this section, the results along with the detailed configurations of the
experiments are presented. We discovered that the AlphaZero algorithm applied
on nim is sensitive to the selection of the configurations and our selection
of the configurations might not guarantee the best results as there are many
factor affecting the training process as shown in the last section and it is
intractable to try out all the options in the search space, but the
configurations presented here are the ones that gave us the best attainable
results in the experiments we conducted. The policy and value network share
one LSTM layer and have separate heads. They were trained simultaneously on
the experiences (rollout data) collected during the self-play. Besides the
number of nodes in the heads are different to adapt to different action
spaces, the AlphaZero algorithm for the nim with three different number of
heaps uses the same architecture. We choose large number of simulations at
each move and increase it as the number of heaps in the nim grow, not only
because more simulations lead to better heuristic, but they offset the effect
of varying hyperparameters to which the algorithm is sensitive. During both
training and evaluation, each move ran $s=\\{50,60,100\\}$ number of
simulations on nim of $h=\\{5,6,7\\}$ heaps respectively. The simulations ran
on 8 CPUs on parallel. The significantly large number of simulation on 7 heaps
nim is used because we intent to eliminate the possibly negative impact on the
performance of the algorithm brought by insufficient number of simulations
although this incurs hefty computational cost. Each heaps contains odd number
of items. For instance, the initial board of 5 heaps of nim, as shown in Fig.
1, consists of $[1,3,5,7,9]$. Every heap in the actual board is represented by
unitary numbers and each of them is separated by -1:

$[1,-1,1,1,1,-1,1,1,1,1,1,-1,1,1,1,1,1,1,1,-1,1,...,1,1,1]$

Every board position of 5 heaps nim is composed of bitstring of length 29.
Similarly, these of 6 and 7 heaps are composed of bitstrings of length 41 and
55. The state spaces of 5, 6, 7 heaps nim are 3840, 46080 and 645120 and the
action space of them are 25, 36, 49, respectively. In average, the number of
moves, if taken randomly by two players, for the 5 heaps nim is 10, for 6
heaps 13 and for 7 heaps 16.

####  6.2.1 Elo rating measurement

Elo rating, commonly used in chess, is an approach of ranking the players for
multiplayer games in terms of their competitiveness. AlphaZero adopted the Elo
rating score to evaluate its performance against other algorithms or programs
like AlphaGo Zero and AlphaGo Lee and Stockfish. Unfortunately, no existing
nim agent with attached Elo rating reflecting its competitiveness is
available. Thus, we opted for a variation of self-play Elo rating [51] as an
approach to measure the relative strength of an agent and monitor the training
progress, in which the relative strength of an agent is evaluated in
comparison with all its ancestors whose rating is updated every time a new
trained agent joins in to ensure that the attached rating reflects their
competitiveness. The Elo rating is measure of champion in terms of its ability
to defeat other players.

In our self-play Elo rating system, every new agent is assigned with a initial
score, 1000. At the end of each training iteration, the trained agent is saved
into a reservoir of the agents that have been trained preceding it, and its
Elo rating is calculated against all the trained agents hoarded in the system.
The agent being trained is denoted as Player A and its opponent who is one of
its predecessors as Player B. Both of them have an expected score representing
their probability of winning the match, calculated by this formula for Player
A:

$E_{A}=\dfrac{1}{1+10^{(R_{B}-R_{A})/400}}$ (11)

Analogously, the expected score for player B is calculated by

$E_{B}=\dfrac{1}{1+10^{(R_{A}-R_{B})/400}}$ (12)

There is only one of two possible outcomes of the match for player A, being
either won or lost. For nim, the drawing situation does not exist. If player A
won the game, its Elo rating is updated by

$R_{A}=R_{A}+K(1-E_{A})$ (13)

where K is called K-factor. The K value is usually set to 16 for masters
(strong players) and 32 for novices (weak players). In our setting, the K
value for the players who have engaged in the tournaments beyond 20 time is
set to 32, and otherwise 16 due to the consideration that the more times a
player engages in matches, the more accurately the Elo ratings reflect its
strength and hence the higher K value should be. The updated Elo rating for
player B is

$R_{B}=R_{B}+K(0-E_{B})$ (14)

This approach is self-contained, not relying on any external program. The
limitation of this method is that the Elo rating is contained and only
measures the performance of the agent against its predecessors, meaning that
it should not be compared with the rating of the agents outside the group.
However, the ratings can be used as an indicator of the performance of the
agents and a baseline for the future research as well.

We monitored the self-play Elo rating of the AlphaZero agent on nim of 5, 6
and 7 heaps. As shown in the Fig. 11, the self-play Elo rating of the agent
being trained grows as the training progresses, indicating it is being more
competitive. The AlphaZero agent for 5 heaps nim grew rapidly since the
commence of the training. In comparison, the growth of the agent on nim of 6
is relatively slow and that of the nim of 7 heaps is stagnant after 420
iterations, showing that while the agent is being more competitiveness and on
the path towards becoming a champion, there seems like a ceiling of its
competitiveness that is hard to crack. This bottleneck, as shown in the next
section, is caused by inability of the policy and value networks on nim.

Figure 11:  The self-play Elo rating score of the agent being trained on nim
of 5, 6 and 7 heaps respectively, calculated at the end of every training
epoch against all the agents archived in the pool. Calculating the Elo rating
during training takes huge amount of time. Our program ran roughly 200 hours
with the above-mentioned configurations to obtain the results for the 7 heaps
nim.

####  6.2.2 Performance of policy and value network

To examine if the agent is capable of being an expert agent on the nim, we
devised two accuracy measurements on the policy and value network. The action
probability distribution yielded by the policy network should bias towards the
moves that have higher chance leading to winning the game. In nim, the winning
moves can be calculated by nim-sum, according to which the accuracy of the
policy network is evaluated by comparing the accuracy of the most probable
moves against the winning moves. The same policy measurement was also used in
[13] as Policy Top 1 Accuracy where the top 1 refers to the move with the
highest probability.

The AlphaZero policy is measured against a random policy. As shown in the Fig.
12, the AlphaZero policy surpasses the random policy by a significant margin
on the 5 heaps nim, but the advantage diminishes on larger board size. The
Alphazero policy on 7 heaps nim is tantamount to the random policy, which is
due to the fact that the inaccurate policy results in poor heuristic which in
turn leads to poor policy improvement. It is undoubtedly true that as more
heap is added to the game, the growing action space is one important factor
that complicates learning the winning moves for the policy network. However,
recall from section 5.2 that even when the size of the action space remains
unchanged, the policy networks still face increasing difficulty as more heaps
are added.

(a) $h=5$ heaps

(b) $h=6$ heaps

(c) $h=7$ heaps

Figure 12:  The accuracy of the policy network measured against the winning
moves on nim of 5, 6 and 7 heaps. The AlphaZero policy is more superior than
the random policy on smaller board, but as the board size grows the accuracy
of the policy drops drastically to the extent where it is equivalent to a
random policy on 7 heaps nim.

The value network yields the estimated outcome of the game at given positions
when following the move suggested by the policy network. In the nim, the won
positions are the ones where the winning move exists. According to this
property, we monitor the accuracy of the value network. All the possible board
positions that could arise from the initial board position of 5 heaps nim are
evaluated, but due to the large state space of 6 and 7 heaps, the evaluation
is conducted on 10000 randomly sampled board positions. The prediction is
considered to be correct if the value network outputs a positive number on won
position and a negative number on lost position. The accuracy of the value
network is shown in the Fig. 13. As the number of heaps increases, so does the
state space and the board size, the value network was facing rising hindrance
in precisely evaluating of the board positions. The value network on 7 heaps
nim barely outperforms random guessing. This result aligns with that of the
experiment shown in section 5.1.

Figure 13:  The accuracy of the value network on nim of 5, 6 and 7 heaps. The
accuracy on the board positions of 5 heaps nim rises constantly and reaches 90
percent at 500 training iteration. The accuracy on the board positions of 6
heaps nim exceeds 60 percent, but that on the ones of the 7 heaps nim
fluctuates near 50 percent.

The policy network learns from the heuristics $\bm{\pi}(\textbf{a}|s)$ derived
from the MCTS, as shown in Formula 10. The value network learns from the
actual game output. To probe how policy and value network fits in the targets,
we keep track of the training loss for each of them during the training
process, and as shown in the Fig. 14. It is salient that both value and policy
network are able to gradually fit in the targets, empowering the agent to be
increasingly competitive. However, the difficulties for the policy network to
digest the heuristic and for the value network to model the expected outcome
of the game grow as the board size increases, which is a major problem that
impedes the agent to become an expert.

Figure 14:  The loss of the policy network (left) and the loss of the value
network (right) on nim of 5, 6 and 7 heaps. It occurs to both neural networks
that the larger the board size grows, the harder it becomes for them to fit in
the heuristic from the MCTS.

The gradually dropping loss of both policy network and network network,
coupled with the rising Elo rating of the agents, indicates the agent is
learning to become an champion. However, the dropping accuracy of the policy
and value network as the size of the board grows shows that it is tremendously
challenging for the agent to become an expert. On 7 heaps nim, the policy and
value network could memorize the heuristics from the MCTS and actual outcome
at the end of the game. But they merely enable the agent to become more
competitive in comparison with its ancestors, and cannot guide the MCTS
effectively to form a positive improvement loop. This illustrate our general
finding that on large boards nim, and impartial games in general is a
challenge for reinforcement learning algorithms.

####  6.2.3 Analysis of AlphaZero on nim positions

(a)

Move |  e9 |  a1
---|---|---
Winning Move |  yes |  no
Prior Probability |  97.9% |  1.9%
Win Probability |  99.5% |  5.0%
V-value |  0.97 |  -0.89
(b)

Figure 15:  The policy and value network accurately evaluate the initial
position of the 5 heap nim, assigning 97.9% prior probability and 99.5%
winning probability to the winning move e9. The move with the second highest
prior probability is a1 that is assigned with 5.0% winning probability.

The graphs and analysis in the previous sections provide a high level overview
of the performance of the algorithm on nim with different number of heaps. In
this section, we will evaluate the performance of the algorithm on the initial
board position along one of the intermediate positions from 5, 6 and 7 heaps
nim, like we did in section 2 where the statistics of the algorithms on some
chess positions by LC0 are obtained and analysed.

On the positions of 5 heaps nim, the policy and value network after training
strongly favors a few moves over the remaining ones, significantly improving
the effectiveness of the search. However, this overly confidence could bring
catastrophic consequence that cannot be restored if it is not well grounded.
On a position in 6 heaps nim where the policy network assigned the top 4 prior
probabilities to 4 losing moves, as it is not obsessed with any particular
move and with the assistance with the value network that evaluates the
majority of the next positions correctly, the algorithm converges to a winning
move. On the initial position of a 7 heaps nim, the policy and value network
fails in providing any constructive guidance that benefits the search.

The analysis on the initial position of a 5 heaps nim from the results of the
trained model is shown in the Fig. 15. All the values are calculated from the
perspective of the player who is making the move on these positions. Each move
is represented by a letter and a digit where the letter is the label to the
heap and the digit denotes the number of counters the move removes from this
heap. For instance, the move e9 is removing 9 counters from the heap labelled
as e. The policy network assign 97.9% prior probability to the winning move,
e9 and the value network accurately estimate the resulting position of taking
e9 is advantageous to the current player.

However, on a intermediate position similar to the initial position as shown
in LABEL:pos:5heaps_2, the search is misled by the policy network that is
obsessed with the losing e8 move as the prior probability assigned to the move
is 97.4% which is overwhelmingly larger than that of other moves. This leads
to the misfortune that the winning move still is rejected after 4 million
simulations even though the value network predicts the value of the position
after e8 accurately.

(a)

Move |  e8 |  b1 |  a1 |  d4
---|---|---|---|---
Is Winning Move |  no |  no |  no |  no
Prior Probability |  97.4% |  0.7% |  0.4% |  0.2%
Win Probability |  0.14% |  5.6% |  12.5% |  9.8%
V-value |  -0.99 |  -0.88 |  -0.74 |  -0.80
(b)

| Number of simulations
---|---
Winning Move | 64 | 256 | 1024 | 65536 | 4194304
e7 | 1.56% | 0.39% | 0.09% | 0.0015% | 0.00021%
(c)

Figure 16:  The only winning move available in this position is e7. The policy
network offers completely wrong estimation. The move e8, a losing move, is
assigned with 97.4% prior probability. Albeit the value network predicts the
resulting position of taking e8 is disadvantageous for the current player with
high confidence, the algorithm fails to find out the winning move after more
than 4 million simulations.

For the initial position of the 6 heaps nim as shown in LABEL:pos:6heaps_1,
the policy network strongly promotes the winning move b2, and the value
network also evaluates the resulting positions correctly with high confidence.

(a)

Move | b2 | a1 | b1 | d6
---|---|---|---|---
Winning Move | yes | no | no | no
Prior Probability | 92.8% | 4.0% | 0.64% | 0.63%
Win Probability | 78.0% | 14.3% | 4.76% | 2.17%
V-value | 0.56 | -0.71 | -0.90 | -0.95
(b)

Figure 17:  The policy and value network succeeds in predicting the winning
move and estimating the resulting position. The probability assigned to the
winning move b2 exceeds the second largest probability which is assigned to
move a1 by a large margin.

There are also positions with 6 heaps where the policy and value network both
stumbled, one of which is shown in LABEL:pos:6heaps_2. However, unlike the
situation with a 5 heaps nim position as shown in Fig. 16, the prior
probabilities assigned to the these winning moves are not high enough to
completely mislead the search. As shown in the table LABEL:tab:heaps6_2, the
winning move f10 is identified by the MCTS after 65536 simulations and the
posterior probability of choosing it increases as more simulations were
conducted.

(a)

Move | f3 | f2 | f4 | f9
---|---|---|---|---
Winning Move | no | no | no | no
Prior Probability | 47.4% | 12.6% | 10.1% | 7.5%
Win Probability | 0.18% | 1.03% | 0.03% | 81.2%
V Value | -0.99 | -0.97 | -0.99 | 0.62
(b)

| Number of simulations
---|---
Winning Move | 64 | 256 | 1024 | 65536 | 4194304
f10 | 4.68% | 1.17% | 0.29% | 53.7% | 99.1%
(c)

Figure 18:  In this position, the only winning move is f10. However, the top 4
probabilities yielded by the policy network are all assigned to losing moves,
causing the algorithm fail to find the winning even after more than 1000
simulations. Fortunately, the value network predicts with high confidence that
the resultant positions from move f3, d2 and f4 are in favor of the opponent
of the current player, making the winning move f10 stand out after 65536
simulations and the confidence is boosted with more simulations.

The initial position of the 7 heaps nim as shown in the Fig. LABEL:pos:7heaps,
the prior probability by the policy network are almost equal for all the
moves, being either winning or losing move. The value network evaluates all
the resulting positions as having around 50% winning probability. These
predictions apparently contribute nothing to the search to the extent where
the winning moves are not recognized by the MCTS after more than 4 million
simulations.

(a)

Move | c4 | c3 | c2 | c5
---|---|---|---|---
Winning Move | no | no | no | no
Prior Probability | 4.37% | 4.06% | 3.95% | 3.88%
Win Probability | 50.1% | 49.5% | 48.9% | 50.1%
V Value | 0.003 | -0.009 | -0.02 | 0.003
(b)

| Number of simulations
---|---
Winning Move | 64 | 256 | 1024 | 65536 | 4194304
e7 | 1.56% | 1.17% | 1.26% | 2.79% | 0.38%
f7 | 1.56% | 0.17% | 1.66% | 0.89% | 1.15%
g11 | 1.56% | not visited | 1.07% | 1.61% | 0.65%
(c)

Figure 19:  The 4 moves with the highest prior probabilities are losing moves,
and the policy network does not particularly favor any of them. The evaluation
from the value network on these positions is near 0, showing they all have 50%
winning probability.

In nim with 5, 6 and 7 heaps, there are positions where the policy and value
networks succeed and positions where they fail. In general the confidence of
choosing the winning move decreases and the difficulty in accurately
evaluating positions increases as the board size (and state-space) grows.

On relatively small boards, the parity issues pertaining to compute the
correct nimsum do not get involved as calculating the parity is feasible, as
shown in 5.1. Learning nim on larger boards is dramatically more difficult
because finding the right move and correctly evaluating large board positions
is parity related, and the huge state space forces the policy and value
network to generalize to unseen states, which as we have argued poses a
fundamental challenge to RL algorithms.

##  7 Concluding remarks and conjectures

The AlphaZero paradigm can be seen as part of a larger ambition to build
intelligent systems that can learn to solve complex tasks by themselves. The
ambition, as articulated by Demis Hassabis, the CEO of Deep Mind, is to solve
intelligence and then use it to solve everything else [41]. While this
ambition is truly inspiring, the results in this paper remind us that thinking
- even in strategy games - varies fundamentally in nature. General AI will
need to handle different modes of thinking.

From a human perspective, games like chess, Go, and shogi somehow feel
distinct from nim and impartial games. From a human point of view, the former
games have clear criteria for good play. Progress in learning these games is
typically incremental, and pattern recognition plays a central role. On the
contrary, nim can be mastered by humans but through an entirely different
thought process and analysis. Learning nim typically happens in non-
incremental steps (like was the case for our LSTM learning experiments
discussed in section 5.1). It seems inconceivable that a human could learn to
master nim on a large board without also having solved the game for any board
size. Thus, when humans master nim, transfer learning and abstract
generalisation play an important role.

AlphaZero has been truly groundbreaking, but new ideas are needed to expand
reinforcement learning to games that, like nim seem to require high-level non-
associative thinking. For humans, counting is a straightforward process. Even
young children understand that the number of objects is an invariant, so
recounting should (in principle) lead to the same number. In mathematics, this
principle is referred to as the pigeon-hole principle; however, as we
explained, such basic counting principles require a kind of insight that seems
challenging for AIs to develop solely one their own.

We acknowledge that parity is a well-known nuisance for neural networks,
trivial to compute but loved by theoreticians to bang NN engineers over the
head. The motivation of our work is not to bang anyone on their head, but to
understand how the AlphaZero paradigm can be expanded. The concept of self-
play in model based AI is just one way an agent can learn by "exploring
around". However, to fully understand this, it is essential to understand the
actual way self-play NN-based RL algorithms learn. This is why we looked
carefully and closely at the way the AlphaZero clone LC0 played chess. And it
is why this paper on impartial games might help navigate further research on
expanding AlphaZero style learning.

Parity-related problems occur naturally for a large class of combinatorial
games. However, we discovered that the difficulty of learning to master these
games is much more dramatic than just learning parity. The problem is robust
and tenacious, and fiddling with the hyperparameters of the algorithm does not
seem to have much effect. We did break down the AlphaZero style algorithm and
checked the various components separately. And we even tested the parity
issues with novel architectures that were not part of the original AlphaZero
algorithms.

There are many factors impacting the performance of our AlphaZero style nim
algorithm. There is an unlimited number of settings so it is impossible to try
all of them out. Proving the results rigorously seems well outside current
theoretical techniques. From a philosophy of science perspective, one can
always object that a specific pattern might fail at values not tested. If such
objections were taken seriously, science would be impossible. Consider
experiments suggesting some formula e.g. $F=ma$. It is always (logically)
possible that the formula would seriously fail for values not tested. It is
always possible to make this kind of objection to an experimental result.
Experimental results should always seen as part of a wider theory and
understanding that is aligned with experiments but in principle could be
falsified [34].

We anticipated that nim would be practically unlearnable by AlphaZero style
algorithms on boards with 50+ heaps. However, to our surprise, the practical
upper bound of the learnability was much lower than we expected, as the
algorithms experienced substantial limitations already with seven heaps. Our
work also shows there is an issue when attempting to applying NNs (e.g.
Stockfish NNUE style NN) to guide the search in the new algorithms [31, 28]
for impartial game, due to the difficulty of the networks guiding the search.

Another point we would like to stress is that the difficulty of learning nim
on small boards is not even due to parity issues. The parity required to
compute correct nim sums etc has not kicked in on small boards as learning
parity for small values of n, (e.g. $n=7$ for 7 piles) is, as our experiments
showed, pretty feasible. On the board $[1,3,5,7,9,11,13]$ we established that
no positive feedback loop occurs and the policy and value network essentially
both drift around without the ability to learn anything besides memorizing
some heuristics derived from MCTS. And remarkably,at least with the resources
we had available, this happened despite that the state space is relatively
small and most states will be seen multiple times during training if the all
the positions are fully explored. On larger boards, where the state space
exceeds any number of states that feasibly can be reached during training, the
value and policy network needs to generalise to unseen positions. Failing to
generalise adds additional noise to the learning as the evaluation on some
positions becomes random and uncorrelated with correct values, preventing the
positive feedback mechanism of RL from functioning properly. Added to this
difficulty, on larger boards the difficulty of learning the parity function
also kicks in an already very noisy situation.

AlphaZero employs a strategy that combines evaluation with search guided
calculation. However, some of aspects of impartial games seem to require
mathematical thinking guided by abstract, symbolic reasoning. Some PSPACE-
complete impartial games, e.g. node kayles and geography, can mimic NP-hard
problems which are intractable. Thus any algorithm that could learn any of
these games to perfection would be able break current cryptography. However,
other impartial games can be solved by mathematical reasoning. Thus, it is
possible to express optimal strategies in simple mathematical terms, e.g.
sprout that has been analysed to a deep level might eventually be solvable by
AI with sufficient built-in reasoning abilities.

Despite the success of AlphaZero, our work has shown that fundamentally new
ideas are needed for an AlphaZero style approach to be successful for
impartial games. When humans learn to master nim, they might scribble on a
piece of paper, play around with small toy examples, form conjectures etc.
Maybe, it is possible to apply AlphaZero style reinforcement learning in an
extended setting that takes auxiliary actions external to the game into
account, such as applying abstract transformations, or reading and writing to
an external memory. These meta-actions, analogous to the actions the algorithm
takes during simulations, are not directly linked to the move it makes but
significantly boost its ability to plan forward. The results in this paper
indicates that new ideas will be needed to make such ideas work.

## Acknowledgment

This work was funded by the Chinese Scholarship Council (CSC). We appreciate
the assistance of ITs Research team at the University of Queen Mary for
supporting us in using the Apocrita HPC facility. Finally, we would like to
thank the Leela Chess Zero development team for providing detailed
instructions for the use and workings of LC0.

## References

  * [1] Hiroyuki Adachi, Hiroyuki Kamekawa and Shigeki Iwata  “Shogi on n$\times$ n board is complete in exponential time”  In _Trans. IEICE_ 70, 1987, pp. 1843–1852
  * [2] Andrea Banino, Jan Balaguer and Charles Blundell  “PonderNet: Learning to Ponder”  In _arXiv preprint arXiv:2107.05407_ , 2021
  * [3] Paul Beame and Søren Riis  “More on the relative strength of counting principles”  In _Proof complexity and feasible arithmetics_ 39, 1998, pp. 13–35
  * [4] Piotr Beling and Marek Rogalski  “On pruning search trees of impartial games”  In _Artificial Intelligence_ 283 Elsevier, 2020, pp. 103262
  * [5] Elwyn R Berlekamp, John H Conway and Richard K Guy  “Winning ways for your mathematical plays, volume 1”  AK Peters/CRC Press, 2001
  * [6] Elwyn R Berlekamp, John H Conway and Richard K Guy  “Winning ways for your mathematical plays, volume 2”  AK Peters/CRC Press, 2002
  * [7] Elwyn R Berlekamp, John H Conway and Richard K Guy  “Winning ways for your mathematical plays, volume 3”  AK Peters/CRC Press, 2003
  * [8] Elwyn R Berlekamp, John H Conway and Richard K Guy  “Winning ways for your mathematical plays, volume 4”  AK Peters/CRC Press, 2004
  * [9] Charles L Bouton  “Nim, a game with a complete mathematical theory”  In _The Annals of Mathematics_ 3.1/4 JSTOR, 1901, pp. 35–39
  * [10] Tristan Cazenave et al.  “Polygames: Improved zero learning”  In _ICGA Journal_ IOS Press, 2020, pp. 1–13
  * [11] Edo Cohen-Karlik, Avichai Ben David and Amir Globerson  “Regularizing Towards Permutation Invariance in Recurrent Models”  In _arXiv preprint arXiv:2010.13055_ , 2020
  * [12] RI Damper  “Parity still isn’t a generalisation problem”  In _Behavioral and Brain Sciences_ 21.2 Cambridge University Press, 1998, pp. 307–308
  * [13] Ivo Danihelka, Arthur Guez, Julian Schrittwieser and David Silver  “Policy improvement by planning with Gumbel”  In _International Conference on Learning Representations_ , 2021
  * [14] Stefan Dantchev and Søren Riis  “" Planar" tautologies hard for resolution”  In _Proceedings 42nd IEEE Symposium on Foundations of Computer Science_ , 2001, pp. 220–229  IEEE
  * [15] Alexey Dosovitskiy et al.  “An image is worth 16x16 words: Transformers for image recognition at scale”  In _arXiv preprint arXiv:2010.11929_ , 2020
  * [16] Aviezri S Fraenkel and David Lichtenstein  “Computing a perfect strategy for n$\times$ n chess requires time exponential in n”  In _International Colloquium on Automata, Languages, and Programming_ , 1981, pp. 278–293  Springer
  * [17] Leonardo Franco and Sergio A Cannas  “Generalization properties of modular networks: implementing the parity function”  In _IEEE transactions on neural networks_ 12.6 IEEE, 2001, pp. 1306–1313
  * [18] Martin Gardner  “Mathematical games: Of sprouts and brussels sprouts; games with a topological avor”  In _Scientific American_ 217.1, 1967, pp. 112–115
  * [19] Michael Hahn  “Theoretical limitations of self-attention in neural sequence models”  In _Transactions of the Association for Computational Linguistics_ 8 MIT Press, 2020, pp. 156–171
  * [20] Armin Haken  “The intractability of resolution”  In _Theoretical computer science_ 39 Elsevier, 1985, pp. 297–308
  * [21] Johan Håstad  “Computational limitations of small-depth circuits”, 1987
  * [22] Sepp Hochreiter and Jürgen Schmidhuber  “Long short-term memory”  In _Neural computation_ 9.8 MIT Press, 1997, pp. 1735–1780
  * [23] Myron E Hohil, Derong Liu and Stanley H Smith  “Solving the N-bit parity problem using neural networks”  In _Neural Networks_ 12.9 Elsevier, 1999, pp. 1321–1323
  * [24] Sergey Ioffe and Christian Szegedy  “Batch normalization: Accelerating deep network training by reducing internal covariate shift”  In _International conference on machine learning_ , 2015, pp. 448–456  PMLR
  * [25] Diederik P Kingma and Jimmy Ba  “Adam: A method for stochastic optimization”  In _arXiv preprint arXiv:1412.6980_ , 2014
  * [26] Nathan Linial, Yishay Mansour and Noam Nisan  “Constant depth circuits, Fourier transform, and learnability”  In _Journal of the ACM (JACM)_ 40.3 ACM New York, NY, USA, 1993, pp. 607–620
  * [27] Derong Liu, Myron E Hohil and Stanley H Smith  “N-bit parity neural networks: new solutions based on linear programming”  In _Neurocomputing_ 48.1-4 Elsevier, 2002, pp. 477–488
  * [28] Shiva Maharaj, Nick Polson and Alex Turk  “Chess AI: Competing Paradigms for Machine Intelligence”  In _arXiv preprint arXiv:2109.11602_ , 2021
  * [29] John McCarthy  “A tough nut for proof procedures”  Stanford University Stanford, CA, USA, 1964
  * [30] Philipp Moritz et al.  “Ray: A distributed framework for emerging $\\{$AI$\\}$ applications”  In _13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)_ , 2018, pp. 561–577
  * [31] Yu Nasu  “Efficiently updatable neural-network-based evaluation functions for computer shogi”  In _The 28th World Computer Shogi Championship Appeal Document_ , 2018
  * [32] Richard J Nowakowski  “Games of no chance”  Cambridge University Press, 1998
  * [33] Adam Paszke et al.  “Pytorch: An imperative style, high-performance deep learning library”  In _Advances in neural information processing systems_ 32, 2019
  * [34] Karl R Popper  “Objective knowledge”  Oxford University Press Oxford, 1972
  * [35] Alethea Power et al.  “Grokking: Generalization beyond overfitting on small algorithmic datasets”  In _arXiv preprint arXiv:2201.02177_ , 2022
  * [36] Mohammed Al-Rawi  “A neural network to solve the hybrid N-parity: Learning with generalization issues”  In _Neurocomputing_ 68 Elsevier, 2005, pp. 273–280
  * [37] Kenneth Wingate Regan and Guy McCrossan Haworth  “Intrinsic chess ratings”  In _Twenty-fifth aaai conference on artificial intelligence_ , 2011
  * [38] Søren Riis  “A complexity gap for tree resolution”  In _Computational Complexity_ 10.3 Springer, 2001, pp. 179–209
  * [39] Søren Riis  “Independence in bounded arithmetic.”, 1994
  * [40] John Michael Robson  “The complexity of Go”  In _Proc. 9th World Computer Congress on Information Processing, 1983_ , 1983, pp. 413–417
  * [41] Matthew Sadler and Natasha Regan  “Game Changer”  In _AlphaZero’s Groundbreaking Chess Strategies and the Promise of AI. Alkmaar. The Netherlands. New in Chess_ , 2019
  * [42] Thomas J Schaefer  “On the complexity of some two-person perfect-information games”  In _Journal of Computer and System Sciences_ 16.2 Elsevier, 1978, pp. 185–225
  * [43] Julian Schrittwieser et al.  “Mastering atari, go, chess and shogi by planning with a learned model”  In _Nature_ 588.7839 Nature Publishing Group, 2020, pp. 604–609
  * [44] Hava T Siegelmann and Eduardo D Sontag  “On the computational power of neural nets”  In _Journal of computer and system sciences_ 50.1 Elsevier, 1995, pp. 132–150
  * [45] David Silver et al.  “A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play”  In _Science_ 362.6419 American Association for the Advancement of Science, 2018, pp. 1140–1144
  * [46] David Silver et al.  “Mastering the game of Go with deep neural networks and tree search”  In _nature_ 529.7587 Nature Publishing Group, 2016, pp. 484–489
  * [47] David Silver et al.  “Mastering the game of go without human knowledge”  In _nature_ 550.7676 Nature Publishing Group, 2017, pp. 354–359
  * [48] David Silver, Satinder Singh, Doina Precup and Richard S Sutton  “Reward is enough”  In _Artificial Intelligence_ 299 Elsevier, 2021, pp. 103535
  * [49] Jiri Sima and Pekka Orponen  “General-purpose computation with neural networks: A survey of complexity theoretic results”  In _Neural Computation_ 15.12 MIT Press, 2003, pp. 2727–2778
  * [50] Chris Thornton  “Parity: the problem that won’t go away”  In _Conference of the Canadian Society for Computational Studies of Intelligence_ , 1996, pp. 362–374  Springer
  * [51] Yuandong Tian et al.  “Elf opengo: An analysis and open reimplementation of alphazero”  In _International Conference on Machine Learning_ , 2019, pp. 6244–6253  PMLR
  * [52] Ashish Vaswani et al.  “Attention is all you need”  In _Advances in neural information processing systems_ , 2017, pp. 5998–6008
  * [53] JULIEN LEMOINE-SIMON VIENNOT  “A further computer analysis of sprouts”, 2007
  * [54] Bodgan M Wilamowski, David Hunter and Aleksander Malinowski  “Solving parity-N problems with feedforward neural networks”  In _Proceedings of the International Joint Conference on Neural Networks, 2003._ 4, 2003, pp. 2546–2551  IEEE
  * [55] David J Wu  “Accelerating self-play learning in go”  In _arXiv preprint arXiv:1902.10565_ , 2019
  * [56] Jingyu Zhao et al.  “Do rnn and lstm have long memory?”  In _International Conference on Machine Learning_ , 2020, pp. 11365–11375  PMLR