스프라그–그런디 정리

게임 이론에 대해 알아봅시다.

 

하나의 게임은 몇 명의 참가자와 참가자들이 할 수 있는 행동, 그리고 이 행동 조합에 따라 받게 되는 보상으로 구성됩니다.

이러한 게임 중 여기에서 다루고자 하는 게임은 다음과 같은 조건을 만족하는 게임입니다.

 

1. 두 명의 참가자가 진행합니다.

2. 두 사람이 차례를 가지고 번갈아가며 진행합니다. (순차적 게임)

3. 모든 참가자가 게임에 대한 모든 정보를 공유합니다. (완전 정보 게임)

4. 자신의 차례에 할 수 있는 행동이 하나도 없으면 패배합니다. (일반 게임)

5. 게임이 무한히 진행되지 않습니다.

 

이런 복잡한 조건들을 만족하는 게임이 대체 뭐가 있냐고 생각하실 수 있지만, 이를 만족하는 간단한 게임이 있습니다.

바로 "베스킨라빈스 31"이라는 게임입니다.

두 명이 번갈아가며 진행하고, 모든 참가자가 현재 어떤 수까지 불려진 상태인지 알 수 있으며, 할 수 있는 행동이 없으면 (31을 부를 수 밖에 없다면) 패배하고, 무한히 진행되지 않기 때문입니다.

 

이러한 게임을 진행할 때 모든 사람이 최선의 전략을 쓰면서 진행한다면 누가 승리하는지, 또 그 때의 필승전략은 무엇인지 알아내는 종류의 문제가 PS에서의 게임 이론 문제입니다.

 

이를 푸는 방법은 생각보다 간단합니다.

현재 게임판의 상태를 \(x\)라고 하고, \(x\)인 상황에서 자신의 차례인 플레이어가 이길 수 있는지 여부를 \(dp[x]\)로 정의합시다.

(\(dp[x] = 0 :\) 현재 플레이어가 무조건 패배, \(dp[x] = 1 :\) 현재 플레이어가 승리할 수 있음)

그러면 다음과 같은 DP 점화식을 세울 수 있습니다.

 

게임판의 상태 \(x\)에서 플레이어가 어떤 행동을 했을 때 게임판의 상태가 \(y\)가 된다고 합시다.

\(dp[y] = 0\)이 되는 \(y\)가 존재한다면, 현재 플레이어는 그렇게 플레이함으로써 승리할 수 있습니다. (\(dp[x] = 1\))

그렇지 않다면, 현재 플레이어는 무조건 패배합니다. (\(dp[x] = 0\))

 

www.acmicpc.net/problem/9655

9655번: 돌 게임

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int dp[1001];
int solve(int x)
{
    int& ret = dp[x];
    if (ret != -1) return ret;
    if (x == 0) return ret = 0;
 
    if (x - 1 >= 0)
    {
        if (solve(x - 1) == 0) return ret = 1;
    }
    if (x - 3 >= 0)
    {
        if (solve(x - 3) == 0) return ret = 1;
    }
 
    return ret = 0;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    memset(dp, -1, sizeof dp);
 
    int n; cin >> n;
    if (solve(n)) cout << "SK";
    else cout << "CY";
}

---

스프라그-그런디 정리

게임판의 상태를 각각 하나의 자연수 (그런디 수)로 치환할 수 있다는 것이 스프라그-그런디 정리입니다.

그런디 수는 다음과 같이 정해집니다.

1. 아무것도 할 수 없는 게임판의 그런디 수는 0입니다.

2. 어떤 게임판의 상태 \(x\)에서 이동할 수 있는 다른 상태들의 그런디 수의 집합 \(Y\)에 대해, 이 게임판의 그런디 수는 \(mex(Y)\)입니다.

(\(mex(Y) :\) \(Y\)에 속하지 않는 자연수 중 가장 작은 수, Minimum EXcluded number)

 

그런디 수가 같은 두 게임판의 상태는 사실상 같은 상태임을 나타냅니다.

따라서 그런디 수가 0인 상태는 무조건 패배하는 상태이며, 0보다 큰 상태에서는 한 번의 행동으로 무조건 그런디 수가 0인 상태로 만들 수 있으므로 승리할 수 있는 상태입니다.

 

그래서 이 그런디 수를 대체 어디다 써먹는가 하면, 이와 같은 게임판이 여러 개 있을 때 사용합니다.

 

현재 \(n\)개의 게임판이 있고, 각 게임판의 그런디 수가 \(g_i\)라고 합시다.

이 \(n\)개의 게임을 동시에 진행한다면, 현재 상태의 그런디 수는 \(g_1 \oplus g_2 \oplus \cdots \oplus g_n\)입니다.

(\(\oplus :\) bitwise xor)

 

www.acmicpc.net/problem/11868

11868번: 님 게임 2

이 문제에서 돌 더미가 하나만 있다고 가정해 봅시다.

약간의 관찰로, 돌 더미에 돌이 \(x\)개 남아있으면 그런디 수도 \(x\)가 됨을 알 수 있습니다.

 

그런 돌 더미가 \(n\)개 있고 이를 동시에 진행하므로, 초기 상태의 그런디 수는 초기 돌 더미에 남아있는 돌의 수를 모두 xor한 값이 됩니다.

 

이 값이 0이면 선공이 패배하고, 그렇지 않으면 승리함을 알 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int n; cin >> n;
 
    int grundy = 0;
    for (int i = 0; i < n; i++)
    {
        int p; cin >> p;
        grundy ^= p;
    }
 
    if (grundy) cout << "koosaga";
    else cout << "cubelover";
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217