Hackenbush (하켄부시 게임)

정의

Hackenbush 는 John H. Conway 가 “On Numbers and Games” (1976) 에서 고안한 combinatorial game. 바닥에 연결된 여러 개의 색깔 가지 (빨강/파랑) 가 있고, Left (파랑) 는 파란 가지를, Right (빨강) 는 빨간 가지를 자른다. 바닥과 연결이 끊긴 부분은 사라진다. 마지막으로 자를 수 있는 플레이어가 이긴다. 각 위치는 surreal number 로 값이 매겨진다.

문제 상황과 동기

combinatorial game theory 에서 위치의 “값”을 어떻게 정의할 것인가? Conway 는 Hackenbush 를 통해 surreal number 를 직관적으로 설명했다.

• naive 접근: minimax tree search. 위치 수가 기하급수적으로 증가.
• 핵심 통찰: Blue-Red Hackenbush 의 각 위치는 surreal number 하나와 대응. 파란 가지 = Left 에게 유리 (+), 빨간 가지 = Right 에게 유리 (-). 가지가 갈라지는 구조는 {L|R} 꼴 surreal number.
• 의의: 모든 partizan game 의 값을 측정하는 기준을 제공.

시각화

핵심 아이디어

Blue-Red Hackenbush 의 값은 각 edge 의 색과 구조로 결정:

• 파란 가지 하나: +1 (Left 에게 유리)
• 빨간 가지 하나: -1 (Right 에게 유리)
• chain 구조: 각 edge 의 값을 단순 합산. B-B-R = (+1) + (+1) + (-1) = +1.
• branching 구조: {L|R} 형식의 surreal number. L = Left 가 자를 수 있는 위치들의 최대값, R = Right 가 자를 수 있는 위치들의 최소값.

surreal number 의 정의: {L|R} 에서 L < R 일 때 이는 유리수에 대응. 예: {0|} = 1, {|0} = -1, {0|1} = 1/2.

알고리즘

evaluate_chain(s):
    val = 0
    for each char c in s:
        if c == 'B': val += 1
        else: val -= 1
    return val

winner(val):
    if val > 0: "Left (Blue)"
    if val < 0: "Right (Red)"
    if val == 0: "Second player"

branching_value(left_options, right_options):
    # left_options = {L1, L2, ...}, right_options = {R1, R2, ...}
    # simplest surreal number between max(L) and min(R)
    return simplest_surreal(max(left_options), min(right_options))

구현

// Hackenbush chain value evaluation
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
struct Frac {
  ll num, den;
  Frac(ll n = 0, ll d = 1) : num(n), den(d) {
      if (den < 0) { num = -num; den = -den; }
      ll g = gcd(abs(num), abs(den));
      num /= g; den /= g;
  }
  Frac operator+(const Frac& o) const {
      return Frac(num * o.den + o.num * den, den * o.den);
  }
  bool operator>(const Frac& o) const { return num * o.den > o.num * den; }
  bool operator<(const Frac& o) const { return num * o.den < o.num * den; }
  bool operator==(const Frac& o) const { return num == o.num && den == o.den; }
};
​
int main() {
  string s; cin >> s;
  Frac val;
  for (char c : s) {
      if (c == 'B') val = val + Frac(1);
      else if (c == 'R') val = val + Frac(-1);
  }
  cout << "Position value: " << val.num << "/" << val.den << "\n";
  if (val > Frac(0)) cout << "Winner: Left (Blue)\n";
  else if (val < Frac(0)) cout << "Winner: Right (Red)\n";
  else cout << "Winner: Second player\n";
  return 0;
}

from fractions import Fraction
import sys
s = sys.stdin.readline().strip()
val = Fraction(0, 1)
for c in s:
  if c == 'B':
      val += Fraction(1, 1)
  elif c == 'R':
      val -= Fraction(1, 1)
print(f"Position value: {val}")
if val > 0:
  print("Winner: Left (Blue)")
elif val < 0:
  print("Winner: Right (Red)")
else:
  print("Winner: Second player")

BBB

Position value: 3
Winner: Left (Blue)

BBR

Position value: 1
Winner: Left (Blue)

RRRB

Position value: -2
Winner: Right (Red)

BR

Position value: 0
Winner: Second player

복잡도

변형 / 활용

• Green Hackenbush: impartial variant. 모든 edge 가 초록색 = 누구나 자를 수 있음. Grundy number 로 평가.
• Hackenbush Hotchpotch: 빨강, 파랑, 초록 세 가지 색 혼합.
• Surreal number 모델: Hackenbush 위치는 surreal number 체계의 직관적 모델. Conway 의 “On Numbers and Games” 에서 이 게임으로 surreal number 를 설명.
• Game theory 교육: partizan game 의 기본 개념을 시각적으로 학습.

함정

1. Branching 구조의 값

단순 chain 의 값이 +1/-1 의 합인 반면, 가지가 갈라지면 {L|R} 형식의 surreal number 가 필요. 예: 파란 가지와 빨간 가지가 같은 높이에서 갈라지면 값은 {1|-1} = 0.

2. Zero game 의 의미

값이 0인 위치는 후수 승. 즉 먼저 자르는 쪽이 진다. “모서리” 위치는 항상 후수 승.

BOJ 연습 문제

참고

• Grundy Number
• Nim Game