This game is played with a sequence of heaps and a position marker, where each heap is owned by exactly one player. The game ends when a player has removed all objects from their own heaps, and this player wins with score equal to the number of remaining objects. Other players lose with score equal to minus the number of objects they still own. Play consists of players cyclically taking turns, where (for the 2-player version) they choose to either:
- Move the position marker forward to any non-empty heap they own, and remove exactly one object from that heap.
- Reset the position marker back to the beginning, before any heaps. (Only valid if the previous player did not reset - this ensures the game is finite.)
What is the optimal strategy for each player in the 2-player version, given an arbitrary initial state?
A state can be specified by:
- A sequence of (size, owner) integer pairs representing the heaps
- A non-negative integer representing the position marker (with the sequence indexed starting from one)
- An integer representing the player about to move
- A Boolean representing whether the previous player chose to reset
So far I have noticed the maximal score seems to eventually follow an arithmetic progression under consistent patterns of adding to the heaps. However, there is a certain region of states with more unstable behaviour. The main problem is the position marker, since without it the game would become trivial.
Update: I have generated the maximum scores for player $0$ with the initial state
$$ \left( \begin{array}{c|cccccccc} \!\!\!& 3 & & x & & 5 & & y & \!\\ \!\!\!& & 6 & & 9 & & 2 & & 4 \! \end{array} \right)_{\text{P}0, \top} $$
as $x$ and $y$ range from $1$ to $11$.
Solid contours represent positive score and dashed contours represent negative score. Interestingly, it can be seen that the behaviour changes only near when two heaps have the same size.
Further, I am fairly confident this maximum score formula
$$ \left( \begin{array}{c|ccc} \!\!\!& h_1 & & h_3 \!\\ \!\!\!& & h_2 & \! \end{array} \right)_{\text{P}0, \top} \,\to\, \left\{ \begin{array}{lrrcr} h_2 - h_1 & \text{if} & h_2 - h_1 < 0 & \text{and} & h_3 - h_2 + 1 \ge 0 \\ h_2 - h_1 + 1 & \text{if} & h_3 - h_1 + 1 \ge 0 & \text{and} & h_2 - h_1 \ge 0 \\ h_3 - h_1 + 1 & \text{if} & h_3 - h_1 + 1 < 0 & \text{and} & h_3 - h_2 + 1 < 0 \end{array} \right. $$
works for all values of $h_i > 0$, and also including when $h_3 = 0$ or $h_2 = h_3 = 0$. In general I think the function would have to be piecewise linear with coefficients in $\{ -1, 0, +1 \}$ and satisfy a heap merge invariance property, meaning for example that $M(h_1, 0, h_3) = M(h_1 + h_3, 0, 0) = M(0, 0, h_1 + h_3)$.