서론
게임 이론에서 게임의 현재 상태를 분석하기 위해 쓰는 스프라그 - 그런디 정리.
백준에서 날먹이라는 말이 있다.
어떤 이론이길래 그렇게 쉽게 되는 것일까?
솔직히 말해서 완벽하게 이 이론을 이해하려면 어렵다고 본다.....구현 자체가 쉽기 때문에 날먹이라는 말이 있는 것 같다.
따라서 오늘 이 글에서는 스프라그 - 그런디 정리를 내가 이해한 바에 따라 쉽게 설명해보고자 한다.
게임 상태
가장 먼저, 게임의 '상태'라는 것을 이해하고 넘어가자.
여러분들은 모두 어릴 적 '베스킨라빈스 31'이라는 게임을 들어본 적이 있을 것이다.
게임의 규칙은 다음과 같다.
선공과 후공이 번갈아가며, 1부터 시작하여 연속한 자연수를 1~3개 부른다. 31을 부르게 되는 사람이 진다.
수학을 좀 해본 사람들이라면(꼭 굳이 그렇지는 않더라도) 이 게임의 필승 전략을 들어본 적이 있을 것이다!
바로, 선공이 맨 처음에 2를 외치고, 후공이 무슨 수를 부르든 간에 선공은 수를 4k+2가 되게 맞추어 부를 수 있고, 그러면 선공은 무조건 30에서 끝나게 되어 후공이 31를 외칠 수 밖에 없게 된다.
조금 생각을 해보면, 만약 현재 게임에서 수가 2, 6, 10, 14, 18, 22, 26, 30이라면 당신은 무조건 이긴다!
그래서 우리는 이 2, 6, 10, 14, 18, 22, 26, 30의 상태를 승리 상태 라고 부른다.
반대로, 이 이외의 수들에서는 상대가 적당한 수를 불러 위 8개 수로 만들 수 있다. 그렇기 때문에 위 8개 수를 제외한 나머지 수들은 패배 상태이다.
님 게임
스프라그 - 그런디 정리를 알기 위해, 대표적인 게임 하나를 알고 들어가보자.
바로 님 게임이다.
초기에 막대기 뭉탱이가 N개 있다. 각각의 뭉탱이에는 막대기가 각각 $x_{i}$개씩 있다.
선공과 후공은 번갈아가면서 자신의 차례에 뭉탱이 하나를 고르고, 원하는 만큼 막대를 가져간다. 막대를 안 가져가는 것은 안된다.
마지막으로 막대기를 가져가는 사람이 승리한다.
님 게임의 현재 상태가 어떤 상태인지 분석할 수 있다.
예를 들어보자.
각 뭉탱이별 막대기의 개수를 리스트처럼 표현한다고 했을 때,
[0, 0, 0, ..., 0]
은 패배 상태이다. 더 이상 막대기를 제거할 수 없기 때문이다. 동시에 이 상태는 님 게임의 최종 상태이다.
우리는 님 합(Nim Sum)을 구하는 방법을 이용해서 님 게임이 현재 어떤 상태에 있는지 분석할 수 있다.
여기서 님 합은 ⊕로 나타낸다. 여기에서 ⊕는 XOR 연산을 나타낸다. (왜 XOR연산을 쓰는지는 뒤에서 알아보자)
님 합이 0이면 패배 상태, 아니면 승리 상태이다. 만약 내 차례에서 게임을 분석해보았는데 패배 상태라면, 당신은 이제 이 게임을 이길 수가 없다.
예를 들어보자.
예를 들어 막대기가 [3, 1, 4] 이렇게 있었다고 하면, 님 합은 3⊕1⊕4 = 6 이기 때문에 현재는 승리 상태이다.
또 다른 예시로, 현재 막대기가 [0, 0, 0]이면 님 합은 0이므로 패배 상태이다.
만약, 막대기가 [2, 2, 0]개 있었다고 해도 님 합은 0이므로 패배 상태이다. 즉 이 상태에서 당신은 무조건 질 수밖에 없다.
이제 님 합과 님 게임 사이에 무슨 연관이 있는지 알아보자.
만약 현재 상태가 패배 상태(님 합이 0)이면, 여기서 당신은 무슨 수를 취하든 님 합이 더 이상 0이 아니게 되어 게임은 승리 상태로 바뀌게 된다.
그리고, 만약 현재가 승리 상태이면 당신은 어떠한 더미를 선택하여 특정 행동을 취함으로써 게임의 상태를 반드시 패배 상태로 옮길 수 있다!
님 게임의 필승 전략과 XOR
위에서, 승리 상태를 반드시 패배 상태로 옮길 수 있다고 하였다. 이는 XOR 연산의 특징에 의해 이렇게 된다. 동시에 이는 님 게임을 분석할 때 XOR 연산을 쓰는 이유가 된다.
현재 게임의 상태의 님 합을 $x_{1}$ ⊕ $x_{2}$ ⊕ ... ⊕ $x_{N}$ = $s$라고 하자.
$x_{i}$ ⊕ $s$ < $x_{i}$를 만족하는 어떠한 뭉탱이가 존재한다면 여기서 적당한 수의 막대기를 빼서 게임을 패배 상태로 만들 수 있다.
예시를 들어보자.
상태 [3, 1, 4]를 생각해보도록 하자.
결론부터 말하자면, 이 상태에서는 4 ⊕ 6 = 2 < 4이므로, 막대기가 4개 남아있는 뭉탱이를 조작해서 님 합을 패배 상태로 만들 수 있다.
그리고, 그렇게 하기 위해서는 4개짜리 뭉탱이가 4 ⊕ 6 = 2 개가 되게 만들어야 한다.
일반적으로 말하자면, $x_{i}$가 $x_{i}$ ⊕ $s$가 되게 해야 한다는 것이다.
이유
위 상태를 보자.
님 합(XOR)의 특성상, 세로로 각 자리수를 보았을 때 1이 홀수 개 있으면 최종적인 비트가 1이 되고, 짝수 개 있으면 0이 됨을 알 수 있다.
어떤 뭉탱이에서 막대기를 빼서 최종적인 님 합이 0이 되게 하려면, 위 상황에서는 님 합의 제일 왼쪽에 있는 비트($2^{2}$의 자리)를 어떻게 좀 없애주어야 할 것이다.
그리고, 여기서는 4가 그 왼쪽 비트를 담당하게 된다.
즉, 4 뭉탱이에서 막대기를 가져가야 함을 알 수 있다.
일반적으로 생각해보아도, 님 합의 가장 왼쪽 비트를 해당하고 있는 수 $x_{i}$는, $s$와 XOR 연산 시 가장 큰 왼쪽 비트가 꺼지게 되므로, $x_{i}$ ⊕ $s$ < $x_{i}$가 됨을 알 수 있다.
님 합의 가장 왼쪽 비트를 담당하고 있는 수가 없을 수 없으므로, $x_{i}$ ⊕ $s$ < $x_{i}$가 되는 뭉탱이는 반드시 존재한다.
좋다, 어떤 뭉탱이에서 막대를 가져가야 하는지를 알았다.
그럼 막대를 얼마나 가져가야 하는가?
위에서 $x_{i}$가 $x_{i}$ ⊕ $s$가 되게끔 막대를 가져가야 한다고 말했는데, 이렇게 되면 님 합이 왜 항상 0으로 바뀌는지를 알아보자.
다시 위의 상황을 보자.
님 합이 0이 되기 위해서는 1이 홀수 개 있는 비트들의 홀짝성이 바뀌어, 모두 짝수가 되도록 만들어야 한다.
따라서 각 홀수 세로 슬롯에 1을 추가하거나 빼서, 짝수가 되게 만들 수 있다.
여기서 $x_{i}$가 $x_{i}$ ⊕ $s$로 바꾸게 되면, 그림에서도 볼 수 있듯이 XOR 연산에 의해 1이 홀수 개 있는 세로 슬롯에 1이 추가되거나 삭제되며 자연스레 홀짝성이 모두 짝수로 바뀌고, 님 합이 0이 됨을 알 수 있다.
결론: 승리 상태를 반드시 패배 상태로 만들 수 있으며, 그 방법의 수는 님 합의 가장 왼쪽 비트를 담당하고 있는 뭉탱이의 개수이다!
스프라그-그런디 정리
스프라그-그런디 정리는 다음 성질을 만족하는 "게임"을 님 게임으로 바꾸어 분석할 수 있다는 것이다.
- 두 플레이어가 번갈아가며 게임을 진행한다.
- 게임은 여러 상태로 구성되어 있으며, 상태 간 이동하는 방법은 누구의 차례인지와 무관한다.
- 움직임이 불가능이 경우 게임을 종료한다.
- 끝나지 않는 게임은 없다.
- 플레이어는 게임의 상태와 가능한 움직임에 대한 모든 정보를 가지고 있으며, 게임에는 무작위적인 요소가 없다.
출처: <알고리즘 트레이닝 2판>, 안티 라크소넨
게임에서 그룬디 수라는 것을 정의할 수 있다. 그룬디 수는 님 게임에서의 '막대기 개수'에 해당한다.
모든 상태에 대한 그룬디 수를 알고 있다면 님 게임처럼 플레이할 수 있다.
그룬디 수는 어떻게 정의하는가?
현재 상태에서 다음으로 이동할 수 있는 모든 상태의 그룬디 수에 대해 mex() 함수를 적용해 현재 상태의 그룬디 수를 구할 수 있다.
mex() 함수는, 집합에 속하지 않은 가장 작은 0 이상의 정수를 구하는 함수이다.
예를 들면, mex({1, 5, 0, 3} = 2이며, mex({2, 5, 3, 1}) = 0이다.
가능한 움직임이 없을 경우(최종 상태)에서의 그룬디 수는 0이 되는데, mex(공집합) = 0이기 때문이다.
님 게임을 생각해보자. 아까 그룬디 수 == 막대기 개수라고 했다.
막대기가 0개 있을 때는 아무것도 할 수 없으므로 그룬디 수는 0이다.
막대기가 1개 있을 때는 막대를 빼서 0개로 만들 수 있다. 그렇기 때문에 막대기가 1개 있을 때 그룬디 수는 mex({막대기가 0개일때 그룬디 수}) = mex({0}) = 1이다.
막대기가 2개 있을 때는 막대를 빼서 0 또는 1개로 만들 수 있다. 그렇기 때문에 막대기가 1개 있을 때 그룬디 수는 mex({막대기가 0개일때 그룬디 수, 막대기가 1개일때 그룬디 수}) = mex({0, 1}) = 2이다.
그래서 그룬디 수를 님 게임에서의 막대기 개수로 생각하면 편하다.
그룬디 수를 2차원에서도 생각해볼 수 있다. 가령 다음과 같은 게임을 생각해보자.
정사각형 모양의 체스판이 있으며, 판 중간중간에 장애물이 있다.
룩(Rook)은 맨 처음에 체스판의 가장 오른쪽 아래 구석에서 시작한다.
선공과 후공이 번갈아가며 룩을 왼쪽 혹은 위쪽 방향으로만 원하는 만큼 움직일 수 있으며,
왼쪽 상단 구석에 도달하거나 장애물에 막히는 등 더이상 말을 움직일 수 없게 되면 지게 된다.
예를 들어 다음과 같은 판이 있다고 하자.
각 칸에 그룬디 수를 적어넣기 시작할 것이다.
가장 먼저, 왼쪽 위(A1)은 더 이상 이동 불가능하므로 그룬디 수가 0이다.
B1의 경우, 이동할 수 있는 칸이 A1밖에 없다. 그룬디 수를 구하기 위해 mex({0})을 구하면 1이다.
이런 식으로 왼쪽 위부터 오른쪽 아래까지 쭉 모든 상태에 대한 그룬디 수를 채워넣을 수 있다.
그룬디 수를 구하기 위해서 mex()함수를 쓰는 이유는 바로 위 보드판을 보면 이해가 된다.
우리는 0(패배 상태)에서 어떤 방법을 써서 반드시 승리 상태로 만들 수 있어야 하고,
자연수(승리 상태)에서 어떤 방법을 써서 반드시 패배 상태로 만들 수 있어야 한다.
시작점의 그룬디 수는 0이다. 이는 룩의 앞으로의 이동 경로에 0이라는 수가 없음을 뜻한다.
즉, 앞으로의 모든 이동경로는 0이 아니라, 자연수다!
어떤 칸의 그룬디 수가 자연수라는 것은, 해당 칸으로부터의 이동 경로 어딘가에 반드시 0이라는 수가 존재함을 뜻한다.
즉!!! 승리 상태에 있는 플레이어는 반드시 어떤 행동을 해서 그룬디 수를 0으로 만들어버릴 수 있다.
참고로, 위 보드판 1개는 뭉탱이 하나로 생각할 수 있다. 그래서 게임의 님 합은 그냥 그룬디 수 그대로이다.
아까처럼 XOR 연산을 쓰는 님 합을 구해서 게임의 상태를 분석하는 경우는 다음과 같은 경우이다.
위와 같은 상황과 같이, 자신의 차례에 보드 하나를 골라서 말을 움직이는 상황을 보자.
각 보드를 뭉탱이 1개로 생각하면 이는 님 게임과 같은 상황이다.
참고로, 현재 게임 상태를 분석해보면 1 ⊕ 0 ⊕ 3 = 2이다. 즉 승리 상태이다!
여기서 어떠한 행동을 해서 님 합을 0, 즉 패배 상태로 만들 수 있다는 말이다.
스프라그-그런디 정리는 백준 문제에서 보통 dp를 이용해서 각 상태의 그룬디 수를 구하는 식으로 쓰인다.
예제
https://www.acmicpc.net/problem/13034
언젠가 정올에서 컴퓨터를 이겨라! 하는 식으로 본 적이 있는 문제이다.
이 다각형 게임은 어떻게 님 게임으로 대응해서 생각해볼 수 있을까?
이 게임의 핵심은, 어떤 특정한 움직임을 택해서 서로 영향을 주지 않는 여러 부분 게임으로 나누어진다는 것에 있다. 이를 그룬디 게임이라고 하며, 이건 마치 님 게임에서 막대 뭉탱이를 둘로 나누어 뭉탱이를 1개 더 추가하는 것과 비슷한 상황이다!
예를 들어서, 다음과 같은 육각형 모양에서 선분을 어디에 긋냐에 따라 게임을 나누는 방법이 달라진다.
예를 들어 선분 13을 그으면 이제 (2) 와 (5, 6) 부분으로 나누어진다. 다음 플레이어는 두 군데 중 하나를 선택에서 행동을 할 수 있다.
각 뭉탱이에 대해 남아있는 점의 개수(상태)의 그룬디를 구해서 dp 방식으로 모든 초기 점의 개수에 대해서 그룬디 수를 구할 수 있다.
초기값은 grundy[0] = 0, grundy[1] = 0, grundy[2] = 1이다. (점이 0개, 1개 남아있을 때는 아무 행동도 할 수 없으므로)
위의 육각형 모양(점 6개)에서 그룬디 수를 구해보자.
당신은 여러가지 선택을 할 수 있는데,
점들을 0:4, 1:3, 2:2, 3:1, 4:0으로 나눌 수 있다.
a:b로 나누어진 상태의 그룬디 수는 grundy[a] ⊕ grundy[b]를 통해 구할 수 있다.
그런 다음 얻은 5개의 그룬디 수에 대해 mex()함수를 적용하면 점이 6개일때의 그룬디 수를 구해줄 수 있다.
이런 식으로 점이 0, 1, 2 ... N개일 때의 그룬디 수를 구할 수 있고, 게임의 상태를 분석할 수 있다.
정답 코드
N = int(input())
dp = [0]*(N+1)
dp[1] = 0
dp[2] = 1
for i in range(3, N+1):
s = set()
for j in range(i-1):
s.add(dp[j]^dp[i-2-j])
for mex in range(1001):
if mex not in s:
dp[i] = mex
break
if dp[-1] != 0:
print(1)
else:
print(2)
결론
스프라그-그런디 정리를 통해 게임들을 '님 게임화' 시켜서 생각해볼 수 있다.
이제 여러분들도 여러 게임들에서 필승전략이나 게임 상태 등을 분석할 수 있다!
'PS' 카테고리의 다른 글
| [Python] 백준 20544 - 공룡게임 (0) | 2025.09.26 |
|---|---|
| [Python] 백준 11717 - Wall Making Game (0) | 2025.08.21 |
| [Python] 백준 8481 - Generator (0) | 2025.08.20 |
| [Python] 백준 1533 - 길의 개수 (0) | 2025.08.18 |
| [Python] 백준 18122 - 색깔 하노이 탑, 백준 27743 - 어려운 하노이 탑 (0) | 2025.08.18 |