The Grundy Number

Computer Science Jun 21, 2025

Introduction

어린 시절을 한국에서 보낸 독자라면 아마 '배스킨라빈스 31게임'에 대하여 들어봤을 것이다. 그래도 모르는 사람을 위해 간략히 설명하자면, 이 게임의 규칙은 다음과 같다 :

배스킨라빈스 31 게임은 숫자 1부터 시작하여 번갈아 가며 숫자를 1개에서 3개까지 외치고, 31을 먼저 말하는 사람이 지는 게임이다.

자, 필자가 이제 여러분을 위해 매우 큰 비밀을 하나 알려주겠다. 이 게임에은 사실 무조건 이길 수 있는 전략이 존재한다는 사실을 아는가?

The Winning Strategy

필자와 게임을 한다고 생각하자. 31개에서 시작한다고 하고, 필자가 우선 숫자 3개를 부른 뒤에 여러분이 2번째 플레이어를 한다고 하자. 여러분이 수 1개를 부르면 필자는 3개를 부를 것이며, 여러분이 2개를 부르면 필자는 2개를 부를 것이고, 여러분이 3개를 부르면 필자는 1개를 부를 것이다. 자, 이기는데 무운을 빈다.

아마 위의 경우를 정확히 시뮬레이션했다면 항상 필자가 이기는 결론으로 끝났을 것이다. 이처럼 특정 종류의 게임에는 무조건 이기는 전략, 즉 필승전략이 존재한다. 특히, 이 예시처럼 2명의 플레이어가 여러 무더기에서 특정한 수의 무언가를 제거하며 진행되는 게임을 통칭하여 님 게임(Nim Game) 이라고 부른다 (이에 대한 글은 미래에 작성할 계획이다). 한국과학영재학교 재학생이라면 수1 부교재 #11.4.4를 한번 풀어보고 오는 것을 추천한다.

시작하자.

The Definition of Games

우선 Nim Game의 정확한 정의를 알아보자. Nim Game을 좀 더 엄밀하게 정의하자면, 다음과 같이 할 수 있다.

Nim is a mathematical combinatorial game in which two players take turns removing (or "nimming") objects from distinct heaps or piles. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap or pile. Depending on the version being played, the goal of the game is either to avoid taking the last object or to take the last object.

-Wikipedia, Nim Game

영어인 점은 양해바란다. 간단히 설명하여, Nim Game은 여러개의 유한한 개수의 아이템이 있는 무더기들에서 양 플레이어가 원하는 개수만큼의 아이템을 가져가서, (일반적으로는) 모든 아이템을 제거하는 최초의 사람이 이기는 게임이다.

아래에서 좀 더 자세히 설명하겠지만, Nim Game은 좀 더 큰 Impartial Game이라는 게임 종류의 대표적인 예시이다. Impartial Game의 정의는 좀 더 간단하다.

An impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first.

-Wikipedia, Impartial Game

즉 두 플레이어의 차이가 먼저 플레이하는가 나중에 플레이하는가 밖에 없는 것이다. 우리가 알아보고자 하는 것은 이런 Impartial Game들에 대한 일반적인 해석법이다.

The Sprague–Grundy theorem

이건 또 무엇인가. 간단히 설명하자면 모든 Impartial Game들은 One-heap Nim Game에 대응시킬 수 있다는 것이다. 즉, 단순히 아이템이 1스택 쌓여있는 Nim Game과 대응된다는 것을 의미한다. 그리고 이 Nim Stack의 아이템의 성질이 게임의 현 상황을 설명하는데 사용되는데, 이 숫자를 Grundy Number라고 불린다. 일반적인 게임, 즉 마지막 아이템을 먹는 사람이 이기는 게임의 경우 \(G.N. > 0\)이면 선수 필승, \(G.N. = 0\)이면 후수 필승 인 것을 알 수 있다.

Grundy Number의 특징들은 다음과 같다 :

여러 Stack에 대하여 행해지는 게임의 경우 각 Stack의 Grundy Number를 XOR한 값이 최종 Grundy Number가 된다.
- 즉, \(n\)개의 스택 \(a_1, a_2, \cdot\cdot\cdot a_n\)에 대하여 Grundy number를 각각 \(g_1, g_2, \cdot\cdot\cdot g_n\)이라 하면, 최종적인 Grundy Number G는 \(g_1\oplus g_2\oplus \cdot \cdot \cdot \oplus g_n\)이라고 정의할 수 있다.
전통적인 One-heap Nim Game의 경우, G(P) = P이다.
한 Stack 내부에서의 Grundy Number는 그 상황 \(P\)에서 동작을 행하여 갈 수 있는 모든 상황들의 Grundy Number들의 Minimum Excludant, 즉 음이 아닌 정수 중 집합에 포합되지 않는 최소 정수가 된다.

이제, 각각을 증명해보자.

CLAIM 1

\(n\)개의 스택 \(a_1, a_2, \cdot\cdot\cdot a_n\)에 대하여 Grundy number를 각각 \(g_1, g_2, \cdot\cdot\cdot g_n\)이라 하면, 최종적인 Grundy Number G는 \(g_1\oplus g_2\oplus \cdot \cdot \cdot \oplus g_n\)이라고 정의할 수 있다.

가장 근본적인 두 집합의 합침을 생각해보자. 두 Nim Game들을 \(A\), \(B\)라고 하고, 각각의 Grundy Number가 \(a\), \(b\) 라고 해보자. 이때, 두개를 같이(\(A+B\)) 고려하는 상황에 대한 Grundy Number를 계산하는 식을 \(a \oplus b\) 라고 하자. 우리는 이제 \(\oplus\)에 해당하는 연산자를 찾고자 한다. (\(\oplus\)연산자가 XOR에 해당한다는 것을 아는 독자들은 잠시만 눈감아주기를 부탁한다...)

우리는 이 연산자가 몇가지 특징을 만족시켜야 함을 알 수 있다.

결합법칙과 교환법칙을 만족해야 한다. 단순히 Stack을 합치는 연산이므로 무엇을 먼저 합치거나 나중에 합치는지는 상관없어야 한다.
항등원은 \(0\)이다. 아이템이 \(0\)개인 Stack을 추가하는것은 사실상 변화가 없기 때문이다.
역원은 자기 자신이다. 이거는 좀 자세한 부연 설명이 필요하다.
- 잠시 고전적인 돌 가져가게 게임으로 돌아와보자. 돌이 n개 있는 Stack에 돌이 n개 있는 Stack를 병렬로 붙이면, 두번째 플레이어한테는 필승전략이 생긴다.
- 선수를 후수가 무조건 대칭하여 따라하는 전략, 즉 Mirror Tactic를 사용시 후수는 항상 선수보다 늦게 돌을 제거하게 되고, 따라서 항상 이기게 된다.
- 더 자세한 설명을 원한다면 글 맨 아래에 붙여놓은 #11.4.4의 풀이를 참고해주기를 바란다.

위 조건을 만족하면 Grundy Number의 합성을 담당하기에 적절한 연산자임을 알 수 있다. 관찰력이 좋은 독자들은 위 두개 조건만 이용시 이것이 + 연산자를 나타내고, 아래 조건까지 포함시 이것이 modulo 2에 대한 덧셈 연산, 혹은 XOR을 나타낸다는 것을 알 수 있다.

CLAIM 2

자명하므로 넘어가자. 이는 증명이 필요하기 보다는 CLAIM 3의 증명에 매우 중요하게 사용된다.

CLAIM 3

자, 그러면 Minimum Excludant, 즉 mex 연산은 어디에서 튀어나온 것일까? 아무리 봐도 관련이 없어 보인다.

mex 연산자를 이해하려면 그 정의 자체보다는 그 주위의 값이 어떻게 되는지를 확인해야 한다. 복습하자면, Minimum Excludant (AKA mex) 연산자는 음이 아닌 정수 중 집합에 포합되지 않는 최소 정수로 정의된다. 즉, 어떤 집합 \(X\)의 mex값이 \(k\)일 경우 \(0~k-1\)은 무조건 다 차있다는 것이다. 즉, One-Heap Nim Game에서 \(k\)의 상황에 대응되는 것이다! \(k\)에서 원하는 만큼 아이템을 제거할 수 있고, 그것은 곳 Grundy Number가 \(k-x\)인 상황에 대응된다. 이거보다 작은 수를 무조건 만들 수 있다는 일종의 약속인 거다.