Scoring Nim

이 논문은 노말 플레이와 미스레 플레이 규칙을 모두 일반화하는 새로운 점수 기반 님 게임 변형을 제안하고, 최적 전략과 보수 함수와 같은 이론적 속성을 분석합니다.

핵심

점수형 님 (Scoring Nim): 마지막 돌을 누가 가져갈까?

이 논문은 고전적인 보드게임인 **'님 (Nim)'**을 바탕으로, 훨씬 더 흥미롭고 복잡한 새로운 게임을 제안합니다. 제목은 **'점수형 님 (Scoring Nim)'**입니다.

기존의 님 게임이 "누가 마지막 돌을 가져가느냐"에 따라 승패가 결정되었다면, 이 새로운 게임은 **"누가 더 많은 점수를 얻느냐"**가 핵심입니다. 마치 체스나 바둑에서 단순히 상대를 잡는 것뿐만 아니라, 얼마나 많은 territory(영토) 를 차지했는지도 중요해지는 것과 비슷합니다.

이 논문의 내용을 일반인이 쉽게 이해할 수 있도록 비유와 함께 설명해 드리겠습니다.

---

1. 게임의 규칙: "돌을 주우면 1 점, 마지막 돌은 보너스!"

상상해 보세요. 여러 개의 바구니에 돌들이 담겨 있습니다. 두 명의 플레이어가 번갈아 가며 바구니 중 하나를 골라 돌을 몇 개든 가져갑니다.

• 기본 점수: 돌 1 개를 가져갈 때마다 1 점을 얻습니다.
• 보너스 점수 (N): 게임의 마지막 돌을 가져가는 사람에게 보너스 점수 N이 주어집니다.

여기서 N이라는 숫자가 게임의 성격을 완전히 바꿉니다. N 은 미리 정해진 숫자이며, 양수일 수도, 음수일 수도, 심지어 무한대일 수도 있습니다.

• N 이 매우 큰 양수 (∞) 일 때: 마지막 돌을 가져가는 것이 천문학적인 보너스입니다. 이는 기존의 "정상 규칙 (Normal Play)" 님 게임과 같습니다. "무조건 마지막 돌을 가져가야 이긴다!"는 전략이 통합니다.
• N 이 매우 큰 음수 (-∞) 일 때: 마지막 돌을 가져가는 것은 치명적인 벌점입니다. 이는 "미스레 규칙 (Misere Play)" 님 게임과 같습니다. "상대방이 마지막 돌을 가져가게끔 유도해야 이긴다!"는 전략이 필요합니다.
• N 이 0 일 때: 보너스도 벌점도 없습니다. 단순히 **"돌을 많이 가져가는 사람"**이 이깁니다. 이때는 전략이 단순해져서, 가능한 한 많은 돌을 한 번에 가져가는 '탐욕스러운 (Greedy)' 전략이 최선이 됩니다.

핵심 아이디어: 이 게임은 N 의 값에 따라 승리의 기준이 연속적으로 변한다는 점입니다. N 이 0 에서 100 으로 변하는 동안, 최적의 전략도 서서히, 혹은 급격하게 바뀌게 됩니다.

---

2. 전략의 변화: "나침반이 흔들리는 게임"

논문의 가장 재미있는 부분은 N 의 값에 따라 최적의 수 (Move) 가 어떻게 달라지는지를 분석한 것입니다.

비유를 들어보자면, N 의 값은 게임의 나침반과 같습니다.

• 나침반이 북쪽 (큰 양수) 을 가리킬 때는 "마지막 돌을 쫓아라!"
• 나침반이 남쪽 (큰 음수) 을 가리킬 때는 "마지막 돌을 피하라!"
• 나침반이 동쪽 (0) 을 가리킬 때는 "돌을 많이 먹어라!"

하지만 문제는 나침반이 북동쪽 (중간 값) 을 가리킬 때입니다. 이때는 "마지막 돌을 쫓기도 하고, 피하기도 하고, 돌을 많이 먹기도 하는" 복잡한 전략이 필요합니다.

예시:
바구니에 (5, 4, 2) 개의 돌이 있다고 칩시다.

• N 이 매우 작을 때: 상대방이 마지막 돌을 가져가게 하려면, 내가 (5, 4, 1) 로 만드는 것이 좋습니다.
• N 이 0 일 때: 내가 (0, 4, 2) 로 만들어서 가능한 한 많은 돌을 가져가는 것이 좋습니다.
• N 이 중간 값 (예: 3) 일 때: 위의 두 전략 모두 최선이 아닙니다. 상대방을 혼란스럽게 하거나, 상대방이 특정 위치로 가게 만드는 중간 전략을 써야 합니다.

논문에 따르면, N 의 값이 조금만 변해도 최적의 첫 수 (First Move) 가 완전히 바뀔 수 있습니다. 마치 N 이라는 '스위치'를 누를 때마다 게임의 지형이 바뀌는 것과 같습니다.

---

3. 수학적 발견: "점프하는 그래프"

연구자들은 이 게임의 점수 차이를 계산하는 함수 (Payoff Function) 를 분석했습니다. 이 함수는 N 에 따라 어떻게 변하는지 보여주는 그래프입니다.

• 매끄러운 곡선이 아닙니다: 이 그래프는 직선들이 꺾여 있는 '계단'이나 '톱니' 모양과 비슷합니다.
• 브레이크 포인트 (Breakpoints): N 의 값이 특정 숫자에 도달하면, 그래프의 기울기가 갑자기 변합니다. 이를 '브레이크 포인트'라고 합니다.
• 돌의 개수가 많아질수록 복잡해짐: 바구니에 있는 돌의 개수가 조금만 늘어나도, 이 브레이크 포인트의 수가 기하급수적으로 늘어납니다. 즉, 게임이 복잡해질수록 최적의 전략을 찾기 위해 고려해야 하는 'N 의 구간'이 훨씬 더 세분화됩니다.

연구자들은 3 개의 바구니가 있는 경우, 특히 마지막 바구니에 돌이 1 개만 남을 때의 전략을 완벽하게 해독했습니다. 그들은 N 의 값에 따라 플레이어가 어떤 돌을 몇 개 남겨야 하는지 정교한 공식을 찾아냈습니다.

---

4. 왜 이 게임이 중요한가요?

이 게임은 단순한 유희를 넘어 수학적 구조의 아름다움을 보여줍니다.

1. 연속성과 불연속성: N 이 연속적으로 변하는데, 최적의 전략은 갑자기 뚝뚝 끊어져서 바뀝니다. 이는 수학적으로 매우 흥미로운 현상입니다.
2. 전략의 유연성: "무조건 이기는 법"이 하나만 있는 게 아니라, 상황 (N 의 값) 에 따라 "이기는 법"이 여러 가지로 바뀐다는 것을 보여줍니다.
3. 실생활의 비유: 이는 비즈니스나 정치에서도 통할 수 있습니다. "상대방을 완전히 무너뜨리는 것 (N=∞)"이 최선일 때도 있고, "자신의 이익을 극대화하는 것 (N=0)"이 최선일 때도 있으며, 그 사이에는 복잡한 협상과 전략이 필요한 경우가 많습니다.

요약

이 논문은 **"마지막 돌을 누가 가져가는지"**가 아니라 **"누가 더 많은 점수를 얻는지"**가 중요한 새로운 님 게임을 소개합니다.

• **보너스 점수 (N)**가 게임의 규칙을 바꿉니다.
• N 의 값에 따라 최적의 전략이 북쪽, 남쪽, 동쪽으로 끊임없이 이동합니다.
• 이 게임은 수학적 그래프로 표현할 때 매우 복잡하고 아름다운 패턴을 만들어냅니다.

결론적으로, 점수형 님은 "누가 이기는가"를 넘어서 "어떻게 이기는가"가 상황에 따라 얼마나 유연하고 복잡하게 변할 수 있는지를 보여주는, 매우 매력적인 수학적 놀이터입니다.

기술 요약

논문 요약: Scoring Nim (점수형 님 게임)

1. 문제 제기 (Problem)
기존의 조합 게임 이론에서 가장 유명한 게임인 '님 (Nim)'은 두 플레이어가 번갈아 가며 돌을 제거하는 게임입니다. 전통적인 님 게임은 승리 조건에 따라 두 가지 규칙으로 나뉩니다.

• 정규 플레이 (Normal Play): 마지막 돌을 가져간 플레이어가 승리합니다.
• 미스레 플레이 (Misère Play): 마지막 돌을 가져간 플레이어가 패배합니다.

그러나 기존 규칙은 승패 여부만 결정할 뿐, 플레이어가 획득한 총 점수 (돌의 개수) 에 대한 고려는 없습니다. 본 논문은 이러한 한계를 극복하고, 승패뿐만 아니라 획득한 점수 (돌의 개수) 를 최대화하려는 목표를 포함하는 새로운 변형 게임인 **'Scoring Nim'**을 제안합니다. 이 게임은 정규 플레이와 미스레 플레이를 특수한 경우로 포함하는 일반적인 형태를 취합니다.

2. 방법론 (Methodology)

• 게임 규칙 정의:
  • $n$개의 더미 (pile) 가 있고, 플레이어는 한 번에 하나의 더미에서 임의의 양의 수만큼 돌을 제거합니다.
  • 점수 시스템: 각 플레이어가 가져간 돌 1 개당 1 점씩 획득합니다.
  • 보너스/페널티: 마지막 돌을 가져가는 플레이어는 추가적으로 $N$점을 얻습니다. 여기서 $N$은 게임 시작 전 고정된 실수 (정수일 필요 없음) 입니다.
    • $N = \infty$: 정규 플레이 님과 동일.
    • $N = -\infty$: 미스레 플레이 님과 동일.
    • $N = 0$: 단순히 돌의 개수만 최대화하는 게임.
    • $N < 0$: 마지막 돌을 가져가는 것이 패널티가 됨.
• 수학적 모델링:
  • 페이오프 함수 (Payoff Function): $f_N(p)$를 1 번 플레이어의 최종 점수에서 2 번 플레이어의 최종 점수를 뺀 값으로 정의합니다. ($p$는 현재 게임 상태).
  • 점화식 (Recursion): 게임이 제로섬 (Zero-sum) 이며 총점의 합이 $|p| + N$으로 일정하므로, 미니맥스 (Minimax) 알고리즘을 적용하여 점화식을 유도했습니다.
    $$f_N(p) = \max_{p \to p'} \{ |p| - |p'| - f_N(p') \}$$
  • 분석 대상: 2 개의 더미, 3 개의 더미 (특히 최소 1 개의 돌이 있는 경우) 에 대한 명시적 공식을 유도하고, $N$의 값에 따른 최적 전략의 변화를 분석했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

• 2 더미 게임의 완전한 분석:

  • 두 더미 $(x, y)$의 경우, $N$의 값에 따라 최적 전략이 명확하게 결정됨을 증명했습니다.
  • $N \ge 0$일 때는 '그리디 (Greedy)' 전략 (큰 더미에서 모든 돌을 가져감) 이나 '님 승리 (Nim-winning)' 전략 (두 더미의 개수를 같게 만듦) 중 하나가 최적임을 보였습니다.
  • $f_N(x, y)$에 대한 명시적인 공식을 유도하여, $N$이 정수일 때와 실수일 때의 값을 모두 계산 가능하게 했습니다.

• 페이오프 함수의 일반적 성질:

  • $f_N(p)$는 $N$에 대해 연속이며, 기울기는 $\pm 1$인 조각별 선형 함수 (Piecewise linear function) 임을 증명했습니다.
  • $N$이 정수일 때의 값만 알면 선형 보간을 통해 모든 실수 $N$에 대한 값을 구할 수 있음을 보였습니다.
  • $|N|$이 매우 크면 게임이 정규 플레이 님 ($N \to \infty$) 또는 미스레 플레이 님 ($N \to -\infty$) 의 P-위치 (패배 위치) 집합에 의해 결정됨을 보였습니다.

• 3 더미 게임의 복잡성과 '브레이크 포인트' (Breakpoints):

  • 3 더미 게임, 특히 $(2k+1, 2k, 1)$ 형태의 위치에서 $N$에 따른 페이오프 함수 $F_k(N)$을 정의하고 분석했습니다.
  • 핵심 발견: $N$의 값이 중간 범위일 때, 최적 전략은 단순히 '그리디'나 '님 승리' 전략이 아닌, 상대방을 특정 위치로 유도하는 복잡한 전략을 취합니다.
  • 브레이크 포인트의 증가: $f_N(2k+1, 2k, 1)$ 함수는 $4k-3$개의 브레이크 포인트 (기울기가 변하는 지점) 를 가집니다. 이는 돌의 개수가 증가함에 따라 최적 전략이 변하는 지점 (N의 구간) 이 기하급수적으로 증가할 수 있음을 의미합니다.
  • 전략의 전환: $N$의 크기에 따라 플레이어가 마지막 돌을 가져갈지, 아니면 상대방이 마지막 돌을 가져가게 할지, 혹은 돌의 개수 자체를 최대화할지 결정하는 전략이 미세하게 변화합니다.

4. 의의 및 중요성 (Significance)

• 게임 이론의 확장: Scoring Nim은 기존에 이분법적이었던 승/패 중심의 게임 분석을, 점수 극대화 (Scoring Games) 로 확장한 중요한 사례입니다. 이는 조합 게임 이론에서 '점수 게임' 연구에 대한 구체적인 모델과 통찰을 제공합니다.
• 전략적 복잡성 규명: $N$이라는 하나의 매개변수 변화가 게임의 최적 전략을 어떻게 복잡하게 변화시키는지, 특히 중간 영역에서 기존 직관 (그리디 또는 님 전략) 이 무효화되는 현상을 수학적으로 규명했습니다.
• 실용적 가치: $N$이 음수, 0, 양수 등 다양한 값을 가질 때의 전략적 차이를 분석함으로써, 다양한 승리 조건을 가진 게임 설계나 알고리즘 연구에 기초 데이터를 제공합니다.
• 수학적 구조: 페이오프 함수가 $N$에 대해 연속이고 기울기가 제한된다는 성질은 계산 복잡성을 줄이고 효율적인 알고리즘 설계에 기여할 수 있습니다.

결론적으로, 본 논문은 Scoring Nim이라는 새로운 게임 변형을 제안하고, 이를 통해 돌의 개수와 마지막 돌 획득 보너스 ($N$) 간의 상호작용이 최적 전략에 미치는 영향을 체계적으로 분석했습니다. 특히 3 개 이상의 더미가 있는 경우, $N$의 값에 따라 최적 전략이 급격하게 변하는 복잡한 구조를 발견하고 이를 수학적으로 증명함으로써 조합 게임 이론의 새로운 지평을 열었습니다.