Nim game

님 게임(Nim game)은 수학적 전략 게임이다. 여러 개의 돌 무더기가 있다. 두 사람이 서로 차례를 번갈아가면서 게임한다. 자신의 차례에 하나의 돌 무더기를 선택하여 1개이상 원하는 만큼의 돌을 제거할 수 있다. 마지막 남은 돌을 제거하는 사람이 게임에서 승리한다.

님 게임에 대한 이해를 돕기 위한 플래시 게임이 있다. http://www.gamedesign.jp/flash/nim/nim.html

님 게임에는 수학적 필승 전략이 있다. 중,고등학교 수준의 KOI, IOI에서는 님 게임 관련 문제가 안나온다. 그렇다고해서 이해하기 어려운건 전혀 아니다. 그 전략은 간단하며, 아래와 같다.

자기 차례에 각 돌 무더기에 있는 돌의 개수를 XOR($\oplus$) 연산 했을 때 값을 0으로 만들어주면 이긴다.

위 전략이 필승 전략임을 증명하겠다. 다음 두 가지 lemma가 맞음이 증명되어야한다. 편의상 각 돌 무더기에 있는 돌의 개수를 XOR한 값을 $x$ 라 하자.

• Lemma 1. $x=0$ 일 때, 다음 차례는 무조건 $x' \neq 0$ 이 된다.
  
  자기 차례 일 때 $x=0$ 이며, 돌을 제거하기 위해 임의의 돌 무더기를 선택했다고 하자. 이 돌 무더기를 제외한 다른 돌 무더기들의 돌 개수를 XOR한 것을 $\chi$ 이라 하고 선택된 돌 무더기의 돌 개수를 $c$라 하자. ($단, c > 0$) 이 때, $c \oplus \chi = 0$ 이다. 돌 무더기를 정하고 1개 이상의 돌을 제거해야만 한다. 따라서 $c$ 값이 $c'$으로 변하게 된다. 그러므로 다음 차례의 $x' = c' \oplus \chi \neq 0$ 이다.
  
  따라서, $x=0$ 일 때, 다음 차레에는 무조건 $x' \neq 0$ 이 된다. 증명 끝.
  
  
• Lemma 2. $x \neq 0$ 일 때, $x'=0$으로 항상 만들어 줄 수 있다.
  
  $x$ 를 2진법으로 표현했을 때 가장 큰 1비트 $\beta$가 존재한다. 또, 돌 무더기 중에서 돌의 개수의 $\beta$가 1인 돌 무더기도 항상 존재한다. 돌을 제거하기 위해 그 돌 무더기를 선택하자. $x'=0$으로 만들기 위해서 $\beta$ 는 무조건 0이 되어야한다. $\beta$를 0으로 만들면 $\beta$ 보다 작은 비트들의 값은 $0$ 부터 $2^{\beta}-1$까지 모두 만들어 줄 수 있다.
  
  이해를 돕기 위해 예를 들어 보겠다. $x=00101100_{(2)}$ 라고 하자. 가장 큰 1비트는 3번째 비트가 된다. $x=00101100_{(2)}$ 이기 때문에, 돌 무더기들 중 돌의 개수의 3번째 비트가 1인 것이 항상 존재한다. 돌을 제거하기 위해 그 돌 무더기를 선택하자. 선택한 돌 무더기의 돌 개수 3번째 비트를 0으로 만든다. 그리고 $x$를 살펴보면 $x=00001100_{(2)}$ 이 될 것이다. 선택한 돌 무더기의 돌 개수 3번째 비트를 0으로 만들어 줌으로써 4번째 이후 모든 비트를 마음대로 바꿀 수 있게 된다. 따라서 선택한 돌 무더기에서 특정 수 만큼의 돌을 제거함으로써 항상 $x'=0$으로 만들어 줄 수 있다.
  
  증명 끝.
  
  
• Fact. 자기 차례일 때 항상 $x=0$ 이면 게임에서 지게 된다.
  
  전체 돌의 개수는 차례가 지남에 따라 항상 감소하게 되어 결국 돌이 남아있지 않게 된다. 돌이 하나도 남지 않은 상황이 자기 차례에 오면 자신이 지게 되는데, 그 상황은 $x=0$이다. 따라서 매 자신의 차례 때 $x=0$ 이면 결국 게임에서 지게된다.

앞서 설명한 모든 것을 다음과 같이 깔끔하게 정리할 수 있다. 두 플레이어가 최적의 전략을 알고 있다고 했을 때, 초기 상태가 $x=0$이면 처음 시작한 사람은 절대 이길 수 없고, 반대로 초기 상태가 $x \neq 0$ 이면 처음 시작한 사람이 무조건 이긴다.