In combinatorial game theory, the subtraction games are a class of two-player impartial games.

Description

edit

The 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

edit

Because 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.