Subtraction game
Subtraction game
In combinatorial-game-theory, a subtraction game is an abstract strategy game whose state can be represented by a natural number or vector of numbers (for instance, the numbers of game tokens in piles of tokens, or the positions of pieces on board) and in which the allowed moves reduce these numbers. Often, the moves of the game allow any number to be reduced by subtracting a value from a specified subtraction set, and different subtraction games vary in their subtraction sets. These games also vary in whether the last player to move wins (the normal play convention) or loses (misère play convention). [[subtract-a-square]] is a variation of nim in which only square numbers of tokens can be removed in a single move. The resulting game has a non-trivial strategy even for a single pile of tokens; the Furstenberg–Sárközy theorem implies that its winning positions have density zero among the integers. fibonacci-nim is another variation of nim in which the allowed moves depend on the previous moves to the same pile of tokens. On the first move to a pile, it is forbidden to take the whole pile, and on subsequent moves, the amount subtracted must be at most twice the previous amount removed from the same pile. *Wythoff's game is played by placing a chess queen on a large chessboard and, at each step, moving it (in the normal manner of a chess queen) towards the bottom side, left side, or bottom left corner of the board. This game may be equivalently described with two piles of tokens, from which each move may remove any number of tokens from one or both piles, removing the same amount from each pile when both piles are reduced. It has an optimal strategy involving Beatty sequences and the golden ratio.
Theory Subtraction games are generally impartial-games, meaning that the set of moves available in a given position does not depend on the player whose turn it is to move. For such a game, the states can be divided up into <math>\mathcal{P}</math>-positions (positions in which the previous player, who just moved, is winning) and <math>\mathcal{N}</math>-positions (positions in which the next player to move is winning), and an optimal game playing strategy consists of moving to a <math>\mathcal{P}</math>-position whenever this is possible. For instance, with the normal play convention and a single pile of tokens, every number in the subtraction set is an <math>\mathcal{N}</math>-position, because a player can win from such a number by moving to zero. The nim-values are zero for <math>\mathcal{P}</math>-positions, and nonzero for <math>\mathcal{N}</math>-positions; according to a theorem of Tom Ferguson, the single-number positions with nim-value one are exactly the numbers obtained by adding the smallest value in the subtraction set to a <math>\mathcal{P}</math>-position. Ferguson's result leads to an optimal strategy in multi-pile misère subtraction games, with only a small amount of change from the normal play strategy.
For a subtraction game with a single pile of tokens and a fixed (but possibly infinite) subtraction set, if the subtraction set has arbitrarily large gaps between its members, then the set of <math>\mathcal{P}</math>-positions of the game is necessarily infinite. For every subtraction game with a finite subtraction set, the nim-values are bounded and both the partition into <math>\mathcal{P}</math>-positions and <math>\mathcal{N}</math>-positions and the sequence of nim-values are eventually periodic. The period may be significantly larger than the maximum value <math>x</math> in the subtraction set, but is at most <math>2^x</math>. However, there exist infinite subtraction sets that produce bounded nim-values but an aperiodic sequence of these values.
Complexity For subtraction games with a fixed (but possibly infinite) subtraction set, such as subtract a square, the partition into P-positions and N-positions of the numbers up to a given value <math>n</math> may be computed in time <math>O(n\log^2 n)</math>. The nim-values of all numbers up to <math>n</math> may be computed in time <math>O(\min(ns,nm\log^2 n))</math> where <math>s</math> denotes the size of the subtraction set (up to <math>n</math>) and <math>m</math> denotes the largest nim-value occurring in this computation.
For generalizations of subtraction games, played on vectors of natural numbers with a subtraction set whose vectors can have positive as well as negative coefficients, it is an undecidable problem to determine whether two such games have the same P-positions and N-positions.