Working with Subtraction Games in Practice
Subtraction games are a specific class of combinatorial games where players take turns removing objects from a pile, and the number you can remove is limited by a fixed set of allowed moves. The last player to move typically wins, though misère variants exist. It sounds simple enough until you actually try to compute positions for anything beyond toy examples. Here is how the mechanics actually work. You start with a heap of n objects. There is a subtraction set S, which is a finite set of positive integers. On each turn, a player chooses some k in S and removes k objects from the heap, provided the heap has at least k objects remaining. If you cannot make a legal move, you lose under normal play convention. That is the entire rule set. The complexity comes from analyzing which positions are winning and which are losing. The standard approach is to compute the Grundy value or simply the N/P position status for each heap size from 0 upward. Position 0 is a losing position by definition since you cannot move. For any other position n, you look at all reachable positions n-k where k is in S. If any of those reachable positions is a losing position for the player whose turn it would be, then n is a winning position. If all reachable positions are winning, then n is losing. This is recursive but straightforward to implement iteratively.
Understanding Subtraction Games Through Examples
Take S = {1, 3, 4}. With a heap of 0, the current player loses immediately. Heap of 1: you can remove 1 and reach 0, which is losing for the next player, so 1 is winning. Heap of 2: you can remove 1 to reach 1, which is winning for the next player, so 2 is losing. Heap of 3: you can remove 3 to reach 0, making it winning. Heap of 4: removing 4 reaches 0, winning. Heap of 5: removing 1 reaches 4 (winning), removing 3 reaches 2 (losing), so 5 is winning because there exists a move to a losing position. The pattern for this subtraction set eventually becomes periodic, which is not a coincidence. Every subtraction game has a periodic sequence of N and P positions. The period length depends on the subtraction set. For S = {1, 3, 4}, the P-positions repeat with period 7: positions 0, 2, 5, 7, 9, 12, 14, 16, 18, 21, and so on. The pre-period is usually zero, meaning the pattern holds from the start, but some subtraction sets do have a short pre-period before entering the cycle. I ran into a case with S = {2, 5, 7} where I was computing by hand and kept getting wrong results because I misidentified the period as 9 when it was actually 10. The sequence of P-positions only stabilizes after you compute enough terms. My workaround was to compute at least 3 times the suspected period length before declaring it found the cycle, and to verify by checking that two consecutive blocks of the claimed period length produced identical results. The Sprague-Grundy theorem extends this to games played with multiple heaps. Each heap is analyzed independently using the same logic, and the overall game state is the Nim-sum (XOR) of the individual heap Grundy values. A position is losing if and only if the XOR of all heap values equals zero. This is where people often make mistakes. They compute the winning/losing status for a single heap and then incorrectly XOR those binary win-loss values across multiple heaps. The Grundy value is not a binary win-loss indicator. It is a non-negative integer, and you must use the integer Grundy values in the XOR calculation, not the N/P classification.
For computation, a simple iterative algorithm works fine for small heaps. Store an array where index i holds either the Grundy value or the N/P status. Fill it sequentially. The time complexity is O(n * |S|) for n heap size and subtraction set of size |S|. For competitive programming or larger instances, you want to detect the periodicity and use it to jump ahead rather than compute every single position. The period for subtraction games is bounded by 2^|S| in the worst case, though typical cases have much shorter periods. There are edge cases worth noting. If your subtraction set does not include 1, the game can have long sequences of consecutive losing positions, which changes the strategic feel entirely. Some subtraction sets produce surprisingly long pre-periods before periodicity kicks in. I once worked with a set where the pre-period was around 50 positions before the cycle of length 12 started repeating, which meant naive computation wasted significant effort on the non-repeating portion. Misère play changes the analysis substantially. Under misère rules, the last player to move loses. For single-heap subtraction games, the misère version can be handled by modifying the base case: position 0 becomes a winning position because the player whose turn it is at 0 has already lost (the previous player took the last object). However, this simple adjustment does not compose cleanly under the Sprague-Grundy framework. Misère play with multiple heaps requires a separate and more complex analysis. There are general theories for misère play of impartial games, but they are significantly more involved and the periodicity properties do not always carry over in an obvious way.
Get the Full Details
If you are implementing this, here is a practical Python snippet for computing N/P positions:
def subtraction_game_positions(n, S):
positions = [False] * (n + 1)
positions[0] = False Losing position
for i in range(1, n + 1):
for k in S:
if i - k >= 0 and not positions[i - k]:
positions[i] = True
break
return positions
Replace the boolean array with a mex-computing loop if you need Grundy values instead of just N/P classification. The mex (minimum excludant) of a set of non-negative integers is the smallest non-negative integer not present in the set. Grundy value of position 0 is 0. For position n, compute the mex of all Grundy values reachable in one move. The main limitation of subtraction games as a study tool or practical application is that they only model very restricted types of games. Real games rarely have a fixed subtraction set that does not change based on board state. Once you move to games like Green Hackenbush or arbitrary impartial games on graphs, the subtraction game framework does not apply directly and you need the full machinery of the Sprague-Grundy theorem with graph-based reachability analysis. But for learning the fundamentals of combinatorial game theory, subtraction games remain one of the most accessible entry points.
