1
$\begingroup$

I'm trying to figure out a strategy for the following nim:

enter image description here

here the rules are that you choose a new position on the path $1$,$2$, or $3$ nodes forward. The other player does the same. Neither player is allowed to jump the other player's position. The player with a final position inside the green circle wins. You also cannot jump over the other player.

The red player starts and there will be a winning strategy for the red player.

Usually with nims it's helpful to consider the end state of the game and work backwards, but I find that this does not work here to figure out a winning strategy. Any other methods I could use?

Improve this question
$\endgroup$
2
  • $\begingroup$ There are 15 white nodes, and each move takes 1, 2, or 3 of them. The winner is the person who takes (moves forward) an odd number of nodes. That makes this game identical to the 15 Pebbles game I linked to as a duplicate. $\endgroup$
    – Jaap Scherphuis
    Jul 20 at 9:52
  • 1
    $\begingroup$ Oh no, I noticed that the top voted answer in Jaap's link looked very similar to the one I posted here. Then I checked who had written that answer... I have absolutely no memory of writing that three years ago, but now that I'm reading it again, it kinda does ring a bell, particularly the part where I had constructed a mnemonic aid for the solution. X-] $\endgroup$
    – Bass
    Jul 20 at 10:39

1 Answer 1

Reset to default
1
$\begingroup$

As you suspected, the correct approach is to start from the end.

First, let's invent a notation for the game positions. Let's view each position from the POV of the player whose turn it is, so that "In,6" means it's your turn to move, you are inside the circle, and there are 6 empty spots between you and the opponent.

Then let's enumerate the positions, starting from the end of the game, to see what kind of a pattern arises.

(Note that with an odd number of empty spaces, the opponent is on the same side of the circle as you, and opposite you otherwise. This means that on rows with even distances, you look for a losing position in the previous 3 lines of the other column, on rows with odd distances you look in the same column.)

 In,0:  W       Out,0:  L
 In,1:  L       Out,1:  W (1)
 In,2:  W (2)   Out,2:  W (1)
 In,3:  W (2)   Out,3:  W (3)
 In,4:  L       Out,4;  W (3)
 In,5:  W (1)   Out,5:  L
 In,6:  W (1)   Out,6:  W (2)
 In,7:  W (3)   Out,7:  W (2)
 In,8:  W (3)   Out,8:  L
 In,9:  L       Out,9:  W (1)
 In,10: W (2)   Out,10: W (1)
 In,11: W (2)   Out,11; W (3)
 In,12: L       Out,12: W (3)

(The numbers in the parens are the winning moves, if any exist.)

The pattern repeats after 8 empty spots, which means we can take the original position (Out,15), subtract 8, and look up "Out,7" in the table.

That position is

winning, and the winning move is to move 2

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks @bass for the answer. I don't quite understand this enumeration. The first row and column seems to be that it's player ones turn to move and there are no empty spots between player 1 and player 2? $\endgroup$
    – Louie
    Jul 20 at 11:57
  • $\begingroup$ @Louie In this table, every entry is given from the perspective of whoever is to move next. So if we read the entry in row 1, column 1, it says "If it's your turn, and you're on the inside, and there are no empty spots between you and the opponent, you win." When one constructs the table this way, one can classify every position as "winning for the player whose turn it is" or "losing for the player whose turn it is", regardless of the blueness or redness of the player, and this lets us use it to evaluate either player's moves. $\endgroup$
    – Bass
    Jul 20 at 12:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.