님과 스프라그–그런디 정리(Nim and the Sprague–Grundy theorem)

돌무더기 세 개에 돌이 1개, 2개, 3개 있습니다. 두 사람이 번갈아 무더기 하나를 골라 거기서 돌을 원하는 만큼(적어도 하나) 가져가고, 마지막 돌을 가져가는 사람이 이깁니다. 먼저 두는 사람은 이길 수 있을까요? 가능한 수를 모두 따져 보면 답은 '아니다'입니다. 무더기 하나를 통째로 없애면(예: 2, 3) 상대가 큰 쪽을 작은 쪽에 맞추고(2, 2), 그 뒤로는 상대가 흉내만 내면 됩니다. 한 무더기를 조금 줄이면(예: 1, 1, 3) 상대가 셋째 무더기를 없애 1, 1을 남깁니다. 어느 수를 두든 상대에게 되받아칠 수가 있습니다.

이 게임이 님입니다. 1901년 하버드의 수학자 찰스 부턴이 『수학 연보』에 실은 글 「님, 완전한 수학적 이론을 가진 게임」에서 이름을 붙이고 풀었습니다. 부턴에 따르면 미국의 대학과 장터에서 여러 형태로 놀던 게임이었습니다. 그의 규칙은 이렇습니다. 무더기의 크기를 이진법으로 적어 자리를 맞추고, 모든 자리에서 1의 개수가 짝수이면 차례인 사람이 집니다. 1, 2, 3은 01, 10, 11이라 두 자리 모두 1이 두 개씩이니, 먼저 두는 사람이 집니다. 자리마다 1의 개수의 홀짝을 적은 수를 님 합이라 하고 $a \oplus b$로 적습니다. 받아올림 없이 자리마다 2를 법으로 더하는 셈이며, 컴퓨터의 비트 연산⁠(bitwise operation)⁠ XOR과 같습니다.

규칙이 옳은 까닭은 세 가지 사실입니다. (1) 돌이 없는 끝 국면의 님 합은 0입니다. (2) 님 합이 0인 국면에서는 무엇을 두어도 님 합이 0이 아니게 됩니다. 무더기 하나만 바뀌고, 그 무더기의 이진법 표기에서 적어도 한 자리가 바뀌어 그 자리의 홀짝이 뒤집히기 때문입니다. (3) 님 합 s가 0이 아니면 0으로 만드는 수가 있습니다. s에서 1인 가장 높은 자리에 1을 가진 무더기 a를 골라 $a \oplus s$개로 줄이면 됩니다. 그 자리가 1에서 0이 되므로 $a \oplus s \lt a$이고, 전체 님 합은 $s \oplus s = 0$이 됩니다. 그러니 님 합을 0으로 넘겨받은 사람은 계속 0이 아닌 국면을 돌려줄 수밖에 없고, 마지막 돌은 상대가 가져갑니다. 이것은 끝에서부터 이기는 자리와 지는 자리를 매기는 거꾸로 따지기⁠(backward induction)⁠를, 국면마다 따지지 않고 공식 하나로 끝낸 것입니다.

표를 보면 님 합의 성질이 보입니다. 대각선은 모두 0입니다($a \oplus a = 0$). 각 행과 각 열에는 0부터 7까지가 한 번씩 나오니, $a \oplus x = b$의 해는 언제나 하나($x = a \oplus b$)입니다. 님 합은 결합법칙⁠(associativity)⁠과 교환법칙⁠(commutative law)⁠을 지키고 0이 항등원⁠(identity element)⁠이며 모든 원소⁠(element)⁠가 자기 자신의 역원⁠(inverse element)⁠이라, 음 아닌 정수⁠(integer)⁠들이 님 합에 대해 군을 이룹니다. 이 군은 2원소 체 위의 벡터⁠(vector)⁠들을 더하는 것과 같습니다. 이진법의 각 자리가 좌표 하나입니다.

스프라그–그런디 정리. 님의 풀이는 님 하나로 끝나지 않았습니다. 1935년 베를린의 고등학교 교사 롤란트 스프라그와, 1939년 케임브리지의 학생 패트릭 그런디가 서로 모른 채 같은 정리를 발표했습니다. 두 사람이 똑같은 수를 쓸 수 있고(공정한 게임⁠, impartial game⁠), 반드시 유한한 수 안에 끝나며, 둘 수 없는 사람이 지는 게임을 생각합시다. 국면 P의 그런디 수⁠(Grundy number)⁠ $g(P)$를 끝에서부터 이렇게 정합니다. P에서 한 번에 갈 수 있는 국면들의 그런디 수를 모아, 거기 없는 가장 작은 음 아닌 정수를 고릅니다. 이 연산을 mex(minimum excluded)라 합니다. 그러면 P는 크기가 $g(P)$인 님 더미 하나와 같고(어떤 게임 옆에 나란히 놓아도 누가 이기는지가 같다는 뜻입니다), 여러 게임을 나란히 놓고 매번 하나를 골라 두는 합 게임의 그런디 수는 각 그런디 수의 님 합입니다. 차례인 사람은 그런디 수가 0일 때, 그리고 그때만 집니다.

왜 mex일까요? 크기 n인 님 더미에서는 0, 1, …, n − 1 크기로 갈 수 있고 n으로는 갈 수 없습니다. 그런디 수가 c인 국면도 mex의 정의 때문에 c보다 작은 모든 값으로 갈 수 있고 c로는 갈 수 없습니다. 더 큰 값으로 갈 수 있을지도 모르지만, 그런 수는 상대가 곧바로 c로 되돌려 놓을 수 있으니 소용이 없습니다. 게임의 승패만 놓고 보면 이 국면은 님 더미 c와 구별되지 않습니다. 그 뒤는 님의 풀이를 그대로 씁니다.

한 번에 가져갈 수 있는 개수를 로 정한 한 무더기 게임입니다. '원하는 만큼'이면 그런디 수는 n 자신이고, 이것이 님 더미입니다. '1, 2, 3개'에서는 n을 4로 나눈 나머지⁠(remainder)⁠가, '1, 3, 4개'에서는 0, 1, 0, 1, 2, 3, 2가 7마다 되풀이됩니다. 가져갈 수 있는 개수의 목록이 유한한 게임에서는 그런디 수가 언젠가 반드시 주기적으로 되풀이됩니다. 한 칸의 값은 바로 앞 몇 칸(가장 큰 가져가기 수만큼)의 값으로 정해지고, 각 값은 가져가기 방법의 수를 넘지 않으니 그 값들의 조합이 유한하기 때문입니다. 이제 이런 게임 몇 개와 님 더미 몇 개를 섞어 놓은 복잡한 게임도, 각각의 그런디 수를 표에서 읽어 님 합을 내면 누가 이기는지 압니다.

규칙을 뒤집어 마지막 돌을 가져가는 사람이 지는 님(미제르 님)은 거의 같게 풀립니다. 보통의 님처럼 두다가, 자기 수를 두고 나면 크기 2 이상인 무더기가 하나도 남지 않게 되는 순간에만 크기 1인 무더기를 홀수 개 남기도록 바꾸면 됩니다. 부턴의 1901년 글도 이런 변형을 다루었습니다. 그러나 미제르 규칙의 일반적인 공정한 게임에는 스프라그–그런디 정리 같은 깔끔한 이론이 없고, 오늘날까지 연구가 이어집니다. 두 사람이 서로 다른 수를 쓰는 게임(바둑의 끝내기처럼)으로 넓힌 이론은 1976년 존 콘웨이의 『수와 게임에 대하여』에서 시작되었습니다. 거기서 어떤 게임들은 수처럼 더하고 크기를 비교할 수 있어서, 실수⁠(real number)⁠와 무한소⁠(infinitesimal)⁠, 무한대를 모두 품는 초현실수⁠(surreal number)⁠라는 수 체계⁠(number system)⁠를 이룹니다. (크기 1인 님 더미처럼 수가 아닌 게임도 있습니다.)

이어지는 곳. 끝에서부터 국면에 이름을 매기는 원리는 게임 트리⁠(game tree)⁠ 탐색과 동적 계획법⁠(dynamic programming)⁠이 공유하고, 그 원리가 우연이 없고 모든 것이 보이는 유한한 게임에 모두 통한다는 것이 체르멜로의 정리입니다. 님 합이 자리마다 2로 나눈 나머지의 덧셈이라는 점은 모듈러 산술과 불 대수⁠(Boolean algebra)⁠의 XOR로, 모든 원소가 자기 역원인 군이라는 점은 군으로 이어집니다. 무한히 이어지는 게임에서도 반드시 이기는 쪽이 있느냐는 물음은 게임의 결정성에서 다룹니다. 님을 직접 두어 보며 체스, ε–δ, 최소최대 정리⁠(minimax theorem)⁠, 논리의 게임과 함께 읽으려면 「이기는 쪽이 존재한다」를 보세요.