63. Nim Game & Sprague-Grundy Theorem

님 게임(Nim Game)은 간단하면서도 게임 이론에서 중요한 역할을 하는 게임으로, 여기서 사용된 전략을 다른 많은 게임에 응용해서 적용할 수 있다. 님 게임은 $0$개 이상의 돌이 있는 $n$개의 더미에서 번갈아 가면서 돌을 가져가는 방식으로 차례를 진행한다. 가져가는 돌의 개수에는 제한이 없지만 한 차례에는 하나의 더미에서만 돌을 가져갈 수 있다. 더이상 돌을 가져갈 수 없는 플레이어가 게임에서 지게 된다.

 

님 게임에서 각각의 더미에 남아 있는 돌의 개수를 $[x_1, x_2, \ldots x_n]$이라고 하면 이 게임의 상태를 님 합(Nim Sum)으로 분류할 수 있다. 님 합 $s = x_1 \oplus x_2 \oplus \ldots \oplus x_n$이며, $\oplus$는 XOR 연산을 나타낸다. 각각의 상태에서 님 합 $s$가 $0$이면 이길 수 없는 상태이고 $0$이 아니면 이길 수 있는 상태인데, 이는 님 합이 $0$이 아닌 상태에서 한 차례를 진행한 후 항상 님 합이 $0$인 상태가 되도록 할 수 있음을 의미한다. 더이상 돌이 없는 경우 님 합이 $0$이므로 이길 수 없는 상태임은 쉽게 알 수 있다.

 

님 합이 $0$이 아닌 상태에서 한 차례를 진행해서 님 합이 $0$인 상태가 되도록 하는 것이 항상 가능함은 다음과 같이 보일 수 있다. $s$가 $0$이 아닌 경우, $s$의 최상위 비트를 $p$라고 하면 더미에 있는 돌의 수에서 비트 $p$의 값이 $1$인 더미가 하나 이상 존재한다. 이 더미에 있는 돌의 수를 $k$라고 하면 $k \oplus s$는 항상 $k$보다 작다. 이제 이 더미에서 적절한 개수의 돌을 가져가서 이 더미에 남은 돌의 수가 $k \oplus s$가 되게 하면 님 합이 $0$으로 변하고 이길 수 없는 상태가 된다. 따라서 원래의 상태는 이길 수 있는 상태이다.

 

님 게임의 승패 여부는 님 합을 이용해서 알아낼 수 있다. 이와 유사한 게임으로 미제르 님 게임(Misère Nim Game)이라는 것이 있는데 이 게임은 님 게임과 규칙은 같고 더이상 돌을 가져갈 수 없는 플레이어가 게임에서 이긴다. 이 게임의 승패 여부 역시 님 합을 이용해서 알아낼 수 있는데, 님 합 $s$가 $1$이면 이길 수 없으며 $1$이 아니면 이길 수 있다. 즉 님 합이 $1$이 되도록 돌을 가져가는 것이 최적의 전략이 된다.

---

스프라그-그런디 정리(Sprague-Grundy Theorem)는 님 합을 이용하는 님 게임 전략을 일반화한 것으로, 게임이 다음 조건을 모두 만족한다면 이 정리를 적용할 수 있다.

• 두 플레이어가 번갈아 가면서 차례를 진행한다.
• 게임에는 여러 상태가 존재하며 상태 간에 이동하는 방법은 누구의 차례인지에 영향을 받지 않는다.
• 더이상 이동할 수 있는 상태가 없으면 게임을 종료한다. 모든 게임은 언젠가는 종료된다.
• 모든 플레이어는 게임의 상태, 움직임 등에 대한 정보를 가지고 있으며 게임에는 무작위적인 요소가 없다.

각각의 상태에는 하나의 그런디 수(Grundy Number)가 대응되며, 다음과 같은 공식을 이용하여 계산할 수 있다.

$$G = \text{mex}(\{g_1, g_2, \ldots g_k\})$$

식에서 $g_1, g_2, \ldots g_k$는 현재 상태에서 이동할 수 있는 각각의 상태의 그런디 수이며, $\text{mex}$ 함수는 주어진 집합에 등장하지 않는 $0$ 이상의 가장 작은 정수를 구하는 함수이다. 더이상 이동할 수 있는 상태가 없는 경우 그런디 수는 $\text{mex}(\varnothing) = 0$이 된다. 그런디 수가 $0$이면 그 상태는 이길 수 없는 상태이며 $0$이 아니면 이길 수 있는 상태이다.

 

그런디 수가 $x$라는 것은 그 상태에서 그런디 수가 $0, 1, \ldots, x-1$인 어떤 상태로 항상 이동할 수 있다는 것과 같다. 또한 그런디 수가 $x$보다 큰 상태로 이동할 수 있는 경우도 있는데, 상대가 다시 그런디 수가 $x$인 상태로 이동할 수 있으므로 실제로 큰 의미는 없다.

 

게임이 여러 개의 부분 게임으로 구성되고 각각의 플레이어가 자신의 차례의 부분 게임 중 하나를 선택하여 이동할 수 있는 경우, 전체 상태의 그런디 수는 각각의 부분 게임의 그런디 수의 님 합과 같다. 또한 어떤 상태에서 특정한 움직임을 통해 게임을 서로 영향을 주지 않는 여러 부분 게임으로 나눌 수 있는 경우도 존재하는데, 이런 경우에도 앞에서 나온 공식을 이용해서 그런디 수를 계산할 수 있다.

 

[연습문제]

 

BOJ 11868. 님 게임 2 (Platinum IV)

기본적인 님 게임 문제이다. 님 합이 $0$이면 지고, 아니면 이긴다.

 

BOJ 16895. 님 게임 3 (Platinum IV)

위에서 설명한 방법대로 님 합을 $0$으로 만들 수 있는 더미의 수를 구하면 된다.

 

BOJ 13034. 다각형 게임 (Platinum III)

스프라그-그런디 정리를 이용하면 각각의 상태에 대한 그런디 수를 구할 수 있다.

 

BOJ 11717. Wall Making Game (Platinum II)

왼쪽 위 칸이 $(i_1, j_1)$이고 오른쪽 아래 칸이 $(i_2, j_2)$인 경우의 그런디 수를 각 칸을 선택하는 경우로 나눠서 그런디 수를 구하면 된다. 시간복잡도는 $\Theta(H^3W^3)$이고 단순화하면 $\Theta(n^6)$이다.

 

→ solved.ac tag: sprague_grundy