https://cp-algorithms.com/game_theory/sprague-grundy-nim.html

---

Sprague-Grundy theorem과 Nim game

소개

이 정리는 공정한 두 명의 플레이어 게임을 설명합니다. 공정한 게임이란, 가능한 수와 승패가 오로지 게임의 상태에만 의존하는 게임을 의미합니다. 즉, 두 플레이어 간의 유일한 차이는 한 플레이어가 먼저 움직인다는 것입니다.

또한, 게임은 완전 정보를 가졌다고 가정합니다. 즉, 플레이어들은 모든 규칙과 가능한 움직임을 알고 있습니다.

게임은 유한하다고 가정합니다. 즉, 일정 수의 움직임 후에는 한 플레이어가 더 이상 이동할 수 없는 패배 상태에 도달합니다. 반대로, 이 패배 상태를 만든 플레이어는 승리합니다. 따라서, 이 게임에는 무승부가 없습니다.

이러한 게임은 유향 비순환 그래프로 완전히 설명할 수 있습니다. 여기서 정점은 게임 상태를 나타내고, 간선은 전이(움직임)를 나타냅니다. 출발 간선이 없는 정점은 패배 정점입니다 (이 정점에서 이동해야 하는 플레이어는 패배합니다).

무승부가 없기 때문에 모든 게임 상태를 승리 상태와 패배 상태로 분류할 수 있습니다. 승리 상태는 다른 플레이어를 반드시 패배하게 하는 이동이 가능한 상태를 의미하며, 패배 상태는 모든 이동이 다른 플레이어를 승리 상태로 만드는 상태를 의미합니다. 요약하자면, 상태가 승리 상태가 되려면 적어도 하나의 전이가 패배 상태로 가야 하고, 패배 상태는 패배 상태로 가는 전이가 없어야 합니다.

우리의 임무는 주어진 게임의 상태를 분류하는 것입니다.

이론은 1935년에 Roland Sprague와 1939년에 Patrick Michael Grundy에 의해 독립적으로 개발되었습니다.

Nim

이 게임은 위에서 설명한 제한 사항을 따릅니다. 또한, 모든 완전 정보 공정한 두 명의 플레이어 게임은 Nim 게임으로 축소할 수 있습니다. 이 게임을 연구하면 다른 유사한 게임들도 해결할 수 있습니다.

게임 설명

여러 개의 더미가 있으며, 각 더미에는 여러 개의 돌이 있습니다. 플레이어는 한 번의 이동에서 임의의 양의 돌을 한 더미에서 가져와 버릴 수 있습니다. 모든 더미가 비어 있을 때 이동할 수 없으면 플레이어는 패배합니다.

게임 상태는 양의 정수의 다중 집합으로 명확히 설명됩니다. 이동은 선택한 정수의 크기를 엄격히 감소시키는 것으로 구성됩니다 (정수가 0이 되면 집합에서 제거됨).

해결 방법

Charles L. Bouton의 해결 방법은 다음과 같습니다:

정리: 현재 플레이어가 승리 전략을 갖고 있는 조건은 오직 더미 크기의 xor-sum이 0이 아닌 경우입니다. xor-sum은 수열 $a$의 $a_1 \oplus a_2 \oplus \ldots \oplus a_n$ 입니다.

증명: 증명의 핵심은 상대방에게 대칭 전략이 존재한다는 점입니다. xor-sum이 0인 상태에서는 장기적으로 xor-sum을 0이 아닌 값으로 만들 수 없다는 것을 보입니다. 만약 0이 아닌 xor-sum의 상태로 이동하면, 상대방은 항상 xor-sum을 다시 0으로 돌리는 이동을 할 수 있습니다.

수학적 귀납법을 통해 정리를 증명합니다.

빈 Nim 상태 (모든 더미가 비어 있는 상태)의 경우, xor-sum은 0이며 정리는 참입니다.

이제 비어 있지 않은 상태를 가정합니다. 귀납 가정을 사용하고 (게임의 비순환성 덕분에) 현재 상태에서 도달 가능한 모든 상태에서 정리가 증명된다고 가정합니다.

그런 다음 증명은 두 부분으로 나뉩니다. 현재 상태의 xor-sum   $s = 0$일 때, 이 상태가 패배 상태임을 보여야 합니다. 즉, 모든 도달 가능한 상태가 xor-sum   $t \neq 0$ 이어야 합니다. 만약   $s \neq 0$라면,   $t = 0$인 상태로 가는 이동이 존재함을 보여야 합니다.

• 경우 1: $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$입니다. 즉, 모든 도달 가능한 상태는 승리 상태이므로 현재 상태는 패배 상태입니다.

• 경우 2:   $s \neq 0$ 일 때, 숫자   $s$의 이진 표현을 고려합시다. $d$를 가장 높은 비트의 인덱스라고 합시다. 우리의 이동은 비트 번호 $d$가 설정된 더미에서 진행됩니다 (그 비트가 설정되지 않았다면,   $s$의 비트가 설정되지 않았을 것입니다). 우리는 $x$를 $y = x \oplus s$로 줄일 것입니다. 비트 $d$는 $x$에는 설정되어 있지만 $y$에는 설정되어 있습니다. 따라서 $y < x$이며, 이는 이동이 합법적임을 보장합니다.

  이제, $t = s \oplus x \oplus y = s \oplus x \oplus( s\oplus x)= 0$

이로써 우리는 도달 가능한 패배 상태를 찾았으며 현재 상태는 승리 상태입니다.

Corollary. Nim의 모든 상태는 xor-sum이 변경되지 않는 한 동등한 상태로 대체될 수 있습니다. 또한, 여러 더미를 가진 Nim을 분석할 때는 단일 더미의 크기 $s$인 Nim으로 대체할 수 있습니다.

Sprague-Grundy 정리의 적용

이제 모든 공정한 게임의 상태에 대해 대응하는 Nim 상태를 찾는 방법을 배웁니다.

Nim에 대한 증가 수정을 고려해 봅시다. Nim에 돌을 추가할 수 있는 규칙이 추가됩니다. 증가가 어떻게 그리고 언제 허용되는지는 중요하지 않습니다. 단, 게임이 비순환성을 유지해야 합니다.

정리: Nim에 증가를 추가해도 승리 상태와 패배 상태를 결정하는 방법에는 변화가 없습니다. 즉, 증가는 쓸모가 없으며 승리 전략에 사용할 필요가 없습니다.

증명: 플레이어가 더미에 돌을 추가했다면, 상대방은 그 이동을 취소하고 돌의 수를 원래 값으로 되돌릴 수 있습니다. 게임이 비순환성이므로, 언젠가는 현재 플레이어가 증가 이동을 사용할 수 없게 되고, 일반적인 Nim 이동을 해야 할 것입니다.

Sprague-Grundy 정리

두 명의 플레이어가 공정하게 플레이하는 게임의 상태   $v$를 고려합시다. 이 상태에서 도달 가능한 상태들을   $v_i$라고 합시다 (여기서   $i \in \lbrace 1, 2, \dots, k \rbrace, k \ge 0$). 이 상태에 대해, 크기   $x$인 하나의 더미를 가진 완전히 동등한 Nim 게임을 할당할 수 있습니다. 이 숫자   $x$를 상태   $v$의 Grundy 값 또는 nim-value라고 합니다.

이 숫자는 다음과 같은 재귀적 방법으로 찾을 수 있습니다:

$ x = \text{mex}\ \lbrace x_1, \ldots, x_k \rbrace$

여기서   $x_i$는 상태   $v_i$의 Grundy 값이며, 함수   $\text{mex}$는 주어진 집합에 없는 가장 작은 비음수 정수입니다.

게임을 그래프로 보고, 우리는 간선이 없는 정점부터 Grundy 값을 점차 계산할 수 있습니다. Grundy 값이 0이면 상태는 패배 상태임을 의미합니다.

증명: 귀납법을 사용하여 증명합니다.

기본 사례: 이동할 수 없는 정점의 경우, Grundy 값   $x$는 빈 집합의   $\text{mex}$로, 이는 0입니다. 빈 Nim은 패배 상태이기 때문에 이것이 맞습니다.

귀납 가정: 이제 다른 임의의 정점   $v$를 고려합시다. 귀납법에 따라,   $v$의 도달 가능한 정점들에 대한 Grundy 값   $x_i$는 이미 계산되었다고 가정합니다.

귀납 단계:

$p = \text{mex}\ \lbrace x_1, \ldots, x_k \rbrace$라고 합시다. 그러면, 모든 정수   $i \in [0, p)$에 대해 Grundy 값이   $i$인 도달 가능한 정점이 존재한다는 것을 알 수 있습니다. 이는   $v$가 크기   $p$인 하나의 더미를 가진 Nim 상태와 동등하다는 것을 의미합니다. 이러한 게임에서는 크기가   $p$보다 작은 모든 크기의 더미로의 전이와, 크기가   $p$보다 큰 더미로의 전이가 가능할 수 있습니다. 따라서   $p$가 현재 고려 중인 상태의 원하는 Grundy 값이 됩니다.

여기서   $x_i$는 상태   $v_i$의 Grundy 값이며, 함수 $\text{mex}$ 는 주어진 집합에 없는 가장 작은 비음수 정수입니다.

게임을 그래프로 보고, 우리는 간선이 없는 정점부터 Grundy 값을 점차 계산할 수 있습니다. Grundy 값이 0이면 상태는 패배 상태입니다.

Grundy 값의 패턴

특정 문제를 해결할 때 Grundy 값을 사용하는 경우, 값의 테이블을 분석하여 패턴을 찾는 것이 유용할 수 있습니다.

많은 게임에서는 이론적 분석이 어려워 보일 수 있지만, Grundy 값이 주기적이거나 이해하기 쉬운 형태로 나타나는 경우가 많습니다. 관찰된 패턴이 대다수의 경우에 맞아떨어지며, 필요하다면 귀납법으로 이를 증명할 수 있습니다.

하지만 Grundy 값이 항상 이러한 규칙성을 가지는 것은 아닙니다. 실제로 매우 간단한 게임들 중에서도 이러한 규칙성의 존재 여부가 아직 해결되지 않은 경우도 있습니다 (예: “Grundy의 게임”).