오로지 PS만을 위한 Sprague-Grundy Theorem(스프라그-그런디 정리)

PS를 하다 보면 Combinatorial Game Theory(조합론적 게임 이론) 분야가 있다. 이번 방학 동안 참가한 알고리즘 캠프에서 알게 된 분야인데, 내용이 상당히 어려웠고 다른 사람들도 어렵게 느낄 것이라는 생각이 들었다.

이 분야를 이해하기 위해 열심히 발버둥친 결과, 증명 등은 배제하고 몇 가지 핵심만 안다면 많은 사람들이 충분히 이 분야의 문제들에 도전해볼 수 있을 것이라는 생각을 했다. 따라서 이 글은 엄밀하게 Combinatorial Game Theory를 공부해 보자는 글은 아니며 오로지 PS만을 위한 응용을 목적으로 하는 글이다. 이어지는 내용에서 결론만 이야기하고 넘어가는 부분들이 많은데 이 글의 목적을 위해서 그렇게 서술한 것이니 관심이 있는 사람들은 마지막에 달아 놓은 링크들을 참고하자.

Combinatorial Game Theory 문제 유형에 대해

Combinatorial Game Theory는 바둑, 오목처럼 플레이어끼리 하는 게임을 분석하는 분야이다. 경제학에서의 게임 이론과는 전혀 다르다! 그리고 Sprague-Grundy Theorem은 Combinatorial Game Theory 안의 한 정리이다. PS에서는 대부분 이 정리를 이용하는 형태이기 때문에 이 정리가 이 글의 핵심 주제가 되겠다. 이 분야의 문제는 대부분 다음과 같은 형태이다.

• ~~~(규칙 설명)~~~ 하는 게임이 있다. 두 플레이어가 최적의 방법으로 게임을 할 때, 누가 이기는가?

즉 "두 플레이어 모두 필승법을 알고 있다면 누가 이기는가?"를 생각하는 문제들이다. 필승법이 존재하는 게임이 있어봐야 얼마나 있다고... 라는 생각이 들 수 있지만 결론적으로 [ 유한 차례 안에 끝나고, 게임이 끝났을 때 비기는 상태가 없는 완전 정보 게임(현재까지의 게임의 전개 과정을 모두 알 수 있는 게임) ] 에서는 항상 둘 중 한명의 플레이어에게 필승법이 존재한다!

엄청나게 중요한 Nim 게임

위 조건을 만족하는 대표적인 게임으로 Nim 게임이 있다. Nim 게임은 뒤에 다룰 Sprague-Grundy Theorem을 위해서도 굉장히 중요하다. 이해하기 쉬운 아주 간단한 게임인데, 몇 개의 돌 더미가 있고 각 플레이어는 자신의 차례에 하나의 돌 더미를 선택해 그 안에서 하나 이상의 돌을 가져간다. 그리고 자신 차례에 가져갈 돌이 없으면 패배하는 게임이다. 이 게임은 필승법이 존재하는데, 이번에도 역시 결론만 말하자면 최적의 방법으로 게임을 할 때 모든 돌 더미의 돌 수를 xor한 값이 0이면 후공이, 그 외에는 선공이 이긴다. 왜 이렇게 되는지가 궁금하다면 글 마지막의 링크를 참고하자.

Sprague-Grundy Theorem

Sprague-Grundy Theorem은 엄청나게 많은 게임을 Nim 게임으로 환원시키는 정리이다. 우리는 이미 Nim 게임의 필승법을 알고 있으니, Sprague-Grundy Theorem을 통해 엄청나게 많은 게임에 대해 최적의 방법으로 플레이했을 때 누가 이기는지 알 수 있게 된다! 정확한 정의는 다음과 같다.

• Sprague-Grundy Theorem: 모든 impartial game(어떤 플레이어의 차례인지에 관계 없이 가능한 행동이 동일한 게임 - Nim, 베스킨라빈스 31 게임 등)은 Nim 게임에서의 돌 더미 하나로 생각할 수 있다.

Sprague-Grundy Theorem이 무엇인지 알았고 엄청나게 유용한 정리라는 것도 알았다. 그런데 Nim 게임에서 누가 이기는지를 판단하는 방법을 곰곰이 생각해 보면 우리는 한 가지 정보가 부족하다. 우리는 돌 더미의 개수를 모른다! 그래서 도입되는 것이 Grundy Number라는 개념이다.

Grundy Number

Grundy Number란, Sprague-Grundy Theorem에서 한 게임에 대응되는 Nim 돌더미의 돌 수이다. 그리고 이는 어떤 게임의 상태에 대응하는 값이다. 가령 현재 게임의 상태를 G라고 하면 Grundy Number는 일종의 함수가 되는 것이고 보통 g(G)로 나타낸다. Grundy Number를 계산할 때의 핵심적인 규칙들을 소개하겠다.

• 할 수 있는 행동이 없는 상태(패배하는 상태)의 Grundy Number는 0이다.
• 일반적인 상태의 Grundy Number는 mex( 가능한 모든 다음 상태의 그런디 수 )이다. mex는 집합에 포함되지 않은 가장 작은 0 이상의 정수를 구하는 함수이다. 예를 들어 mex( 0, 1, 3, 4, 7, 9 ) == 2이다. 다시 말하면 현재 상태로부터 가능한 다음 상태는 여러 가지가 있을 텐데, 그 모든 상태의 Grundy Number를 구하고 그것들에 대해 mex 함수를 취해 주면 그 값이 현재 상태의 Grundy Number가 된다.
• 게임이 여러 개이고 각 게임마다 Grundy Number가 a, b, c, ...라고 하면 모든 게임을 합친 게임의 Grundy Number는 a ^ b ^ c ^ ...이다. 게임이 여러 개라는 것은 Nim 게임에서 돌 더미가 여러 개라는 것이고 따라서 Nim 게임에서와 같은 논리로 xor 연산을 해 주는 것이다!

이렇게 많은 종류의 게임을 Nim 게임으로 환원시킬 수 있게 되었다. 즉 Grundy Number만 구하면 Nim과 같은 필승법을 적용할 수 있다는 의미이고 결국 두 플레이어가 최선의 선택을 할 때 어떤 게임이든 Grundy Number가 0이 아니면 선공이 이기며, 0이면 후공이 이긴다.

문제로의 적용 - [BOJ #3596] 크로스와 크로스

문제는 매우 짧고 간단하니 따로 읽어보면 되겠다. Sprague-Grundy Theorem을 적용해서 바로 풀어 볼 텐데, 적용 이전 문제를 Sprague-Grundy Theorem을 적용하기 좋은 형태로 변형해 보겠다. 플레이어가 어떤 칸에 x 표시를 하면, 다음 플레이어는 어떤 곳에 x 표시를 할 수 있을까? 조금만 생각해 보면 표시된 x를 기준으로 왼쪽 2칸, 오른쪽 2칸을 제외한 곳에 x 표시를 할 수 있다. 그렇지 않은 곳에 x 표시를 하면 연속된 3개의 x를 만들 수 있는 상태를 상대에게 넘겨주게 되기 때문이다.

 

즉 x 표시를 하는 행위는 그 위치를 중심으로 총 5칸을 없애는 행위라고 볼 수 있고, 자신 차례에 x 표시를 할 칸이 없다면 패배하는 게임이라고 볼 수 있게 된다. 이제 Grundy Number를 구해 보자. 이 게임은 간단해서 게임의 상태는 보드의 칸 수에만 영향을 받는다. 따라서 g(n)을 n칸짜리 보드의 Grundy Number라고 정의하겠다.

 

먼저 x 표시를 할 칸이 없다면 패배하므로 g(0)은 0이다. g(1)의 경우 다음 상태가 g(0) = 0뿐이므로 g(1) = mex(g(0)) = mex(0) = 1이다. g(2)과 g(3)도 마찬가지로 1이다. g(4)부터 이야기가 조금 달라지는데 가능한 다음 상태는 두 가지가 있다. 첫 번째 경우는 맨 왼쪽에 x 표시를 해서 1칸을 남기는 경우이고, 두 번째 경우는 왼쪽으로부터 두 번째 칸에 x 표시를 해서 0칸을 남기는 경우이다. 따라서 g(4) = mex(g(1), g(0)) = mex(1, 0) = 2이다. g(5)도 마찬가지 방식으로 2이다.

 

여기까지를 base case로 잡고 이제 다른 모든 n에 대해서 가능한 모든 다음 상태를 논할 수 있다. n == 10인 상황을 예로 들겠다.

대칭을 제외하고 생각해 보면 n == 10일 때 가능한 다음 상태는 총 5가지가 있다. 각 상태의 Grundy Number를 구해 보면 1번 상태는 g(7), 2번 상태는 g(6), 3번 상태는 g(5), 4번 상태는 g(1) ^ g(4), 5번 게임은 g(2) ^ g(3)이다. 4번, 5번 상태는 게임이 독립적인 두 개의 게임으로 나뉘었기 때문에 이렇게 구해지는 것이다! 따라서 g(10) = mex(g(7), g(6), g(5), g(1)^g(4), g(2)^g(3))으로 구할 수 있다. g(10)을 구하기 위해 10보다 작은 값들에 대한 Grundy Number만 필요하므로 우리는 bottom-up 방식으로 모든 상태에 대한 Grundy Number를 구할 수 있다! 그 후 Grundy Number가 0이 아니면 선공이 이기고 0이면 후공이 이긴다고 보면 된다.

 

이 문제로의 적용을 마지막으로 이 주제에 대한 글을 마치도록 하겠다.

참고

Zermelo's Theorem: en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theory)

Nim#Proof of the winning formula: en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formula

Sprague-Grundy Theorem: en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem