  While AlphaZero-style reinforcement learning (RL) algorithms excel in various
board games, in this paper we show that they face challenges on impartial games
where players share pieces. We present a concrete example of a game - namely
the children's game of Nim - and other impartial games that seem to be a
stumbling block for AlphaZero-style and similar self-play reinforcement
learning algorithms.
  Our work is built on the challenges posed by the intricacies of data
distribution on the ability of neural networks to learn parity functions,
exacerbated by the noisy labels issue. Our findings are consistent with recent
studies showing that AlphaZero-style algorithms are vulnerable to adversarial
attacks and adversarial perturbations, showing the difficulty of learning to
master the games in all legal states.
  We show that Nim can be learned on small boards, but the learning progress of
AlphaZero-style algorithms dramatically slows down when the board size
increases. Intuitively, the difference between impartial games like Nim and
partisan games like Chess and Go can be explained by the fact that if a small
part of the board is covered for impartial games it is typically not possible
to predict whether the position is won or lost as there is often zero
correlation between the visible part of a partly blanked-out position and its
correct evaluation. This situation starkly contrasts partisan games where a
partly blanked-out board position typically provides abundant or at least
non-trifle information about the value of the fully uncovered position.
