2명의 플레이어가 게임을 진행하고, 순차적, 완전 정보, 공정, 노멀 플레이, 유한 상태, loopfree인 게임일 때의 필승법에 대한 정리이다.

• 순차적 게임 : 바둑, 체스같이 상대 행동이 모두 끝나면 내 차례가 온다.
• 완전 정보 게임 : 바둑, 체스처럼 모든 정보가 공개되어있다. 포커는 완전 정보 게임이 아니다.
• 공정 게임 : 플레이어에 상관 없이 게임의 상태에 의해서만 할 수 있는 행동이 정해진다. 체스는 플레이어가 움직일 수 있는 말이 다르므로 공정 게임이 아니다.
• 노멀 플레이 : 할 수 있는 행동이 없는 플레이어가 패배한다.
• 유한 상태 : 플레이어가 할 수 있는 행동이 항상 유한하다.
• loopfree : 같은 상태가 2번 이상 나타나지 않는다. 체스는 loopfree가 아니다.

---

Nim Game

1개 이상의 더미에 돌이 쌓여있고, 두 명에서 플레이어가 번갈아가며 돌을 제거해나가는 게임이다. 돌을 제거할 땐 하나의 더미에서 한 개 이상의 돌을 제거해야만 한다. 마지막 돌을 제거한 사람이 이기는 게임이다. 위의 조건들을 모두 만족한다.

---

그런디 수

그런디 수는 $*0, *1, *2, ...$ 처럼 별표와 $0$ 이상의 정수로 표시된다.
그런디 수는 더미가 한 개인 님 게임에서의 돌의 개수를 나타낸다. 즉, $*n$은 님 게임에서 더미가 하나 있고, 돌이 $n$개 쌓여있는 상태를 나타낸다.
그런디 수는 nimber라고도 부른다.

---

행동 집합

행동 집합(a set of options)을 현재 상태에서 해당 차례의 플레이어가 취한 행동에 따라 바뀌는, 가능한 모든 상태(position)들의 집합으로 정의하자.
현재 상태에서 플레이어의 선택으로 게임을 $*0, *1$중 하나의 상태로 만들 수 있을 때, 게임의 상태 $G$를 다음과 같이 행동 집합으로 표현할 수 있다.
$G = \{*0, *1\}$
$G$는 사실상 $*2$와 같다. 어떤 그런디 수 $*n$은 다음을 만족한다.
$*n = \{*0, *1, *2, ..., *(n-1)\}$

---

행동 집합의 덧셈

같은 게임의 두 행동 집합 $A$와 $B$를 합쳐 하나의 게임으로 진행할 수 있다. 이를 $A+B$라고 표현한다. 예를 들어 님 게임에서 돌이 3개 쌓인 더미($*3$)와 돌이 5개 쌓인 더미($*5$)를 합쳐 진행할 수 있다. 행동 집합의 합 $A + B$ 를 아래와 같이 재귀적으로 표현할 수 있다.
$A+B=\{A+b \ | \ b\in B\} \cup \{a+B \ | \ a\in A\}$

행동 집합의 덧셈은 교환법칙과 결합법칙이 성립한다.

---

$\mathcal{P}$-position과 $\mathcal{N}$-position

2명의 플레이어가 게임을 진행하고, 순차적, 완전 정보, 공정, 노멀 플레이, 유한 상태, loopfree인 게임의 모든 행동 집합은 $\mathcal{P}$-position과 $\mathcal{N}$-position으로 나눌 수 있다. $\mathcal{P}$-position은 이전(다음) 차례의 사람이 무조건 이길 수 있는 행동 집합이고, $\mathcal{N}$-position은 이번 차례의 사람이 무조건 이길 수 있는 행동 집합이다.

노멀 플레이에서 $*0$은 $\mathcal{P}$-position이고, 이외에는 전부 $\mathcal{N}$-position이다.

---

정의 1.

두 행동 집합 $A$, $B$가 임의의 행동 집합 $G$에 대해 $A+G$, $B+G$ 모두 $\mathcal{P}$-position이거나 $\mathcal{N}$-position으로 같을 경우 $A \approx B$ 라고 쓰자. 이때, $A$와 $B$를 동등하다고 말한다.

정리 1.

행동 집합 $A$가 $\mathcal{P}$-position이면 임의의 행동 집합 $G$에 대해 $G \approx A+G$이다.

임의의 행동 집합 $H$에 대해 $G+H$와 $A+G+H$가 둘 다 $\mathcal{P}$-position이거나 $\mathcal{N}$-position임을 증명하면 된다.

증명 1. $G + H$가 $\mathcal{P}$-position일 때

$A$도 $\mathcal{P}$-position이므로 상대방은 $A$와 $G+H$에서 모두 승리 전략을 구사하여 무조건 이길 수 있다. 따라서 $A+G+H$또한 $\mathcal{P}$-position이다.

증명 2. $G + H$가 $\mathcal{N}$-position일 때

$G+H$에서 $\mathcal{P}$-position으로 이동하여 $(G+H)'$로 만들자. $A+(G+H)'$는 증명 1과 같이 $\mathcal{P}$-position이다. 따라서 $A+G+H$는 $\mathcal{N}$-position이다.

정리 2.

$A \approx B \iff A+B$ 는 $\mathcal{P}$-position

증명 1. $A \approx B \Rightarrow A+B$ 는 $\mathcal{P}$-position

$A \approx B$ 이므로 $A+A$와 $A+B$는 둘 다 $\mathcal{N}$-position이거나 $\mathcal{P}$-position이다. 그런데 $A+A$는 똑같은 게임 두 개를 갖다놓고 하기 때문에 한쪽에서 내가 어떻게 두든 상대방이 반대쪽에서 나와 똑같은 행동을 하면 마지막에 돌을 가져가는 건 상대방이다. 따라서 $A+A$는 $\mathcal{P}$-position이고 $A+B$ 또한 $\mathcal{P}$-position이다.

증명 2. $A \approx B \Leftarrow A+B$ 는 $\mathcal{P}$-position

$A+B$가 $\mathcal{P}$-position이면 정리 1에 의해 $A \approx A+A+B$ 이다. 그리고 $A+A$도 $\mathcal{P}$-position이기 때문에 또한 정리 1에 의해 $B \approx A+A+B$ 이다. 따라서 $A \approx B$ 이다.

정리 3.

행동 집합 $G = \{G_1, G_2, ..., G_k\}$ 의 각 원소 $G_i$ 와 동등한 그런디 수를 $*n_i$라고 할 때, 행동 집합 $G'=\{*n_1,*n_2,...,*n_k\}$ 은(는) $G$ 와 동등하다.

증명

행동 집합 $G+G'$ 이(가) $\mathcal{P}$-position이라면 정리 2에 의해 $G \approx G'$ 이다.

$G+G'$에서 내가 $G$를 골라서 $G_i$로 이동하면 상대는 $G'$에서 $*n_i$로 이동할 수 있다. $G_i \approx *n_i$ 이므로 정리 2에 의해서 $G_i + *n_i$ 은(는) $\mathcal{P}$-position이다. 내가 $G'$을 고르는 경우에도 마찬가지이다. 따라서 $G+G'$ 은(는) $\mathcal{P}$-position이다.

정리 4.

$G'=\{*n_1,*n_2,...,*n_k\}$ 은(는) 행동 집합이다. 집합 $\{n_1,n_2,...,n_k\}$에 속하지 않는 가장 작은 음이 아닌 정수(minimum excluded value, mex)를 $m$이라고 할 때, $G' \approx *m$이다.

증명

행동 집합 $G' + *m$ 이(가) $\mathcal{P}$-position이라면 정리 2에 의해 $G' \approx *m$ 이다.

$G'$가 공집합이면 $m = 0$ 이고, $*m = *0$ 또한 공집합이므로 $G' + *m$ 은(는) $\mathcal{P}$-position이다.
$G'$가 공집합이 아니라면, 나는 $G'$에서 $*n_i$로 이동할 수 있다. $n_i < m$ 이라면 상대방은 $*m$에서 $*n_i$로 이동하여 $*n_i + *n_i$로 만들 수 있다. 이는 $\mathcal{P}$-position이다. $n_i > m$ 라면 상대방은 $*n_i$에서 $*m$으로 이동하여 $*m + *m$으로 만들 수 있다. 이 또한 $\mathcal{P}$-position이다.
$m > 0$ 라면, $*m$이 공집합이 아니므로 나는 $G'$대신 $*m$을 선택할 수 있다. 하지만 $m$의 정의에 따라 $*m$에서 어떤 선택을 하던 상대방이 $G'$에서 같은 상태로 만들 수 있고, 내 차례는 $\mathcal{P}$-position이다. 따라서 $G' + *m$ 은(는) $\mathcal{P}$-position이다.

정리 5.

$a \oplus b \oplus c = 0 \iff$ 행동 집합 $*a + *b + *c$ 은(는) $\mathcal{P}$-position

여기서 $\oplus$ 연산은 binary XOR을 뜻한다. 조합 게임 이론에선 nim-sum이라고 부른다.

증명

$s$를 다음과 같이 정의하자.
$s = a_1 \oplus a_2 \oplus ... \oplus a_n$ ($a_i \ge 0$)

$s$에서 임의의 $a_k > 0$를 골라서 $a_k$보다 작고, 0이상으로 만들자. 이것을 다음과 같이 정의하자.
$t = b_1 \oplus b_2 \oplus ... \oplus b_n$
$i \ne k$ 라면 $a_i = b_i$이다.

따라서,
$t = 0 \oplus t$
$=(s \oplus s) \oplus t$
$=s \oplus (s \oplus t)$
$=s \oplus ((a_1 \oplus a_2 \oplus ... \oplus a_n) \oplus (b_1 \oplus b_2 \oplus ... \oplus b_n))$
$=s \oplus ((a_1 \oplus b_1) \oplus (a_2 \oplus b_2) \oplus ... \oplus (a_n \oplus b_n))$
$=s \oplus (0 \oplus 0 \oplus ... \oplus (a_k \oplus b_k) \oplus ... \oplus 0)$
$=s \oplus (a_k \oplus b_k)$

$s = 0$ 이면 $t \ne 0$ 이다.

$a_k \oplus b_k \ne 0$ 이다. 그렇지 않다면,
$a_k = a_k \oplus 0$
$= a_k \oplus (a_k \oplus b_k)$
$= (a_k \oplus a_k) \oplus b_k$
$= b_k$
이므로 모순이다.
따라서,
$t = s \oplus (a_k \oplus b_k)$
$= 0 \oplus (a_k \oplus b_k)$
$= a_k \oplus b_k$
$\ne 0$

$s \ne 0$ 이면 $t = 0$ 으로 만들 수 있다.

$s$를 이진수로 표현했을 때, 최상위 비트를 $2^x$ 이라고 하자. $\oplus$ 연산의 특성 때문에 $2^x$이 포함된 $a_k$ 또한 반드시 존재한다. $a_k$를 $b_k$로 바꾸자. $b_k = s \oplus a_k$ 이다. $s$의 최상위 비트($2^x$)가 사라지므로 $b_k < a_k$ 을(를) 만족한다.

따라서,
$t = s \oplus (a_k \oplus b_k)$
$= s \oplus (a_i \oplus (s \oplus a_i))$
$= (s \oplus s) \oplus (a_i \oplus a_i)$
$= 0$

내 차례에 nim-sum이 $0$ 이고 상대방이 필승법을 알고 있다면, 나는 계속 nim-sum이 0일 것이다. 언젠간 내 행동 집합은 공집합($*0$, 이또한 nim-sum이 0임)이 될 것이다. 따라서 nim-sum이 0인 상태는 $\mathcal{P}$-position이고, nim-sum이 0이 아니라면 nim-sum을 0으로 무조건 만들 수 있으므로 $\mathcal{N}$-position이다.

정리 6.

음이 아닌 정수 $n$과 $m$에 대하여 다음이 성립한다. $*n + *m \approx *(n \oplus m)$

증명

$n \oplus m \oplus (n \oplus m) = 0$
$\therefore$ 정리 5에 의해 $*n + *m + *(n \oplus m)$ 은(는) $\mathcal{P}$-position이다.
$\therefore$ 정리 2에 의해 $*n + *m \approx *(n \oplus m)$

따라서 (앞서 서술한 조건의) 여러 게임을 동시에 진행하는 경우에도 스프라그-그런디 정리를 이용하면 누가 이기는지 쉽게 알 수 있다. 즉, 정리 4를 이용하여 각 게임과 동등한 그런디 수를 구하고, 그것들의 nim-sum이 0인 사람이 패배한다.

참고 자료

• casterian.net
• misere quotient
• Brilliant - Nim