Best strategy for stick-taking game

Question

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?

Answer 1

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.