Combinatorial Games - Winning Positions

When analyzing a finite combinatorial game, the two key questions are:

1) Who wins, if both players play optimally?
2) What playing strategy is "optimal"?

That is, given the current state (or "position") of the game, the question is whether the player whose turn it is to move can force a win, and if so, what move(s) must be made to do so. Some famous combinatorial games whose strategies have been studied extensively include chess, nim, and tic tac toe.

The problem-solving technique that is often useful in this context is inductive reasoning. In other words, start by analyzing simple versions of the game to build up an understanding of who wins in which positions, at which point the result can be extended to the full game. Here is a basic example.

In a two-player game, starting with a pile of $n$ stones, the players take turns choosing to remove either $1,2,3,$ or $4$ stones from the pile. The winner is the player who takes the last stone from the pile. For which $n$ can the second player guarantee that he or she will win?

---

Solution: Begin by looking at small cases. If the pile contains $\le 4$ stones, then the first player wins immediately by taking them all. But if the pile contains $5$ stones, the second player can win, because after the first player removes some stones, the second player can remove the rest.

But if there are $6,7,8,$ or $9$ stones, the first player can win by leaving $5$, since $5$ is a losing position for the player whose move it is. Here we are inductively building on our knowledge of earlier positions. Similarly, $10$ is a win for the second player.

Often at this point it is easiest to make an educated guess at the general situation, and then to explain why the guess is true (since the reasoning is inductive, the proof often uses induction as well). Here the correct claim appears to be that multiples of $5$ are wins for the second player, and everything else is a win for the first player. This can be proved by induction. The base case is done already. Now suppose the claim is true for $n \le 5k$. For $n = 5k+1,5k+2,5k+3,5k+4$ the first player wins by taking $1,2,3,4$ respectively, and for $n = 5k+5$ the first player cannot help but leave $5k+1,5k+2,5k+3,$ or $5k+4$, which are wins for the player whose turn it is. So the claim is true for $n \le 5(k+1)$, which establishes the inductive step. $\square$

To further check your understanding, consider this example which is an extension of the example in the introduction:

With the above examples in mind, we can use the following 3 rules to classify all positions as winning or losing, depending on whether the player to move will ultimately win or lose with perfect play on both sides.

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:

Problem-solving strategy for combinatorial games:
1. Analyze simple starting positions, to build a library of basic winning and losing positions.
2. Conjecture a general description of winning and losing positions, based on the examples.
3. Prove the conjecture (often by induction): show that a winning position can always move to a losing position, and that a losing position can only move to a winning position.

Here is another example which uses this terminology and strategy.

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. The pattern will continue for all 5 rows, so if the token is in the $1^\text{st}, 3^\text{rd},$ or $4^\text{th}$ column, it is a winning position, and if it is in the $2^\text{nd}$ or $5^\text{th}$ column, it is losing. $_\square$

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

Chomp is an impartial combinatorial game whose rules are as follows: A rectangular $m \times n$ chocolate bar (where $mn \ge 2$) is cut into $1 \times 1$ squares. Alice and Bob take turns eating the bar from the top right: they pick a square and eat it along with all the squares above and to the right of it (including the squares directly above and directly to the right). Each player must eat at least one square at each turn. The person who eats the lower left square loses.

Chomp (not played with optimal strategy)

Case 1: Chomp with one row.

Alice (the first player) wins by eating all but the lower left square.

Case 2: Chomp with two rows.

Denote a two-row bar in the middle of a Chomp game by $(a,b)$ where $a$ is the number of squares in the top row and $b$ the number of squares in the bottom row. So $a \le b$. The claim is that the losing positions are precisely $(a,a+1)$.

To see that $(a,a+1)$ is losing, we proceed by induction. It's easy to see that $(1,2)$ (or $(0,1)$) is losing. Now suppose Alice must move from $(a,a+1)$. She has two options. If she bites just the top row, to reduce to $(c,a+1)$, Bob can reduce to $(c,c+1)$ which is losing for Alice by induction. If she bites both rows to reduce to a rectangle $(c,c)$, Bob can reduce to $(c-1,c)$, which is losing for Alice by induction.

It's clear that these are the only losing positions: if Alice moves from any other position, she can bite the bar to reduce to $(a,a+1)$, so Alice wins. So in particular, starting from a two-row rectangle, Alice wins by eating the top right square only.

Case 3: Chomp with three (or more) rows.

Even three-rowed Chomp is a complex problem, the subject of contemporary research. The best first move for Alice (as a function of the number of columns) is not obvious, but it turns out to be easier to prove that Alice must always win for any nontrivial rectangular starting shape.

It can be proved that Chomp is always a win for the first player under optimal play, even though the general game strategy is unknown.

To show this, suppose a certain rectangular bar is a win for the second player, Bob. Then if Alice starts by eating just the top right corner, Bob must have a devastating move that leaves Alice a losing position. But Alice could have made that move instead at her first turn, which would leave Bob that same losing position. This is a contradiction.

This is a textbook example of a nonconstructive proof: it is clear that the first player must win, but the proof gives almost no insight into the correct winning move (or moves).

• Combinatorial Games - Definition
• Chess Puzzles
• Nim
• Tic Tac Toe
• Recursive Backtracking
• K-level Thinking