User:N Shar/Sandbox

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

Description

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

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.