돌 가져가기 게임

한눈에 보기

님(Nim)은 우연이 전혀 없고 모든 정보가 공개된 2인 게임이라, 시작 위치만 보면 누가 이기는지 계산으로 정해집니다. 열쇠는 무더기 크기를 이진수로 바꿔 XOR한 값(님 합)입니다. 이 글에서 얻는 것은 규칙과 필승 수 계산법, 시작 배치별 승률, 님 게임이 역사 속에서 어떻게 쓰였는지, 그리고 흔한 오해입니다.

• 님 합이 0이 아니면 지금 차례인 사람이 이기고, 0이면 진다(상대가 실수하지 않는 한).
• 이기는 수는 "님 합을 0으로 만드는 수"이며 계산으로 찾을 수 있다.
• 이 페이지는 마지막 돌을 가져가면 이기는 규칙이다. 반대 규칙(미제르)과 막판 전략이 다르다.
• 이 게임은 컴퓨터 역사에서 초기 "게임하는 기계"의 소재로 쓰였다.

게임 규칙과 이 페이지의 설정

• 돌은 3개 또는 4개(같은 확률)의 무더기로 나뉘며, 무더기마다 1~7개가 무작위로 정해집니다. 시작 시 전체 돌은 최소 3개, 최대 28개입니다.
• 자기 차례에는 무더기 하나를 골라 그 안에서 1개 이상, 그 무더기 전체까지 원하는 개수를 가져갈 수 있습니다. 두 무더기 이상에서 동시에 가져갈 수는 없습니다.
• 마지막 남은 돌을 가져가는 사람이 승리합니다(마지막 돌을 가져가면 지는 변형 규칙은 쓰지 않습니다).
• 가져가고 싶은 무더기의 돌을 클릭하면, 클릭한 돌부터 그 무더기 맨 끝까지가 한 번에 제거됩니다. 첫 번째 돌을 누르면 그 무더기 전체가 사라집니다.
• 사람이 항상 먼저 둡니다. 컴퓨터는 약 0.6초 뒤에 응답하고, 직전에 컴퓨터가 가져간 돌의 정보가 화면 아래에 표시됩니다.
• 점수나 전적은 저장하지 않으며 난수는 브라우저의 Math.random()(보안용이 아님)으로 시작 배치에만 쓰입니다.

필승 전략: XOR(님 합)

님(Nim)은 두 사람이 번갈아 두며 우연 요소가 없는 완전 정보 게임으로, 1901년 찰스 L. 바우턴이 분석해 모든 위치의 승패를 가르는 방법을 밝힌 것으로 알려져 있습니다. 핵심은 각 무더기의 돌 개수를 이진수로 쓰고 자리마다 XOR(같으면 0, 다르면 1)을 취한 값, 이른바 님 합(nim-sum)입니다.

• 님 합이 0이 아니면: 지금 차례인 사람이 이기는 위치입니다. 님 합을 0으로 만드는 수가 반드시 존재합니다.
• 님 합이 0이면: 지금 차례인 사람이 지는 위치입니다. 어떤 수를 두어도 님 합이 0이 아니게 되어 상대가 다시 0으로 되돌릴 수 있습니다.

이기는 수를 찾는 방법은 이렇습니다. 전체 님 합을 X라고 할 때, 각 무더기 c에 대해 c XOR X를 계산합니다. 그 값이 c보다 작은 무더기가 있으면, 그 무더기를 (c XOR X)개가 되도록 줄이면 님 합이 0이 됩니다. 이 페이지의 컴퓨터는 님 합이 0이 아닐 때 이 계산으로 첫 번째로 찾은 무더기에서 수를 두고, 님 합이 0이면(이길 길이 없으면) 비어 있지 않은 무더기 하나를 무작위로 골라 돌 1개를 가져갑니다.

필승 수 계산 예시 (빌드 시 계산)

예를 들어 3, 4, 5는 011 XOR 100 XOR 101 = 010(2)입니다. 3 XOR 2 = 1이 3보다 작으므로 첫 번째 무더기에서 2개를 가져가 1, 4, 5로 만들면 님 합이 0이 됩니다. 4 XOR 2 = 6, 5 XOR 2 = 7은 원래 개수보다 커서 쓸 수 없으므로 이 위치의 이기는 수는 하나뿐입니다.

이 페이지에서 사람이 이길 확률

사람이 항상 먼저 두므로, 시작 위치의 님 합이 0이 아니면 이길 수 있는 위치입니다. 무더기 수(3 또는 4)와 개수(1~7)를 모두 대입해 센 결과는 다음과 같습니다.

3개 무더기와 4개 무더기가 반반이므로, 시작부터 불리한 위치(님 합 0)일 확률은 약 12.4%이고 나머지 약 87.6%는 사람이 이길 수 있는 위치입니다. 이 페이지의 컴퓨터는 님 합이 0이 아닌 위치를 만나면 언제나 최적의 수를 두므로, 시작이 유리해도 한 번이라도 잘못 두면 컴퓨터가 바로 역전해 끝까지 이깁니다. 반대로 시작부터 님 합이 0이면 사람이 어떤 수를 두어도 컴퓨터가 다시 0으로 되돌리므로 이길 길이 없습니다. 이기려면 정확한 계산이 필요합니다.

참고로 3개 무더기에서 님 합이 0인 조합(순서 무시)은 아래 7가지뿐입니다. 이 배치는 선공이 이길 수 없는 모양이므로 외워 두면 판세를 빨리 읽을 수 있습니다.

손으로 계산하는 요령과 흔한 실수

• 마지막 단계 감각: 무더기가 두 개 남았다면 개수가 같을 때 선공이 집니다(님 합 0). 많은 쪽을 적은 쪽과 같게 줄이는 것이 이기는 수입니다.
• 1개 무더기만 남기는 실수: 막판에 크기 1짜리 무더기가 홀수 개만 남고 큰 무더기가 없는 위치(예: 1, 1, 1)는 1개씩 번갈아 가져가는 게임이 되어 홀수 개면 선공이 이깁니다. 님 합으로 확인하면 1 XOR 1 XOR 1 = 1이라 선공이 유리하다는 결과와 일치합니다.
• 이진수 자리 맞춤: 7은 111, 5는 101처럼 3자리면 충분하므로 항상 3자리로 맞춰 쓰면 계산 실수가 줄어듭니다.
• "많이 가져가는 쪽이 유리"라는 오해: 님은 개수가 많은 쪽이 아니라 님 합이 중요한 게임입니다. 큰 무더기를 통째로 가져가는 수는 대개 님 합을 0으로 만들지 못합니다.

힌트 기능 사용법

힌트 보기를 누르면 현재 무더기의 님 합을 보여 주고, 이기는 수가 있으면 해당 무더기의 가져갈 돌을 강조 표시합니다(실제로 돌을 제거하지는 않습니다). 님 합이 0이라 이기는 수가 없을 때는 돌 1개를 가져가며 컴퓨터가 실수하기를 기다리는 수밖에 없다고 안내하는데, 이 페이지의 컴퓨터는 이길 수 있는 위치에서는 실수하지 않으므로 사실상 승부가 정해진 판입니다. 연습할 때는 먼저 직접 계산한 뒤 힌트로 확인해 보세요.

님 게임의 기원과 역사 (위키백과 기준)

님은 중국의 "돌 줍기(jiǎn-shízǐ)" 놀이와 닮은 것으로 거론되며, 유럽에서 확인되는 가장 이른 언급은 16세기 초로 정리됩니다. "Nim"이라는 이름과 완전한 이론은 1901년 하버드의 찰스 L. 바우턴(Charles L. Bouton)이 붙이고 정리했습니다. 이름의 유래는 독일어 "nimm(가져가라)"에서 왔다는 설명이 옥스퍼드 영어 사전에 있지만, 확실히 밝혀지지는 않았다고 합니다.

실제 사례: 님을 두는 기계들

사례 1. 1940년 뉴욕 세계박람회의 님 기계

웨스팅하우스가 전시한 "니마트론(Nimatron)"은 님을 두는 기계로, 1940년 5월 11일부터 10월 27일까지 박람회에서 관람객과 대결했습니다. 이긴 사람은 드물었고, 이긴 사람에게는 "Nim Champ"라고 적힌 동전을 주었다고 합니다. 이 기계는 전문가 지식을 규칙으로 담아 사람과 겨루게 한 초기 사례입니다. 님이 계산으로 완전히 풀리는 게임이라 기계가 이기기 쉬웠다는 점이 배울 점입니다. 개발자 이름은 확인하지 못해 쓰지 않았습니다.

사례 2. 1951년 영국 페스티벌의 님로드

1951년 영국 페스티벌(Festival of Britain)에서는 페란티(Ferranti)가 만든 님 전용 컴퓨터 "님로드(Nimrod)"가 전시되었습니다. 이듬해인 1952년에는 W. L. 맥슨 사(Maxson Corporation)의 기술자들이 23kg짜리 님 기계를 만들었는데, 사람 상대를 자주 이겼다고 합니다. 모두 관객이 직접 수를 두며 "기계와 승부한다"는 경험을 준 초기 전시였다는 점에서 의미가 있습니다.

사례 3. 영화 속의 님

1961년 프랑스 누벨바그 영화 「지난해 마리앙바드에서」에는 님의 한 변형이 등장합니다. 영화에서의 규칙은 이 페이지와 다를 수 있으므로, 영화 속 장면을 이 글의 필승법에 그대로 대입하지는 마세요.

가상 예시: 3, 4, 5로 시작하는 한 판

아래는 이해를 돕기 위한 가상 예시이며 실제 대국 기록이 아닙니다. 무더기가 3, 4, 5개이고 내가 먼저 둡니다. 님 합은 2이므로 첫 무더기에서 2개를 가져가 1, 4, 5(님 합 0)를 만듭니다. 상대가 세 번째 무더기에서 3개를 가져가 1, 4, 2가 되면 님 합은 7이므로 두 번째 무더기에서 1개를 가져가 1, 3, 2(님 합 0)로 되돌립니다. 상대가 세 번째 무더기에서 2개를 가져가 1, 3, 0이 되면 님 합이 2이므로 두 번째 무더기에서 2개를 가져가 1, 1, 0으로 만들고, 상대가 1개를 가져가면 마지막 1개를 가져가 이깁니다.

흔한 오해와 정정

• 오해: 마지막 돌을 가져가면 진다. 실제: 두 규칙이 모두 쓰입니다. 위키백과는 님이 흔히 미제르(마지막을 가져가면 패)로 설명되기도 한다고 정리합니다. 이 페이지는 마지막을 가져가는 쪽이 이깁니다.
• 오해: 선공이 항상 유리하다. 실제: 시작 님 합이 0이면 선공이 집니다.
• 오해: 돌이 많은 무더기를 줄이면 유리하다. 실제: 판단 기준은 개수가 아니라 님 합입니다.
• 오해: XOR 계산을 모르면 이길 수 없다. 실제: 직접 계산하지 않아도 상대가 실수하면 이길 수 있습니다. 다만 이 페이지의 컴퓨터는 이길 수 있는 위치에서는 실수하지 않습니다.

한계와 변형

• 이 페이지는 "마지막 돌을 가져가는 사람이 승리"하는 일반 규칙만 구현합니다. 마지막 돌을 가져가면 지는 규칙(미제르)은 막판 전략이 달라지며 여기서는 지원하지 않습니다.
• 무더기 개수와 크기가 작아 컴퓨터가 매번 완벽하게 둘 수 있게 만든 연습용 설정입니다. 무한한 크기의 문제나 실제 게임 이론 논문의 결과를 대표하지 않습니다.
• 컴퓨터의 난이도를 조절하는 기능은 없습니다.

자주 묻는 질문

함께 해 볼 만한 게임

규칙이 단순한 또 다른 전략 게임으로는 틱택토와 오목이 있고, 재귀적으로 최소 이동 횟수를 구하는하노이의 탑, 힌트로 코드를 추리하는 컬러 코드 추리 게임도 이어서 해 보세요.