Wherever you go, I win!

In theory, the objective of chess is to capture the king, but in practice, the game ends two moves earlier in the position of checkmate. We can imagine the losing player making another move, and then the winning player capturing the king on the next turn, but these moves are never played out. Similarly, in the game of noughts and crosses (tic-tac-toe) shown above, it does not matter where player O moves, because player X is certain to win on the following turn. Both the positions shown can be regarded as snapshots of a game in its penultimate position, two moves before the true end.

Chess and noughts and crosses are both examples of partisan games, which means that the allowable moves at any stage of the game depend on whose turn it is. For example, in noughts and crosses, an X can only be played if it is X’s turn, and an O can only be played if it is O’s turn, and analogous rules apply in chess. 

A game that is not partisan is called impartial. An example of an impartial game is Dots and Boxes, shown above. Regardless of whose turn it is, the next move in a game of Dots and Boxes consists of connecting two dots with a line. If the act of doing this creates the fourth side of a square, the player initials the completed square and moves again. After all the dots have been connected, the player who has completed the most squares is the winner.

The objective of the game Tak is to use pieces (called stones) to create a road that connects opposite edges of a board. The standard version of the game (shown above) is partisan, and there are two types of pieces, as in chess. However, there is also an impartial version of the game with only one type of piece. The objective of the impartial version of the game, shown below, is to connect two opposite sides of the board with a path of blue squares that touch edge to edge. The position shown is the penultimate position of a game, which means that the next player to move will immediately lose, unless the other player makes a mistake. For example, if the next player plays in the square with the yellow dot, the other player can win by playing in the square with the red dot, thus connecting the top and bottom sides of the board with a blue path.

The impartial version of Tak is studied in depth in the recent paper The Penults of Tak: Adventures in impartial, normal-play, positional games, by Boris Alexeev, Paul Ellis, Michael Richter, and Thotsaporn Aek Thanatipanonda. The word penult is formed from the word penultimate by removing the last two syllables, because it refers to a penultimate position of a game, ignoring the last two moves. The novelesque title of the paper is fitting because Tak first appeared as a fictional game in the fantasy trilogy The Kingkiller Chronicle by Patrick Rothfuss.

Not all penults in impartial Tak contain the same number of blank squares. The examples above give three examples of penults on a 4×4 board with six, seven, and eight filled-in squares. Note that if we are playing on a square n×n board, a position in Tak must have at least two blank squares in each row and in each column to qualify as a penult, because a row or column with only one blank square would lead to a win on the next turn. 

The authors show that it is always possible to construct a penult with this minimal number of blank squares, by using the arrangement shown above. It follows that a penult on a square board contains at most n² – 2n squares, and that this upper bound is achievable. The problem of finding a lower bound for the number of squares is considerably more difficult, but the authors make some progress towards finding one. In the cases n=4, n=5, and n=6, the authors have computed that the lower bounds are given by 6, 10, and 16 respectively. They also show that the possible numbers of blue squares are intervals in each case. For example, in the case n=6, this means that the number of blue squares in a penult is at least 16 and at most n² – 2n = 24. The “interval” part means that any integer in the range 16 up to 24 is indeed the number of blue squares in some penult.

The authors also prove that the game of impartial Tak is a win for the second player on an n×n board if n is even. A winning strategy is to choose a line of symmetry of the board, and simply mirror the first player’s move until it is possible to play a winning move. In contrast, if n=5, the game is a win for the first player. In this case, a winning strategy is to play the middle square first, and then to mirror player 2’s moves across the middle square until it is possible to play a winning move. The authors expect that the game is a win for the first player if n is odd and at least 7, but there does not seem to be a similarly simple strategy.

The paper analyses several other games, including a game the authors call D&B. D&B is a reduced version of Dots and Boxes in which the first player to complete a box wins. The picture above shows some possible penults in the game D&B. These behave in a broadly similar way to the penults of impartial Tak. It turns out that a penult of a 3×3 game of D&B can have 4, 5, 6, 7, or 8 tokens, where the “tokens” in this case are the red line segments, and a 4×4 game can have between 8 and 14 tokens.

---

Picture credits and relevant links

The game Tak was created by James Ernest in collaboration with Patrick Rothfuss. It was published by Cheapass Games in 2016. The photograph of the Tak board is by nycavri and appears on Wikipedia. The picture of the Tak box comes from amazon.com, but the game seems to be out of stock.

The picture of checkmate is by Bubba73 and appears on Wikipedia.

The picture of noughts and crosses is a screenshot of Google search’s version of the game.

The game Dots and Boxes was invented by the mathematician Édouard Lucas (1842–1891) of Lucas numbers fame. The sample play of Dots and Boxes is by Tiger66 and appears on WIkipedia.

The other pictures are edited versions of pictures in the paper by by Boris Alexeev, Paul Ellis, Michael Richter, and Thotsaporn Aek Thanatipanonda.

Substack management by Buzz & Hum.