별과 정리 · 제54장 · 1부 · 누구나 손댈 수 있는 것

돌 가져가기 놀이

Nim

먼저 두는 사람이 반드시 이기는 자리가 있다

돌 세 무더기, 먼저 두면 이깁니다

돌을 세 무더기로 쌓아 둡니다. 둘이 번갈아 한 무더기에서 원하는 만큼 가져가고, 마지막 돌을 집는 사람이 이깁니다.

운으로 갈리는 놀이 같지요. 그런데 아닙니다. 돌을 늘어놓은 순간 누가 이길지 이미 정해져 있습니다. 이기는 사람이 아는 것은 무엇일까요?

이야기

1901년, 하버드의 찰스 부턴이 이 놀이에 「니임」이라는 이름을 붙이고 완전히 풀어 발표했습니다. 누가 이길지, 어떻게 두어야 하는지를 남김없이 밝힌 것입니다. 놀이가 이렇게 통째로 풀린 것은 드문 일이었습니다.

그런데 이 놀이는 뜻밖의 자리에서 다시 나타납니다. 1940년 뉴욕 세계박람회에 「니마트론」이라는 커다란 기계가 전시되었습니다. 무게가 1톤이나 나가는 이 기계는 사람과 니임을 두었고, 십만 판 넘게 두어 대부분 이겼습니다. 세상에서 가장 이른 게임 기계 가운데 하나입니다.

이기는 법은 이렇습니다. 각 무더기의 돌 수를 이진법으로 적고, 자리마다 1의 개수를 셉니다. 모든 자리가 짝수인 상태를 상대에게 넘기면 이깁니다.

왜 될까요. 모두 짝수인 상태에서는 무엇을 집어도 반드시 어딘가가 홀수로 깨집니다. 한 무더기만 건드리는데 그 무더기의 이진수가 바뀌기 때문입니다.

거꾸로 홀수인 자리가 있으면 언제나 다시 모두 짝수로 만드는 수가 존재합니다. 그러니 이기는 쪽은 짝수를 계속 넘기기만 하면 되고, 마지막에 돌이 하나도 없는 상태 — 그것도 모두 짝수인 상태입니다 — 를 상대에게 넘기게 됩니다.

오늘 이것이 하는 일

「먼저 두면 반드시 이긴다」를 계산으로 아는 법입니다. 돌 무더기를 이진수로 적어 XOR 하면 승패가 나옵니다.

이 생각이 게임 이론으로 자라 인공지능이 바둑과 체스를 두는 방식의 밑돌이 되었습니다.

계단 넷 — 같은 사실을 네 깊이로

초4 · 초5 — 손으로 해 본다

돌을 놓고 둘이 겨룬다

바둑돌을 1개, 2개, 3개처럼 작은 수로 무더기를 만들어 둘이 번갈아 가져가 봅니다. 마지막 돌을 가져가는 사람이 이기는 규칙으로 몇 판 겨뤄 보세요.

무더기가 둘이고 개수가 같을 때는 상대가 한쪽에서 가져간 만큼 다른 쪽에서 똑같이 가져오면 항상 이깁니다. 돌의 개수가 다를 때도 똑같은 모양을 되돌려 주는 자리를 눈으로 찾아보세요.

돌을 가져가 보세요

돌 더미 (3개, 4개, 5개)를 이진수 비트 막대(011, 100, 101)로 겹쳐서 XOR 합을 본다

먼저 두면 이기나 —n mod (k+1) —처음에 가져갈 수 —

돌 수 n — 21

한 번에 최대 — 1

겉보기엔 평범한 돌 세 더미인데, 그런데 이진수 비트 막대를 겹쳐 XOR 합이 0이 되는 순간 상대는 절대로 못 이긴다
돌을 아무렇게나 집는 것 같지만 이진수 막대기 짝을 맞추는 순간 백전백승 마법이 걸린다

중1 · 중2 — 까닭을 찾는다

이기는 자리 찾기

두 무더기일 때는 개수를 같게 만들어 상대에게 넘겨주면 이깁니다. 상대가 짝을 깨뜨리면 나는 다시 같게 맞출 수 있기 때문입니다.

세 무더기 이상일 때는 각 무더기의 돌 수를 2의 거듭제곱(1, 2, 4, 8) 묶음으로 나누어 적어 봅니다. 각 묶음의 개수가 모두 짝수가 되도록 돌을 집어내면 상대는 어떤 수를 두어도 반드시 짝수 균형을 깨뜨리게 됩니다.

지는 자리를 찾아 보세요

더미 A=3(011), B=4(100), C=5(101)에서 각 자리 비트를 끄고 켜는 슬라이더를 움직인다

지는 자리인가 —나머지 —다음 지는 자리 —

돌 수 n — 20

한 번에 최대 — 1

돌을 무턱대고 많이 가져온다고 유리한 게 아니라, 그런데 XOR 합의 최상위 비트(bit 1)를 가진 더미 A에서 정확히 2개를 빼서 1(001)로 만드는 단 한 수만이 승리를 보장한다
돌을 무조건 많이 집는 게 아니라 이진수 짝을 맞추는 정답 1수를 두어야 이긴다

고1 · 고2 — 넓혀 본다

이진법 XOR

각 무더기의 돌 수를 이진법으로 나타낸 뒤, 자리올림 없이 각 자릿수를 더하는 배타적 논리합(XOR)을 계산합니다. 이를 님 합(Nim-sum)이라 부릅니다.

님 합이 0인 상태는 패배 위치(P-position), 0이 아닌 상태는 승리 위치(N-position)입니다. 님 합이 0이 아니면 적절한 무더기에서 돌을 덜어내어 항상 님 합이 0이 되도록 상대에게 넘길 수 있으며, 님 합이 0이면 어떻게 돌을 가져가도 0이 아닌 상태로 바뀝니다.

더미가 여럿이면

돌을 한 번에 최대 3개까지만 가져갈 수 있는 변형 님 게임에서 각 상태의 mex(최소 제외수) 값을 계산한다

XOR —먼저 두면 이기나 —합 —

첫째 더미 — 3

둘째 더미 — 5

셋째 더미 — 0

규칙이 복잡하게 바뀐 게임이라도, 그런데 모든 공정한 불완전 정보 없는 게임 상태는 정확히 1개의 님 더미 크기(G-값)로 환원되어 똑같이 XOR 합으로 격파된다
어떤 변형 게임이든 상태마다 점수를 매겨 합치면 결국 똑같은 돌 게임으로 변한다

대학 — 어디까지 가나

조합 게임 이론

찰스 부턴이 1901년 증명한 님의 해법은 조합 게임 이론(Combinatorial Game Theory)의 초석이 되었습니다. 마지막 수를 두는 사람이 이기는 모든 유한 불편 게임(impartial game)은 님 게임으로 바꿀 수 있습니다.

스프라그-그런디(Sprague-Grundy) 정리에 따르면, 동등한 규칙의 모든 게임 상태는 하나의 님 무더기(Grundy 값)로 대응됩니다. 복잡한 바둑이나 체스의 종반 분석에서도 이와 같은 상태 평가 방식이 핵심 원리로 작동합니다.

스프라그–그런디 수

더미를 밀어 보세요.

그런디 수 —이기는 수 —만들 목표 —

더미 A — 9

더미 B — 12

더미 C — 5

모든 공평 게임은 어떤 님 더미 하나와 같습니다 (스프라그–그런디).
게임이 아무리 복잡해도 수 하나로 요약됩니다.

풀어 보기

중학교 · 고등학교 수준 · 답은 검산을 마쳤습니다

돌 세 무더기 놀이. 세 무더기에 돌이 각각 3개, 4개, 5개 놓여 있다. 두 사람이 번갈아 한 무더기에서 1개 이상의 돌을 가져가며, 마지막 돌을 가져가는 사람이 이긴다.

(1) 세 수 3, 4, 5를 이진법으로 나타내고, 세 수의 님 합(XOR)을 십진수로 구하시오.
(2) 첫 번째 사람이 첫 수로 반드시 이기려면 어느 무더기에서 몇 개의 돌을 가져와야 하는가? (모든 가능한 수를 쓰시오)
(3) 돌이 1개, 2개, 3개 놓인 판에서 첫 번째 사람이 반드시 이기는 첫 수를 말하시오.

(1) 3(011₂), 4(100₂), 5(101₂)의 XOR 합은 010₂ = 2입니다. 님 합이 0이 되도록 조절합니다.

답과 풀이 보기

(1)
자리마다 1 의 개수를 세면 (1,2,2) 이고, 홀수인 자리는 맨 아래 하나입니다.
— 0 이 아니므로 먼저 두는 사람이 이깁니다.

(2) 님 합이 0 이 되도록 넘겨야 합니다.
3 개짜리 무더기를 1 로 만들면 입니다. → 3 개짜리에서 2 개를 가져간다 (남는 것 1, 4, 5)
다른 길은 없습니다. 4 를 고치려면 으로 만들어야 하는데 6 > 4 이고, 5 를 고치려면 인데 7 > 5 이기 때문입니다. 이기는 수는 단 하나입니다.

(3) 입니다.
이미 0 이므로 먼저 두는 사람이 집니다. 이기는 첫 수가 없습니다 — 상대가 실수하기를 기다리는 수밖에 없습니다.

돌 가져가기 놀이에 이진법이 숨어 있을 줄은 아무도 몰랐습니다. 1901 년 찰스 부턴이 밝혔습니다.

만지는 수학으로 손에 쥐어 보기

이 장과 이어지는 「만지는 수학」 칼럼입니다. 손끝으로 직접 끌고 눌러 보며 같은 생각을 몸으로 겪을 수 있습니다.

경우의수고1

더 멀리

이 놀이에서 조합 게임 이론이라는 분야가 자랐습니다.

다른 놀이로 — 여러 놀이를 합친 것도 같은 방법으로 분석합니다
인공지능 — 바둑·체스 프로그램의 뿌리에 이런 생각이 있습니다
직접 해 보기 — 3·4·5 무더기로 시작해 보세요. 먼저 두는 쪽이 이깁니다

이어지는 장

돌 무더기의 개수를 이진법으로 적어 각 자리마다 짝홀을 맞추는 순간 필승의 수가 환하게 드러납니다 — 제26장 에서 익힌 이진법이 어떻게 게임의 승패를 결정짓는 강력한 계산 무기가 되는지 만나보세요.

영감을 받은 곳

미국 하버드 대학교의 수학자 찰스 부턴(Charles L. Bouton)이 1901년 학술지 『수학연보』(Annals of Mathematics)에 발표한 논문 「님, 완전한 수학적 해법을 가진 게임」(Nim, a Game with a Complete Mathematical Theory)에서 왔습니다.