수 순서 — 가지치기 효율의 비밀
알파-베타의 효율은 자식들을 어떤 순서로 보느냐에 절대적으로 의존해.
📖 수 순서가 중요한 이유
가지치기는 "어떤 가지에서 좋은 값을 발견 → 다른 가지를 안 봄" 패턴이야. 좋은 가지를 먼저 봐야 일찍 자른다.
- 최선 순서 (강한 수가 먼저) → b^(d/2) 노드 — sqrt 효과
- 최악 순서 (약한 수가 먼저) → b^d 노드 — 가지치기 효과 0
실제로는 둘 사이 어딘가. 좋은 수 순서 휴리스틱이 엔진 성능에 크리티컬.
그래서 진짜 체스 엔진은 다음 휴리스틱들로 수 순서를 정해:
- 최근 강했던 수 우선 — killer move heuristic
- 기물 잡는 수 우선 — capture가 보통 강함
- 이전 깊이의 best move 먼저 — iterative deepening
- 체크 일으키는 수 우선
- 역사 휴리스틱 — 과거 좋았던 수 통계
⚠️ 바둑에서는?
바둑은 "어떤 수가 강한 수"인지 사람도 잘 모름. 체스의 "기물 잡기" 같은 명확한 신호가 없거든. 그래서 수 순서 휴리스틱 자체가 어려움.
2006년 이전 컴퓨터 바둑이 약했던 이유 중 하나. PART 3에서 MCTS가 이 문제를 다르게 풀고, PART 4에서 신경망이 "어떤 수가 좋은 수일지"를 직접 학습해서 알려주게 됨.
다음 페이지에서 수 순서가 효율에 얼마나 영향 주는지 직접 측정해보자.