# Best strategy for stick-taking game

Rules of the game:

• It's a two player game. Moves will alternate between players.
• There are N sticks on a table.
• A value M is defined at the start of the game such that 2 < M <= N.
• On their turn, each player must take between 1 and M sticks from the table.
• A player cannot take a number of sticks equal to the number of sticks taken in one of the last two moves.
• If a player is unable to make a legal move on their turn, they lose.

Example

• Say the number of sticks (N) is 20, and the maximum number of sticks that can be taken (M) is 4.
• Player one takes 4 sticks. Remaining: 16.
• Player two cannot take 4 sticks. They take 1 stick. Remaining: 15.
• Player one cannot take 4 or 1 stick(s). They take 2 sticks. Remaining: 13.
• Player two cannot take 1 or 2 stick(s). They take 3 sticks. Remaining: 10.
• Player one cannot take 2 or 3 sticks. They take 4 sticks. Remaining: 6.

and so on and so forth. The player who cannot make a move loses.

What is a good strategy to play this game?

• Hi @johnchakder, welcome to Puzzling SE! I've edited your question to improve the formatting and grammar - if any of the edits conflict with your original intent, let me know. Also, you say that "The player who takes the last stick wins" in the rules, but in the example you say "The player who cannot make a move loses." Which one is the actual winning condition, or can either of these situations be a win? Thanks!
– HTM
Apr 9 at 7:23
• @ΗΤΜ I was also perplexed at first, but it is clear. Let's say there is 1 remaining on your turn, but last move was your opponent taking 1. Then you can't play 1 and thus you lose. Apr 9 at 7:33
• You could just ignore the last-stick=win condition, since if a player takes the last stick, the opponent cannot make a move and loses. Apr 9 at 7:46
• @HTM, Thanks... and the wining condition is - " the player who cannot make a move loses". Apr 9 at 9:06
• I'm tempted to say, ask any dog. They're experts at stick taking games!! Apr 9 at 16:11

Pretty much all Nim games can be solved by starting at the end and working backwards.

Let's first solve the basic Nim, with only one pile, and simple actions (take 1-4). Let's enumerate the endgame situations by how many sticks are left, and see what kind of pattern emerges:

Rules: 2 players, one pile, take 1-4, taking last wins

0: loss, cannot take
1: win (take 1)
2: win (take 2)
3: win (take 3)
4: win (take 4)
5: loss (can only leave wins)
6: win (take 1)
7: win (take 2)
8: win (take 3)
9: win (take 4)
10: loss (can only leave wins)
11: win (take 1)
12: win (take 2)
...


Because the rules are very simple, the emerging pattern is too, and we won't even have to continue all the way to 20 to see that..

If you start with 20 sticks, only the second player has a winning strategy

and that strategy is

when you leave N sticks for the opponent, choose the N that is divisible by 5.

Because this is so simple, there are usually some more complex constraints. Here, the game history restriction (cannot repeat two previous moves) is added, and it's a nasty one, since it basically forces branching, and makes for a really messy pattern.

For the given example case though, we can just skip all that, and use the strategy from the simple case. Yes, really.

If we are in a winning position, we can always play the required move, because

1. in that strategy, we never want to play the same number the opponent just played, and
2. the only way for the opponent to cause us to repeat our own previous move is to repeat their own previous move, which is forbidden.

This same logic applies to all cases where M is even and N is a multiple of M+1 (Thanks, Jaap), but for odd M the first point doesn't apply, and for other N the second point doesn't, so the messy approach cannot be avoided, I think.

To see why the game history restriction is so horrible, let's examine just the first few cases of M=5:

Rules: 2 players, one pile, take 1-5, taking last wins, can't repeat previous 2

Case | Prev 2 | sticks left: strategy
-----+--------+---------------------
0    | any    | 0: loss, cannot take
-----+--------+---------------------
1a   | 1,X    | 1: loss, cannot take
1b   | X,1    | 1: loss, cannot take
1c   | other  | 1: win, take 1
-----+--------+----------------------
2a   | 1,2    | 2: loss, cannot take
2b   | 2,1    | 2: loss, cannot take
2c   | 2 ok   | 2: win, take 2
2d   | 1 ok   | 2: win, take 1 (leaves 1b for opponent)
-----+--------+---------------------------------------
3a   | 3 ok   | 3: win, take 3
3b   | 3,1    | 3: win, take 2 (leaves 1a for opponent)
3c   | 3,2    | 3: win, take 1 (leaves 2b for opponent)
3d   | other  | 3: loss, can only leave wins
-----+--------+---------------------------------------
4a   | 4 ok   | 4: win, take 4
4b   | 4,1    | 4: win, take 2 (leaves 2b) or 3 (leaves 1a)
4c   | other  | 4: loss
-----+--------+---------------------------------------
5a   | 5 ok   | 5: win, take 5
5b   | 5,1    | 5: win, take 4 (leaves 1a)
5c   | other  | 5: loss


and so on. This is an absolutely devastating task to do by hand, because if there's a single mistake at any point, everything after the mistake becomes worthless as well.

The basic idea is still the same though: we need to consider every game position, and in this case, the game position includes the history. In other words, for every number of sticks, there are $$P(M,2) + M + 1 = M^2+1 = 26$$ game positions with different (possibly empty) histories to consider. Then, starting at the losing positions at end of the game, mark all the positions from which a losing position can be reached with one move as winning. If you find a position from which every legal move leaves a winning position for the opponent, mark that position as losing too.

• The even M case is not so trivial if the starting number of sticks is not a multiple of M+1. For M=4 it seems the first player can then always win by eventually getting to a point where the standard strategy works, but for larger even M there are starting numbers that are not multiples of M+1 where the second player wins (for example 89 or 97 for N=6 if my quick program is correct). I don't have time to look into it further right now. Apr 9 at 11:27
• Ah yes, the second point doesn't apply when it's the first move of the other player. Urgh. :-)
– Bass
Apr 9 at 11:34