2명이 교대로 두는 완전 정보 게임을 상태 공간 문제(State Space Problem)의 일종으로 정식화하고, 미니맥스 알고리즘(Minimax Algorithm)이 게임 트리(Game Tree) 위에서 어떻게 작동하는지 확인합니다. 조합론적 폭발(Combinatorial Explosion)로 인해 완전한 게임 트리의 탐색이 불가능해진다는 점을 짚어본 뒤, 정적 평가(Static Evaluation)를 통한 가지치기 탐색, α-β 가지치기(α-β Pruning), 정지 탐색(Quiescence Search), 반복 심화(Iterative Deepening), 치환 테이블(Replacement Table), 필살수 휴리스틱(Killer Heuristic) 등 게임 프로그래머들이 실제로 사용하는 트릭들을 차례대로 살펴봅니다. 샘플 프로그램으로는 체커(Checkers)를 Swift로 구현하여, 각 기법이 탐색 노드 수를 얼마나 줄여주는지 실측합니다. 마지막으로 이 분야의 최첨단인 컴퓨터 체스(Computer Chess)와 장기(Shogi), 바둑(Go)으로의 응용을 다룹니다.

• 서론
• 1. 기술 게임과 상태 공간의 대응 관계
• 2. 게임 트리
• 3. 막대 잡기 게임 ― 완전한 게임 트리를 풀기
• 4. 미니맥스 알고리즘 (Minimax Algorithm)
• 5. 네가맥 (Negamax) ― 두 가지 관점을 하나로 통합하기
• 6. 조합론적 폭발 (Combinatorial Explosion)
• 7. 정적 평가를 통한 가지치기 탐색
• 8. 정적 평가 함수
• 9. α-β 가지치기 (α-β Pruning)
• 10. α-β의 효율과 수 순서 정하기 (Move Ordering)
• 11. 샘플 프로그램 ― 체커
• 12. 미니맥스와 α-β의 실측
• 13. 정지 탐색과 수평선 효과 (Horizon Effect)
• 14. 반복 심화 (Iterative Deepening)
• 15. 치환 문제와 치환 테이블 (Replacement Table)
• 16. 필살수 휴리스틱과 이력 휴리스틱 (History Heuristic)
• 17. 초반 정석집과 종반 데이터베이스
• 18. 컴퓨터 체스
• 19. 장기 (Shogi)
• 20. 바둑 (Go)
• 요약
• 주석
• 참고 자료

지난 기사에서는 단독 주체가 목표를 향해 상태 공간을 나아가는 탐색을 다루었습니다. 지도 위에서 경로를 찾을 때, 연산자(Operator)를 적용하는 것은 자신뿐입니다. 아무도 방해하지 않습니다.

게임에서는 상황이 달라집니다. 연산자를 적용하는 것은 자신과 상대가 교대로 이루어지며, 심지어 상대는 자신의 목표를 방해하는 것을 목표로 합니다. 이 한 가지 점이 추가되는 것만으로 탐색의 프레임워크는 크게 재구성됩니다. '목표에 이르는 경로'를 하나 찾아내는 것만으로는 의미가 없습니다. 상대가 어떻게 응수해 오더라도 대처할 수 있는 **방침(Policy)**을 가질 필요가 있기 때문입니다.

이 기사에서는 2명이 플레이하는, 이산적(Discrete)이고, 완전 정보(Perfect Information)이며, 결정론적인(Deterministic) 게임만을 다룹니다. 체스, 장기, 바둑, 체커, 오셀로가 이에 해당합니다. 포커나 마작(숨겨진 정보가 있음), 백개먼(주사위라는 우연적 요소가 있음)은 대상에서 제외합니다. 이 제한 덕분에 게임 트리라는 단일 구조로 모든 것을 표현할 수 있습니다.

다루는 도구는 1950년 전후에 제안된 미니맥스와 정적 평가라는 두 가지 개념, 그리고 그 위에 쌓아 올린 고속화 기법들입니다. 후자는 모두 조합론적 폭발이라는 단 하나의 적과 싸우기 위해 고안된 것입니다.

게임은 크게 두 종류로 나뉩니다.

기술 게임 (Game of Skill): 결과가 완전히 플레이어의 선택으로 결정됨. 우연적 요소가 없음 -
운 게임 (Game of Chance): 주사위나 카드 배분 등 우연이 결과에 영향을 미침

이 기사에서 다루는 것은 기술 게임이며, 추가로 다음 조건을 부여합니다.

이러한 조건을 만족하는 게임은 지난번에 정의한 상태 공간 문제와 거의 그대로 대응됩니다.

대응하지 않는 부분이 딱 하나 있습니다. 바로 해(Solution)의 형태입니다.

• 상태 공간 문제의 해는
  경로 (Path), 즉 연산자의 나열이다 - 게임의 해는
  전략 (Strategy), 즉 "상대가 이렇게 두면 나는 이렇게 둔다"라는 대응의 전체이다

왜냐하면, 경로 중에서 자신이 선택할 수 있는 것은 한 수 건너 하나뿐이기 때문입니다. 나머지 절반은 상대가 결정합니다. 따라서 "첫 수는 이것, 다음은 이것"이라는 일직선상의 계획은 세울 수 없습니다. 상대의 모든 응수에 대한 대비가 필요합니다.

이 차이는 형식적으로, 연산자를 적용하는 주체가 교대로 바뀌며, 게다가 한쪽은 목표 판정을 최대화(Maximize)하려 하고 다른 한쪽은 최소화(Minimize)하려 한다고 바꿔 말할 수 있습니다. 게임 탐색 알고리즘이 모두 "최대화와 최소화의 교체" 형태를 띠는 것은 바로 이 구조에서 직접적으로 비롯됩니다.

또한, 이 조건을 만족하며 반드시 유한한 수 내에 종료되는 게임에는 확정된 이론값(선수 필승, 후수 필승, 무승부 중 하나)이 존재한다는 사실이 알려져 있습니다. Ernst Zermelo가 1913년에 제시한 결과입니다(주1). 체스의 이론값이 무엇인지는 지금도 알 수 없지만, "모른다"는 것이 "정해져 있지 않다"는 뜻은 아닙니다.

**게임 트리 (game tree)**는 국면을 노드(node), 합법적인 수를 에지(edge)로 하여, 초기 국면으로부터 도달 가능한 모든 국면을 전개한 트리입니다.

뿌리 (자신의 차례) ← MAX 노드
/ | \
수 a 수 b 수 c
...

MAX 노드: 자신의 차례인 국면. 자신에게 유리한 값을 최대화 (maximize) 하는 수를 선택 -
MIN 노드: 상대의 차례인 국면. 상대는 자신에게 유리한 값을 최소화 (minimize) 하는 수를 선택 -
잎 (leaf): 종료된 국면. 승리·패배·무승부의 이득(utility)이 확정됨

여기서 "값"은 항상 한쪽 플레이어의 관점에서 본 값으로 정의합니다. 관례적으로 MAX 측(탐색하는 측)에서 본 값을 사용하며, 승리를 +1, 무승부를 0, 패배를 -1로 합니다.

중요한 점은, 게임 트리가 탐색 트리 (search tree)이지 상태 공간 (state space) 그 자체는 아니라는 점입니다. 동일한 국면이 서로 다른 순서로 나타나면, 트리의 다른 위치에 별개의 노드로 중복되어 나타납니다. 이 중복은 나중에 설명할 치환 문제로 이어집니다.

먼저, 게임 트리 전체를 끝까지 탐색할 수 있을 정도로 작은 게임을 통해 메커니즘을 확인해 보겠습니다. **막대 가져가기 게임 (Last One Loses)**을 사용합니다.

• 막대가 n개 놓여 있음 - 2명이 번갈아 가며 1개, 2개, 3개 중 하나를 가져감
• 마지막 1개를 가져가는 쪽이 패배

상태(state)는 "남은 막대 수"와 "차례"뿐입니다.

enum Turn {
case max, min
var opponent: Turn { self == .max ? .min : .max }
...
}

utility의 부호에 주의하십시오. 막대가 0개가 된 국면에서 차례가 돌아왔다는 것은, 직전에 상대가 마지막 1개를 가져갔다는 뜻입니다. 따라서 그 국면에서 차례를 가진 쪽이 승자입니다.

이 게임에는 손으로 풀 수 있는 필승법이 있습니다. 남은 개수가 4k + 1일 때 차례가 된 쪽이 패배합니다. 상대에게 항상 "4의 배수 플러스 1"을 계속 넘겨주면 되기 때문입니다. 프로그램이 이 구조를 스스로 찾아낼 수 있는지가 다음의 확인 사항입니다.

미니맥스 (MINIMAX) 알고리즘은 게임 트리를 재귀적으로 따라가며, 각 노드의 값을 다음과 같이 결정합니다.

• 잎 노드의 값은 해당 종료 시의 이득 (utility)
• MAX 노드의 값은 자식 노드 값들의 최댓값 (maximum)
• MIN 노드의 값은 자식 노드 값들의 최솟값 (minimum)

즉, "상대의 유리함을 최소화하고, 자신의 유리함을 최대화하는" 수를 선택한다는 원리를 그대로 코드로 옮긴 것입니다. 전제로, 상대도 최선을 다한다고 가정합니다. 이 가정은 비관적이지만 안전한 가정입니다. 상대가 최선을 다하지 않는다면, 결과는 가정보다 좋아질 수는 있어도 나빠지지는 않습니다.

var visited = 0
func minimax(_ s: Sticks) -> Int {
visited += 1
...
}

막대 개수를 바꿔가며 실행한 결과입니다.

막대 1개: 값 -1 최선수 1개 탐색 노드 2
막대 2개: 값 +1 최선수 1개 탐색 노드 4
막대 3개: 값 +1 최선수 2개 탐색 노드 8
...

값이 -1 (차례인 쪽의 패배)이 되는 경우는 1개, 5개, 9개일 때로, 예상대로 4k + 1 형태를 띠고 있습니다. 이길 수 있는 국면에서는 항상 남은 개수를 4k + 1로 만드는 수를 선택하고 있습니다. 미니맥스는 필승법을 배운 것이 아니라, 게임 트리를 끝까지 살펴본 결과로서 그것을 재발견하고 있는 것입니다.

동시에, 오른쪽 끝의 노드 수에 주목하십시오. 막대가 3개씩 늘어날 때마다 노드 수가 약 6배씩 증가하고 있습니다. 이 정도의 단순한 게임조차도 지수적으로 증가하고 있는 것입니다.

위의 코드에는 max를 취하는 가지와 min을 취하는 가지가 별도로 작성되어 있습니다. 제로섬 (zero-sum) 게임이라는 점을 이용하면 이를 하나로 합칠 수 있습니다.

어떤 노드의 차례인 쪽에서 본 값은, 자식 노드의 자식 차례인 쪽에서 본 값의 부호를 반전시킨 것의 최댓값과 같다.

minimax(s, MAX) = -minimax(s, MIN)

이런 관계가 성립하기 때문입니다. 이러한 작성 방식을 **네가맥스 (negamax)**라고 부릅니다 (주2).

func negamax(_ s: Sticks) -> Int {
if isTerminal(s) { return 1 } // 종국은 항상 차례인 쪽의 승리 (차례인 쪽에서 본 값)
var best = Int.min
...

분기가 사라지고, max와 부호 반전만 남게 되었습니다. 네가맥스 형식을 사용할 때의 약속은 단 하나뿐입니다. 평가값은 항상 "그 국면에서 차례를 가진 쪽에서 본 값"이어야 한다. 제3절의 utility는 MAX 측에서 본 값을 반환하는 함수였으므로, 여기서는 그대로 사용할 수 없습니다. 이 게임의 종국은 "차례가 돌아온 쪽의 승리"로 정해져 있으므로, 차례인 쪽에서 본 종국의 값은 항상 +1입니다. 실수로 utility(s)를 반환하면, 패배 국면까지 승리로 판정하는, 원인을 알기 어려운 버그가 발생합니다. 이후의 코드는 모두 이 형식으로 작성합니다.

막대 가져가기 게임(Sticks game)은 끝까지 탐색할 수 있었습니다. 실제 게임에서는 그렇게 되지 않습니다.

게임 트리 (game tree)의 노드 수는 대략 b^d입니다. b는 분기 계수 (branching factor) (평균 합법 수), d는 게임의 깊이 (depth) (종국까지의 평균 수, 한쪽의 1수를 1로 계산)입니다. 주요 게임의 추정치는 다음과 같습니다 (주3).

체스에 대해 Claude Shannon이 1950년 논문에서 추정한 10¹²⁰이라는 수는 **샤논 수 (Shannon number)**라고 불립니다 (주4). 표의 10¹²³은 그 이후의 재추정치이며, 자릿수 측면에서는 같은 의미입니다. 관측 가능한 우주의 원자 수가 약 10⁸⁰이라고 하니, 비교 대상이 되지 않습니다.

이렇게 선택지가 지수적으로 증가하는 현상을 **조합론적 폭발 (combinatorial explosion)**이라고 부릅니다. 이것이 게임 프로그래밍에서의 유일하고도 최대의 적이며, 이후에 다룰 기법들은 모두 이에 대한 대책입니다. 대책은 두 가지 방향으로 나뉩니다.

• 탐색을 얕게 중단하기: 완전한 게임 트리 대신, 도중에 멈추고 추정치를 사용함 (제7~8절)
• 불필요한 가지를 보지 않기: 결론에 영향을 주지 않는 부분 트리를 탐색에서 제외함 (제9절 이후)

끝까지 탐색할 수 없다면, 정해진 깊이에서 멈출 수밖에 없습니다. 하지만 멈춘 지점은 종국이 아니므로 승패가 확정되지 않았습니다. 그래서 그 국면이 얼마나 유리한지를 추정하는 함수를 준비합니다. 이를 **정적 평가 함수 (static evaluation function)**라고 부릅니다. "정적"이라는 것은, 앞을 내다보지(look-ahead) 않고 판면(board)만 보고 판단한다는 의미입니다.

미니맥스의 종료 조건을 "종국에 도달하면"에서 "종국에 도달했거나, 정해진 깊이까지 왔다면"으로 바꾼 것을 절단 탐색 (truncated search), 또는 깊이 제한 탐색이라고 부릅니다.

func negamax(_ b: Board, depth: Int) -> Double {
let ms = legalMoves(b)
if ms.isEmpty { return -winScore } // 수가 없음 = 차례인 쪽이 패배
...

종국 판정을 깊이 판정보다 먼저 작성하고 있다는 점이 중요합니다. 깊이 제한에 도달했더라도 종국 상태라면, 추정치가 아닌 확정된 승패를 반환해야 합니다.

이 변경을 통해 탐색은 "정답을 내는 절차"에서 "한정된 계산량으로 좋아 보이는 수를 선택하는 절차"로 바뀝니다. 얻어지는 값은 더 이상 게임의 이론값이 아니라, 깊이 d까지의 탐색과 평가 함수의 조합에 의한 추정치입니다.

그리고 다음의 중요한 성질이 성립합니다. 같은 평가 함수를 사용한다면, 깊게 탐색할수록 강해진다. 평가 함수의 오차는 깊게 탐색할수록 실제 종국에 가까운 국면에서 측정되기 때문에 작아지기 때문입니다. 이 성질 덕분에 "탐색을 빠르게 하는 것"이 곧바로 "강해지는 것"이 됩니다. 게임 프로그래밍이 철저하게 속도를 추구해 온 이유가 여기에 있습니다.

정적 평가 함수의 설계는 탐색의 속도와 나란히 하는 또 다른 기둥입니다. 전형적으로는, 판면에서 읽어낼 수 있는 특징량(feature)의 **선형 결합 (linear combination)**으로서 만들어집니다.

평가치 = w₁ × 특징량₁ + w₂ × 특징량₂ + … + wₙ × 특징량ₙ

체스나 체커에서는 다음과 같은 특징량이 사용됩니다.

Shannon이 1950년에 제시한 체스의 평가 함수는 기물 이득에 기동성(mobility)과 폰 구조(pawn structure) 항을 더한 선형 형식(linear form)이었습니다. Arthur Samuel의 체커 프로그램(1959년)은 이러한 특징량의 가중치(weight)를 대국 경험으로부터 자동 조정하는 것을 시도하였으며, 이는 머신러닝 (machine learning)의 초기 대표 사례로 알려져 있습니다 (주5).

이 기사의 샘플 프로그램에서는 다음과 같은 단순한 평가 함수를 사용합니다.

0.7 × (아군 킹 − 적군 킹) + 0.3 × (아군 기물 − 적군 기물)

킹의 차이에 가중치 0.7, 기물 수의 차이에 가중치 0.3을 부여한 것입니다. 체커의 킹은 앞뒤 양방향으로 움직일 수 있으므로 일반 기물보다 가치가 높으며, 그 차이를 이 가중치가 나타냅니다.

평가 함수에 대해 반드시 짚고 넘어가야 할 점이 두 가지 있습니다.

첫째, 절대값에는 의미가 없으며 순서에만 의미가 있습니다. 평가치가 0.3이라는 것에 물리적인 의미는 없습니다. 다른 국면의 평가치와 비교했을 때 대소 관계가 올바르게 나열되어 있다면 그것으로 충분합니다. 따라서 가중치 전체에 상수를 곱하더라도 탐색 결과는 변하지 않습니다.

둘째, 정밀도와 계산 비용은 트레이드오프 (trade-off) 관계에 있습니다. 평가 함수를 정교하게 만들면 한 국면당 판단 능력은 좋아지지만, 그만큼 초당 평가할 수 있는 국면 수가 줄어들어 탐색 깊이가 얕아집니다. 제7절에서 언급했듯이 깊이는 강함과 직결되므로, 이는 실제로 매우 까다로운 거래입니다. 역사적으로는 비교적 단순한 평가 함수로 깊게 탐색하는 방침 (Shannon이 말하는 Type A)이, 복잡한 평가 함수로 선택적으로 탐색하는 방침 (Type B)에 대해 우위를 점해 왔습니다.

가지치기 탐색을 통해 깊이는 유한해졌지만, b^d 형태는 그대로 유지됩니다. 여기서 핵심적인 역할을 하는 것이 **α-β 가지치기 (alpha-beta pruning)**입니다.

α-β 가지치기는 미니맥스 (minimax)와 완전히 동일한 값을 반환하면서, 결론에 영향을 주지 않는 부분 트리의 탐색을 생략하는 기법입니다. 근사치가 아닙니다. 답은 단 1비트도 변하지 않으며, 단지 빨라질 뿐입니다.

MAX 노드에서 이미 값 6을 확보할 수 있는 수를 찾았다고 가정해 봅시다. 다음 수를 조사하던 중, 그 너머의 MIN 노드에서 값 4를 발견했다고 가정합니다. MIN 노드는 자식 노드 중 최솟값을 선택하므로, 이 MIN 노드의 값은 반드시 4 이하가 됩니다. 즉, 이 수를 선택하더라도 6보다 낮은 값만을 얻게 될 뿐입니다. 따라서 이 MIN 노드의 나머지 자식들을 조사할 필요가 없습니다.

이 판단에 사용하는 두 가지 값이 α와 β입니다.

탐색은 항상 구간 [α, β]를 가지며 진행되고, 이 구간을 벗어난 가지는 버려집니다.

• α 가지치기 (alpha cutoff): MIN 노드에서 값이 α 이하가 되었다. MAX 측은 이 가지를 선택하지 않으므로, 나머지 형제 노드들을 버린다.
• β 가지치기 (beta cutoff): MAX 노드에서 값이 β 이상이 되었다. MIN 측은 이 가지로 들어오게 하지 않으므로, 나머지 형제 노드들을 버린다.

네가맥스 (negamax) 형식에서는 이 두 가지가 하나의 조건으로 통합됩니다.

func alphaBeta(_ b: Board, depth: Int, alpha: Double, beta: Double) -> Double {
let ms = legalMoves(b)
if ms.isEmpty { return -winScore }
...

재귀 호출에서 alpha: -beta, beta: -alpha로 전달하는 부분이 핵심입니다. 값의 부호를 반전시키면 구간의 상하가 뒤바뀝니다.

값을 고정한 작은 게임 트리에서 실제로 무엇이 버려지는지 살펴보겠습니다. 깊이 4 (MAX → MIN → MAX → 잎 노드), 각 노드의 자식은 2~3개입니다.

indirect enum Node {
case leaf(Int)
case branch([Node])
...

잎(leaf)을 평가한 순서와 가지치기(pruning)가 일어난 위치를 기록하며 실행한 결과입니다.

미니맥스(Minimax) 값: 15 (평가한 잎 18개)
α-β 값: 15 (평가한 잎 14개)
잎 111 = 3 [α=-∞, β=+∞]
...

값은 둘 다 15로 일치하며, 평가한 잎은 18개에서 14개로 줄었습니다. 두 곳에서 가지치기가 일어났습니다.

• 두 번째 MIN 자식(노드 2)에서, 첫 번째 자식이 4로 판명되었다. 루트(root)에서는 이미 α = 6을 확보했으므로, 이 MIN 자식은 4 이하가 될 수밖에 없다. 남은 부분 트리(잎 3개)를 통째로 버렸다.
• 세 번째 가지의 MAX 노드(노드 32)에서 20이 발견되었다. 부모인 MIN 노드는 이미 β = 15를 가지고 있으므로, 이 가지로는 들어가지 않는다. 남은 잎들을 버렸다.

버려진 부분 트리 안에는 사실 13이라는 큰 값이 포함되어 있었습니다(노드 22의 자식). 그럼에도 답이 바뀌지 않는 이유는, 그 값에 도달하기 전에 MIN 측이 다른 수를 선택하기 때문입니다. α-β 가지치기가 안전한 이유는 값을 추측하는 것이 아니라, "이 부분 트리의 값이 어떻든 결론은 변하지 않는다"는 것을 논리적으로 확인하기 때문입니다.

α-β 가지치기가 얼마나 이득을 보는지는 수를 탐색하는 순서에 결정적으로 의존합니다.

• 최선의 경우 (Best case): 각 노드에서 최선의 수를 가장 먼저 탐색한다. 이때 탐색하는 노드 수는 b^(d/2) 정도로 떨어진다.
• 최악의 경우 (Worst case): 각 노드에서 최선의 수를 가장 마지막에 탐색한다. 가지치기가 한 번도 일어나지 않아 순수한 미니맥스(Minimax)와 같은 b^d가 된다.

최선의 경우인 b^(d/2)라는 결과는 Donald Knuth와 Ronald Moore에 의한 분석으로 제시된 것으로, 실질적인 분기 계수(branching factor)가 b에서 √b로 낮아짐을 의미합니다(주6). 이는 극적입니다. 같은 시간 동안 2배 더 깊은 곳까지 읽을 수 있다는 뜻이기 때문입니다.

물론 최선의 수를 처음부터 알고 있다면 탐색할 필요가 없습니다. 실제로는 근사적으로 좋은 순서를 만들어가게 됩니다. 자주 사용되는 단서는 다음과 같습니다.

순서 정하기와 관련하여, 이 글의 체커(checker) 구현에서 측정하며 알게 된 점이 하나 있습니다. 무작위로 순서를 바꿔도 성능은 거의 변하지 않습니다. 효과가 있는 것은 "좋은 수를 먼저 본다"라는 정보를 가진 순서 정하기뿐입니다. 실측 결과는 제16절에서 보여드리겠습니다.

지금까지의 기법을 실제로 측정하기 위해, 체커(English Draughts)를 Swift로 구현합니다. 규칙은 다음과 같습니다.

• 8×8 보드에서 어두운 칸만 사용한다 (32칸). 양측 12개씩의 기물로 시작한다.
• 일반 기물은 대각선 앞방향으로 1칸 전진한다. **킹(King)**은 대각선 앞뒤 양방향으로 움직일 수 있다.
• 상대의 기물을 뛰어넘어(jump) 잡는다. 뛰어넘기가 가능한 경우에는 반드시 뛰어넘어야 한다 (강제 잡기).
• 연속해서 뛰어넘을 수 있는 경우에는 뛰어넘을 수 있는 만큼 전부 뛰어넘는다.
• 가장 끝 열에 도달한 기물은 킹으로 승격한다. 단, 뛰어넘는 도중에 승격하면 해당 차례는 종료된다.
• 움직일 수 있는 수가 없어진 쪽이 패배한다.

보드 판은 64칸의 배열로 관리합니다. Board를 Hashable하게 만드는 이유는 나중에 치환 테이블(replacement table)의 키(key)로 사용하기 위해서입니다.

enum Player: Int, Hashable {
case black = 0, white = 1
var opponent: Player { self == .black ? .white : .black }
...

초기 국면을 표시하면 다음과 같습니다. 소문자는 일반 기물, 대문자는 킹, .은 비어 있는 어두운 칸입니다. 흑(b)은 위에서 아래로, 백(w)은 아래에서 위로 전진합니다.

a b c d e f g h
8 b b b b
7 b b b b
...

수는 경로(통과하는 칸의 목록)와 잡은 기물의 위치로 나타냅니다. 연속 뛰어넘기가 있기 때문에 단일 이동 목적지만으로는 표현할 수 없습니다.

struct Move: Hashable {
var path: [Int] // 출발 칸부터 도착 칸까지
var captured: [Int]
...

점프(jump)는 재귀(recursion)를 통해 생성합니다. 점프한 지점에서 더 점프할 수 있는 경우, 그 연속된 움직임만을 결과에 포함합니다 (도중에 멈추는 것은 허용되지 않기 때문입니다).

func jumpMoves(from square: Int, piece: Piece, cells: [Piece?],
path: [Int], captured: [Int]) -> [Move] {
let r = square / 8, c = square % 8
...

마지막 행의 jumps.isEmpty ? steps : jumps

가 강제 잡기(forced capture) 규칙입니다. 이 한 줄 때문에, 체커(checkers)에서는 특정 노드의 합법적인 수(legal moves)가 "전부 점프"이거나 "전부 일반적인 수" 중 하나가 됩니다. 이 성질은 나중에 정적 탐색(static search)과 수 순서 정하기(move ordering) 모두에 영향을 미칩니다.

탐색 측정을 하기 전에, 수 생성(move generation)이 올바른지 확인합니다. 게임 프로그래밍에서는 초기 국면에서 깊이 d까지의 리프(leaf) 노드 수를 세는 perft라는 검증 방식이 자주 사용됩니다. 잉글리시 드래프츠(English Draughts)의 값은 공개되어 있으므로, 이를 대조해 봅니다.

func perft(_ b: Board, _ depth: Int) -> Int {
if depth == 0 { return 1 }
let ms = legalMoves(b)
...

perft(1) = 7 기대값 7 OK
perft(2) = 49 기대값 49 OK
perft(3) = 302 기대값 302 OK
...

깊이 9까지 완전히 일치했습니다. 강제 잡기, 연속 점프, 그리고 승급(promotion)으로 해당 차례가 종료되는 규칙까지 포함하여, 수 생성이 올바르다는 것을 확인할 수 있습니다. 이후의 측정값은 이 토대 위에서 얻은 것입니다.

제8절에서 언급한 식을 그대로 구현합니다. 네가맥스(Negamax) 형식으로 사용하기 위해, 인자로 전달된 플레이어의 관점에서 본 값을 반환합니다.

func evaluate(_ b: Board, for player: Player) -> Double {
var myKings = 0, oppKings = 0, myPieces = 0, oppPieces = 0
for cell in b.cells {
...

초기 국면에서는 양측이 대칭이므로 평가값(evaluation value)은 0.0이 됩니다. 기물을 하나 더 많이 가지고 있는 국면에서는 0.3, 킹(king)을 하나 더 많이 가지고 있다면 추가로 0.7이 더해집니다.

측정에는 자기 대국(self-play)으로 16수를 진행한 다음의 중반 국면을 사용합니다. 차례는 흑, 합법적인 수는 8개, 기물 수는 흑 10개·백 9개입니다.

a b c d e f g h
8 . . b b
7 b b b b
...

이 국면을 순수 네가맥스, $\alpha\text{-}\beta$ 가지치기($\alpha\text{-}\beta$ pruning), 그리고 $\alpha\text{-}\beta$에 이후 절에서 다룰 개선 사항(수 순서 정하기, 置換 테이블(replacement tables), 반복 심화(iterative deepening))을 모두 적용한 개선판의 세 가지 방식으로 탐색하여, 방문한 노드 수를 세었습니다. **실효 분기 계수(effective branching factor)**는 노드 수의 $d$제곱근, 즉 "한 수당 실질적으로 몇 개의 가지를 보았는가"를 의미합니다.

깊이 9에서는 $\alpha\text{-}\beta$만으로도 노드 수가 약 38분의 1로 줄어들었고, 개선판에서는 약 197분의 1로 줄어들었습니다. 효과가 깊이가 깊어질수록 커진다는 점이 중요합니다. 지수의 밑이 낮아지기 때문에, 더 깊이 읽을수록 차이가 벌어집니다.

실효 분기 계수로 보면, 순수 네가맥스의 5.01에 대해 $\alpha\text{-}\beta$는 3.35입니다. 제10절에서 언급한 이상적인 값은 $\sqrt{5.01} \approx 2.24}$이므로, 거기까지는 도달하지 못했습니다. 수의 순서가 이상적이지 않기 때문입니다. 개선판에서는 2.78까지 내려가며 이상적인 값에 가까워집니다.

고정된 깊이에서 탐색을 중단하는 것에는 심각한 부작용이 있습니다.

깊이 제한의 바로 경계 지점에서, 기물을 잡는 수를 두었을 때 탐색이 멈췄다고 가정해 봅시다. 평가 함수는 "기물을 하나 더 많이 가지고 있다"고 판단하여 그 수를 높게 평가합니다. 하지만 다음 한 수에서 바로 되잡힌다면, 그 평가는 오류입니다. 탐색의 지평선(horizon) 너머에 있는 사실이 보이지 않는 것입니다.

이를 **수평선 효과(horizon effect)**라고 부릅니다. Hans Berliner가 1973년에 명명했습니다 (주7).

제11절의 체커(Checkers)에서 실제로 이 현상이 발생하는 국면을 찾아보았습니다. 흑의 차례이며, 점프(jump)가 강제된 국면입니다.

a b c d e f g h
8 b b b b
7 . b b b
...

깊이(depth)를 변화시키며 루트(root)의 평가값이 어떻게 변하는지 살펴보겠습니다.

왼쪽 열이 교과서에 나오는 대로 진동을 보여주고 있습니다. 홀수 깊이에서는 0.6, 짝수 깊이에서는 0.3 또는 0.0. 홀수 깊이에서는 자신이 기물을 잡은 지점에서 탐색이 멈추기 때문에 유리해 보이고, 짝수 깊이에서는 다시 되돌려주는 지점까지 보이기 때문에 평가값이 낮아집니다. 깊이 4 이후에야 비로소 안정됩니다. 즉,

깊이 3의 탐색은 이 국면을 "기물을 이득 볼 수 있다"라고 잘못 판단했던 것입니다.

대책은 깊이 제한에 도달하더라도 국면이 "정적(quiet)"이지 않다면 탐색을 계속하는 것입니다. 이를 **정지 탐색 (quiescence search)**이라고 부릅니다. 정적인 국면이란 큰 변화를 일으키는 수(주로 기물을 잡는 수)가 남아있지 않은 국면을 말합니다.