게임 이론 (Game Theory)

정의

게임 이론 (Game Theory) 은 둘 이상의 플레이어가 정해진 규칙 아래 의사 결정을 내리는 상황을 수학적으로 모델링하는 분야. PS에서는 두 명이 완벽한 플레이를 할 때 승자를 결정하는 조합 게임(combinatorial game)에 집중한다.

문제 상황과 동기

두 플레이어가 번갈아 행동하며, 마지막 행동을 하는 사람이 이기거나(정상 게임) 지는(미저리 게임) 규칙의 게임.

• naive: 가능한 모든 게임 트리 전개. 상태 수가 기하급수적.
• DP + Nim-XOR: 상태가 작으면 win/loss DP O(N), 돌무더기가 여러 개면 Nim XOR O(N) 로 승패 결정.

핵심 통찰: Impartial game (두 플레이어의 행동이 동일) 은 모두 Nim-heap 하나로 환원 가능 (Sprague-Grundy 정리).

시각화

핵심 아이디어

Win/Loss 상태

• Winning state (W): 현재 턴인 플레이어가 이길 수 있는 상태.
• Losing state (L): 현재 턴인 플레이어가 무조건 지는 상태.

점화식:

dp[i] = (i번째 상태에서 이기는가?)
dp[i] = true if ∃move to dp[j] = false  (W = 갈 수 있는 L이 존재)
dp[i] = false if all moves go to dp[j] = true (L = 모든 행선지가 W)

Nim 게임

돌무더기 여러 개. 각 더미에서 1개 이상 제거 가능. 정상 규칙(마지막 돌 가져가는 사람 승).

Nim-XOR (Bouton): XOR sum = p1 xor p2 xor ... xor pk. XOR sum != 0 이면 선공 승, 0 이면 후공 승.

nim_win(piles):
    xor_sum = fold(xor, piles)
    return xor_sum != 0

Zero-Sum Game

한 플레이어의 이득이 다른 플레이어의 손실과 정확히 일치하는 게임. Minimax 원칙으로 최적 전략 계산.

알고리즘

# 돌 게임 (N개 돌, 1 or 3개 가져감)
win[0] = false
for i = 1..N:
    win[i] = false
    if i >= 1 and not win[i-1]: win[i] = true
    if i >= 3 and not win[i-3]: win[i] = true

# Nim XOR
xor = 0
for p in piles: xor ^= p
if xor != 0: First wins else Second wins

구현

// 돌 게임 (N, take 1 or 3) + Nim XOR
#include <bits/stdc++.h>
using namespace std;
​
int main() {
  // 1. 돌 게임 DP (N <= 1000)
  int N; cin >> N;
  vector<bool> win(N + 1, false);
  for (int i = 1; i <= N; i++) {
      if (i >= 1 && !win[i-1]) win[i] = true;
      if (i >= 3 && !win[i-3]) win[i] = true;
  }
  cout << "Stone game winner: "
       << (win[N] ? "SK" : "CY") << "\n";
​
  // 2. Nim XOR
  int k; cin >> k;
  long long xsum = 0;
  for (int i = 0; i < k; i++) {
      long long p; cin >> p;
      xsum ^= p;
  }
  cout << "Nim winner: "
       << (xsum ? "koosaga" : "cubelover") << "\n";
  return 0;
}

# 돌 게임 DP + Nim XOR
import sys
input = sys.stdin.readline
​
N = int(input())
win = [False] * (N + 1)
for i in range(1, N + 1):
  if (i >= 1 and not win[i-1]) or (i >= 3 and not win[i-3]):
      win[i] = True
print("SK" if win[N] else "CY")
​
k = int(input())
piles = list(map(int, input().split()))
xsum = 0
for p in piles:
  xsum ^= p
print("koosaga" if xsum else "cubelover")

import java.util.*;
import java.io.*;
​
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(br.readLine());
      boolean[] win = new boolean[N + 1];
      for (int i = 1; i <= N; i++) {
          if ((i >= 1 && !win[i-1]) || (i >= 3 && !win[i-3]))
              win[i] = true;
      }
      System.out.println(win[N] ? "SK" : "CY");
​
      int k = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      long xsum = 0;
      for (int i = 0; i < k; i++)
          xsum ^= Long.parseLong(st.nextToken());
      System.out.println(xsum != 0 ? "koosaga" : "cubelover");
  }
}

5
2
3 7

Stone game winner: SK
Nim winner: cubelover

1000
4
1 2 3 4

Stone game winner: CY
Nim winner: koosaga

복잡도

변형 / 활용

게임 패밀리

응용

• 최적 전략 게임 (Minimax): 제로섬 게임에서 최적 행동.
• 게임 트리 + DP: 상태 공간이 작으면 완전 탐색 DP 로 족보 판정.

함정

1. XOR 이해 오류

XOR sum 이 0 이면 선공 패, != 0 이면 선공 승. misere 에서는 예외 (모든 더미가 1 이하일 때 반대).

2. 상태 정의 누락

DP 정의 시 “현재 턴인 플레이어 기준” 임을 명확히. 실제 판정과 반대로 정의하는 실수.

3. 큰 N / 큰 P

돌 개수가 10^12 면 DP 불가. 패턴 찾아 O(1) 또는 SG 주기성 활용.

BOJ 연습 문제

참고

• 스프라그-그런디 정리
• 다이나믹 프로그래밍