In combinatorial game theory, the subtraction games are a class of two-player impartial games.
Description
editThe typical subtraction game is played with a number of objects in distinct heap. On each player's turn, that player must remove a number of objects from one of the heaps. The number of objects a player can remove is restricted to a certain set, called the subtraction set. Generally, the game is played under the normal play convention, so that a player loses when he or she is unable to move.
In many cases, the game is played with only one heap.
Analysis
editBecause subtraction games are impartial, any position in a subtraction game is equivalent to some nimber, by the Sprague-Grundy theorem. In Winning Ways, Elwyn Berlekamp, John Horton Conway, and Richard Guy tabulated the nim-values of many subtraction games with small subtraction sets.