NIM Game 이란?

NIM Game은 2명의 플레이어가 서로 다른 더미에서 개체를 번갈아 제거하는 수학적 전략 게임이다.
매 턴마다 각 플레이어는 하나 이상의 물체를 제거해야한다.
게임에 따라 마지막 개체를 가져가는 것을 피하거나 마지막 개체를 가져가는 버전이 있다.

NIM은 일반적으로 misère 게임으로 즉, 마지막 개체를 가져가는 플레이어가 패배합니다.

Misère Game
게임 규칙에 따라 지는 사람이 승자인 게임

NIM에 대한 완벽한 해법은 1901년 하버드 대학의 수학과 교수 Charles L. Bouton에 의해 제시되었고, NIM 이라는 용어도 그 때 처음 사용되었다.

---

NIM 게임 예시: 배스킨라빈스 31

'배스킨라빈스 31'이라는 게임을 아는 사람이 있다면 위에서 설명한 NIM 게임이 정확히 무엇인지 알 수 있을 것이다.

'배스킨라빈스 31' 게임은 1부터 31까지의 숫자를 한 사람당 1 ~ 3개씩 번갈아 불러 마지막 숫자인 31을 부르는 사람이 지는 게임으로 NIM 게임의 한 종류라고 볼 수 있다.

이 게임을 2명에서 할때의 필승법은 상당히 잘 알려져 있는데, 바로 첫번째 사람이 2개의 숫자 즉, 1과 2를 부르고 그 다음부터는 상대가 부르는 숫자의 개수와 자신이 부를 숫자의 개수의 합이 4개가 되도록 맞춰부르면 된다. $(2 + 4 \times 7 + 1 = 31)$

물론 3인 이상의 NIM 게임은 공정한 게임이기 때문에 3명 이상이 플레이한다면 어떻게 될지 알 수 없다.
하지만 2명이 플레이 한다고 하면 NIM 게임은 항상 우승 전략이 존재하며, '배스킨라빈스 31'의 경우 더미가 1개인 경우이지만 더미가 그것보다 많더라도 우승 전략이 존재한다.

---

NIM 게임 우승 전략

승리 포지션(Winning Poistions)

Nim 게임에서 승리하기 위한 전략은 플레이어가 상대방을 승리 포지션에 두게 만드는 것이다.

'배스킨라빈스 31' 게임과 달리 더미가 2, 3, 4개가 있는 경우 상대방 차례에 아래 표와 같은 승리 포지션을 가지게 된다면 해당 게임을 우승할 수 있다.

2 Heaps	3 Heaps	4 Heaps
1 1 *	1 1 1 **	1 1 1 1 *
2 2	1 2 3	1 1 n n
3 3	1 4 5	1 2 4 7
4 4	1 6 7	1 2 5 6
5 5	1 8 9	1 3 4 6
6 6	2 4 6	1 3 5 7
7 7	2 5 7	2 3 4 5
8 8	3 4 7	2 3 6 7
9 9	3 5 6	2 3 8 9
n n	4 8 12	4 5 6 7
	4 9 13	4 5 8 9
	5 8 13	n n m m
	5 9 12	n n n n

Heaps: 더미들
*: 일반적인 게임 한정
**: misère game 한정
n, m > 0

우승 전략 구하기

nim-sum

Nim은 초기 힙과 개체 수에 관계없이 수학적으로 해결되었으며, 어떤 플레이어가 이길지, 어떤 승리 동작이 해당 플레이어에게 열려 있는지를 쉽게 계산할 수 있는 방법이 있다.

게임 전략의 핵심은 각 힙의 사이즈에 대한 이진 합(binary digital sum)이다.
해당 연산은 XOR 연산 또는 모듈로(modulo) 연산이라고도 하며, 조합 게임 이론 내에서는 일반적으로 nim-sum이라고 불린다.
(해당 연산 기호는 ⊕로 표기된다.)

힙이 A, B, C가 있고 각 힙의 사이즈가 3, 4, 5라고 했을 때 nim-sum은 다음과 같다.

Binary Decimal Sum

$011_{2}$ $3_{10}$  Heap A
$100_{2}$ $4_{10}$  Heap B
$101_{2}$ $5_{10}$  Heap C

=======================

$010_2$ 210  The nim-sum of heaps A, B, and C, 3 ⊕ 4 ⊕ 5 = 2

정상적인 규칙에서의 우승 전략

정상적인 규칙 즉, 마지막으로 옮길 객체가 없는 사람이 이기는 규칙에서의 전략은 모든 턴에서 이러한 nim-sum을 0을 만드는 것이다.
자기 차례 전에 nim-sum이 0이 아니라면 이것을 항상 가능하며, nim-sum이 0이라면 상대는 지게된다.

어떤 힙에서 얼마나 제거해야 하는지 알기 위해서는 먼저 모든 힙 사이즈들의 nim-sum인 X를 알아야 한다.
그 후 각각의 힙의 사이즈와 X를 nim-sum하여 기존 힙 사이즈보다 작은 힙을 찾고, 기존 힙의 사이즈와 X를 nim-sum하여 얻은 값의 차이만큼 해당 힙에서 제거하면 된다.

예를 들어, 사이즈 3, 4, 5를 가지는 힙 A, B, C가 있다고 했을 때, X는 다음과 같다.

$X = 3 ⊕ 4 ⊕ 5 = 2$

그 다음 X와 각 힙 사이즈과 nim-sum을 하면 다음과 같다.

A ⊕ X = 3 ⊕ 2 = 1
B ⊕ X = 4 ⊕ 2 = 6
C ⊕ X = 5 ⊕ 2 = 7

이 상황에서 유일하게 줄어드는 힙은 A이기 때문에 A의 크기를 2개 제거하여 1로 줄인다.
이러면 nim-sum이 0이 되기 때문에 항상 이기는 상황이 만들어져 상대를 이길 수 있다.

misère game에서의 우승 전략

misère game 즉, 객체를 마지막으로 옯기는 사람이 지는 규칙에서의 전략은 정상적인 규칙에서의 우승 전략과 같지만 최소 2개의 객체가 있는 더미수가 홀수개가 될 때까지 수행한다는 점에서 다르다.

예를 들어, 사이즈 3, 4, 5를 가지는 힙 A, B, C가 있다고 했을 때 misère game 전략은 다음과 같이 적용된다.

player1, player2
A B C nim-sum
3 4 5 $010_2=2_{10}$ - 1
1 4 5 $000_2=0_{10}$ - 2
1 4 3 $110_2=6_{10}$ - 3
1 2 3 $010_2=0_{10}$ - 4
1 2 2 $010_2=1_{10}$ - 5
0 2 2 $010_2=0_{10}$ - 6
0 2 1 $010_2=3_{10}$ - 7
0 0 1 $010_2=1_{10}$ - 8

1. A에서 2개를 가져오면 nim-sum이 0이 되기 때문에 player1이 이길 것이다.
2. player2가 C에서 2개를 가져간다.
3. player1이 B에서 2개를 가져간다.
4. player2가 C에서 1개를 가져간다.
5. player1이 A에서 1개를 자겨산다.
6. player2가 C에서 1개를 가져간다.
7. player1이 B에서 2개를 가져간다.
8. player2가 C에서 1개를 가져가야 하기 때문에 player2가 지고, player1이 이긴다.

---

우승 전략 증명

NIM 게임의 우승 전략의 증명은 Charles L. Bouton에 의해 입증되었다.

Theorem
일반적인 NIM 게임에서의 초기에 nim-sum이 0이 아니라면 첫번째 플레이어가 이긴다.
먄약 초기에 nim-sum이 0이라면 두번때 플레이어가 이긴다.

이러한 이론의 증명은 다음과 같다.

nim-sum(⊕)은 결합 법칙, 교환 법칙을 따르며, 추가적으로 $x ⊕ x = 0$도 만족한다.
$x_1, ..., x_n$이 이동 전 힙의 크기이고, $y_1, ..., y_n$이 이동 후 힙의 크기라고 할 때, nim-sum $s, t$에 대해 $s = x_1 ⊕ ... ⊕ x_n$, $t = y_1 ⊕ ... ⊕ y_n$이라고 하자.
이 때, 이동이 힙 $k$에 있었다면, $i \neq k$에 대해 $x_i = y_i$이고 $x_k \geq y_k$이다.

그렇다면 nim-sum의 성질의 의해 다음과 같이 표현할 수 있다.

$\begin{aligned} t &= 0 ⊕ t\\ &= s ⊕ s ⊕ t\\ &= s ⊕ (x_1 ⊕ ... ⊕ x_n) ⊕ (y_1 ⊕ ... ⊕ y_n) = s ⊕ (x_1 ⊕ y_1) ⊕ .. ⊕ (x_n ⊕ y_n)\\ &= s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (x_k ⊕ y_k) ⊕ 0 ⊕ ... ⊕ 0\\ &= s ⊕ x_k ⊕ y_k \end{aligned}$
$(*) t = s ⊕ x_k ⊕ y_k$

Theorem은 아래 두 보조정리(Lemma)으로부터 증명된다.

보조정리(Lemma)
다른 정리를 증명하는 데 쓸 목적으로 증명된 명제

보조정리 1
$s = 0$이면, 어떤 이동을 하든 $t \neq 0$이다.

만약 $s = 0$이라고 가정했을 때, 이동할 객체가 있다면 승패가 명확하게 결정된 상태이기 때문에 의미가 없다. 따라서 이동할 객체가 있다고 하자.
그렇다면 $(*)$에 의해 $t = 0 ⊕ x_k ⊕ y_k$이고, $x_k \neq y_k$이므로 $t = x_k ⊕ y_k \neq 0$이다.

보조 정리 2
$s \neq 0$이면, $t = 0$으로 만들 수 있는 수가 존재한다.

이제 $s \neq 0$이라고 가정하자.
$s$를 2진법으로 나타냈을 때, 제일 왼쪽에 존재하는 1의 자리 수를 $d$라고 한다면, $s \neq 0$이기 때문에 $d$의 존재가 보장된다.

이제 2진법으로 나타냈을 때, $d$번째 자리의 수가 0이 아닌 $x_k$를 고른다.
만약 이런 $x_k$가 존재하지 않는다면, 모든 $x_i$의 $d$번째 자리는 0이고, nim-sum을 구하면 $s$의 $d$번째 자리는 0이 되어 모순이다.

이제 $y_k = s ⊕ x_k$라고 하자. $x_k \gt y_k$임을 보일 것이다.
$x_k$와 $y_k$의 $d$자리 왼쪽은 전부 똑같고, $s$의 $d$자리 왼쪽은 전부 0이므로 $d$자리의 수는 1에서 0으로 줄어든다.
이 차이는 10진법으로 $2^d$이고, $d$자리 오른쪽의 수는 아무리 차이나 봤자 $2^d - 1$이다. 따라서 $x_k$는 $y_k$보다 적어도 1 크다.
이는 곧 $x_k - y_k$개의 돌을 $k$번째 더미에서 가져갈 수 있음을 보장한다.
또한, $(*)$에서, $t = s ⊕ x_k ⊕ y_k = s ⊕ x_k ⊕ (s ⊕ x_k) = 0$이다.

따라서 보조정리에 의해 Theoreum이 증명된다.

---

참고 자료

• https://en.wikipedia.org/wiki/Nim
• https://en.wikipedia.org/wiki/Mis%C3%A8re
• https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=nyseul&logNo=220009539606
• https://librewiki.net/wiki/%ED%95%84%EC%8A%B9_%EC%A0%84%EB%9E%B5_%EA%B2%8C%EC%9E%84#.EC.84.B8_.EB.8D.94.EB.AF.B8_.EC.9D.B4.EC.83.81