1. 양화에서 게임으로

지난 강의에서 TQBF를 게임으로 읽는 법을 잠깐 보았다. ∃ 차례의 플레이어와 ∀ 차례의 플레이어가 번갈아 변수를 채우고, 마지막에 식이 참이면 ∃이 이긴다. 이 시점에서 합리적인 의문 하나. 그렇다면 우리가 일상에서 즐기는 보드게임 — 체스, 바둑, 오목 — 의 결정 문제들도 같은 틀에 들어가지 않을까?

답은 "들어간다"이지만, 어디에 들어가는지가 미묘하다. 보드 크기를 매개변수로 일반화하면 어떤 게임은 PSPACE-완전, 어떤 게임은 EXPTIME-완전이 된다. 이번 강의에서는 그 가운데 가장 깔끔한 견본인 일반화 지오그래피를 통해, "2인 완전정보 게임의 승자 판정 = 양화식의 진리 판정"이라는 등식을 또렷이 보일 것이다.

양화자의 깊이는 게임의 길이와 같다. 게임이 다항 길이로 끝나면 PSPACE 안에 머문다(TQBF의 PSPACE 멤버십과 같은 깊이 우선 평가). 게임이 지수적으로 길어질 수 있으면 EXPTIME 영역으로 올라간다.

2. 일반화 지오그래피

어릴 적 끝말잇기를 떠올려 보자. 한 사람이 단어를 말하면 다음 사람은 그 단어의 마지막 글자로 시작하는 단어를 댄다. 더 못 대는 쪽이 진다. 이 게임을 그래프로 추상화한 것이 지오그래피다. 정점은 단어, 간선은 "끝 글자가 시작 글자와 일치"라는 관계.

왜 토큰 한 개로, 왜 정점 재방문 금지인가? 단어 끝말잇기에서 같은 단어를 두 번 쓰지 않는 규칙을 그대로 옮긴 것이다. 이 단순한 규칙 두 줄이 게임을 충분히 풍부하게 만들어 준다.

멤버십 GG ∈ PSPACE는 어렵지 않다. 위치 = (현재 정점, 방문한 정점 집합)인데, 후자를 비트 벡터로 들고 있어도 |V| 비트면 충분하다. minimax를 깊이 우선으로 재귀 평가하면 재귀 깊이도 |V|. 따라서 다항 공간이면 충분하다.

핵심은 PSPACE-경도 — 즉 TQBF ≤_p GG. 임의의 양화 부울식 φ를 받아, 그래프 G_φ와 시작 정점을 만들어 "φ가 참 ⇔ 선공 승리"가 되도록 한다.

3. 환원 가젯

일반성 잃지 않고 φ를 다음과 같이 정규화하자. 양화자가 ∃와 ∀가 교대로 나오고, 행렬은 3-CNF.

φ = ∃x₁ ∀x₂ ∃x₃ … Q_nx_n C₁ ∧ C₂ ∧ … ∧ C_k.

그래프 G_φ는 두 부분으로 나뉜다. 변수 가젯의 사슬과, 그 끝에 매달린 절 가젯들.

변수 가젯: 다이아몬드

각 변수 x_i마다 다이아몬드 모양의 가젯을 둔다. 위쪽 정점 a_i에서 두 갈래(왼쪽: x_i = T, 오른쪽: x_i = F)로 갈라졌다가 아래쪽 정점 b_i에서 다시 합쳐진다. 그리고 b_i는 다음 변수의 a_i+1로 이어진다.

다이아몬드의 갈래는 두 개의 정점(t_i와 f_i)으로 표현된다. 시작 정점이 a_i이고 차례인 플레이어가 t_i 또는 f_i를 고르면, 상대편이 자동으로 다음 정점 b_i로 가야 한다. 이 한 라운드 안에서 차례인 플레이어가 사실상 변수의 진리값을 결정한다.

핵심은 차례를 어떻게 짜 두느냐. 양화자 ∃x_i이면 i번째 다이아몬드의 a_i가 플레이어 1(∃)의 차례에 오도록, ∀x_i이면 플레이어 2(∀)의 차례에 오도록 정렬한다. 다이아몬드 한 개는 두 수(a_i → t_i/f_i → b_i)를 잡아먹으므로, 시작 위치를 적절히 잡으면 차례가 정확히 맞아떨어진다.

마무리: 절 가젯과 함정

n번째 다이아몬드의 b_n은 절 선택 정점 c로 이어진다. c에서는 플레이어 2(∀)의 차례. ∀는 절 C₁, …, C_k 중 하나를 고른다. 즉 c에서 절 정점 v_j로 간선이 나와 있고, ∀는 그중 하나를 선택한다.

절 정점 v_j에서는 다시 플레이어 1(∃)의 차례. v_j는 자신의 절 C_j의 세 리터럴 각각으로 간선이 나 있다. ∃는 그중 하나를 골라 이동한다. 그리고 결정적인 부분: 각 리터럴 정점은, 변수 가젯에서 해당 리터럴을 "참"으로 만든 갈래의 정점(t_i 또는 f_i)으로 간선이 이어져 있다. 즉 리터럴 x_i는 t_i로, ¬x_i는 f_i로.

그런데 t_i 혹은 f_i는 이미 게임 초반에 한 번 방문되었을 수도, 그렇지 않을 수도 있다. 이게 트릭이다. 변수 단계에서 차례인 플레이어가 t_i를 고르면 t_i가 방문 표시된다. 즉 x_i를 T로 정한 셈. 그러면 절 단계에서 어떤 리터럴이 t_i로 가려 해도 정점이 이미 사용되었으므로 갈 수 없다.

잠깐, 방향이 거꾸로 아닌가? 다시 정리. 절 가젯에서 ∃이 리터럴 ℓ을 골라 t_i(또는 f_i)로 들어가면, 그 정점에서 다시 한 수가 나가야 한다. 그래프를 설계할 때, t_i와 f_i 각각에서 더 이상 갈 곳이 없도록(혹은 한 단계만 더 가는 막다른 길이도록) 만든다. 그러면 절 단계에서 ∃이 ℓ을 골라 들어가면 그 다음은 ∀의 차례인데 ∀는 갈 곳이 없어 진다 — 단, 그 정점 t_i/f_i가 아직 방문되지 않았을 때만. 만약 변수 단계에서 이미 방문되었다면 ∃이 그 리터럴 정점으로 들어가는 수 자체가 막혀, 결국 ∃의 막다른 길이 되어 ∃이 진다.

요약하자면, 절 단계에서 ∃이 살아남으려면 절 C_j를 만족시키는 리터럴이 적어도 하나는 있어야 하고, 그 리터럴에 해당하는 변수 정점이 방문되지 않은 상태여야 한다. 그런데 변수 가젯에서 t_i를 골랐다는 것은 x_i = T로 두었다는 뜻이고, 이때 방문되지 않은 채 남은 정점은 f_i다. f_i는 x_i = F를 의미하는 리터럴 ¬x_i의 표적이고, 따라서 ¬x_i가 절을 만족시키려면 절 안에 ¬x_i가 있어야 한다. 결국 "리터럴 ℓ이 절을 참으로 만든다"와 "ℓ에 대응하는 정점이 절 단계에서 비방문 상태이다"가 정확히 일치하도록 설계된다.

4. 보드게임의 자리는 어디인가

일반화 지오그래피의 환원 기술은, 더 본격적인 보드게임으로 확장된다. 다만 클래스 위치는 게임의 "자연스러운 길이"에 따라 달라진다.

다항 길이 게임은 PSPACE 안에 머문다. 위치 인코딩과 전략 평가가 다항 공간 안에 들어가기 때문이다. 지수 길이 게임은 EXPTIME으로 올라간다. 시간 자체가 지수가 되면 PSPACE 평가가 통하지 않는다.

• n×n 체스(50수 무승부 규칙 없이): 대국이 지수 길이일 수 있어 EXPTIME-완전.
• n×n 바둑(일본 룰 변종): 대국 길이가 지수, EXPTIME-완전. 단, 어떤 룰을 채택하느냐로 결과가 흔들린다.
• n×n 오목(Gomoku) 류의 라인업 게임: 보통 PSPACE-완전.
• Generalized Geography: 길이 ≤ |V|이므로 PSPACE-완전.

"무승부 규칙이 있으면 게임 길이가 다항으로 강제되어 PSPACE에 떨어진다"는 한 줄짜리 직관이 꽤 자주 들어맞는다.

5. 마무리

2인 완전정보 게임의 결정 문제를 양화 부울식의 진리 판정과 한 줄로 잇는 데 성공했다. 그 결과 TQBF가 누리던 PSPACE-완전성은 깔끔한 가젯 환원을 통해 일반화 지오그래피로 전염되었고, 그 너머로 Hex와 같은 보드게임에까지 번져 있다.