1
$\begingroup$

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$. contour plot of maximum scores 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)$.

$\endgroup$
  • $\begingroup$ what is the meaning of "optimal strategy" when there are more than two players ? $\endgroup$ – mercio Aug 3 '18 at 10:52
  • $\begingroup$ @mercio Sorry, I meant optimal strategy for two players. What are the options for more than two players? For a given player, it could be to maximise their score if a win is guaranteed, otherwise minimise the variance among the players' scores. $\endgroup$ – D. G. Aug 3 '18 at 11:11
  • $\begingroup$ By the way, the final Boolean in your state seems a bit redundant, since during play the position marker is before any heaps iff the previous player reset it. Or do you want to allow your arbitrary starting position to be inconsistent in this respect, so that a starting position may or may not allow a reset move regardless of the starting location of the marker? $\endgroup$ – Jaap Scherphuis Aug 3 '18 at 13:24
  • $\begingroup$ @JaapScherphuis Yes it annoys me, but here is why I have left it there: 1) the special case exists either way, so may as well make it explicit; 2) it is only a Boolean in the 2-player case, in the n-player generalisation it can take on n values; and... $\endgroup$ – D. G. Aug 3 '18 at 15:22
  • $\begingroup$ @JaapScherphuis 3) Whenever there is an empty heap, I delete it and merge the adjacent heaps to reduce complexity if possible (for 2 players this makes the heap ownership alternate). Thus if the first player deletes the first heap, then the second player will not know if they can reset the position marker, unless they have the Boolean. Then there are three options: leave empty heaps and no Boolean, remove empty heaps and add Boolean, or remove empty heaps and add a phantom empty heap at the beginning. The middle option seems to be the most convenient. $\endgroup$ – D. G. Aug 3 '18 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.