text:
\section{Introduction}
\label{sec:intro}

The AlphaZero algorithm and its variations have been highly successful in producing high-quality moves in complex strategy games, including chess, Go, and shogi \cite{silver2017mastering,silver2018general,schrittwieser2020mastering}. 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 \cite{sadler2019game}.
This sentiment is expressed by former chess world champion Garry Kasparov who wrote {\it 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 \cite{sadler2019game} {\it 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 \cite{cazenave2020polygames}. 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 \cite{wu2019accelerating}. The open-source Go project Elf is also worth mentioning \cite{tian2019elf}.

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 \cite{berlekamp2001winning,berlekamp2002winning,berlekamp2003winning,berlekamp2004winning}. 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 \cite{berlekamp2001winning,berlekamp2002winning}. 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 \cite{berlekamp2001winning}. 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 \textit{e.g.} node kayles and geography that are PSPACE complete \cite{schaefer1978complexity}), 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 \cite{bouton1901nim, nowakowski1998games}. 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 \textit{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. \ref{fig:nim_board} demonstrates an example of an initial nim board, a board positions during play and the final board position.

\begin{figure}[h]
\centering
\includegraphics[width=0.8\textwidth]{figures/Nim_board.eps}
\caption{\label{fig:nim_board} The initial board consists of a series of heaps (\textit{aka} rows or piles) of counters (\textit{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. }
\end{figure}

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 \footnote{In 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, \textit{i.e.}, the sum (in binary), neglecting all carries from one digit to another \cite{bouton1901nim}. Within combinatorial game theory this is commonly referred to the \textit{nim-sum} (see \ref{sec:Impartial games} 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 {\it the statistical neutrality} of the parity function \cite{thornton1996parity} 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 \textit{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 \textit{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:

\begin{enumerate}[label=(\arabic*), noitemsep]
    \item The policy network is unable to guide the MCTS better than random \label{enu:one}
    \item The value network is unable to evaluate a position better than random \label{enu:two}
\end{enumerate}

According to \ref{enu:one}, the network essentially cannot learn to select relevant candidate moves necessary to identify winning or high-quality moves.
According to \ref{enu:two}, 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 \ref{enu:one} and \ref{enu:two}
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 \textit{e.g.} Dawson's chess that in effect is a impartial game in disguise \cite{berlekamp2001winning}.

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:
\begin{itemize}[noitemsep]
    \item Identify a class of strategic games that require nontrivial modifications of AlphaZero style algorithms or in general current RL algorithms to work.
    \item 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 \ref{sec:value_network}), the policy network (see example 3 in section \ref{sec:policy_network}) or the parity-related issue (see section \ref{sec:low_complexity}) 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 \ref{sec:conclusion}).
    \item Propose two levels of mastery of a RL agent, champion and expert, which are essential in evaluating the performance of an agent (see section \ref{sec:differnt}). To the best of our knowledge these concepts are not mentioned in the literature.
    \item 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.
    \item Briefly outlining of how one might expand the AlphaZero paradigm approach for future algorithms.
\end{itemize}

The paper is structured as follows. In section \ref{sec:revisiting_alphazero} 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 \ref{sec:background} 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 \ref{sec:differnt}, 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 \ref{sec:prelimiary}, 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 \ref{sec:reinforcement_learning}, 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.\footnote{The code for the experiments in this paper is publicly available at: \url{https://github.com/sagebei/Impartial-Games-a-Chanllenge-for-Reinforcement-Learning}}

\section{Revisiting AlphaZero and LCZero}
\label{sec:revisiting_alphazero}
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. LCZero\footnote{version: 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 \cite{maharaj2021chess}, 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) \cite{nasu2018efficiently} 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 \ref{sec:results} 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 \cite{regan2011intrinsic}. 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 \cite{sadler2019game}. AlphaZero's use of its policy network, its evaluation networks and MCTS were explained by a detailed analysis of the position in Fig. \ref{fig:LC0}. 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 \footnote{More 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.

\begin{figure}[H]
 \label{fig:LC0}
    \centering
    \subfloat[chess board position]{
        \newgame
        \fenboard{r1b2qk1/1pp3rp/4pnp1/1PP5/p2PBp2/P7/1BQ2P2/K1R1R3 w - - 0 1}
        \scalebox{0.7}{\showboard}
    }
    \hspace{1em}
    \subfloat[Prior probabilities for the top moves]{
        \begin{tabular}{lcccccccc}
        \toprule
        \textbf{Move}  &  \bishop d3 & \bishop f3 & c6 & d5 & \bishop g2 & f3 & \bishop h1 & \queen c4\\
        \midrule
        \textbf{Prior prob (AlphaZero)} & 29.77\% & 18.82\% & 16.15\% & 10.21\% & 4.75\% & 3.5\% & 4.75\% & 1.2\% \\
        \midrule
        \textbf{Prior prob (LCZero)} & 6.01\% & 12.36\% & 16.27\% & 23.13\% & 1.74\%  & 3.73\% & 1.41\% & 8.68\%\\
        \bottomrule
        \end{tabular}

    }
    \hspace{1em}
    \subfloat[AlphaZero and LCZero win probabilities after MCTS]{ \begin{tabular}{lccccccc}
        \toprule
        \textbf{Move}  &  \bishop d3 & \bishop f3 & c6 & d5 & \bishop g2 & f3 & \bishop h1 \\
        \midrule
        \textbf{Win prob (AlphaZero 64 nodes)} & 60.1\% & 64.5\% & 77.3\% & 87.1\% & 61.6\% & 67.3\% & 61.6\%  \\
        \midrule
        \textbf{Win prob (AlphaZero 256 nodes)} & 60.1\% & 64.5\% & 77.7\% & 83.1\% & 61.6\% & 67.3\% & 61.6\%  \\

       \midrule
        \textbf{Win prob (LCZero 64 nodes)} & 62.8\% & 62.8\% & 71.2\% & 71.6\% & 55.7\% & 55.7\% &55.7\% \\
        \midrule
        \textbf{Win prob (LCZero 256 nodes)} & 59.0\% & 62.2\% & 63.3\% & 67.8\% & 50.0\% & 58.2\% & 50.0\%  \\
        \bottomrule
        \end{tabular}
        }
        \hspace{1em}
    \subfloat[Comparison after MCTS. The move d5 was considered to be the best in all cases]
                { \begin{tabular}{lccccc}
                    \toprule
                    \textbf{Nodes visited} &  64 & 256 & 1024 & 65536 & 4194304  \\
                    \midrule
                    \textbf{AlphaZero eval} & 65.7\% & 74.1\% & 71.6\% & 67.9\% & 73.5\%  \\
                    \midrule
                    \textbf{LCZero eval} & 70.1\% & 65.0\%  & 67.4\% & 68.3\% & 73.1\% \\
                    \bottomrule
                    \end{tabular}
                    }

    \caption{\label{fig:LC0} LCZero and AlphaZero very fast agree that d5 is the best move, and though both engines discover various defensive resources, they reach similar evaluations.}
\end{figure}

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 \cite{sadler2019game}. The moves selected by LC0 without search (\textit{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, \textit{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. \ref{fig:LC1}.  Any decent chess player can "see" intuitively - essentially without any calculation - that white has a won position leading to mate (1.\queen g8+,\rook g8 and 2.\knight 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.\knight 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.

\begin{figure}[h]
    \centering
    \subfloat[board position]{
        \newgame
        \fenboard{1rr4k/6pp/7N/3Q4/8/qPp5/P1P5/1K6 w - - 0 1}
        \scalebox{0.8}{\showboard}
    }
    \hspace{0.1em}
    \subfloat[LCZero evaluations for the top 4 moves]{
        \begin{tabular}{lccc}
        \toprule
        \textbf{Move}  &  \knight f7 & \queen g8 & \queen d8  \\
        \midrule
        \textbf{Prior Prob} & 60.69\% & 15.96\% & 2.50\%  \\
        \midrule
         \textbf{V-value} & -0.276 & 0.588 & -0.968 \\
        \midrule
        \textbf{Win prob} & 36.2\% & 79.4\% & 1.6\% \\
         \midrule
        \textbf{Q-value (15 nodes)} & -0.075\% & 1 & 0 \\
         \midrule
        \textbf{Win prob (15 nodes)} & 48.5\% & 100\% & 0\% \\
        \bottomrule
        \end{tabular}
        \vspace{2em}
    }
    \caption{\label{fig:LC1} 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 (\textit{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 \knight f7, and switch to investigate the winning move \queen g8. And only while at node 15 does the program find the forced mate.}
\end{figure}

The next example Fig. \ref{fig:LC2} 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.

\begin{figure}[H]
    \centering
    \subfloat[board position]{
        \newgame
        \fenboard{6k1/2p5/5P1P/p7/8/2P2p1p/P7/6K1 w - - 0 1}
        \scalebox{0.8}{\showboard}
    }
    \hspace{0.1em}
    \subfloat[LCZero evaluations for the top 4 moves]{
        \begin{tabular}{lcccc}
        \toprule
        \textbf{Move}  &  a4 & c4 & a3 & f7 \\
        \midrule
        \textbf{Prior prob} & 50.4\% & 20.7\% & 15.4\% & 4.4\%  \\
        \midrule
        \textbf{V-value} & -0.632 & 0.806 & -0.817 & -0.88 \\
        \midrule
        \textbf{Win prob} & 18.4\% & 90.3\% & 9.2\% & 6\%  \\
        \midrule
         \textbf{Q-value (3 nodes)} & -0.632\% & 0.806 & -0.248 &  -0.248 \\
         \midrule
        \textbf{Win prob (3 nodes)} & 18.4\% & 90.3\% & 37.6\%  & 37.6\% \\

        \bottomrule
        \end{tabular}
        \vspace{2em}
    }

    \caption{\label{fig:LC2} 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}

\end{figure}

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. \ref{fig:LC3} that occured in a game between Stockfish 12 and LCZero.  The white player can force checkmate in a sequence of 5 moves, starting with \rook c2. However, the policy network give the move of \rook 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.

\begin{figure}[H]
    \centering
    \subfloat[board position]{
        \newgame
        \fenboard{6r1/5p2/1r6/2kpPb2/Rp1p4/3P2P1/1R3PK1/3B4 w - - 0 1}
        \scalebox{0.8}{\showboard}
    }
    \hspace{0.1em}
    \subfloat[LCZero evaluations for the top 4 moves]{
        \begin{tabular}{lcccc}\hline
            \toprule
            \textbf{Move} & \rook a5 & \rook c2 & \bishop e2 &  \rook b3 \\
            \midrule
            \textbf{Prior prob} & 35.9\% & 16.5\% & 10.3\% & 4.7\%  \\
            \midrule
            \textbf{V-value} & 0.29 & 0.27 & -0.005 & 0.06  \\
            \midrule
        \textbf{Win prob} & 64.5\% & 63.5\% & 49.8\% & 53.0\%  \\
            \bottomrule
        \end{tabular}
        \vspace{3em}
    }
    \caption{\label{fig:LC3} 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.\rook c2+,\king b5 2.\rook a5+!! 2.- \king a5 3. \rook a2+,\king b5 4.\bishop a4+, and now 4.-\king c5 5. \rook c2+mate, or 4.-\king a5 or 4.-\king a6 followed by 5.\bishop c6+ mate.}
\end{figure}

\section{Background and related work}
\label{sec:background}

\subsection{Impartial games and nim}
\label{sec:Impartial games}
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 (\textit{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

\begin{equation}
    G(s) = \text{mex}(\{G(s')\}: s' \in N(s))
\end{equation}

\noindent
where $s' \in N(s)$ denotes all the state $s'$ 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 \cite{beling2020pruning}.
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 \cite{berlekamp2001winning, gardner1967mathematical}
invented by John Conway and Michael Paterson.

Positions in sprout typically have nimber values $0,1,2$ and $3$ \cite{berlekamp2003winning}.  The position in Fig. \ref{fig:sprout_a} has nimber value 3. The Sprout position in Fig. \ref{fig:sprout_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 \ref{fig:sprout_b} can mimic any nim position that can arrive from a staring positions with $n$ heaps with $3$ counters.

\begin{figure}[H]
\centering
\begin{subfigure}[b]{0.25\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/sprout_small.eps}
\caption{sprout position}
\label{fig:sprout_a}
\end{subfigure}
\hspace{3em}
\begin{subfigure}[b]{0.35\textwidth}
\centering
\includegraphics[width=0.8\textwidth]{figures/sprout.eps}
\caption{sprout position serving as a gadget}
\label{fig:sprout_b}
\end{subfigure}
\caption{\label{fig:Sprout}  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 \cite{berlekamp2003winning} for details).}
\end{figure}

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 \ref{sec:psapce_nexptime} 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 \cite{viennot2007further}. Recently \cite{beling2020pruning} 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.

\subsection{Intrinsic complexity bottlenecks}
\label{sec:psapce_nexptime}
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 (\textit{i.e.}guarantees the player who moves from the position a win with optimal play) is NEXPTIME complete for chess, Go and shogi \cite{fraenkel1981computing, robson1983complexity, adachi1987shogi}.
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 \cite{vsima2003general}. 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 \cite{schaefer1978complexity}. 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 \cite{vsima2003general}.

\subsection{Low complexity bottlenecks: Parity and low-level thinking}
\label{sec:low_complexity}

Issues related to the parity function has a long history in AI. In \cite{mccarthy1964tough} 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.

\begin{figure}[h]
\centering
\includegraphics[width=0.4\textwidth]{figures/MutilatedBoard.eps}
\caption{\label{fig:MutilatedBoard} 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? }
\end{figure}

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  \cite{dantchev2001planar}.

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 \cite{riis1994independence,beame1998more}.
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  \cite{riis2001complexity} 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 \cite{riis2001complexity} 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 \cite{haken1985intractability}. 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:
\begin{equation}
    f({x_1, \ldots ,x_n}) = \sum_{i=1}^n x_i  \ mod \ 2
\end{equation}
where $x_1,x_2,...x_n \in \{0,1\}$.
In \cite{haastad1987computational} 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 \cite{linial1993constant}.

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  \ref{sec:parity_function_nerual_network} 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 $\boldsymbol{X} = (\bar{x}_1,\bar{x}_2, \ldots ,\bar{x}_s)$ with the corresponding list $\boldsymbol{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 \boldsymbol{X}$ there is no relation between the already seen data $(\boldsymbol{X},\boldsymbol{y})$ and $f(\bar{x})$. To see this, notice that there are exactly
$2^{2^n-s}$ Boolean functions that fit the observations $(\boldsymbol{X},\boldsymbol{y})$, and exactly half \textit{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 $(\boldsymbol{X},\boldsymbol{y})$ that happens to fit the parity function? There is no doubt that a human investigating the data $(\boldsymbol{X},\boldsymbol{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 $(\boldsymbol{X},\boldsymbol{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 (\textit{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 \cite{thornton1996parity, damper1998parity}.

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.

\bigskip
\noindent
{\bf 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.

\subsection{Practical challenge: Parity and neural networks}
\label{sec:parity_function_nerual_network}
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 \cite{banino2021pondernet}:
\begin{equation}
    f({x_1, \ldots ,x_n}) = \left(\sum_{i=1}^n x_i \; \textbf{\textit{if}} \; x_i == 1 \right) \ mod \ 2
\end{equation}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. \cite{al2005neural} 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 \cite{hohil1999solving, liu2002n, franco2001generalization, wilamowski2003solving, franco2001generalization}. 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 \cite{al2005neural}. 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 \textit{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 \ref{sec:value_network}).

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 \cite{zhao2020rnn}. In \cite{zhao2020rnn} 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. \cite{cohen2020regularizing} 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 \ref{sec:value_network}) 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) \cite{al2005neural, siegelmann1995computational} 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 {\it vanishing gradient problem} \cite{hochreiter1997long}. With the number of bitstring increasing, the difficulty of the RNN modelling the parity function also escalates drastically.

Self-Attention network (\textit{a.k.a} Transformer architectures) \cite{vaswani2017attention} underpins many Natural Language Processing (NLP) applications since its emergence in 2017. However, \cite{hahn2020theoretical} 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 \cite{banino2021pondernet} 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, \textit{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 \cite{dosovitskiy2020image}. 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.

\section{Different levels of mastery}
\label{sec:differnt}

The goal of an RL agent during training is to cultivate the ability of gaining maximum rewards in a Markov decision process (MDP) \cite{silver2021reward}. 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 \ref{tab:level_optimality}.

\begin{table}[h]
\caption{Two types of optimality}
\label{tab:level_optimality}
\centering
\begin{tabular}{l p{.70\linewidth}}
\toprule
\multicolumn{1}{c}{Type of Optimality} & \multicolumn{1}{c}{Description} \\ [0.5ex]
\midrule
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 \\
\bottomrule
\end{tabular}
\end{table}

\noindent
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 \ref{tab:level_mastery}. The general complexity results for chess, Go and shogi might only concern the type 2 notion of optimality.

\begin{table}[h]
\caption{Two Levels of Mastery}
\label{tab:level_mastery}
\centering
\begin{tabular}{l p{.70\linewidth}}
\toprule
\multicolumn{1}{c}{Mastery Level} & \multicolumn{1}{c}{Description} \\ [0.5ex]
\midrule
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 \\
\bottomrule
\end{tabular}
\end{table}

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 \cite{maharaj2021chess}. 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 \ref{sec:reinforcement_learning}. We also use an analogy and a crafted nim board below to expound the distinction between them.

\medskip
\noindent
{\bf 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.

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

\medskip
\noindent
{\bf 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 \textit{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 \ref{sec:implement_alphazero}.

\section{Preliminary experimental results}
\label{sec:prelimiary}

Among various types of neural networks we investigated and surveyed in the section \ref{sec:background} 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.

\subsection{Model parity function using value network}
\label{sec: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.

\begin{enumerate}[label={(\arabic*)}, noitemsep]
  \item Single LSTM layer with 128 nodes
  \item Linear layer with 1 node
  \item Sigmoid function
\end{enumerate}

The batch normalization layers \cite{ioffe2015batch} are not used in the value network as in \cite{silver2017mastering} because we found it adversely impacts the performance of the model. We use Adam \cite{kingma2014adam} 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 \footnote{\url{https://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 \cite{banino2021pondernet}. 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. \ref{fig:value_network}. 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. \ref{fig:value_network}, 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, \textit{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.

\begin{figure}[h]
\centering
\includegraphics[width=0.45\textwidth]{figures/bistrings_acc.eps}
\hspace{1ex}
\includegraphics[width=0.45\textwidth]{figures/lr_acc.eps}
\caption{\label{fig:value_network} 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. }
\end{figure}

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 \cite{power2022grokking}. We have made some remarks on this phenomenon in section \ref{sec:conclusion}.

\subsection{Learn winning moves using policy networks}
\label{sec:policy_network}

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) \cite{silver2016mastering}. 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 \cite{silver2017mastering}. 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 \ref{fig:LC3}) 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.

\medskip
\noindent
{\bf 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.
\noindent
Such positions fall into the following 4 different categories, as shown in the Table \ref{tab:winning_move}.

\begin{table}[h]
\caption{Winning Moves on nim Board Positions}
\label{tab:winning_move}
\centering
\begin{tabular}{ll}
\toprule
Winning Move & Nim Board Positions \\ [0.5ex]
\midrule
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 \\
\bottomrule
\end{tabular}
\end{table}

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]$ \textit{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.

\begin{enumerate}[label={(\arabic*)}, noitemsep]
  \item LSTM layer(s), each of which contains 128 nodes
  \item Batch normalization
  \item A rectifier nonlinearity
  \item Linear layer with 3 nodes
  \item Softmax function
\end{enumerate}

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. \ref{fig:policy_network} 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 \ref{sec:value_network}, 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.

\begin{figure}[H]
    \centering
    \begin{subfigure}[b]{0.32\textwidth}
    \centering
    \includegraphics[width=\textwidth]{figures/policy7_train_acc.eps}
    \caption{$h=7$ heaps}
    \end{subfigure}
    \hspace{0em}
    \begin{subfigure}[b]{0.32\textwidth}
    \centering
    \includegraphics[width=\textwidth]{figures/policy8_train_acc.eps}
    \caption{$h=8$ heaps}
    \end{subfigure}
    \hspace{0em}
    \begin{subfigure}[b]{0.32\textwidth}
    \centering
    \includegraphics[width=\textwidth]{figures/policy9_train_acc.eps}
    \caption{$h=9$ heaps}
    \end{subfigure}
\end{figure}
\vspace{-1.5em}
\begin{figure}[H]
\centering
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/policy7_test_acc.eps}
\caption{$h=7$ heaps}
\end{subfigure}
\hspace{0em}
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/policy8_test_acc.eps}
\caption{$h=8$ heaps}
\end{subfigure}
\hspace{0em}
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/policy9_test_acc.eps}
\caption{$h=9$ heaps}
\end{subfigure}
\caption{\label{fig:policy_network} 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.}
\end{figure}

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 (\textit{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.

\section{Reinforcement Learning for nim}
\label{sec:reinforcement_learning}
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 \cite{paszke2019pytorch} for neural network training and Ray \cite{moritz2018ray} 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 \cite{silver2017mastering, silver2018general}, while necessary changes to neural network architectures tailored to the nim were made, which will be specified in the section \ref{sec:implement_alphazero}.

\subsection{Implementing an AlphaZero style algorithm for nim}
\label{sec:implement_alphazero}
The AlphaZero algorithm starts training from a clean slate with no specific game knowledge, besides knowing the rules of the games \cite{ silver2018general}. 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 \ref{eqn:action_selection} \footnote{See 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.
\begin{equation}
    a_t = \argmax_a(Q(s,a)+U(s,a))
    \label{eqn:action_selection}
\end{equation}

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

\begin{equation}
\label{eqn:q_value}
    Q(s, a) = \frac{1}{N(s, a)}\sum_{s'|s, a\rightarrow s'}V(s')
\end{equation}

in which $N(s, a)$ is a counter that records the number of times action $a$ has been taken from state $s$, $s'|s, a\rightarrow s'$ denotes that action $a$ is taken at state $s$ and this simulation terminates at state $s'$, and $V(s')$ 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'$ is an intermediate state or the game itself as a reward if it is a terminal state. The $U(s,a)$ is calculated using

\begin{equation}
\label{eqn:puct}
    U(s,a)=c_{put}P(s,a)\dfrac{\sqrt{\sum_b{N(s,b)}}}{1 + N(s,a)}
\end{equation}

where the $c_{put}$ is a constant controlling the level of exploration. AlphaGo \cite{silver2016mastering}, AlphaGo Zero \cite{silver2017mastering} and AlphaZero \cite{silver2018general} 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. \cite{tian2019elf} 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 \cite{schrittwieser2020mastering} to calculate the $U(s,a)$, as shown below.

\begin{equation}
\label{eqn:u(s,a)}
    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)
\end{equation}

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.

\begin{equation}
   P(s,a) \leftarrow (1-\epsilon) \cdot P(s,a) + \epsilon \cdot \eta_{a}
    \label{eqn:add_noise}
\end{equation}

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.

\begin{equation}
    \label{eqn:u_s_a}
    U(s,a) \propto \dfrac{P(s,a)}{1 + N(s,a)}
\end{equation}

As shown in the equation \ref{eqn:u_s_a}, 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 \ref{eqn:pi_action_selection}, from which an action is sampled to take at board state $s$.
\begin{equation}
    \boldsymbol\pi(\textbf{a}|s) = \dfrac{N(s,\textbf{a})^{1/\tau}}{\sum_{b}N(s,b)^{1/\tau}}
    \label{eqn:pi_action_selection}
\end{equation}

where $\tau$ is the temperature that changes according to the number of moves that have been made during game play. We call the $\boldsymbol\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 \ref{subsec:policy_value}.  \cite{danihelka2021policy} 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 \cite{danihelka2021policy} 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 (\textit{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.

\subsection{Experimental setup and results}
\label{sec: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. \ref{fig:nim_board}, 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.

\subsubsection{Elo rating measurement}
\label{subsec:elo_rating}
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 \cite{tian2019elf} 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}:
\begin{equation}
    E_A = \dfrac{1}{1 + 10^{(R_B-R_A)/400}}
\end{equation}
Analogously, the expected score for player {B} is calculated by
\begin{equation}
    E_B = \dfrac{1}{1 + 10^{(R_A-R_B)/400}}
\end{equation}
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
\begin{equation}
    R_A = R_A + K(1 - E_A)
\end{equation}
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
\begin{equation}
    R_B = R_B + K(0 - E_B)
\end{equation}

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. \ref{fig:elo_rating}, 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.

\begin{figure}[H]
\centering
\includegraphics[width=0.45\textwidth]{figures/elo_rating.eps}
\caption{\label{fig:elo_rating} 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.}
\end{figure}

\subsubsection{Performance of policy and value network}
\label{subsec:policy_value}
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 \cite{danihelka2021policy} 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. \ref{fig:alphazero_policy_accuracy}, 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 \ref{sec:policy_network} that even when the size of the action space remains unchanged, the policy networks still face increasing difficulty as more heaps are added.
\begin{figure}[h]
\centering
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/policy_accuracy_5.eps}
\caption{$h=5$ heaps}
\end{subfigure}
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/policy_accuracy_6.eps}
\caption{$h=6$ heaps}
\end{subfigure}
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/policy_accuracy_7.eps}
\caption{$h=7$ heaps}
\end{subfigure}
\caption{\label{fig:alphazero_policy_accuracy} 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.}
\end{figure}

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. \ref{fig:alpha_value_accuracy}. 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 \ref{sec:value_network}.

\begin{figure}[h]
\centering
\includegraphics[width=0.45\textwidth]{figures/value_accuracy.eps}
\caption{\label{fig:alpha_value_accuracy} 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.}
\end{figure}

The policy network learns from the heuristics $ \boldsymbol\pi(\textbf{a}|s)$ derived from the MCTS, as shown in Formula \ref{eqn:pi_action_selection}. 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. \ref{fig:alpha_value}. 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.

\begin{figure}[H]
\centering
\includegraphics[width=0.4\textwidth]{figures/policy_loss.eps}
\hspace{1em}
\includegraphics[width=0.4\textwidth]{figures/value_loss.eps}
\caption{\label{fig:alpha_value} 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.}
\end{figure}

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.

\subsubsection{Analysis of AlphaZero on nim positions}
\label{subsec:alphazero_nim_positions}

\begin{figure}[H]
    \centering
    \subfloat[\label{pos:5heaps_1}{5 heaps: [1, 3, 5, 7, 9]}]{\includegraphics[width=0.35\textwidth]{figures/5piles_nim_position.eps}}
    \centering
    \hspace{1.5em}
    \subfloat[\label{tab:heaps5_1}Evaluations from policy and value network for the 2 moves with the highest prior probabilities. In 10,000 MCTS simulations, these are the only two moves selected on this position.]{
        \begin{tabular}{p{0.25\textwidth}p{0.08\textwidth}p{0.05\textwidth}}\hline
            \toprule
            \textbf{Move} & e9 & a1 \\
            \midrule
            \textbf{Winning Move} & yes &  no \\
            \midrule
            \textbf{Prior Probability} & 97.9\% & 1.9\% \\
            \midrule
            \textbf{Win Probability} & 99.5\% & 5.0\%  \\
            \midrule
            \textbf{V-value} & 0.97 & -0.89  \\
            \bottomrule
        \end{tabular}
        \vspace{1em}
    }
    \caption{\label{fig:alphazero_5piles_1} 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.}
\end{figure}

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 \ref{sec:revisiting_alphazero} 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. \ref{fig:alphazero_5piles_1}. 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 \ref{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.

\begin{figure}[H]
    \centering
    \subfloat[\label{pos:5heaps_2}{5 heaps: [1, 3, 5, 5, 9]}]{\includegraphics[width=0.3\textwidth]{figures/5_piles_nim_position.eps}}
    \centering
    \hspace{1.5em}
    \subfloat[Evaluations from policy and value network for the 4 moves with the highest prior probabilities.]{
        \begin{tabular}{p{0.25\textwidth}p{0.08\textwidth}p{0.05\textwidth}p{0.05\textwidth}p{0.05\textwidth}}\hline
            \toprule
            \textbf{Move} & e8 & b1 & a1 & d4 \\
            \midrule
            \textbf{Is Winning Move} & no &  no & no &  no \\
            \midrule
            \textbf{Prior Probability} & 97.4\% & 0.7\% & 0.4\% & 0.2\%\\
            \midrule
            \textbf{Win Probability} & 0.14\% & 5.6\% & 12.5\% & 9.8\% \\
            \midrule
            \textbf{V-value} & -0.99 & -0.88 & -0.74 & -0.80 \\
            \bottomrule
        \end{tabular}
        \vspace{1em}
    }
    \vspace{1em}
    \subfloat[\label{tab:heaps5_2}The posterior probability of the winning move e7 given different number of MCTS simulations]{
            \begin{tabular}{cccccc}
            \toprule
             & \multicolumn{5}{c}{\textbf{Number of simulations}} \\
            \midrule
            \textbf{Winning Move}&  64 & 256 & 1024 & 65536 & 4194304  \\
            \midrule
            e7 & 1.56\% & 0.39\% & 0.09\% & 0.0015\% & 0.00021\%  \\
            \bottomrule
            \end{tabular}
    }

    \caption{\label{fig:alphazero_5piles_2} 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.}
\end{figure}

For the initial position of the 6 heaps nim as shown in \ref{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.

\begin{figure}[H]
    \centering
    \subfloat[\label{pos:6heaps_1}{6 heaps: [1,3,5,7,9,11]}]{\includegraphics[width=0.3\textwidth]{figures/6piles_nim_position.eps}}
    \centering
    \hspace{1.5em}
    \subfloat[\label{tab:heaps6_1}Evaluations from policy and value network for the 4 moves with the highest prior probabilities.]{
        \begin{tabular}{lcccc}\hline
            \toprule
            \textbf{Move} & b2 & a1 & b1 &  d6 \\
            \midrule
            \textbf{Winning Move} & yes &  no & no &  no \\
            \midrule
            \textbf{Prior Probability} & 92.8\% & 4.0\% & 0.64\% & 0.63\%  \\
            \midrule
            \textbf{Win Probability} & 78.0\% & 14.3\% & 4.76\% & 2.17\%  \\
            \midrule
            \textbf{V-value} & 0.56 & -0.71 & -0.90 & -0.95  \\
            \bottomrule
        \end{tabular}
        \vspace{1em}
    }
    \caption{\label{fig:alphazero_6piles_1} 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. }
\end{figure}

There are also positions with 6 heaps where the policy and value network both stumbled, one of which is shown in \ref{pos:6heaps_2}. However, unlike the situation with a 5 heaps nim position as shown in Fig. \ref{fig:alphazero_5piles_2}, the prior probabilities assigned to the these winning moves are not high enough to completely mislead the search. As shown in the table \ref{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.

\begin{figure}[!h]
    \centering
    \subfloat[\label{pos:6heaps_2}{6 heaps: [1,3,3,5,4,10]}]{\includegraphics[width=0.3\textwidth]{figures/6_piles_nim_position.eps}}
    \hspace{1.5em}
    \subfloat[Evaluations from policy and value network for the 4 moves with the highest prior probabilities.]{
        \begin{tabular}{lcccc}\hline
            \toprule
            \textbf{Move} & f3 & f2 & f4 &  f9 \\
            \midrule
            \textbf{Winning Move} & no & no & no &  no \\
            \midrule
            \textbf{Prior Probability} & 47.4\% & 12.6\% & 10.1\% & 7.5\%  \\
            \midrule
            \textbf{Win Probability} & 0.18\% & 1.03\% & 0.03\% & 81.2\%  \\
            \midrule
            \textbf{V Value} & -0.99 & -0.97 & -0.99 & 0.62  \\
            \bottomrule
        \end{tabular}
        \vspace{1em}
    }
    \vspace{1em}
    \subfloat[\label{tab:heaps6_2}The posterior probability of the winning move f10 given different number of MCTS simulations]{
            \begin{tabular}{cccccc}
            \toprule
             & \multicolumn{5}{c}{\textbf{Number of simulations}} \\
            \midrule
            \textbf{Winning Move}&  64 & 256 & 1024 & 65536 & 4194304  \\
            \midrule
            f10 & 4.68\% & 1.17\% & 0.29\% & 53.7\% & 99.1\%  \\
            \bottomrule
            \end{tabular}
    }
    \caption{\label{fig:alphazero_6piles_2} 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.}
\end{figure}

The initial position of the 7 heaps nim as shown in the Fig. \ref{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.

\begin{figure}[H]
    \centering
    \subfloat[\label{pos:7heaps}{7 heaps: [1, 3, 5, 7, 9, 11, 13]}]{\includegraphics[width=0.3\textwidth]{figures/7piles_nim_position.eps}}
    \centering
    \hspace{1.5em}
    \subfloat[Evaluations from policy and value network for the 4 moves with the highest prior probabilities.]{
        \begin{tabular}{lcccc}\hline
            \toprule
            \textbf{Move} & c4 & c3 & c2 &  c5 \\
            \midrule
            \textbf{Winning Move} & no & no & no &  no \\
            \midrule
            \textbf{Prior Probability} & 4.37\% & 4.06\% & 3.95\% & 3.88\%  \\
            \midrule
            \textbf{Win Probability} & 50.1\% & 49.5\% & 48.9\% & 50.1\%  \\
            \midrule
            \textbf{V Value} & 0.003 & -0.009 & -0.02 & 0.003  \\
            \bottomrule
        \end{tabular}
        \vspace{1em}
    }
    \vspace{1em}
    \subfloat[The posterior probability of the winning moves e7, f7 and g11 given different number of MCTS simulations]{
            \begin{tabular}{cccccc}
            \toprule
             & \multicolumn{5}{c}{\textbf{Number of simulations}} \\
            \midrule
            \textbf{Winning Move}&  64 & 256 & 1024 & 65536 & 4194304  \\
            \midrule
            e7 & 1.56\% & 1.17\% & 1.26\%  & 2.79\% & 0.38\% \\
            \midrule
            f7 & 1.56\% & 0.17\% & 1.66\% & 0.89\% & 1.15\% \\
            \midrule
            g11 & 1.56\% & not visited & 1.07\% & 1.61\% & 0.65\%  \\
            \bottomrule
            \end{tabular}
    }
    \caption{\label{fig:alphazero_7piles} 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.}
\end{figure}

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 \ref{sec:value_network}. 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.

\section{Concluding remarks and conjectures}
\label{sec:conclusion}

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 \cite{sadler2019game}. 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 \ref{sec:value_network}). 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 \textit{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 \cite{popper1972objective}.

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 \cite{nasu2018efficiently, maharaj2021chess} 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, (\textit{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, \textit{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, \textit{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.

\section*{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.

\printbibliography

\end{document}