Sprague-Grundy Theorem (1) - Grundy Number의 정의, theorem 증명

algorithm.game ― [ game-theory , sprague-grundy ]
\[\newcommand{\mex}{\text{mex}} \newcommand{\Z}{\mathbb{Z}_{0}}\]

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 = \{\emptyset\}\), \(B = \{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 = \{\ast 0, \ast 1, \cdots, \ast (k-1)\} = \ast(k-1) \cup \{\ast(k-1)\}\)이 된다. 마치 자연수가 정의되는 원리와 비슷하여 Nimber라고도 부른다.

pile이 1개인 경우의 move set에서 pile이 \(n\)개인 경우로 확장하는 방법은 아래와 같다. \(\ast(a_{1},a_{2},\cdots,a_{n}) = \bigcup_{i=1}^{n} \left\{\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 \(\Z\)의 finite subset에 대해 정의되는 함수로, \(\mex(S) = \min_{x \notin S} x\)로 정의된다. \(\mex(\emptyset) = 0\), \(\mex\{1,3,4\} = 0\), \(\mex\{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\{ 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 = \{(a, B) \mid a \in A \} \cup \{ (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 \Z\)와 \(A \subset \Z\)에 대해 \(x \oplus A = \{x \oplus a \ \mid \ a \in A\}\)로 정의하자.

Lemma 5. \(A, B \subset \Z\)에 대해, \(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}\)를 \(\{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와 관련된 몇 가지 예제와 연습문제를 들고 올 생각이다.

Written on March 7, 2020