Experimental Study of the Game Exact Nim(5, 2)

Abstract

We compare to different extensions of the ancient game of nim: Moore's nim$(n,\le k)$ and exact nim$(n,=k)$. Given integers $n$ and $k$ such that $0<k\le n$, we consider $n$ piles of stones. Two players alternate turns. By one move it is allowed to choose and reduce any (i) at most $k$ or (ii) exactly $k$ piles of stones in games nim$(n,\le k)$ and nim$(n,=k)$, respectively. The player who has to move but cannot is the loser. Both games coincide with nim when $k=1$. Game nim$(n,\le k)$ was introduced by Moore (1910) who characterized its Sprague-Grundy (SG) values 0 (that is, P-positions) and 1. The first open case is SG values 2 for nim$(4,\le 2)$. Game nim$(n,=k)$, was introduced in 2018. An explicit formula for its SG function was computed for $2k\ge n$. In contrast, case $2k<n$ seems difficult: even the P-positions are not known already for nim$(5,=2)$. Yet, it seems that the P-position of games nim$(n+1,=2)$ and nim$(n+1,\le 2)$ are closely related. (Note that P-positions of the latter are known.) Here we provide some theoretical and computational evidence of such a relation for $n=5$.