스프라그-그런디

공정 조합 게임

두 사람이 번갈아 두고, 둘 다 같은 수를 둘 수 있으며(공정성), 정보가 모두
공개되고 무승부가 없으며, 더 둘 수 없는 사람이 지는 게임을 공정 조합 게임
(impartial game) 이라 한다. 스프라그-그런디 정리는 이런 게임의 승패를 하나의
수로 환원한다.

님 게임

돌무더기가 여러 개 있고, 한 번에 한 무더기에서 원하는 만큼 가져간다. 마지막
돌을 가져가는 사람이 이긴다(normal play). 님의 필승 판정은 놀랍도록 간단하다.

모든 무더기 크기의 XOR가 0이 아니면 선공 승, 0이면 후공 승이다.

XOR가 0이 아니면 항상 XOR를 0으로 만드는 수가 있고, 0이면 어떤 수를 둬도
0이 아니게 된다 — 이 두 사실이 귀납적으로 필승 전략을 보장한다.

그런디 수 (Sprague-Grundy)

일반 게임의 한 상태 \(s\)에 대해, 거기서 한 번에 갈 수 있는 다음 상태들의 그런디
수 집합을 보고 그 집합에 없는 가장 작은 음이 아닌 정수를 그런디 수로
정의한다. 이 연산을 mex(minimum excludant)라 한다.

$$ g(s) = \operatorname{mex}\{\, g(t) : s \to t \,\} $$

• 더 둘 수 없는(종료) 상태의 그런디 수는 \(0\).
• \(g(s) = 0\)이면 그 상태는 패배(P-position), \(g(s) \ne 0\)이면 승리
  (N-position) 다.

직관: 크기 \(k\)인 님 무더기의 그런디 수가 정확히 \(k\)이므로, 그런디 수는 "이
게임이 크기 얼마짜리 님 무더기와 같은가"를 알려 준다.

스프라그-그런디 정리

여러 게임을 동시에 진행(한 턴에 그중 한 게임에서만 둠)하는 합 게임의 그런디
수는 각 게임 그런디 수의 XOR다.

$$ g(G_1 + G_2 + \dots + G_k) = g(G_1) \oplus g(G_2) \oplus \dots \oplus g(G_k) $$

따라서 복잡한 게임도 (1) 부분 게임마다 그런디 수를 구하고, (2) 전부 XOR한 뒤,
(3) 0인지로 승패를 판정하면 된다. 이 정리가 조합 게임 이론의 핵심이다.

적용 조건

normal play(마지막에 두는 사람이 승), 공정성, 유한·무사이클(또는 잘 정의된
종료)이 전제다. misère(마지막에 두면 짐)나 비공정 게임에는 그대로 쓸 수
없으니 주의한다.

mex와 그런디 수 계산

상태가 작은 정수로 표현되는 게임은 DP로 그런디 수를 채운다. 예로 "한 무더기에서
1, 3, 4개만 가져갈 수 있는 게임"의 그런디 수를 구해 보자.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
int grundy[MAXN];
int moves[] = {1, 3, 4};   // 가져갈 수 있는 개수

int mex(set<int>& s) {
    int m = 0;
    while (s.count(m)) m++;   // 집합에 없는 최소 음이 아닌 정수
    return m;
}

int main() {
    grundy[0] = 0;            // 종료 상태
    for (int n = 1; n < MAXN; n++) {
        set<int> reach;
        for (int d : moves)
            if (n - d >= 0) reach.insert(grundy[n - d]);
        grundy[n] = mex(reach);
    }
    // 여러 무더기 a1, a2, ... 이면 grundy[a1] ^ grundy[a2] ^ ...
    // 결과가 0이 아니면 선공 승
    return 0;
}

여러 무더기로 이뤄진 합 게임이면, 위에서 구한 무더기별 그런디 수를 모두 XOR해
0인지 본다.

흔한 실수

• mex 오해 — mex는 "집합의 최댓값+1"이 아니라 "빠진 가장 작은 음 아닌
  정수"다. \(\{0, 1, 3\}\)의 mex는 2다.
• 종료 상태 그런디 — 더 둘 수 없는 상태는 반드시 \(0\)으로 둬야 한다.
• misère 혼동 — 마지막에 두면 지는 규칙은 그런디 정리를 그대로 못 쓴다.
  님 한정으로 별도 misère 정리가 있다.
• XOR 빠뜨림 — 부분 게임이 여럿이면 단순 합이 아니라 XOR여야 한다.

그런디 수의 규칙 찾기

게임이 커서 직접 DP가 불가능하면, 작은 값들을 출력해 주기/공식을 추측한다.
예컨대 "1개 또는 2개를 가져가는 님"의 그런디 수는 \(n \bmod 3\)이고, "마지막에
두면 이기는 단일 무더기"는 \(g(n) = n\)이다. 패턴을 찾으면 큰 \(n\)도 \(O(1)\)로
답한다.

대표 응용

스프라그-그런디는 "공정 게임의 승패"라는 광범위한 문제를 XOR 한 줄로 답하게
해 주는 강력한 환원이다. 핵심은 게임을 독립된 부분 게임의 합으로 보는 안목과,
각 부분의 그런디 수를 정확히 계산하는 mex DP다.