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.
Basic Approach
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:
In a game, Bob goes first, and he has to say a positive integer less than or equal to 16.
Then, Allison must add a positive integer less than or equal to 16 to Bob’s number, at which point Bob must add a positive integer less than or equal to 16, and so on. The winner is whomever says the number 2015.
What number must Bob say first to ensure that he will win the game if both players play optimally?
Winning and losing positions
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.
- The empty game (the game where there are no moves to be made) is a losing position.
- 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.
- 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?
Dan and Sam play a game in which the first to start says the number 1, the next says 2, and the one who's next must say an integer strictly between the previous number and twice of it (not including the endpoints).
For example, Dan begins saying 1, then Sam says 2. Dan's options are now all integers between 2 and 4, exclusive. But there's only one such option, 3, so Dan is forced to say 3. Sam's options are now between 3 and 6, which are 4 and 5.
The game finishes when someone says 100 or greater; that player wins.
If Dan begins, who will win, assuming both players play optimally?
This is the first problem of the set Winning Strategies.
You take these nine cards out of a standard deck (ace through 9 of hearts), put them all face up on a table and play the following game against another player:
Both players take turns choosing a card. The first player to have three cards that add up to 15 wins. The ace counts as one.
If both players play optimally, which player has a winning strategy?
You play a game with a pile of \(N\) gold coins.
You and a friend take turns removing 1, 3, or 6 coins from the pile.
The winner is the one who takes the last coin.
For the person that goes first, how many winning strategies are there for \(N < 1000?\)
\(\)
Clarification: For \(1 \leq N \leq 999\), for how many values of \(N\) can the first player develop a winning strategy?
Chomp and Strategy Stealing
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).
Let \( N \ge 2 \) be a positive integer. Alice and Bob play the following divisor game: starting with the set \( D_N \) of positive divisors of \( N\), the players take turns removing some elements from the set. At a player's turn, he or she chooses a divisor \( d \) that remains, and removes \( d \) and any of the divisors of \( d \) that remain. The player who moves last loses.
For example: \( N = 18, D_N = \{ 1,2,3,6,9,18 \} \). Alice chooses \( d=2 \), so she removes \( 1 \) and \( 2 \). The remaining set is \( \{3,6,9,18\} \). Bob chooses \( d = 9 \) and so must also remove \( 3 \). The remaining set is \( \{6,18\} \). Alice takes \( 6 \), and now Bob is forced to take \( 18 \), so he loses.
Let \( n \ge 2 \) be the largest positive integer \( \le 200 \) such that if Alice and Bob play the divisor game for \( n \) and both of them play optimally, the second player wins. Find \( n \). If no such \( n \) exists, enter \( 999 \).