스프라그-그런디 정리. Nim¶
소개¶
이 정리는 이른바 공평한(impartial) 2인 게임, 즉 가능한 수와 승패가 오직 게임의 상태에만 의존하는 게임을 다룹니다. 다시 말해, 두 플레이어 사이의 유일한 차이는 그중 한 명이 먼저 둔다는 점뿐입니다.
또한 게임이 완전 정보(perfect information) 게임이라고 가정합니다. 즉, 플레이어에게 숨겨진 정보가 전혀 없습니다(플레이어는 규칙과 가능한 수를 알고 있습니다).
게임은 유한하다고 가정합니다. 즉, 일정한 횟수의 수를 둔 뒤에는 플레이어 중 한 명이 패배 위치에 놓이게 되며, 그 위치에서는 다른 위치로 이동할 수 없습니다. 반대로, 상대에게 이러한 위치를 만들어 준 플레이어가 승리합니다. 당연히 이 게임에는 무승부가 없습니다.
이러한 게임은 방향 비순환 그래프(directed acyclic graph)로 완전히 표현할 수 있습니다. 정점은 게임 상태이고 간선은 전이(수)입니다. 나가는 간선이 없는 정점은 패배 정점입니다(이 정점에서 수를 두어야 하는 플레이어가 패배합니다).
무승부가 없으므로 모든 게임 상태를 승리 상태 또는 패배 상태로 분류할 수 있습니다. 승리 상태란 상대가 최선으로 대응하더라도 상대의 패배를 피할 수 없게 만드는 수가 존재하는 상태입니다. 패배 상태란 모든 수가 상대에게 승리 상태로 이어지는 상태입니다. 요약하면, 어떤 상태에서 패배 상태로 가는 전이가 하나 이상 있으면 그 상태는 승리 상태이고, 패배 상태로 가는 전이가 하나도 없으면 패배 상태입니다.
우리의 과제는 주어진 게임의 상태를 분류하는 것입니다.
이러한 게임의 이론은 1935년 Roland Sprague와 1939년 Patrick Michael Grundy가 각각 독립적으로 발전시켰습니다.
Nim¶
이 게임은 위에서 설명한 제약 조건을 따릅니다. 더 나아가, 완전 정보를 가진 공평한 2인 게임은 어떤 것이든 Nim 게임으로 환원할 수 있습니다. 이 게임을 연구하면 다른 모든 유사한 게임을 풀 수 있게 되지만, 이에 대해서는 나중에 더 자세히 다룹니다.
역사적으로 이 게임은 고대에 인기가 있었습니다. 이 게임의 기원은 아마도 중국일 것입니다. 적어도 Jianshizi라는 게임이 이와 매우 비슷합니다. 유럽에서 이 게임에 대한 가장 이른 언급은 16세기의 것입니다. 이 이름은 Charles Bouton이 붙였으며, 그는 1901년에 이 게임에 대한 완전한 분석을 발표했습니다.
게임 설명¶
여러 개의 더미가 있고, 각 더미에는 여러 개의 돌이 있습니다. 한 번의 수에서 플레이어는 아무 더미 하나를 골라 양의 정수 개수만큼 돌을 가져가 버릴 수 있습니다. 수를 둘 수 없는 플레이어가 패배하며, 이는 모든 더미가 비었을 때 일어납니다.
게임 상태는 양의 정수로 이루어진 중복집합(multiset)으로 모호함 없이 표현됩니다. 한 번의 수는 선택한 정수를 순감소시키는 것입니다(0이 되면 집합에서 제거됩니다).
풀이¶
Charles L. Bouton의 풀이는 다음과 같습니다:
정리. 현재 플레이어가 필승 전략을 가질 필요충분조건은 더미 크기들의 xor 합이 0이 아닌 것입니다. 수열 $a$의 xor 합은 $a_1 \oplus a_2 \oplus \ldots \oplus a_n$이며, 여기서 $\oplus$는 비트 단위 배타적 논리합입니다.
증명. 증명의 핵심은 상대방의 대칭 전략이 존재한다는 점입니다. xor 합이 0인 상태에 한 번 놓인 플레이어는 장기적으로 이를 0이 아닌 값으로 만들 수 없음을 보이겠습니다. 플레이어가 xor 합이 0이 아닌 상태로 전이하면, 상대는 항상 xor 합을 다시 0으로 되돌리는 수를 둘 수 있습니다.
수학적 귀납법으로 정리를 증명하겠습니다.
빈 Nim(모든 더미가 비어 있는 경우, 즉 멀티셋이 비어 있는 경우)에서는 xor 합이 0이며 정리가 성립합니다.
이제 비어 있지 않은 상태에 있다고 가정합시다. 귀납법의 가정(그리고 게임의 비순환성)을 이용하여, 현재 상태에서 도달 가능한 모든 상태에 대해 정리가 증명되었다고 가정합니다.
그러면 증명은 두 부분으로 나뉩니다. 현재 상태의 xor 합이 $s = 0$이면 이 상태가 지는 상태임을, 즉 도달 가능한 모든 상태의 xor 합이 $t \neq 0$임을 증명해야 합니다. $s \neq 0$이면 $t = 0$인 상태로 이어지는 수가 존재함을 증명해야 합니다.
-
$s = 0$이라 하고 임의의 수를 생각해 봅시다. 이 수는 크기가 $x$인 더미를 크기 $y$로 줄입니다. $\oplus$의 기본 성질을 이용하면 다음을 얻습니다.
$$ t = s \oplus x \oplus y = 0 \oplus x \oplus y = x \oplus y $$$y < x$이므로 $y \oplus x$는 0이 될 수 없고, 따라서 $t \neq 0$입니다. 즉 (귀납법의 가정에 의해) 도달 가능한 모든 상태는 승리 상태이므로, 현재 우리는 패배 상태에 있습니다.
-
$s \neq 0$이라 합시다. 수 $s$의 이진 표현을 생각해 봅시다. $d$를 그중 0이 아닌 최상위(가장 큰 값의) 비트의 인덱스라 합시다. 크기의 $d$번 비트가 켜져 있는 더미에서 수를 둡니다(그러한 더미는 반드시 존재합니다. 그렇지 않다면 $s$에서 그 비트가 켜져 있을 수 없습니다). 그 더미의 크기 $x$를 $y = x \oplus s$로 줄입니다. $x$와 $y$에서 $d$보다 높은 위치의 모든 비트는 일치하며, $d$번 비트는 $x$에서는 켜져 있지만 $y$에서는 꺼져 있습니다. 따라서 $y < x$이며, 수가 규칙에 맞으려면 이것만으로 충분합니다. 이제 다음이 성립합니다:
$$ t = s \oplus x \oplus y = s \oplus x \oplus (s \oplus x) = 0 $$즉 (귀납법의 가정에 의해) 도달 가능한 패배 상태를 찾았으므로 현재 상태는 승리 상태입니다.
따름정리. Nim의 모든 상태는 xor 합이 바뀌지 않는 한 동등한 상태로 대체할 수 있습니다. 또한 여러 더미로 이루어진 Nim을 분석할 때, 이를 크기가 $s$인 단일 더미로 대체할 수 있습니다.
Misère 게임¶
미제르 게임에서는 게임의 목표가 반대이므로, 마지막 막대를 가져가는 플레이어가 게임에서 집니다. 미제르 Nim 게임은 표준 Nim 게임과 거의 같은 방식으로 최적으로 플레이할 수 있음이 밝혀졌습니다. 아이디어는 먼저 미제르 게임을 표준 게임처럼 플레이하다가, 게임의 마지막 단계에서 전략을 바꾸는 것입니다. 새로운 전략은 다음 수를 둔 후 각 더미에 막대가 최대 하나씩만 남게 되는 상황에서 도입됩니다. 표준 게임에서는 수를 둔 후 막대가 하나인 더미의 개수가 짝수가 되도록 수를 골라야 합니다. 하지만 미제르 게임에서는 막대가 하나인 더미의 개수가 홀수가 되도록 수를 고릅니다. 이 전략이 통하는 이유는 전략이 바뀌는 상태가 게임에서 항상 나타나며, 이 상태는 막대가 두 개 이상인 더미를 정확히 하나 포함하므로 nim 합이 0이 아니어서 승리 상태이기 때문입니다.
불편 게임과 Nim의 동치성 (Sprague-Grundy 정리)¶
이제 임의의 불편 게임의 임의의 게임 상태에 대해, 이에 대응하는 Nim의 상태를 찾는 방법을 알아보겠습니다.
증가가 허용된 Nim에 관한 보조정리¶
Nim을 다음과 같이 변형한 게임을 생각해 봅시다. 선택한 더미에 돌을 추가하는 것도 허용합니다. 증가가 언제, 어떻게 허용되는지에 대한 정확한 규칙은 우리의 관심사가 아니지만, 그 규칙은 게임을 비순환적으로 유지해야 합니다. 이후 절에서 예시 게임들을 살펴봅니다.
보조정리. Nim에 증가를 추가해도 승리 상태와 패배 상태가 결정되는 방식은 바뀌지 않습니다. 다시 말해, 증가는 쓸모가 없으며 승리 전략에서 이를 사용할 필요가 없습니다.
증명. 어떤 플레이어가 더미에 돌을 추가했다고 가정합시다. 그러면 상대는 그 수를 그대로 되돌릴 수 있습니다 — 개수를 이전 값으로 다시 줄이면 됩니다. 게임은 비순환적이므로, 조만간 현재 플레이어는 증가 수를 사용할 수 없게 되어 일반적인 Nim의 수를 두어야 합니다.
스프라그-그런디 정리¶
두 플레이어 불편 게임의 상태 $v$를 생각하고, $v_i$를 그 상태에서 도달 가능한 상태들이라고 합시다(여기서 $i \in \{ 1, 2, \dots, k \} , k \ge 0$). 이 상태에 크기가 $x$인 더미 하나로 이루어진, 완전히 동치인 Nim 게임을 대응시킬 수 있습니다. 수 $x$를 상태 $v$의 그런디 값 또는 nim 값이라고 합니다.
또한 이 수는 다음과 같은 재귀적인 방법으로 구할 수 있습니다.
여기서 $x_i$는 상태 $v_i$의 그런디 값이고, 함수 $\text{mex}$(minimum excludant)는 주어진 집합에 없는 가장 작은 음이 아닌 정수입니다.
게임을 그래프로 보면, 나가는 간선이 없는 정점부터 시작하여 그런디 값을 점진적으로 계산할 수 있습니다. 그런디 값이 0이라는 것은 해당 상태가 패배 상태라는 뜻입니다.
증명. 귀납법을 사용하여 증명하겠습니다.
둘 수 있는 수가 없는 정점의 경우, 값 $x$는 공집합의 $\text{mex}$이며, 이는 0입니다. 빈 Nim은 패배 상태이므로 이는 올바릅니다.
이제 다른 임의의 정점 $v$를 생각해 봅시다. 귀납법에 의해, 그 정점에서 도달 가능한 정점들에 대응하는 값 $x_i$가 이미 계산되어 있다고 가정합니다.
$p = \text{mex}\ \{ x_1, \ldots, x_k \}$라고 합시다. 그러면 임의의 정수 $i \in [0, p)$에 대해 그런디 값이 $i$인 도달 가능한 정점이 존재함을 알 수 있습니다. 이는 $v$가 크기가 $p$인 더미 하나로 이루어진, 증가가 허용된 Nim 게임의 상태와 동치임을 의미합니다. 이러한 게임에서는 $p$보다 작은 모든 크기의 더미로 가는 전이가 있으며, $p$보다 큰 크기의 더미로 가는 전이가 있을 수도 있습니다. 따라서 $p$는 실제로 현재 고려하고 있는 상태에 대해 구하고자 하는 그런디 값입니다.
정리의 응용¶
마지막으로, 임의의 2인 불편 게임에 적용할 수 있는, 게임의 승패 결과를 판정하는 알고리즘을 설명합니다.
주어진 상태의 그런디 값을 계산하려면 다음을 수행해야 합니다:
-
이 상태에서 가능한 모든 전이를 구합니다
-
각 전이는 독립적인 게임들의 합(퇴화된 경우에는 게임 하나)으로 이어질 수 있습니다. 각 독립적인 게임의 그런디 값을 계산하고 이들을 xor 합합니다. 물론 게임이 하나뿐이라면 xor은 아무런 영향을 주지 않습니다.
-
각 전이에 대해 그런디 값을 계산한 후, 이 수들의 $\text{mex}$로 해당 상태의 값을 구합니다.
-
값이 0이면 현재 상태는 패배 상태이고, 그렇지 않으면 승리 상태입니다.
앞 절과 비교하면, 여기서는 결합된 게임으로의 전이가 있을 수 있다는 사실을 고려합니다. 이들을 더미의 크기가 독립적인 게임들의 그런디 값과 같은 Nim으로 간주합니다. Bouton의 정리에 따라 일반적인 Nim과 마찬가지로 이들의 xor 합을 구할 수 있습니다.
그런디 값의 패턴¶
그런디 값을 이용하여 구체적인 문제를 풀 때, 패턴을 찾기 위해 값의 표를 살펴보는 것이 도움이 되는 경우가 매우 많습니다.
이론적으로 분석하기 상당히 어려워 보이는 많은 게임에서도 그런디 값이 주기적이거나 쉽게 이해할 수 있는 형태로 나타납니다. 대부분의 경우 관찰된 패턴은 참으로 밝혀지며, 원한다면 귀납법으로 증명할 수 있습니다.
그러나 그런디 값이 항상 이러한 규칙성을 가지는 것과는 거리가 멀며, 매우 단순한 일부 게임에서조차 그러한 규칙성이 존재하는지를 묻는 문제가 여전히 미해결로 남아 있습니다(예: "그런디 게임").
게임 예시¶
십자-십자¶
규칙. 크기가 $1 \times n$인 칸으로 나뉜 띠를 생각해 봅시다. 한 번의 수에서 플레이어는 십자 하나를 놓아야 하지만, 두 십자를 서로 붙여서(인접한 칸에) 놓는 것은 금지됩니다. 늘 그렇듯이, 유효한 수가 없는 플레이어가 패배합니다.
풀이. 플레이어가 어떤 칸에 십자를 놓으면, 띠가 십자의 왼쪽과 오른쪽이라는 두 개의 독립적인 부분으로 나뉜다고 생각할 수 있습니다. 이때 십자가 놓인 칸과 그 왼쪽 및 오른쪽 이웃 칸은 파괴되어 더 이상 아무것도 놓을 수 없습니다. 따라서 칸에 $1$부터 $n$까지 번호를 매기면, 위치 $1 < i < n$에 십자를 놓는 것은 띠를 길이가 $i-2$와 $n-i-1$인 두 띠로 나누는 것, 즉 게임 $i-2$와 $n-i-1$의 합으로 이동하는 것입니다. 양 끝 칸인 $1$번 또는 $n$번 위치에 십자를 놓는 경계 경우에는 게임 $n-2$로 넘어갑니다.
따라서 그런디 값 $g(n)$은 다음과 같은 형태를 가집니다:
따라서 $O(n^2)$ 풀이를 얻었습니다.
실제로 $g(n)$은 $n=52$부터 길이 34의 주기를 가집니다.