Subtract-a-square (also referred to as take-a-square) is a two-player mathematical subtraction game.
[1][2] It is an impartial game, meaning that the set of moves available from any position does not depend on whose turn it is.
Solomon W. Golomb credits the invention of this game to Richard A.
[3] A normal play game starting with 13 coins is a win for the first player provided they start with a subtraction of 1: Player 2 now has three choices: subtract 1, 4 or 9.
[6] The exact growth rate of the cold numbers remains unknown, but experimentally the number of cold positions up to any given threshold
At each turn the player to make a move first selects one of the numbers, and then subtracts a square from it.
This theorem states that each position in the game subtract-a-square may be mapped onto an equivalent nim heap size.
Optimal play consists of moving to a collection of numbers such that the nim-sum of their equivalent nim heap sizes is zero, when this is possible.
The equivalent nim heap size of a position may be calculated as the minimum excluded value of the equivalent sizes of the positions that can be reached by a single move.
For subtract-a-square positions of values 0, 1, 2, ... the equivalent nim heap sizes are In particular, a position of subtract-a-square is cold if and only if its equivalent nim heap size is zero.
It is also possible to play variants of this game using other allowed moves than the square numbers.
For instance, Golomb defined an analogous game based on the Moser–de Bruijn sequence, a sequence that grows at a similar asymptotic rate to the squares, for which it is possible to determine more easily the set of cold positions and to define an easily computed optimal move strategy.
[3] Additional goals may also be added for the players without changing the winning conditions.
For example, the winner can be given a "score" based on how many moves it took to win (the goal being to obtain the lowest possible score) and the loser given the goal to force the winner to take as long as possible to reach victory.
With this additional pair of goals and an assumption of optimal play by both players, the scores for starting positions 0, 1, 2, ... are Subtract-a-square can also be played as a misère game, in which the player to make the last subtraction loses.