A strategy for moving the queen

Chess is an extraordinarily subtle game, both in the strategic contest between the two players and in the mathematical analysis of all possible games. Yet the same setup can be used for a more elementary variant, accessible even to complete beginners, that still holds a little interest.

To set up the game, take a chessboard (or a larger checkerboard) and orient it: in other words, agree with your opponent on which sides are left and right, and which are top and bottom (see our feature "L'Orientation", Tangente 206, 2022). Then place a queen on any square, and the match can begin!

There are two rules: the players take turns moving the queen any number of squares they wish, but only to the left, downward, or diagonally down and to the left; a player who can no longer move the piece—that is, whose turn begins with the queen already in the lower-left corner—loses.

This game is easier than chess, but it can still offer some satisfaction and arouse the curiosity of players and mathematicians alike. We encourage you to try it before reading on.

Winning and losing positions ----------------------------------------------

To analyse the game, first note that if the queen starts in the lower-left corner, the first player cannot move it without breaking the rules and therefore loses. If, however, the queen is on any other square in the first column, the first row, or the diagonal, the first player has an obvious winning strategy: move it all the way along that row, column, or diagonal to the lower-left corner, leaving the opponent with no possible move.

####

(red cross: losing position; green circle: winning position).

Now suppose that the queen starts in the third column from the left and the second row from the bottom, a position denoted by (3, 2). The player can move it:

• to the left: to position (2, 2), a move of one square, or to (1, 2), a move of two squares;

• downward: to position (3, 1);

• diagonally: to position (2, 1).

The player cannot move the queen directly to the lower-left corner, and whichever move is chosen, it will end up in the first row, the first column, or the diagonal running from the lower-left corner. The second player can therefore move it to the corner with ease and win the game. Thus, if the opponent plays well, position (3, 2) is losing for the first player: whatever the first player does, the second has a winning strategy. You can continue the analysis by hand and check, for example, that position (6, 4) is also losing for the player who starts the game.

At this point, we have seen that there are two types of position: those from which the first player is certain to have a winning strategy, and those from which the first player will lose. The task, then, is to classify every position according to this criterion. More precisely, a square is losing if it is the lower-left corner, or if every move from it takes the opponent to a winning position; a square is winning if there is a move that takes the opponent to a losing position. This definition is tricky because of its recursive structure: read too quickly, it may seem incorrect, as though it "loops". It does not: it allows us to determine the status of every square on the board step by step—and, admittedly, laboriously. We place a red cross on every losing position (initially just the lower-left corner), then green circles on all squares that allow a move to a red cross, then a red cross on every square whose moves all lead to green circles, and so on. After a few steps, we obtain the result shown in the figure below.

Naturally, no two losing positions ever lie in the same row, the same column, or the same "diagonal". Proving this property is a delightful exercise in getting to grips with the definition!

The Sprague–Grundy generalization --------------------------------------

Now return to the game and spell out a "good" way to play when starting from a square marked with a green circle. The winning strategy is to move the queen to a square marked with a red cross, which is always possible by definition. Your opponent, unless already defeated, must then move the queen back to a green circle: once again, the definition leaves no alternative! By continuing in this way, you will always play from a green circle and your opponent from a red cross. Since the blocking position—the lower-left corner—is marked with a red cross, only your opponent can find themselves there, and you cannot lose. All that remains is to note that there must be a loser—a draw or an infinite game is impossible under these rules—to conclude that you will win.

This method of analysing games by distinguishing and progressively determining their "winning" and "losing" configurations is not unique to this game. In the 1930s, the German Roland Percival Sprague (1894–1967) and the Briton Patrick Michael Grundy (1917–1959) extended it to other games satisfying a few simple assumptions: the two players take turns, the game can neither end in a draw nor continue indefinitely, and there is a form of "impartiality" between the players, meaning that if both players found themselves in the same game configuration, they would have the same possible moves.

This theoretical framework excludes many of our everyday pastimes, such as chess and go. It does, however, include others, such as the matchstick game (or Nim), Sprouts (or the game of sprouts), and even Subtract a Square, which entertains some mathematicians: starting from an integer, the players take turns subtracting a square. For example, a player can move from 37 to:

36 = 37 – 1²; 33 = 37 – 2²;

28 = 37 – 3²; 21 = 37 – 4²;

12 = 37 – 5²; 1 = 37 – 6².

The player who reaches 0 loses.

The queen game on the chessboard comes with a small mathematical bonus: the set of winning positions is not only determined by the Sprague–Grundy method described above, but also completely characterized by an explicit mathematical formula!

As early as 1907, the Dutch mathematician Willem Abraham Wythoff (1865–1939) obtained the coordinates of every losing position. Perhaps surprisingly, they can be expressed simply in terms of the golden ratio $\phi ={\displaystyle \frac{1+\sqrt{5}}{2}}\backslash varphi=\; \backslash dfrac\{1+\; \backslash sqrt\{5\}\}\; \{2\}$ (see our feature in Tangente 203, 2022) and an integer parameter: each value of the parameter yields a losing position, and each losing position corresponds to one value of the parameter. There is always something astonishing about seeing mathematics emerge from such an innocuous situation!