Chapter 132

Home

Sprague-Grundy Theorem

Every impartial combinatorial game is equivalent to a Nim heap of size Grundy(n). Base: Grundy(terminal) = 0. For any position, Grundy = mex{ Grundy(reachable positions) }. The XOR of component Grundy numbers determines the overall winner.

Computing Grundy Numbers

C++ — Grundy for a subtraction game

vector grundy(int max_n, vector& moves) {
    vector g(max_n + 1, 0);
    for (int n = 1; n <= max_n; n++) {
        vector seen(moves.size() + 2, false);
        for (int m : moves)
            if (n >= m) seen[g[n - m]] = true;
        while (seen[g[n]]) g[n]++;
    }
    return g;
}

// mex = minimum excluded non-negative integer.
// Grundy = mex of Grundy values of all reachable positions.