티스토리 뷰

공부

Nim game

전명우 2013. 7. 29. 20:42

님 게임(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$ 이면 처음 시작한 사람이 무조건 이긴다.

'공부' 카테고리의 다른 글

Suffix Array와 LCP  (14) 2014.08.14
Manacher's Algorithm  (0) 2014.08.13
중국인의 나머지 정리와 확장 유클리드 알고리즘  (0) 2014.07.25
고속 푸리에 변환 (Fast Fourier Theorem, FFT)  (5) 2014.07.25
포함-배제의 원리  (0) 2014.07.20
Nim game  (5) 2013.07.29
댓글
  • 프로필사진 pce913 엄청납니다 정말. 감사합니다. 2017.10.28 22:53
  • 프로필사진 hgmhc 이 증명은 결국 수학적 귀납법이라고 말할 수 있는데,
    x의 상태가 귀납 n=k가정, x’의 상태가 귀납 n=k+1 증명과 대응되잖아요?
    그러면 초항에 대해 조건이 성립하는지가 보여져야 하는데 그렇지 않은 것 같아서 질문합니다!
    2020.10.15 20:01 신고
  • 프로필사진 hgmhc 인터넷 다 뒤져도 초항에 관한 얘기는 없더라고요ㅠ 2020.10.15 20:02 신고
  • 프로필사진 전명우 음.. 이 증명을 수학적 귀납법이라고 생각하시는 이유가 뭔가요? 적힌 글을 다 읽어봤을 때 보충해야 되는 내용은 없는 것 같습니다. 2020.10.16 14:40 신고
  • 프로필사진 hgmhc 혼자 미궁에 빠졌던 거네요...
    좋은 정보 감사합니다!
    2020.10.28 23:05 신고
댓글쓰기 폼