Nim Game: XOR 규칙

Nim Game, 님 게임, nim

정의

Nim 은 여러 돌무더기에서 두 플레이어가 번갈아 한 무더기의 돌을 임의 수만큼 가져가는 게임. 마지막 돌을 가져가는 쪽이 승 (normal play).

Bouton’s Theorem

필패 상태 (P-position) ⟺ 모든 무더기의 XOR = 0.

즉, heap1 ⊕ heap2 ⊕ ... ⊕ heapn == 0 이면 다음 플레이어 패.

증명 스케치

1. 모든 무더기 크기 = 0 은 P-position (자명)
2. XOR ≠ 0 인 상태에서는 XOR = 0 으로 만드는 이동이 존재
3. XOR = 0 인 상태에서는 어떤 이동도 XOR 을 0 이 아닌 값으로 만듬

Misère Nim

마지막 돌을 가져가는 쪽이 패 (거꾸로 규칙). 무더기 개수 및 크기에 따라 규칙 달라짐:

• 모든 무더기가 1 이면: 무더기 개수의 홀짝
• 그 외: 일반 Nim 규칙과 동일

Sprague-Grundy

Nim 은 Sprague-Grundy 정리의 원형. 임의 impartial game 의 Grundy 값 = Nim 무더기 크기와 등가.

참고

• Sprague-Grundy
• Game Theory