Nim and simple mathematical proofs 3/3

In this post I present to you yet another game, Northcott’s Game, and another example of how new problems can be solved using experience and knowledge gained from previous ones. Again, the post is based of Thomas S. Ferguson’s book Game Theory.

Northcotts’s Game is a game where black and white pieces are placed on a checkerboard, one piece of each color on each row (see Picture 1 below). The players take turns in moving their piece on a single row and only on a single row per turn. A piece cannot jump over another piece. The last player to move his piece wins. In its essence, this game is about blocking the other player’s pieces in such a way, that your last move blocks their final piece, ensuring you the win. But how to do that? It turns out that knowing how to play Nim is a huge advantage.

 

Picture 1: Northcott's Game, start position.
Picture 1: Northcott’s Game, start position.

 

 

 

 

 

 

 

Winning in Northcott’s Game

Before going deeper into Northcott’s Game we’ll recall the definition of a combinatorial game. A combinatorial game is such that (see Ferguson’s Game Theory, Part 1, chapter 1, page 4):

  1. It is played by two players.
  2. There is a usually finite set of possible positions in the game.
  3. The rules of the game specify which moves are legal. If both players have the same options of moving from each position, the game is called impartial. Otherwise the game is called partisan.
  4. The players alternate moving.
  5. The game ends when a position is reached from which no moves are possible for the player whose turn it is to move. Under the Normal Play Rule, the last player to move wins. Under the Misère Rule the last player to move loses.
  6. The game ends in a finite number of moves no matter how it is played. (Ending Condition)

It has to be noted that Northcott’s Game is not a variant of Nim. More specifically, it is a partisan game, since both players have distinct moves. Furthermore, Northcott’s game does not satisfy the Ending Condition, since it is possible to keep playing forever. Thus, Northcott’s Game is not a combinatorial game due to not obeying the Ending Condition, but is still related to them. Therefore, knowing how to play combinatorial games, Nim in particular, is helpful in winning in Northcott’s Game.

As often in game theory, we start from the end, using backward induction, and ask ourselves, how the end of the game would look like. To make this easier, Picture 2 presents an abbreviated version of the game in Picture 1, showing only the top 3 rows.

Picture 2: Abbreviated Northcott's Game, start position.
Picture 2: Abbreviated Northcott’s Game, start position.

 

 

 

 

Picture 3 shows a “near penultimate” final position of the game in Picture 2, where the white player has moved his piece in the lowest row next to the black piece in the same row. It is now black player’s turn, and he can only move right, leaving the white player with the final move. In this final move, the white player “blocks” the black player’s last piece and wins the game.

Picture 3: Abbreviated Northcott's Game, "near penultimate" position.
Picture 3: Abbreviated Northcott’s Game, “near penultimate” position.

 

 

 

 

It is clear that the position presented in Picture 3 is a potential P-position. Our next question is, how to get into this penultimate P-position, and this is where Nim steps in.

Play first Nim, then win in Northcott’s Game

The game before the penultimate P-position in Northcott’s Game can be interpreted as Nim with the following parallels:

  • Each row is a pile of sticks.
  • The number of empty squares between the white and the black piece is the number of sticks in a pile.

Now the target is to make the Nim-sum of the squares between the two pieces on a single row zero to reach a P-position, eventually the terminal position. The terminal position in this game is a position where the pieces are next to each other in each row, since then the number of squares between the pieces will have been reduced to zero on each row. The player to have moved last before this position will win, since the next player can only move towards his end of the row, and then the next player, the one who reached the terminal position, can always cover this distance, eventually making the last move and winning the game. This is generalizable to any number of rows.

Here we also see why Northcott’s Game could go on forever. While in Nim a player must always remove a stick from one of the piles, thus eventually leaving no piles on the table, in Northcott’s Game the players could keep moving their pieces back and forth without even trying to block one another. This kind of play would be pointless, but is possible, and therefore Northcott’s Game does not obey the Ending Condition for combinatorial games.

Like Nimble, Northcott’s Game is a good a example of how to use existing models and knowledge to solve new problems, and how existing solutions can be used to represent a solution to a novel problem as a combination of existing solutions, executed as steps one after another. I hope you will have as much as fun with these games and solving them as I am having.

Leave a Reply

Your email address will not be published. Required fields are marked *