한양과학기술고등학교

에듀테크 프로젝트 대시보드

님 게임 (Nim)

님(Nim) 은 두 사람이 번갈아 여러 돌 무더기 중 한 무더기에서 원하는 만큼(1개 이상) 돌을 가져가고, 마지막 돌을 가져가는 사람이 이기는 게임입니다. 놀랍게도 이 게임은 완전히 풀려 있습니다 — 각 무더기 크기를 모두 XOR 한 값(님 합, nim-sum)만 보면 누가 이길지 바로 알 수 있습니다.

🎮 님 게임 당신 차례

무더기의 돌을 클릭해 가져갈 만큼 선택한 뒤 가져가기를 누르세요. (한 번에 한 무더기에서만 가능)

돌을 클릭해 선택하세요.

// 게임 로그

🧮 님 합 (nim-sum) = 이진수 XOR

판정 규칙
· 님 합이 0 → 지금 둘 차례인 사람이 진다 (P-position, 필패)
· 님 합이 0이 아님 → 지금 둘 차례인 사람이 이긴다 (N-position, 필승)

필승 수 찾기
님 합 x 의 최상위 1비트 를 가진 무더기를 골라, 그 무더기를 a XOR x 개로 줄이면 님 합이 0이 됩니다.

🤔 왜 하필 XOR일까?

핵심은 두 가지 성질입니다.

① 님 합이 0이면 어떤 수를 둬도 0이 깨진다

한 무더기만 바뀌므로, 바뀐 무더기의 값이 달라지면 전체 XOR도 반드시 달라집니다. → 상대에게 0이 아닌 판을 넘기게 됨.

② 님 합이 0이 아니면 0으로 만드는 수가 존재한다

최상위 1비트를 가진 무더기는 a XOR x < a 이므로 그만큼 덜어내는 합법적인 수가 항상 있습니다.

③ 끝 판( 000…0 )

모든 돌이 사라진 상태는 님 합 0이고, 둘 차례인 사람은 둘 수가 없어 패배.

결국 "님 합 0" 상태를 상대에게 계속 떠넘기면 마지막엔 상대가 빈 판을 받습니다.

🐍 최적 수 계산

def nim_sum(piles): x = 0 for a in piles: x ^= a # 전체 XOR return x def best_move(piles): x = nim_sum(piles) if x == 0: return None # 필패 — 버티기만 for i, a in enumerate(piles): target = a ^ x if target < a: # 이만큼으로 줄이면 승리 return i, a - target

컴퓨터는 이 best_move 로 둡니다. 당신이 필승 상태(님 합≠0) 에서 정확한 수 를 두지 않으면, 컴퓨터가 즉시 주도권을 가져가 절대 지지 않습니다.

🧩 스프라그–그런디 정리

모든 "공정한(impartial) 조합 게임"은 하나의 님 무더기 와 동등합니다. 각 상태의 크기를 그런디 수(Grundy number, 님值)라 부릅니다.

g(s) = mex{ g(다음 상태들) }
mex = 그 집합에 없는 가장 작은 0 이상 정수.

여러 게임을 동시에 하면 각 그런디 수를 XOR — 님과 똑같습니다.

예: "한 무더기에서 1·2·3개만 가져가기" 게임의 그런디 수

돌 n	0	1	2	3	4	5	6	7
g(n)	0	1	2	3	0	1	2	3

g(n)=0 인 4의 배수 가 필패 위치.