[STAT155] Nim Game 정리

조합 게임(combinatorial games)이란, 두 명의 플레이어가 서로 차례를 번갈아가며 이동하여 승리 조건을 만족시키는 게임을 말합니다. 이 조합 게임은 크게 또 2가지로 나뉘는데, 불공정 게임(impartial game)과 partisan game으로 나눠볼 수 있습니다. 

Impartial game이란 두 플레이어가 모든 위치에서 동일한 선택지를 갖는 게임을 말합니다. Nim게임에서는 두 플레이어가 번갈아가면서 동일한 규칙에 따라 칩을 제거하죠.

Partisan game이란 두 플레이어가 각자 다른 법칙 혹은 선택지를 가진 경우의 게임을 말합니다. 게임의 규칙이나, 이동 가능성이 플레이어마다 다르게 설정된 거죠. Hex, 체스나 바둑이 이에 해당합니다. 

 

조합 게임의 impartial game의 대표적인 예시로, Nim 게임이 있습니다. 해당 포스팅에선 이 Nim게임에 대해 다루어보고자 합니다.

---

 

 

돌 빼기 게임과 같이 돌을 규칙에 따라 서로 번갈아가며 빼며, 마지막 돌을 가져가는 사람이 지게 되는 게임 을 Nim Game이라고 합니다. 규칙은 아래와 같습니다.

---

<규칙>
1. 돌은 몇개의 더미로 나뉘고 각각의 더미(piles)에 배열된다. (9, 10, 11, 12)
2. 플레이어가 먼저 시작해서 상대방과 번갈아가며 돌을 제거한다.
3. 돌은 한 줄내에서만 제거가 가능하며 최소 1개 이상, 최대로 한줄에 있는 돌 전부 제거할 수 있다.
4. 마지막 돌 1개를 가져가는 사람이 패배한다.

---

 

Nim 게임에서의 "position": 게임의 현재 상태를 나타냄.

n개의 줄에 돌이 각각 a1, a2, a3, a4씩 있을 때, (a1, a2, a3, a4)로 표현한다.

 

Next player: 현재 플레이어

 

Previous player: 상대방 플레이어

P-Position (Previous Position): 이 위치로 시작하면 반드시 패배하는 위치로, 어떤 위치를 취해도 상대방이 승리할 수 있는 위치가 존재하는 상태.

N-Position (Next Position): 이 위치로 시작하면 반드시 승리하는 위치로, 플레이어가 승리할 수 있는 위치가 존재하는 상태.

베타적 논리합(XOR): 비트간 베타적 논리합이란, 이진법의 수에서 표현하였을 때 수가 같으면 0 수가 다르면 1을 출력하는 연산기호로 기호로 ⊕를 씀.

Nim-Sum: Nim-game의 각 위치의 이진수 표현에서의 배타적 논리합을 Nim-Sum이라고 한다. 

즉, 각 더미 크기의 XOR 연산 결과를 나타냄,

 

nim-sum이 0이면 현재 상태는 P-Position(패배 상태) losing position

nim-sum이 0이 아니면 현재 상태는 N-Position(승리 상태) winning position

 

Terminal Point:  더 이상의 이동이 불가능한 게임 상태. 

 

Winning Move(최적의 첫 번째 수):

N-posiition에서 승리하기 위해서, 한 개의 더미를 골라 조작해서 nim-sum을 0으로 만들어야한다.

nim-sum이 0이 된 상태를 상대방에게 돌림으로써, 상대방은 뭘해도 패배 상태가 되는 것.

---

page32 연습문제 

 

 

 

(a)

마지막 칩을 제거하는 플레이어가 승리

각 더미의 크기를 이진수로 변환합시다.

9 = 1001 (이진) 10 = 1010 (이진) 11 = 1011 (이진) 12 = 1100 (이진)

XOR 계산을 단계적 적용시, 0100 (이진) = 4가 나온다.

해당 Nim-sum의 값은 0이 아니기에, N-position입니다. 결론적으로, Next player가 이기는 위치에 있습니다.

 

(b)

9,10,11,12의 더미들이 있는 상황에서, 플레이어는 턴당 최대 9개의 칩을 제거할 수 있다는 조건이 붙었습니다.

초기 상태에서, 현재 상태는 N-position인지, P-position인지를 묻고 있네요. (a)에서 우린 이미 nim-sum의 개념을 이용해서, 현재 상태가 N-position 상태라는걸 알고 있습니다. 달라지는건 없죠.

---

B.A. in Statistics at University of California, Berkeley

 

works cited:

https://gomgom-o-zz.tistory.com/5