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.
[1] These games also vary in whether the last player to move wins (the normal play convention) or loses (misère play convention).
[2] Another winning convention that has also been used is that a player who moves to a position with all numbers zero wins, but that any other position with no moves possible is a draw.
[1] Examples of notable subtraction games include the following: 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.
-positions (positions in which the previous player, who just moved, is winning) and
For instance, with the normal play convention and a single pile of tokens, every number in the subtraction set is an
In this way, the optimal strategy for the overall game can be reduced to the calculation of nim-values for a simplified set of game positions, those in which there is only a single number.
-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
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.
[8] 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
The period may be significantly larger than the maximum value
[10] However, there exist infinite subtraction sets that produce bounded nim-values but an aperiodic sequence of these values.
denotes the largest nim-value occurring in this computation.
[12] 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.