조합 게임 이론(Combinatorial Game Theory)은 두 플레이어가 완전 정보, 무작위성 없이 번갈아 움직이는 게임을 분석한다. Nim 게임과 Sprague-Grundy 정리가 핵심이다.
Nim 게임
n개의 돌 더미에서 번갈아 임의 개수를 가져가고, 마지막을 가져가는 쪽이 이기는 게임.
승리 조건: 모든 더미 수의 XOR ≠ 0
패배 조건: 모든 더미 수의 XOR = 0 (Nim-value = 0)
예: 더미 [3, 5, 7]
3 XOR 5 XOR 7 = 011 XOR 101 XOR 111 = 001 ≠ 0 → 선공 승리
Sprague-Grundy 정리
모든 공정 게임(Impartial Game)은 Nim 게임으로 표현 가능하다.
python
from functools import lru_cache
def mex(s):
"""최소 제외 수 (Minimum EXcluded value)"""
i = 0
while i in s: i += 1
return i
@lru_cache(maxsize=None)
def grundy(state):
"""게임 상태의 Grundy 값(Nim-value) 계산"""
# state에서 가능한 다음 상태들의 Grundy 값 집합
reachable = set()
for next_state in get_moves(state):
reachable.add(grundy(next_state))
return mex(reachable)
# 0이면 현재 플레이어 패배, 0 이외면 승리
def composite_game(*states):
"""복합 게임: 각 게임 Grundy 값을 XOR"""
result = 0
for s in states:
result ^= grundy(s)
return result # 0이면 패배
대표적 게임
| 게임 | Grundy 계산 |
|---|
| Nim | 더미 크기 자체 |
| Subtraction Game | 주기적 패턴 |
| Green Hackenbush | 사이클·경로 분석 |
관련 개념
