님 (게임)

3. 게임 규칙

님 게임은 여러 개의 돌 무더기를 놓고 두 명의 플레이어가 번갈아 가며 돌을 가져가는 방식으로 진행된다. 각 플레이어는 자신의 차례에 하나 이상의 돌을 가져가야 하며, 한 번에 하나의 무더기에서만 돌을 가져갈 수 있다.^[2] 마지막 돌을 가져가는 플레이어가 승리하는 규칙을 '정규형(Normal Play)'이라고 하며, 마지막 돌을 가져가는 플레이어가 패배하는 규칙을 '역형(Misère Play)'이라고 한다.^[18]

다음은 밥과 앨리스가 3개, 4개, 5개의 돌로 시작하는 정규형 게임을 진행하는 예시다.

님 게임에서 이기기 위한 전략은 상대방을 특정 위치로 몰아넣는 것이다. 아래 표는 일반형과 미제르형에서 중요한 위치를 나타낸다.

3. 1. 변형 규칙

• 뺄셈 게임: 한 번에 가져갈 수 있는 돌의 개수를 제한한다. (예: 한 번에 1, 2, 3개의 돌)
• 21 게임: 여러 명이 차례로 숫자를 말하고, 21을 말하면 진다. 4의 배수를 말하는 것이 승리 전략.
• 100 게임: 두 명이 번갈아 숫자를 더해 100을 만들면 이긴다. 자릿수가 연속적인 숫자(01, 12, 23, 34...)에 도달하는 것이 승리 전략.
• 여러 무더기 규칙: 한 무더기 외에 각 무더기에서 동일한 수의 돌을 제거 가능.
• 원형 님(Circular Nim): 원형으로 배치된 돌 중 인접한 돌을 1, 2, 3개 제거.
• 그런디 게임: 하나의 무더기를 크기가 다른 두 개의 무더기로 나눈다.
• 탐욕 님(Greedy Nim): 가장 큰 무더기에서만 돌을 선택.^[10]
• 인덱스-k 님(Index-k Nim): 최대 k개의 서로 다른 무더기에서 돌 제거.^[12]
• 님 만들기(Building Nim): 두 플레이어가 님 게임을 구성 후 진행.^[13]
• 고차원 님(Higher-dimensional Nim): 다차원 보드에서 연속된 조각 제거.^[14]
• 그래프 님(Graph Nim): 그래프에서 인접한 정점 제거.^[15]
• 캔디 님(Candy Nim): 마지막 물건과 최대 개수의 캔디를 가져가는 것이 목표.^[16]

4. 필승 전략

님 게임의 필승 전략은 각 무더기에 있는 돌의 개수를 이진수로 표현하고, 이진수 각 자리의 숫자를 XOR (배타적 논리합, 님-합) 연산하여 결정된다. 정규형에서는 님-합이 0이 아닌 경우 첫 번째 플레이어가 필승하고, 님-합이 0인 경우 두 번째 플레이어가 필승한다.

일반적인 게임에서 승리하는 전략은 모든 힙의 님-합을 0으로 만드는 것이다. 만약 님-합이 0이 아니라면, 항상 0으로 만들 수 있다. 님-합이 이미 0이라면, 상대방이 실수하지 않는 이상 다음 플레이어는 패배한다.

어떤 돌을 가져와야 할지 결정하기 위해서는, 모든 힙 크기의 님-합을 계산한다. 이 값을 X라고 하자. 그런 다음 X와 각 힙 크기의 님-합을 계산하여, 그 결과가 원래 힙 크기보다 작은 힙을 찾는다. 승리하는 수는 그 힙에서 돌을 가져와서, 힙의 크기를 원래 크기와 X의 님-합으로 줄이는 것이다.

예를 들어, 힙의 크기가 각각 3, 4, 5라고 하면, 님-합은 다음과 같이 계산된다.

• 3 = 011₂
• 4 = 100₂
• 5 = 101₂
• 님-합 (X) = 010₂ = 2₁₀

• 3 ⊕ 2 = 1
• 4 ⊕ 2 = 6
• 5 ⊕ 2 = 7

4. 1. 님-합 (Nim-Sum)

• 0 XOR 0 = 0
• 0 XOR 1 = 1
• 1 XOR 0 = 1
• 1 XOR 1 = 0

암산하기 더 쉬운 등가 절차는 힙 크기를 2의 서로 다른 지수의 합으로 표현하고, 동일한 거듭제곱 쌍을 취소한 다음 남은 것을 더하는 것이다.

3 = 0 + 2 + 1 = 2 1 힙 A

4 = 4 + 0 + 0 = 4 힙 B

5 = 4 + 0 + 1 = 4 1 힙 C

• -------------------------------------------------------------------

5. 수학적 이론

님 게임은 스프라그-그런디 정리의 핵심적인 예시이며, 이 정리는 모든 불편 게임이 님 게임의 님-합과 동등하다는 것을 보여준다.^[9] 님 게임은 유한한 초기 힙과 개수에 대해 수학적으로 해결된 게임이며, 어떤 플레이어가 이길지, 그리고 어떤 승리 수가 있는지 쉽게 계산할 수 있다.^[9] 님 게임은 포셋 게임의 특수한 경우이며, 세 개의 힙을 가진 님 게임의 진화 그래프는 울람-워버튼 오토마톤의 진화 그래프와 관련이 있다.^[9]

게임 이론의 핵심은 힙 크기의 이진 디지털 합(비트 연산 XOR 또는 GF(2)에서의 벡터 덧셈, 조합 게임 이론에서는 '님-합')이다. ''x''와 ''y''의 님-합은 ''x'' ⊕ ''y''로 표기한다. 예를 들어 크기가 3, 4, 5인 힙의 님-합은 다음과 같이 계산한다.

다른 계산법으로는 힙 크기를 2의 서로 다른 지수의 합으로 표현하고, 동일한 거듭제곱 쌍을 취소한 다음 남은 것을 더하는 방법이 있다.

일반 플레이에서 승리 전략은 모든 수의 님-합을 0으로 만드는 것이다. 님-합이 0이면 상대방이 실수하지 않는 한 다음 플레이어가 진다. 승리하는 수는 X를 모든 힙 크기의 님-합이라 할 때, X와 힙 크기의 님-합이 힙 크기보다 작은 힙을 찾아, 그 힙을 원래 크기와 X의 님-합으로 줄이는 것이다.

힙이 두 개만 남으면 더 큰 힙의 개체를 줄여 힙을 같게 만드는 것이 전략이다. 그러면 상대방이 어떤 수를 두든, 플레이어는 다른 힙에 동일한 수를 두어 마지막 개체를 가져갈 수 있다.

미제르 게임으로 플레이할 때, 님 전략은 일반 플레이 수가 크기가 1인 힙만 남을 경우에만 다르다. 이 경우, 올바른 수는 크기가 1인 힙을 홀수 개로 남기는 것이다.

크기가 3, 4, 5인 힙을 가진 미제르 게임에서 전략 적용 예시는 다음과 같다.

참조

_[1] 논문 Context and driving forces in the development of the early computer game Nimbi http://muse.jhu.edu/[...]
_[2] 서적 Kvant Selecta: Combinatorics, I, Volume 1 https://books.google[...] American Mathematical Society
_[3] 논문 Nim, ''a game with a complete mathematical theory''
_[4] 서적 The Art of Clear Thinking Harper and Brothers Publishers
_[5] 웹사이트 The Nimatron https://daily.jstor.[...] 2022-03-01
_[6] 뉴스 The Talk of the Town – It http://www.newyorker[...] 1952-08-02
_[7] 웹사이트 How to Construct NIM Playing Machine http://harveycohen.n[...]
_[8] 논문 Games and game structures in Robbe-Grillet
_[9] arXiv Nim Fractals
_[10] 서적 Winning Ways for your Mathematical Plays A K Peters Ltd
_[11] 간행물 Nim Restrictions http://www.emis.de/j[...]
_[12] 논문 A Generalization of the Game Called Nim https://www.jstor.or[...] Annals of Mathematics 1910
_[13] arXiv Building Nim
_[14] 웹사이트 1021 - 2D-Nim http://poj.org/probl[...] Poj.org 2019-01-09
_[15] 논문 The Game of Nim on Graphs https://library.ndsu[...] 2011
_[16] arXiv P Play in Candy Nim 2018-05-18
_[17] 웹사이트 The History of Combinatorial Game Theory http://www.mathstat.[...] Dalhousie University 2009-01-24
_[18] 웹사이트 組み合わせゲームとゲーム木について https://dev.classmet[...] クラスメソッド株式会社 2018-03-23
_[19] 웹사이트 石取りゲーム(Nim) [いかたこのたこつぼ] https://ikatakos.com[...]