iv. Loopy Games and Retrograde Analysis

When positions can repeat, the game graph has cycles: plain memoized recursion loops forever, and infinite play (a draw) becomes a possible outcome. Two tools: retrograde analysis (win / loss / draw with optimal game lengths, the way endgame tablebases are built) and the generalized Sprague–Grundy function of Smith and Fraenkel (to combine sums of loopy games).

Tool	Answers	Cost
retrograde analysis	outcome of every position, moves to the end (winner hurries, loser stalls)	$O(V+E)$
generalized SG $\gamma$	a value $\gamma (v)\in \{0,1,2,\dots \}\cup \{\infty (K)\}$ per position, enough to decide any sum	$O((V+E)\cdot (\max \gamma +2))$
partizan or “mover matters” games	run retrograde on states (position, player to move)	doubles the graph

Sum rule for the generalized SG function: all parts finite: XOR rule as usual; exactly one infinite part $\infty (K)$ and XOR $x$ of the others: the first player wins iff $x\in K$, otherwise draw; two or more infinite parts: draw.

// adj[v] = positions reachable in one move; a position with no move is a loss for the player to move.
// res[v] = 1 win, -1 loss, 0 draw (for the player to move); len[v] = moves until the end with optimal play.
pair<vector<int>, vector<int>> retrograde(const vector<vector<int>>& adj) {
    int n = sz(adj); vector<vector<int>> radj(n); vector<int> deg(n), res(n, 0), len(n, -1), q;
    for (int v = 0; v < n; v++) {
        deg[v] = sz(adj[v]);
        for (int u : adj[v]) radj[u].push_back(v);
        if (!deg[v]) res[v] = -1, len[v] = 0, q.push_back(v);
    }
    for (int h = 0; h < sz(q); h++) {
        int v = q[h];
        for (int p : radj[v]) {
            if (res[p]) continue;
            if (res[v] == -1) res[p] = 1, len[p] = len[v] + 1, q.push_back(p);           // a losing follower: win
            else if (--deg[p] == 0) res[p] = -1, len[p] = len[v] + 1, q.push_back(p);    // all followers win: loss
        }
    }
    return {res, len};                                       // res 0 = draw
}
 
// Generalized Sprague-Grundy (Smith): g[v] >= 0 finite value, or -1 (infinity) with K[v] = sorted finite follower values.
pair<vector<int>, vector<vector<int>>> loopyGrundy(const vector<vector<int>>& adj) {
    int n = sz(adj); vector<vector<int>> radj(n);
    for (int v = 0; v < n; v++) for (int u : adj[v]) radj[u].push_back(v);
    const int OPEN = -2, INF = -1;
    vector<int> g(n, OPEN), cnt(n), q; vector<char> has(n); int open = n;
    for (int i = 0; open > 0; i++) {
        // has[u]: u has a follower of value i; cnt[u]: followers that are open, or infinite without a follower of value i
        fill(all(has), 0); q.clear();
        for (int u = 0; u < n; u++) {
            cnt[u] = 0;
            for (int v : adj[u]) cnt[u] += g[v] < 0;
            if (g[u] == OPEN && !cnt[u]) q.push_back(u);
        }
        while (!q.empty()) {
            int u = q.back(); q.pop_back();
            if (g[u] != OPEN || has[u] || cnt[u]) continue;
            g[u] = i, open--;
            for (int p : radj[u]) {
                cnt[p]--;
                if (has[p]) continue;
                has[p] = 1;
                if (g[p] >= 0) continue;
                for (int r : radj[p]) if (--cnt[r] == 0 && g[r] == OPEN && !has[r]) q.push_back(r);
            }
        }
        for (int u = 0; u < n; u++) if (g[u] == OPEN && !has[u]) g[u] = INF, open--;
    }
    vector<vector<int>> K(n);
    for (int u = 0; u < n; u++) {
        if (g[u] != INF) continue;
        for (int v : adj[u]) if (g[v] >= 0) K[u].push_back(g[v]);
        sort(all(K[u])); K[u].erase(unique(all(K[u])), K[u].end());
    }
    return {g, K};
}
 
int loopyOutcome(int g, const vector<int>& K) {             // single game: 1 win, -1 loss, 0 draw
    if (g >= 0) return g ? 1 : -1;
    return binary_search(all(K), 0) ? 1 : 0;
}
 
int loopySumOutcome(const vector<pair<int, vector<int>>>& parts) {   // parts = {(g, K)} of the components
    int x = 0, inf = 0; const vector<int>* K = nullptr;
    for (auto& [g, k] : parts) { if (g >= 0) x ^= g; else inf++, K = &k; }
    if (inf == 0) return x ? 1 : -1;
    if (inf >= 2) return 0;
    return binary_search(all(*K), x) ? 1 : 0;
}

Definition used by loopyGrundy (Smith 1966, Fraenkel): $\gamma (u)=i$ iff (1) no follower has value $i$, (2) every $j<i$ is the value of some follower, and (3) every follower of value $\infty$ has itself a follower of value $i$ (so the opponent’s escape to an infinite position can be reversed). The values are assigned in rounds $i=0,1,\dots$; positions that can never satisfy the conditions get $\infty$.

Proof: retrograde analysis is correct, including draws and lengths

Labels are correct. A position is labelled win only when some follower is already a proven loss, and loss only when all its followers are proven wins (or it has none); by induction on the order of labelling, every label is a true outcome. Unlabelled positions are draws. At the end, an unlabelled position has no losing follower (it would have been labelled win) and at least one unlabelled follower (if all followers were wins, its counter would have reached 0). So the player to move cannot win (every follower is a win for the opponent or unlabelled) but can always move to another unlabelled position; the same holds for the opponent, so with correct play the game never ends: a draw. Lengths. The queue is processed in non-decreasing order of len (each push uses len[v] + 1 of the current, minimal element). A win is labelled from its first losing follower to be popped, i.e. the one with the smallest length: the winner takes the fastest win. A loss is labelled when its last follower is popped, i.e. with the largest length among its (winning) followers: the loser stalls as long as possible. Checked against a bounded-horizon brute force (“can the mover force a win within $d$ moves?” for increasing $d$) on random graphs.

Proof: the generalized SG function and sums

The defining conditions and the sum theorem are due to C. A. B. Smith (1966) and A. S. Fraenkel (with Perl and Yesha); a full proof is in Winning Ways (vol. 2, “Adders and Ladders”) and Fraenkel’s survey. The finite part works like Nim: from a sum with finite values and XOR $x\ne 0$ the mover moves a component of value $c$ with $c\oplus x<c$ to a follower of value $c\oplus x$ (condition 2); from XOR 0, a move to a smaller value is answered the same way, and a move to a larger or infinite value is reversed by moving back to the old value (condition 3, or condition 2 for finite larger values); Smith’s counter function makes sure the winner also makes progress, so the game ends. With one infinite component $\infty (K)$ and the rest XOR-ing to $x$, the mover wins by moving that component to a follower of value $x$ if $x\in K$; otherwise neither player can profitably leave the infinite component’s cycle, and play is drawn; two infinite components let each player keep play going forever. Here the statement is verified computationally: for random pairs and triples of graphs, loopySumOutcome agrees with retrograde analysis run on the product graph of the sum.

Applications. Endgame tablebases (chess, checkers), token games on general graphs, “cops and robbers”-type pursuit games (state = both positions plus the mover), and any contest game where a move can return to an earlier state.

Related notes

• Combinatorial Games and Nim
• Sprague–Grundy
• DAGs and Topological Sort (the acyclic case)