스프라그-그런디 정리 (Sprague-Grundy)

정의

스프라그-그런디 정리 (Sprague-Grundy) 는 모든 impartial combinatorial game (두 플레이어가 같은 행동 가능, 무작위성 없음, 완전 정보) 이 Nim-heap 하나와 동등함을 증명하는 정리. 각 게임 상태는 Grundy number (nimber) 로 표현되며, Grundy number 가 0 이면 패배 상태, 0 이 아니면 승리 상태.

문제 상황과 동기

여러 impartial game 이 동시에 진행될 때 (e.g., Nim 의 여러 더미), 각각을 독립 분석 후 XOR 로 합성.

• naive: 전체 상태 공간의 game tree 그리기. 상태 폭발.
• SG 이론: 각 부분 게임의 Grundy 수를 XOR. 모든 상태를 Nim 으로 환원.

핵심 통찰: 모든 impartial game 의 상태는 자연수 (Grundy number) 로 완전히 추상화되며, 게임의 합성은 XOR.

시각화

핵심 아이디어

Grundy Number 정의

G(v) = mex({ G(u) | v -> u })

• mex: Minimum EXcluded non-negative integer.
• v -> u: 상태 v 에서 한 번의 행동으로 도달 가능한 상태 u.
• G(v) = 0: losing state (P-position).
• G(v) != 0: winning state (N-position).

게임 합성 (Nim-Sum)

여러 독립 게임 G1, G2, ..., Gk 가 동시에 진행될 때:

G_total = G1 xor G2 xor ... xor Gk

G_total = 0 이면 후공 승, != 0 이면 선공 승.

계산 예시 (돌 게임, take {1, 3, 4})

G(0) = 0                  (terminal, no moves)
G(1) = mex({G(0)}) = mex({0}) = 1
G(2) = mex({G(1)}) = mex({1}) = 0
G(3) = mex({G(2), G(0)}) = mex({0, 0}) = 1
G(4) = mex({G(3), G(1), G(0)}) = mex({1, 1, 0}) = 2
G(5) = mex({G(4), G(2), G(1)}) = mex({2, 0, 1}) = 3

알고리즘

compute_grundy(max_state, moves):
    G[0..max_state] = 0
    for s = 1..max_state:
        reachable = empty set
        for m in moves:
            if s >= m:
                reachable.add(G[s - m])
        G[s] = mex(reachable)
    return G

mex(S):
    g = 0
    while g in S: g++
    return g

# 게임 합성
xor_sum = 0
for g in grundy_numbers_of_each_game:
    xor_sum ^= g
winner = "First" if xor_sum != 0 else "Second"

구현

// Grundy number DP + 게임 합성
#include <bits/stdc++.h>
using namespace std;
​
int mex(const vector<bool>& seen) {
  int g = 0;
  while (g < (int)seen.size() && seen[g]) g++;
  return g;
}
​
int main() {
  const int MAX = 1000;
  vector<int> moves = {1, 3, 4};
  vector<int> G(MAX + 1, 0);
​
  for (int s = 1; s <= MAX; s++) {
      vector<bool> seen(MAX + 1, false);
      for (int m : moves)
          if (s >= m) seen[G[s - m]] = true;
      G[s] = mex(seen);
  }
​
  int N; cin >> N;
  if (G[N])
      cout << "G(" << N << ") = " << G[N]
           << " -> First wins\n";
  else
      cout << "G(" << N << ") = 0 -> Second wins\n";
​
  // 여러 게임 합성
  int k; cin >> k;
  int xsum = 0;
  for (int i = 0; i < k; i++) {
      int p; cin >> p;
      // Nim: Grundy = pile size
      xsum ^= p;
  }
  cout << "Nim XOR = " << xsum << " -> "
       << (xsum ? "First" : "Second") << "\n";
  return 0;
}

# Grundy number + Nim XOR
def mex(seen):
  g = 0
  while g < len(seen) and seen[g]:
      g += 1
  return g
​
MAX = 1000
moves = [1, 3, 4]
G = [0] * (MAX + 1)
for s in range(1, MAX + 1):
  seen = [False] * (MAX + 1)
  for m in moves:
      if s >= m:
          seen[G[s - m]] = True
  G[s] = mex(seen)
​
N = int(input())
if G[N]:
  print(f"G({N}) = {G[N]} -> First wins")
else:
  print(f"G({N}) = 0 -> Second wins")
​
k = int(input())
piles = list(map(int, input().split()))
xsum = 0
for p in piles:
  xsum ^= p
print(f"Nim XOR = {xsum} -> {'First' if xsum else 'Second'}")

import java.util.*;
import java.io.*;
​
public class Main {
  static int mex(boolean[] seen) {
      int g = 0;
      while (g < seen.length && seen[g]) g++;
      return g;
  }
​
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int MAX = 1000;
      int[] moves = {1, 3, 4};
      int[] G = new int[MAX + 1];
​
      for (int s = 1; s <= MAX; s++) {
          boolean[] seen = new boolean[MAX + 1];
          for (int m : moves)
              if (s >= m) seen[G[s - m]] = true;
          G[s] = mex(seen);
      }
​
      int N = Integer.parseInt(br.readLine());
      if (G[N] != 0)
          System.out.println("G(" + N + ") = " + G[N] + " -> First wins");
      else
          System.out.println("G(" + N + ") = 0 -> Second wins");
​
      int k = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      int xsum = 0;
      for (int i = 0; i < k; i++)
          xsum ^= Integer.parseInt(st.nextToken());
      System.out.println("Nim XOR = " + xsum + " -> " + (xsum != 0 ? "First" : "Second"));
  }
}

5
3
1 2 3

G(5) = 3 -> First wins
Nim XOR = 0 -> Second

2
2
3 3

G(2) = 0 -> Second wins
Nim XOR = 0 -> Second

복잡도

변형 / 활용

응용 분야

SG + DP

• 다각형 게임 (BOJ 13034): N-각형 대각선 긋기. 분할 영역의 Grundy XOR.
• 격자 게임: 2차원 격자 말 이동. 각 행/열 독립 후 XOR.

함정

1. mex 계산 실수

mex 는 집합에 없는 가장 작은 0 이상 정수. 0부터 순차 확인.

2. 게임 합성 착각

독립적일 때만 XOR 합성 성립. 상태가 연동되면 각각 SG 따로 계산 불가.

3. 큰 상태 공간

MAX 10^6 이상이면 DP 불가. 주기성 찾거나 수식 도출.

BOJ 연습 문제

참고

• 게임 이론