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. ^{[1] [2]} 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. ^[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

Examples of notable subtraction games include the following:

• Nim is a game whose state consists of multiple piles of tokens, such as coins or matchsticks, and a valid move removes any number of tokens from a single pile. Nim has a well-known optimal strategy in which the goal at each move is to reach a set of piles whose nim-sum is zero, and this strategy is central to the Sprague–Grundy theorem of optimal play in impartial games. However, when playing only with a single pile of tokens, optimal play is trivial (simply remove all the tokens in a single move). ^[3]
• 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. ^[4]
• 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. ^[5]
• 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. ^[6]

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 ${\displaystyle {\mathcal {P}}}$-positions (positions in which the previous player, who just moved, is winning) and ${\displaystyle {\mathcal {N}}}$-positions (positions in which the next player to move is winning), and an optimal game playing strategy consists of moving to a ${\displaystyle {\mathcal {P}}}$-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 ${\displaystyle {\mathcal {N}}}$-position, because a player can win from such a number by moving to zero. ^[2]

For normal-play subtraction games in which there are multiple numbers, in which each move reduces only one of these numbers, and in which the reductions that are possible from a given number depend only on that number and not on the rest of the game state, the Sprague–Grundy theorem can be used to calculate a "nim value" of each number, a number representing an equivalent position in the game of nim, such that the value of the overall game state is the nim-sum of its nim-values. 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. ^[7] The nim-values are zero for ${\displaystyle {\mathcal {P}}}$-positions, and nonzero for ${\displaystyle {\mathcal {N}}}$-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 ${\displaystyle {\mathcal {P}}}$-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. ^[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 ${\displaystyle {\mathcal {P}}}$-positions of the game is necessarily infinite. ^[9] For every subtraction game with a finite subtraction set, the nim-values are bounded and both the partition into ${\displaystyle {\mathcal {P}}}$-positions and ${\displaystyle {\mathcal {N}}}$-positions and the sequence of nim-values are eventually periodic. The period may be significantly larger than the maximum value ${\displaystyle x}$ in the subtraction set, but is at most ${\displaystyle 2^{x}}$. ^[10] However, there exist infinite subtraction sets that produce bounded nim-values but an aperiodic sequence of these values. ^[11]

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 ${\displaystyle n}$ may be computed in time ${\displaystyle O(n\log ^{2}n)}$. The nim-values of all numbers up to ${\displaystyle n}$ may be computed in time ${\displaystyle O(\min(ns,nm\log ^{2}n))}$ where ${\displaystyle s}$ denotes the size of the subtraction set (up to ${\displaystyle n}$) and ${\displaystyle m}$ 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. ^[13]

See also

• Grundy's game and octal games, generalizations of subtraction games in which a move may split a pile of tokens in two

Notes

1. Golomb (1966).
2. Berlekamp, Conway & Guy (2001), "Subtraction games", pp. 83–86.
3. Bouton (1901–1902); Golomb (1966); Berlekamp, Conway & Guy (2001), "Green hackenbush, the game of nim, and nimbers", pp. 40–42.
4. Golomb (1966); Eppstein (2018)
5. Whinihan (1963); Larsson & Rubinstein-Salzedo (2016)
6. Wythoff (1907); Coxeter (1953)
7. Golomb (1966); Berlekamp, Conway & Guy (2001), "Games with heaps", p. 82.
8. Ferguson (1974), p. 164; Berlekamp, Conway & Guy (2001), "Ferguson's pairing property", p. 86.
9. Golomb (1966), Theorem 4.1, p. 451.
10. Golomb (1966), Example (a), p. 454; Althöfer & Bültermann (1995)
11. Larsson & Fox (2015).
12. Eppstein (2018).
13. Larsson & Wästlund (2013).

References

• Althöfer, Ingo; Bültermann, Jörg (1995), "Superlinear period lengths in some subtraction games", Theoretical Computer Science , 148 (1): 111–119, doi:10.1016/0304-3975(95)00019-S, MR   1347670
• Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2001), Winning Ways for your Mathematical Plays, vol. 1 (2nd ed.), A K Peters
• Bouton, Charles L. (1901–1902), "Nim, a game with a complete mathematical theory", Annals of Mathematics , Second Series, 3 (1/4): 35–39, doi:10.2307/1967631, JSTOR   1967631
• Coxeter, H. S. M. (1953), "The golden section, phyllotaxis, and Wythoff's game", Scripta Mathematica , 19: 135–143, MR   0057548
• Eppstein, David (2018), "Faster evaluation of subtraction games", in Ito, Hiro; Leonardi, Stefano; Pagli, Linda; Prencipe, Giuseppe (eds.), Proc. 9th International Conference on Fun with Algorithms (FUN 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 100, Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 20:1–20:12, doi: 10.4230/lipics.fun.2018.20
• Ferguson, T. S. (1974), "On sums of graph games with last player losing", International Journal of Game Theory, 3 (3): 159–167, doi:10.1007/BF01763255, MR   0384169
• Golomb, Solomon W. (1966), "A mathematical investigation of games of "take-away"", Journal of Combinatorial Theory , 1 (4): 443–458, doi: 10.1016/S0021-9800(66)80016-9 , MR   0209015
• Larsson, Urban; Fox, Nathan (2015), "An aperiodic subtraction game of nim-dimension two" (PDF), Journal of Integer Sequences , 18 (7), Article 15.7.4, arXiv: 1503.05751 , MR   3370791
• Larsson, Urban; Rubinstein-Salzedo, Simon (2016), "Grundy values of Fibonacci nim", International Journal of Game Theory, 45 (3): 617–625, arXiv: 1410.0332 , doi:10.1007/s00182-015-0473-y, MR   3538534
• Larsson, Urban; Wästlund, Johan (2013), "From heaps of matches to the limits of computability", Electronic Journal of Combinatorics , 20 (3): P41:1–P41:12, arXiv: 1202.0664 , doi:10.37236/2244, MR   3118949
• Whinihan, Michael J. (1963), "Fibonacci nim" (PDF), Fibonacci Quarterly , 1 (4): 9–13
• Wythoff, W. A. (1907), "A modification of the game of nim", Nieuw Archief voor Wiskunde, 7 (2): 199–202