Sprague-Grundy Theorem: 게임 이론 통일

Sprague-Grundy Theorem, Sprague-Grundy, Grundy Number, 님 값

정의

Sprague-Grundy Theorem: 모든 impartial game (플레이어 무관, deterministic, no draw) 은 하나의 Nim 무더기와 등가.

각 상태 v 의 Grundy number g(v):

$$g(v)=\text{{}mex\}\{g(u):v\to u\}$$

mex = Minimum EXcluded non-negative integer.

게임 합 (game sum)

여러 게임을 병렬로 진행하는 합 게임의 Grundy = 개별 Grundy 의 XOR.

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

필패 판정

g(state) = 0 ⟺ P-position (다음 플레이어 패)

예제

• Nim: g(pile of n) = n
• Kayles: 특정 패턴 반복
• Green Hackenbush: 트리로 환원

참고

• Nim Game
• Game Theory
• Hackenbush