Winning Positions

A combinatorial game is a two player game that satisfies the following conditions:

1) The game is deterministic. There is no randomization mechanism such as flipping a coin or rolling a die.
2) The game will always end. There is no sequence of moves the players can make that will cause the game to proceed indefinitely.
3) There is perfect information in the game. Each player knows all the information about the state of the game, nothing is hidden.
4) The first player who is unable to make a move loses the game.

Well-known examples of combinatorial games are Tic-Tac-Toe, Checkers, Chess, Go and Nim.

The combinatorial games that are easiest to study are impartial games. For a game to be impartial, it must satisfy two additional conditions.

5) The moves available depend only on the position of the game and not on which player’s turn it is.
6) The value of any particular move is the same for both players.

Condition 5 excludes Checkers, Chess and Go as impartial games. In both games, one player can only move/place white pieces and the other black pieces.

The most well-known impartial game is the game of Nim. The game of Nim is played by 2 players and uses $k$ piles of stones, with sizes $(a_1, a_2, \ldots, a_k)$. During a turn, a player is allowed to remove any number of stones from a single pile. The game ends when there are no stones left and the person whose turn it is to move will lose the game.

Before we look at Nim more in depth, let’s talk a bit about how we can analyze impartial games. We define two types of positions. A position is a winning position if, from that position, the player whose turn it is can always win the game if they play optimally. A position is a losing position if, from that position, no matter how a player moves, the other player can win the game with optimal play.

We can use the following 3 rules to classify all positions:

1) The empty game (the game where there are no moves to be made) is a losing position.
2) A position is a winning position if at least one of the positions that can be obtained from this position by a single move is a losing position.
3) A position is a losing position if every position that can be obtained from this position by a single move is a winning position.

Due to the deterministic nature of the game, one can show via backward induction that every position can be uniquely characterized as a winning or a losing position. Rule 2 also tells us, in general terms, how to move optimally when we are at a winning position. We move to a position that is a losing position. As such, this provides us with a very simple algorithm to understand how these games are played.

Let's consider the game of Nim in greater detail.

Case 1. Nim with 1 pile of stones.

When there is a single pile of size $n \geq 1$, the first player is able to win the game by taking all the stones, so every position is winning. This is a direct application of rule 2, since we showed that there is a losing position we can get to from the starting position.

Case 2. Nim with 2 piles of stones.

We already know that when there is exactly 1 pile of stones, it is a winning position for the next player. We start with the smallest example of 2 piles, namely when the piles have sizes $(1,1)$. In this case, the first player can only take away a single stone from one of the piles, and then the second player will take away the other stone and win the game. So $1,1$ is a losing position. For any position of the form $(a_1,1)$ or $(1,a_2)$ with $a_1,a_2 > 1$, the player can move to the losing position $(1,1)$, so this is a winning position. We see that we can say the same thing about $(2,2)$, and any position of the form $(a_1,2)$ or $(2,a_2)$ with $a_1,a_2 > 2$.

In general, it is easy to see that any position of the form $(a,a),$ will be a losing position, since whatever the first player does to one pile, the second can do to the other pile. And since from any other two-pile position you can get to one of these positions, these must be the only losing positions.

Worked Examples

1. Determine the losing positions for Nim games of the form $(a_1, a_2, 1)$.

Solution: Claim: The losing positions of Nim with starting sizes $(a_1, a_2, 1)$ are piles of $(2k+1, 2k, 1 )$, and the losing positions of 2-pile Nim.

Proof: From any of these losing positions, it is clear that we cannot reach another losing position, since we need to change the sizes of at least 2 piles.

From any of the winning positions which have 3 piles, we can always remove stones from the largest pile, to get it into the form of $(2k+1, 2k, 1)$. From any of the winning positions which have 2 piles, we know from before that they are winning positions already.$_\square$

Determine a general characterization for when a Nim position is winning or losing. It helps to look at the numbers in base 2.

2. A two player game is played on a $5 \times 5$ grid. A token starts in the bottom left corner of the grid. On each turn, a player can move the token one or two units to the right, or to the leftmost square of the above row. The last player who is able to move wins. Determine which positions of the token are winning positions and which are losing.

Solution: It is easy to determine the winning and losing positions for the top row, since the only options are to move 1 or 2 positions to the right. This gives the top row of W L W W L. Since the first position in the row is a winning position, it is never advantageous to move up here from the previous row. This means that the last position in the next row is also losing, and the whole row will have the same pattern as this row. We see that the pattern will continue for all 5 rows, so if the token is in the 1st, 3rd, or 4th column, it is a winning position, if it is in the 2nd or 5th column, it is losing. $_\square$

Generalize this problem to larger grids. How many winning positions are there on a $k \times n$ grid?