Solving the Matchsticks Game

I was on holiday in Iceland last week, and while we were away, Charlie introduced me to the "Matchsticks" game. We played a few rounds and it got me thinking about how to solve it. I couldn't find any information about the game online so I'm sharing what I've learnt...

The game

The game is played with 15 matchsticks, arranged in 3 rows. 3 matchsticks in the first row, 5 matchsticks in the second row, and 7 matchsticks in the third row.

| | |
| | | | |
| | | | | | |

2 players each take turns to remove some number of matchsticks. On each turn, the player may remove any number of matchsticks from any row, provided all of the removed matchsticks are on the same row, and at least one matchstick is removed.

The player to remove the final matchstick loses, and the game ends.

It's helpful to try a few rounds to develop a feel for the nature of the game, so if you're playing along at home I recommend giving it a go now. If more convenient, you can draw the matchsticks on paper and cross them off, instead of using physical objects.

Observations

It will quickly become clear that all of the matchsticks on each row are equivalent. It doesn't matter whether you take one from the start or from the end, the only thing that matters about each row is how many matchsticks are on it. We can therefore represent the game state by referring to the number of matchsticks on each row, independent of their location. The opening position is therefore represented as (3,5,7).

It will also become clear that the order of the rows does not matter, so we can further restrict our state space by enforcing that the coordinates are ordered. For example, if the first player removes all of the matchsticks from the third row, instead of moving from (3,5,7) to (3,5,0), we can say he moved from (3,5,7) to (0,3,5).

The player who has to play on (0,0,1) has lost. Therefore the player who can play a move which results in (0,0,1) has won. There are only 2 generalised ways to do this. If you have to play on (0,0,n) for n != 1 you win: just remove all matchsticks except one. If you have to play on (0,1,n) for n != 0 you also win: just remove all matchsticks from the n row. Taking another step up, you lose if you are forced to play a move which puts your opponent in such a position ((1,1,1) and (0,2,2) are the only examples here), and another step up from that, you win if you can put your opponent in such a position ((0,2,3) => (0,2,2), (1,2,2) => (0,2,2), (1,1,2) => (1,1,1) etc.).

The (3,5,7) position can only be played by the opening player, and (for example) (2,5,7) can only ever be played by the second player. But consider what happens if player 1 opens with (3,5,7) => (3,5,6) and player 2 responds with (3,5,6) => (3,5,5): then player 1 is to play on (3,5,5). But (3,5,7) => (3,5,5) is also a valid opening move, which would leave player 2 to play on (3,5,5). So if we want our document to say whether a given position is a win for player 1 or for player 2, that's not possible: we instead have to say whether it is a win or a lose for the player who is about to play on that position.

Any given position can be described as a "win" if it is possible for the player playing on this position to force the other player to lose, and a position can be described as a "lose" if it is not possible for the player playing on this position to force the other player to lose.

Solution format

Each reachable position is equivalent to a point (x,y,z) in 3-space with integer coordinates and which lies between (0,0,0) and (3,5,7). We can annotate each point with whether it is a win or a lose, a recommended move, and how many moves before the game ends assuming optimal play.

It's hard to draw a 3-dimensional table, but the first coordinate only has 4 possibilities (0,1,2,3), so we can draw 4 2-dimensional tables, and we can say in each cell of the table whether the corresponding position is a win or a lose, and what is the best move to play. For a won position the best move is the one that ends the game most quickly, and for a lost position the best move is the one that drags the game on for as long as possible.

This leaves us with a 6*8 table for x=0, a 5*7 table for x=1, a 4*6 table for x=2, and a 3*5 table for x=3. That's already only 122 cells in total, but (0,0,0) is unreachable, and if we also enforce that the co-ordinates are ordered we're left with only 80 cells to complete.

Since the contents of each cell depend only on those cells which are closer to the origin in 3-space, this problem is ripe for a dynamic programming solution, and 80 cells is small enough that we could plausibly execute a dynamic programming solution by hand. I did try to do this while in Iceland but I kept making mistakes and eventually gave up.

Solution

Here are the final tables I generated. Green cells are won positions, pink cells are lost positions, and the number in parentheses is the number of moves remaining.