Nim

Nim is the oldest game with a known perfect strategy. Two players face several piles of objects; they move in turn, and a move is to take any number of objects, at least one, from a single pile. Take the last object and you win. Charles Bouton settled the game completely in $1901$: write each pile size in binary, add the columns without carrying, and the player to move loses exactly when every column comes out even. That column sum without carry is the bitwise exclusive-or of the pile sizes, now called the nim-sum, and the whole of strategy is to hand your opponent a position whose nim-sum is zero. The rule is so clean that it reads less like a heuristic than like a law, and it is the kind of law an integer program can be made to obey. Chlond and Akyol gave the formulation in the INFORMS Transactions on Education puzzle column; the modelling lesson is how to make a solver respect a constraint about binary digits.

The position

Four piles hold one, two, four, and eight objects, as in Figure 23.1. It is your move. The nim-sum is the exclusive-or of the four sizes; in binary each pile lights a single distinct bit, so the four together light every bit up to the fourth, and the nim-sum is fifteen, not zero. The position is therefore won for the player to move, and the task is to find the move that wins: reduce one pile so that the nim-sum of the four becomes zero.

The model

Variables

Let the current pile sizes be $a_1, \dots, a_n$. For each pile let $y_i \in \{0, \dots, a_i\}$ be its size after the move, and let $d_i \in \{0, 1\}$ flag the single pile that changes. To reason about the nim-sum we expose the binary digits: with $B$ bits enough to hold the largest pile, let $z_{ib} \in \{0, 1\}$ be bit $b$ of $y_i$, and let $w_b \ge 0$ be an integer used to force a column to be even.

Constraints

A move touches exactly one pile, and that pile strictly shrinks while the others stay put: $$\sum_{i} d_i = 1, \qquad y_i = a_i \ \text{if}\ d_i = 0, \qquad y_i \le a_i - 1 \ \text{if}\ d_i = 1.$$ The digits must be the genuine binary expansion of the new size, $$y_i = \sum_{b=0}^{B-1} 2^{b}\, z_{ib},$$ and the winning condition is that every binary column sums to an even number, which is exactly nim-sum zero: $$\sum_{i} z_{ib} = 2\, w_b, \qquad b = 0, \dots, B - 1.$$ There is no objective. A feasible point is a winning move; if the program is infeasible, no winning move exists and the position is already lost for the player to move, which Bouton’s theorem says happens precisely when the current nim-sum is zero.

The solver

The model goes straight to CP-SAT. The even-column constraint is the whole trick: it linearises the exclusive-or that defines the nim-sum, so the solver never has to reason about bit arithmetic directly, only about parity.

from ortools.sat.python import cp_model

def winning_move(piles):
    n = len(piles)
    B = max(piles).bit_length()
    m = cp_model.CpModel()
    y = [m.NewIntVar(0, piles[i], f"y{i}") for i in range(n)]
    d = [m.NewBoolVar(f"d{i}") for i in range(n)]
    m.Add(sum(d) == 1)
    for i in range(n):
        m.Add(y[i] == piles[i]).OnlyEnforceIf(d[i].Not())
        m.Add(y[i] <= piles[i] - 1).OnlyEnforceIf(d[i])
    z = {(i, b): m.NewBoolVar(f"z{i}_{b}")
         for i in range(n) for b in range(B)}
    for i in range(n):
        m.Add(y[i] == sum((1 << b) * z[i, b] for b in range(B)))
    for b in range(B):
        w = m.NewIntVar(0, n // 2, f"w{b}")
        m.Add(sum(z[i, b] for i in range(n)) == 2 * w)
    s = cp_model.CpSolver()
    if s.Solve(m) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    return tuple(s.Value(y[i]) for i in range(n))

On the piles $(1, 2, 4, 8)$ the solver returns $(1, 2, 4, 7)$: the only winning move is to take a single object from the pile of eight, leaving seven, shown as the copper ring in Figure 23.1. It is unique. The nim-sum’s top bit, the fourth, is lit by the pile of eight alone, so that pile is the only one whose size the move can lower without first having to raise another. After the move the piles are $1, 2, 4, 7$, every binary column holds an even count, and the position is handed back with a nim-sum of zero.

The misère turn

Bouton solved a second version in the same paper. In misère Nim the player who takes the last object loses, and the optimal play is identical to the ordinary game right up to the endgame: play to leave a nim-sum of zero until your move would leave only piles of a single object, and at that moment leave an odd number of them instead. The integer program adapts by switching the endgame condition once the heaps thin out, but the engine, the even-column constraint that pins the nim-sum, is the same. That a game this old yields entirely to a few parity constraints is the point worth carrying away: the binary representation is not a computational convenience laid over the game, it is the structure of the game, and an integer program that respects the digits inherits the whole theory for free.

Sources. The integer-programming treatment follows Martin J. Chlond and Oguz Akyol, A Nimatron, INFORMS Transactions on Education volume $3$, number $3$ ($2003$), pages $90$–$99$. The complete theory of the game is Charles L. Bouton, Nim, a Game with a Complete Mathematical Theory, Annals of Mathematics volume $3$ ($1901$–$1902$), pages $35$–$39$, which introduced the nim-sum and the binary winning rule. The chapter’s title recalls the Nimatron, the relay machine built by Edward Condon for Westinghouse that played Nim against visitors to the $1940$ New York World’s Fair (U.S. patent $2{,}215{,}544$, “Machine to Play Game of Nim,” granted $24$ September $1940$). The position solved here is a re-authored instance with a unique solution.