Grundy Number는 PS에서 굉장히 자주 쓰이는 데 비해 그 증명이나 수학적 배경이 잘 알려져 있지 않다. 앞으로 일련의 포스팅에서는 Sprague-Grundy Theorem에 대해 공부한 것을 PS 스타일로 정리하려 한다. 그 중에서 이 글은 Grundy Number의 정의와 Sprague-Grundy theorem의 증명에 대해 다룬다.

Nim-Game의 필승 전략에 대한 사전 지식이 필요하며, 문제풀이에 최적화된 글이기 때문에 statement가 실제 theorem의 내용과는 다소 차이가 있다.

References

sirkingnightingfail, “A Blog on Sprague-Grundy Theorem”

Wikipedia: Sprague-Grundy theorem

Definition of Game

“게임”은 상당히 광범위한 용어이지만, Sprague-Grundy theorem의 영향 아래 있는 “Game”은 다음의 조건을 만족하는 일종의 state collection을 말한다.

  • 게임은 player A, B 2명이 즐기는 two-player game이다.
  • 동일한 상황에서 두 player가 취할 수 있는 행동의 집합 (다시말해, 도달할 수 있는 ‘다음 상태’의 집합) (move set)은 같다. (Impartial Game)
  • 각 player는 해당 상황에서 취할 수 있는 모든 행동을 알고 있다. (Perfect Information)
  • 더 이상 행동을 취할 수 없는 사람이 진다. (Normal Play Convention)
  • 어떤 행동을 하더라도 유한한 move 안에 게임의 승패가 결정된다. (Ending Condition)

Game의 notation으로는 각 상태의 move set을 재귀적으로 나타내는 것이 일반적이다. 가장 먼저 아무 행동도 취할 수 없는 상태를 $\emptyset$으로 나타내고, $\emptyset$으로만 갈 수 있는 상태 $A$가 있다면 $A = \set{\emptyset}$, $B = \set{A,\emptyset} \cdots$ 과 같이 나타내는 형식이다. 상태 $S$에 대해, $S$를 받은 선수가 어떤 행동을 취해도 패배한다면 $S$를 losing position, 그렇지 않다면 $S$를 winning position이라고 한다.

Nim Game의 예시를 보자.

Set notation of Nim Game (Nimber)

Nim Game의 정의를 복기하자.

  • $n$개의 pile에 각각 $a_{1},\cdots,a_{n}$개의 돌이 쌓여 있다.
  • Player A, B는 pile을 하나 골라 $1$개 이상의 돌을 제거할 수 있다. (Impartial, Perfect-information)
  • 더 이상 돌을 제거할 수 없는 사람이 패배한다. (Ending Condition & Normal play convention)

우선 pile이 1개라고 하자. 이 게임의 승패 판별은 자명하지만 그것은 별로 중요하지 않다. 이 게임을 결정하는 유일한 변수는 pile에 남아있는 돌의 개수가 된다. pile이 비어있는 경우 move set은 $\ast 0 = \emptyset$이 되고, 돌이 $k \ge 1$개 남아있는 경우 move set은 $\ast k = \set{\ast 0, \ast 1, \cdots, \ast (k-1)} = \ast(k-1) \cup \set{\ast(k-1)}$이 된다. 마치 자연수가 정의되는 원리와 비슷하여 Nimber라고도 부른다.

pile이 1개인 경우의 move set에서 pile이 $n$개인 경우로 확장하는 방법은 아래와 같다. $ \ast(a_{1},a_{2},\cdots,a_{n}) = \bigcup_{i=1}^{n} \left\set{\ast(a_{1},\cdots,a_{i-1},x,a_{i+1},\cdots,a_{n}) \ \vert \ x \in \ast a_{i} \right} $

Grundy Number

Mex function $\mex$는 nonnegative integer $\nonneg$의 finite subset에 대해 정의되는 함수로, $\mex(S) = \min_{x \notin S} x$로 정의된다. $\mex(\emptyset) = 0$, $\mex\set{1,3,4} = 0$, $\mex\set{0,1,2,3,5}=4$이다. 이제 $\mex$를 이용하여 Grundy number를 정의한다.

게임의 상태 $S$에 대해, $S$의 grundy number $G(S)$의 정의는 다음과 같다. $ G(S) = \mex_{s \in S} \ G(s) $ 즉, $S$에서 이동할 수 있는 state들의 Grundy number를 모은 집합의 mex가 $S$의 grundy number가 된다. $G(\emptyset) = 0$이 자연스럽게 정의됨을 확인하자. 다른 예로, 두 pile에 각각 $2,3$개의 돌이 놓여있는 nim game의 grundy number는 $G(\ast(2,3)) = \mex \left\set{ G(\ast(0,3)), G(\ast(1,3)), G(\ast(2,0)),G(\ast(2,1)), G(\ast(2,2)) \right}$로 계산된다.

Theorem 1. $S$가 losing position인 것은 $G(S) = 0$과 동치이다.

Proof. $S$는 유한 턴 안에 끝나는 게임이므로, $S$에서 게임이 끝나기 위해 걸리는 턴 수의 최댓값 $\mathcal{T}(S)$가 잘 정의된다. $\mathcal{T}(S)$에 대한 strong induction으로 증명하자.

  • $\mathcal{T}(S) = 0$은 $S = \emptyset$과 동치이다. $G(\emptyset) = 0$이고 $\emptyset$은 당연히 losing position.
  • $\mathcal{T}(S) > 0$일 때, $s \in S$에 대해 당연히 $\mathcal{T}(s) < \mathcal{T}(S)$이므로 귀납가정을 쓸 수 있다.
    • 이 때 losing position $l \in S$가 존재한다면 귀납가정에 의해 $G(l) = 0$이고, 자연히 $G(S) \neq 0$이다. 한편 $l$이 losing position이라면 선수가 $l$로 이동하면 되기 때문에 $S$는 winning position이 된다.
    • $S$의 원소 중 losing position이 존재하지 않는다면 모든 $s \in S$에 대해 $G(s) > 0$이므로 $G(S) = 0$이다. 한편 $S$가 losing position이 됨은 자명. $\blacksquare$

Nim-Game의 예시가 빠질 수 없다.

Grundy number of Nimbers

Proposition 2. $G(\ast k) = k$.

$k$에 대한 strong induction으로 쉽게 증명할 수 있고, Theorem 1과 우리의 ‘상식적인 결과’가 잘 맞아떨어진다는 것을 확인할 수 있다. 다만 이것으로는 부족하다는 것을 잘 알고 있을 것이다.

Question 3. $G(\ast(a_{1},a_{2},\cdots,a_{n})) = ?$

Classical nim game에 대해, 선수의 승리 조건이 $a_{1} \oplus \cdots \oplus a_{n} \neq 0$임을 알고 있을 것이다. ($\oplus$는 bitwise-XOR) 마찬가지로 $G(\ast(a_{1},a_{2},\cdots,a_{n})) = a_{1} \oplus \cdots \oplus a_{n}$이 된다. 하지만 왜?

Combining Games

앞서, pile이 여러 개인 경우 Nim-game을 정의한 바 있다. 비슷하게, 게임1의 상태가 $A$, 게임2의 상태가 $B$일 때 player가 취할 수 있는 행동이 다음 중 하나라고 하자.

  • 게임1에서 한 턴을 움직인다. (즉, $A \leftarrow a$ for some $a \in A$)
  • 게임2에서 한 턴을 움직인다. (즉, $B \leftarrow b$ for some $b \in B$)
  • 게임1, 2에서 모두 움직일 수 없는 사람이 패배한다. (즉, $(\emptyset,\emptyset)$이 losing state)

이때, 새로운 게임의 state를 $A + B$로 표기한다. $A+B$의 구성은 역시 다음과 같다:

$ A + B = \set{(a, B) \mid a \in A } \cup \set{ (A,b) \mid b \in B }$

그리고 PS에서 흔히 Sprague-Grundy Theorem이라고 불리는, 우리가 제일 좋아하는 정리는 다음과 같다.

Theorem 4. $G(A+B) = G(A) \oplus G(B)$.

이 정리를 증명한다면 Question 3에 대한 답은 자연스레 따라온다. 증명에 필요한 Lemma를 먼저 보고 가자.

$ x \in \nonneg$와 $A \subset \nonneg$에 대해 $x \oplus A = \set{x \oplus a \ \mid \ a \in A}$로 정의하자.

Lemma 5. $A, B \subset \nonneg$에 대해, $C = (\mex(A) \oplus B) \cup (A \oplus \mex(B))$로 정의하자. $\mex(C) = \mex(A) \oplus \mex(B)$ 이다.

Proof. 가장 먼저 $u := \mex(A) \oplus \mex(B)$가 $C$에 속하지 않음을 보이자. $u \in C$라면 $u \in \mex(A) \oplus B$ 또는 $u \in A \oplus \mex(B)$가 성립하는데, 각각 $\mex(B) \in B$와 $\mex(A) \in A$가 유도되어 모순. $\blacksquare$

이제 모든 $x < u$에 대해 $x \in C$임을 보이자.

$z = x \oplus u$를 정의하자. $x \neq u$이므로 $z \neq 0$이고, $z$의 maximal bit $k$가 잘 정의된다. $z=10110_{2}$라면 $k=2^{4}$이다. 이 때 $\oplus$의 정의에 따라 $k$는 $x$나 $u$ 중 정확히 하나에만 포함되어 있다.

만약 $k$가 $x$에 포함되어 있다면 $x < u$이므로, $k \le (x\text{의 maximal bit}) \le (u\text{의 maximal bit})$가 성립하고, 등호조건 2개가 동시에 성립하지 않는다. 즉, $k < (u\text{의 maximal bit})$가 성립한다. 그렇다면 $(x\text{의 maximal bit}) > k$ 또는 $(x\text{의 maximal bit}) < (u\text{의 maximal bit})$ 중 하나가 성립해야 하는데, 각 경우에서 모순을 보일 수 있다.

  • $k < (x\text{의 maximal bit})$: $k$의 정의상 $k$보다 큰 비트는 $x, u$에 모두 포함되어 있어야 하고, $k$는 $x$에만 포함되어 있으므로 $x > u$가 되어 모순이다.
  • $(x\text{의 maximal bit}) < (u\text{의 maximal bit})$: 이 경우 $u$의 maximalㄴ bit가 $z$에 포함되므로 $k$의 최대성에 모순이다.

따라서 $k$는 $u$에만 포함되어 있다. $u = \mex(A) \oplus \mex(B)$이므로, $\mex(A)$와 $\mex(B)$ 중 하나만 $k$를 포함한다. 일반성을 잃지 않고 $\mex(A)$가 $k$를 포함한다고 하자. 그렇다면 $x \oplus \mex(B)$는 $k$를 포함하지 않는다. 이 때 $x \oplus \mex(B) < \mex(A)$가 성립함을 보이자.

만약 $x \oplus \mex(B) > \mex(A)$라면 $x \oplus \mex(B)$에는 포함되지만 $\mex(A)$에 포함되지 않는 가장 큰 비트 $l$이 존재한다. 이 때 $z$의 최대 비트가 $l$이 되어야 하므로 $k$의 정의에 모순. $\blacksquare$

이렇게 Lemma 5의 증명이 끝난다. 이를 바탕으로 Theorem 4를 보이자. 역시 $\mathcal{T}(A+B)$에 대한 strong induction이다.

  • $\mathcal{T}(A+B) = 0$인 경우는 $(A,B) = (\emptyset,\emptyset)$ 뿐이므로 성립.
  • $a \in A$에 대해 귀납가설로부터 $G(a+B) = G(a) \oplus G(B)$이고, 마찬가지로 $b \in B$에 대해 $G(A + b) = G(A) \oplus G(b)$이다. 이 때 $S_{A}$를 $\set{G(a) \mid a \in A}$라고 한다면 $G(a+B)=G(a) \oplus \mex(S_{B})$, $G(A + b) = \mex(S_{A}) \oplus G(b)$가 성립한다. $G(A+B) = \mex( (S_{A} \oplus \mex(S_{B})) \cup (\mex(S_{A}) \oplus S_{B}) )$ 임을 확인할 수 있고, Theorem 4에 따라 $G(A+B) = \mex(S_{A}) \oplus \mex(S_{B}) = G(A) \oplus G(B)$가 된다. $\blacksquare$

Further Reading

  1. 사실 Sprague-Grundy theorem의 수학적 statement에서는 두 state의 equivalence relation $\approx$를 정의한다. 이를 바탕으로 $A \approx \ast(G(A))$임을 보인다. Wikipedia를 참고. PS에 적용하기엔 딱히 merit가 없어 다루지 않았다.
  2. Nimber에도 algebra를 줄 수 있다. 게임의 덧셈과 비슷하게 nimber의 덧셈을 정의하면 $\ast(a) + \ast(b) = \ast(a \oplus b)$가 된다. 비슷하게 곱셈까지 정의해서 field가 되게 만들 수 있는데 어디 쓸 수 있는지 감도 안 온다;; 알게 되면 블로그에 추가할 예정.

다음 글에는 Grundy number와 관련된 몇 가지 예제와 연습문제를 들고 올 생각이다.