Chapter 133

Home

Refactoring: Memoized Grundy

The iterative Grundy table computes ALL values up to N. For games with large state spaces, memoisation computes only reachable positions — top-down recursion with caching.

Before: Iterative table (computes all)

C++ — O(N × |moves|)

for (int n = 1; n <= max_n; n++) { /* compute all */ }

After: Top-down memoisation

C++ — memoised Grundy

vector memo;
vector moves;

int grundy(int n) {
    if (n == 0) return 0;
    if (memo[n] != -1) return memo[n];

    vector seen(moves.size() + 2, false);
    for (int m : moves)
        if (n >= m) seen[grundy(n - m)] = true;

    int g = 0;
    while (seen[g]) g++;
    return memo[n] = g;
}

// Only computes states reachable from the query.
// Saves time when the state space is sparse.