Sprague-Grundy Theorem For Problem Solving

이 글은 Problem Solving를 위한 스프라그-그런디 이론 기초 설명입니다.

먼저 님 게임을 알아봅시다.

 

Nim game

• 돌 무더기 \(n\)개가 있고, 각 돌 무더기는 \(p_{1}, p_{2}, ... ,p_{n}\)개의 돌로 구성되어 있습니다.
• 두 명의 플레이어는 자신의 차례마다 돌 무더기 하나를 고른 뒤, 그 돌 무더기에서 $1$개 이상의 돌을 덜어냅니다.
• 자신의 차례에 덜어낼 돌이 없는 플레이어가 패배합니다. 즉, 마지막 돌을 가져간 플레이어가 승리합니다.

님 게임에서 두 플레이어가 완벽하게 플레이했을 때 선공/후공 중 누가 이기는 지는 정해져 있습니다. 두 플레이어 모두 최적으로 행동한다는 전제하에, winning state에서 턴을 가지는 플레이어는 반드시 승리하며, losing state에서 턴을 가지는 플레이어는 반드시 패배한다고 합시다. 이러한 성질을 만족하려면 정의가 아래와 같아야합니다.

• winning state : 이 상태에서 턴을 가진 플레이어가 할 수 있는 모든 행동 중, 다음 상태를 losing state로 만드는 행동이 반드시 \(1\)개 이상 존재하는 state
• losing state : 이 상태에서 턴을 가진 플레이어가 할 수 있는 모든 행동이 다음 상태를 winning state로 만드는 state

즉, 어떤 플레이어가 winning state에 있다면 상대 플레이어를 losing state로 보내버릴 수 있기 때문에 게임의 승자가 됩니다. 반면 losing state에 있는 플레이어는 어떤 행동을 하더라도 상대방을 winning state로 보내기 때문에 게임에서 지게됩니다.

 

어떤 state가 winning state인지 losing state인지 판단할 수 있는 방법은 아래와 같습니다.

• \(state = (p_{1}, p_{2}, ... ,p_{n})\)일 때, \(s=p_{1}\oplus p_{2}\ \oplus ... \oplus \ p_{n}\)이 \(0\)이면 losing state이고,  아니라면 winning state이다.

즉, 모든 돌 무더기에 있는 돌의 개수를 $XOR$ 연산한 결괏값으로 판단 가능합니다. 왜 가능할까요?

• \(s=0\)인 상태에서, 특정 돌 무더기 \(c\)를 선택합시다. 그리고 이 돌무더기를 제외한 다른 모든 돌 무더기를 $XOR$연산한 값을 \(k\)라고 합시다. 즉, \(c\oplus k=0\)입니다. 이때 \(c\)에서 몇 개의 돌을 덜어낸 후 남은 돌의 개수를 \(c'\)라고 합시다. 그러면 \(c'\oplus k \ne 0\)입니다. 이는 losing state에서의 모든 행동이 다음 상태를 winning state로 만들어 버리는 특성을 잘 만족합니다.
• \(s \ne 0\)인 상태에서, \(s\)를 이진수를 나타냈을 때 가장 왼쪽에 있는 \(1\)인 비트에 주목합시다. 이 비트는 \(s \ne 0\)이기 때문에 반드시 존재합니다. 예를 들어봅시다. $s=001011$이라고 해봅시다. 우리는 왼쪽에서 세 번째 위치한 비트에 주목해야 합니다. 그렇다면 반드시 돌이 $c=001...$개인 돌무더기가 존재합니다. 그러니까 $XOR$ 값이 $001...$이 될 수 있었겠죠? 우리는 이 돌무더기에서 특정 개수의 돌을 덜어냄으로써 다음 state를 losing state로 만들 수 있습니다. 이 돌무더기에서 돌을 덜어내는 이유는, 가장 왼쪽에 위치한 $1$인 비트를 $0$으로 만들어야 하기 때문입니다. 즉, 이 돌무더기의 돌의 개수를 $c$라고 하고, 나머지 돌무더기들의 돌의 개수를 $XOR$한 값을 $k$라고 하면 현재 $c \oplus k = 001011$입니다. $c$에서 몇 개의 돌을 덜어내서 $c^{'}$개를 남겼다고 합시다. $c^{'} \oplus k = 0$이면 다음 state가 losing state라는 말입니다. 그러므로 남는 돌이 $c^{'}$개가 되도록 돌을 덜어내면 됩니다. 

님 게임의 초기 상태의 $s=0$이면 후공이 이기고, 아니면 선공이 이긴다는 사실을 알게되었습니다. 님 게임같은 게임을 impartial game이라고 합니다. impartial game의 특성은 아래와 같습니다.

• 게임판의 모든 정보가 공개된 게임
• 어떤 플레이어의 턴인지에 관계없이 할 수 있는 행동의 집합이 같은 게임
• 게임판 상태 간에 사이클이 없는 게임(즉, 유한 번의 행동으로 게임이 종료됨)
• 선공과 후공의 목표가 동일한 게임

스프라그-그런디 정리는 두 플레이어가 완벽하게 플레이 한다는 가정하에 매우 많은 impartial game을 님 게임으로 환원시키는 정리입니다.

 

스프라그-그런디 정리를 본격적으로 알아보기 전에, 님 게임의 한 가지 variant에 주목해야합니다. 특정 돌무더기에 자신이 원하는 개수의 돌을 추가하는 행동이 가능한 님 게임을 생각해봅시다. 물론, 이러한 행동을 수행하는 횟수에 제한이 있어야 합니다. 그렇지 않다면 한 플레이어가 추가한 돌을 다른 플레이어가 그대로 제거할 수 있고, 이 사이클이 계속 반복되면 게임이 끝나지 않기 때문입니다.

 

이 게임에서 승자를 결정하는 방식은 님 게임과 같습니다. 위에서 언급한 것처럼, 한 플레이어가 돌을 추가했다면 다른 플레이어가 해당 돌을 제거할 수 있기 때문입니다. 돌을 추가한 플레이어의 입장에선 다시 원점으로 돌아온 것과 마찬가지이므로, 아무것도 변하지 않습니다. 돌을 추가할 수 있다고 해서 승자가 바뀌진 않습니다.

 

이제 좀 더 복잡한 impartial game에서, 스프라그-그런디 정리가 어떻게 게임의 승자를 결정하는 지를 봅시다. 좀 더 복잡한 게임이란 돌을 제곱수 개수로만 덜어낼 수 있다건가, 돌무더기에 있는 돌 중 절반 이하의 돌만 덜어낼 수 있다던가, 돌을 \(x\)의 배수만큼 덜어낼 수 있는 등의 게임을 일컫습니다. 우리는 돌을 제곱수 개수로 덜어내야 하는 님 게임을 풀어봅시다. 일단 돌무더기가 여러 개면 승자를 결정하기 어려우므로, \(1\)개의 돌무더기만 있다고 합시다. 게임의 각 state마다 어떤 value를 매핑합시다. 이 value가 \(0\)이면 losing state이고, 아니라면 winning state라고 해봅시다. 이러한  value를 일반적으로 grundy number 혹은 nimber라고 합니다.

 

\(G(u)\)를 state $u$의 grundy number라고 할때, \(G(u)\)는 \(u\)의 다음 state의 모든 grundy number의 minimum excludant로 정의됩니다. 이를 \(mex\)라고 부르며, \(mex(s)\)란 집합 \(s\)에 없는 가장 작은 음이 아닌 정수를 반환하는 함수입니다.

 

돌무더기의 개수가 여러개면 어떻게 승자를 결정할까요? 여기서 비로소 스프라그-그런디 정리가 등장합니다.

• 스프라그-그런디 정리 : 모든 돌무더기의 grundy number를 $XOR$한 값이 state의 grundy number입니다. 즉, 그 값이 \(0\)이면 losing state이고, 아니라면 winning state입니다. 이는 일반적인 님 게임에서 승자를 결정하는 방법과 같습니다.

각 돌무더기의 grundy number는 일반적으로 top-down Dynamic Programming을 통해 재귀적으로 계산됩니다.

 

그런데 grundy number를 구하는 데 뜬금없이 왜 \(mex\) 함수가 사용될까요? 이 부분이 스프라그-그런디 정리의 가장 난해한 부분이라고 생각합니다. 사실 \(mex\) 함수는 일종의 '약속'으로서 사용됩니다. \(G(p)=g\)의 의미는, state \(p\)에서 grundy number가 \(0\sim g-1\)인 모든 state로 넘어갈 수 있음을 의미합니다. 이는 마치 일반적인 님 게임에서의 상태 전이와 같습니다. 돌의 개수가 \(g\)개인 돌 무더기가 있을 때, 우리는 여기서 돌을 덜어냄으로써 \(0\sim g-1\)개의 돌을 남길 수 있습니다. 즉, \(mex\) 함수는 복잡한 impartial game에서의 상태 전이를 마치 님 게임의 상태 전이와 맥락이 같게끔 reframe하는 역할을 수행합니다. 그럼으로써 돌 무더기가 여러 개 존재하는 impartial game에서도 마치 님 게임처럼 그저 모든 grundy number를 $XOR$한 결과를 통해 게임의 승자가 누군지 파악할 수 있게 됩니다.

 

하지만 님 게임과 다른 점이 하나 있습니다. \(G(p)=g\)일 때, 우리는 \(g\)보다 큰 grundy number를 가진 state에 도달할 수도 있다는 점입니다. 이는 $mex$ 함수의 정의 때문입니다. 하지만 이 점은 전혀 문제가 되지 않습니다. 우리는 이미 돌을 추가하는 행동이 가능한 님 게임이 일반 님 게임과 같다는 것을 확인했습니다. 즉, grundy number가 \(g\)인 state에서 \(g<h\)인 state로 넘어갔다고 해봅시다. \(mex\) 함수의 정의상, 이 state에선 grundy number가 \(0\sim h-1\)인 state로 전이할 수 있음이 보장됩니다. 그러므로 다시 grundy number가 \(g\)인 state로 넘어갈 수 있습니다. 즉, 돌을 추가한 플레이어의 행동을 완전히 undo 시킬 수 있음이 여기서도 똑같이 보장됩니다.

 

지금까지 님 게임의 필승 전략과 grundy number로의 확장, 스프라그-그런디 정리에 대해 다뤄보았습니다. Problem Solving 분야에서 쉬운 스프라그-그런디 정리 문제들은 보통 grundy number를 계산하는 효율적인 수식을 찾아내는 것이 풀이의 핵심인 경우가 많습니다. 그러나 스프라그-그런디 정리를 응용해야 하는 어려운 문제들도 많습니다.

 

더불어, 님 게임처럼 마지막 돌을 가져가는 사람이 이기는 것이 아닌, 마지막 돌을 가져가는 사람이 지는 게임은 misere game이라고 합니다. misere game은 스프라그-그런디 정리로 해결할 수 없으며, 각 게임만의 애드 혹 적인 규칙을 통해서 게임의 승자를 판별해야 한다고 알려져 있다고합니다.

 

스프라그-그런디 정리를 가볍게 이용할 수 있는 BOJ 22846번 인증된 쉬운 게임에 대한 코드입니다.

https://www.acmicpc.net/problem/22846

22846번: 인증된 쉬운 게임

#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
int N, dp[100001];

int go(int n) {
    if (dp[n] != -1) return dp[n];
    int& ret = dp[n] = 0;
    set<int> next_grundy_number;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (n + i <= N) next_grundy_number.insert(go(n + i));
            if (n + (n / i) <= N) next_grundy_number.insert(go(n + (n / i)));
        }
    }
    if (next_grundy_number.empty()) return dp[n];
    while (1) {
        if (next_grundy_number.find(ret) == next_grundy_number.end()) {
            return ret;
        }
        ret++;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    fill(dp, dp + 100001, -1);

    cout << (go(1) == 0 ? "Ringo" : "Kali");
}

 

 

reference

https://codeforces.com/blog/entry/66040

https://developerhan.tistory.com/30

https://ohgym.tistory.com/21

https://blog.myungwoo.kr/27