지평선 효과

게임 개발 소프트웨어 마지막 수정: 2026-07-23 04:45:39

1. 개요[편집]

지평선 효과(horizon effect)는 고정 깊이로 탐색하는 미니맥스 알고리즘(및 알파-베타 가지치기) 계열 게임 트리 탐색이 가진 고전적인 한계다. 피할 수 없는 나쁜 결과(말을 잃거나 외통수에 걸리는 등)가 탐색 깊이 한 수 너머에 놓여 있을 때, 순진한 엔진은 그 나쁜 결과를 탐색 지평선 바깥으로 밀어내는 지연 수(delaying move)들에 속아, 사실은 진 국면을 멀쩡한 국면으로 오판한다. 진짜 평가값은 “지평선 너머”에 숨어 있어 엔진의 눈에 보이지 않는다.¹

이름 그대로다. 배가 수평선 너머를 못 보듯, 깊이 $d$ 까지만 읽는 탐색기는 $d+1$ 수째에 벌어질 재앙을 원리적으로 볼 수 없다. 문제는 엔진이 그 재앙을 없앤 게 아니라 그저 못 보게 만들 수 있다는 것 — 그리고 순진한 엔진은 기꺼이 그렇게 자신을 속인다.

2. 어떻게 속는가[편집]

전형적인 시나리오는 이렇다. 엔진이 곧 퀸을 잃을 운명인데, 마침 상대 왕을 계속 체크할 수단이 있다고 하자. 엔진은 의미 없는 연속 체크를 퍼부어 퀸을 잃는 순간을 한 수, 또 한 수 뒤로 미룬다. 각 체크가 탐색 깊이를 한 칸씩 잡아먹으므로, 결국 “퀸을 잃는 그 수”가 깊이 한계 바깥으로 밀려난다. 지평선 안에서 보면 엔진은 여전히 퀸을 쥐고 있으니 국면 평가는 멀쩡하다. 실제로는 체크를 헛되이 낭비하며 국면만 더 망친 채, 정확히 같은 파멸을 향해 걸어가고 있다.²

핵심은 평가가 특정 깊이에서 칼같이 잘린다는 데 있다. 그 절단면 위의 정적 평가함수는 “지금 이 순간 말 개수·위치”만 보므로, 바로 다음 수에 판이 뒤집힌다는 사실을 반영하지 못한다. 탐색을 아무리 깊게 해도 지평선은 그저 더 멀리 갈 뿐, 없어지지는 않는다.

3. 완화 기법[편집]

지평선 효과는 완전히 없앨 수는 없어도 크게 억누를 수 있다. 실전 엔진이 쓰는 대표적 처방은 다음과 같다.

정적 탐색(quiescence search): 명목 깊이 한계에 도달해도 곧장 평가하지 않고, 잡기·체크처럼 국면을 뒤흔드는 “시끄러운” 수가 남아 있는 한 그 갈래만 계속 파고들어 국면이 “조용해질”(quiet) 때까지 탐색을 연장한다. 지평선 바로 너머의 폭발적 교환을 미리 정산해버리는 셈이라, 지평선 효과의 가장 직접적인 해독제다.³
반복 심화(iterative deepening) + 수순 정렬(move ordering): 깊이를 1, 2, 3… 으로 점점 늘려가며 얕은 탐색 결과로 유망한 수를 먼저 보게 정렬한다. 알파-베타 가지치기 효율을 끌어올려, 같은 시간에 더 깊이 봄으로써 지평선을 밀어낸다.
탐색 연장(search extension): 체크가 걸린 국면 등 위험 신호가 있는 갈래는 깊이를 추가로 더 준다. “위험한 곳은 더 깊이 보라”는 상식의 코드화다.

4. MCTS와의 대조[편집]

몬테카를로 트리 탐색(MCTS)은 고정 깊이 미니맥스와 같은 방식의 지평선 문제를 같은 형태로는 겪지 않는다. MCTS는 모든 갈래를 정해진 수(ply)에서 칼같이 자르고 정적 평가함수로 값을 매기는 대신, 유망한 갈래를 선택적으로 게임 끝(혹은 훨씬 깊은 곳)까지 시뮬레이션으로 굴려 통계를 쌓는다. 그래서 “깊이 한계 바로 너머의 재앙”이라는 고정 지평선 자체가 흐릿해진다.

다만 MCTS가 모든 지평선류 문제에서 면역이라고 과장하면 안 된다. MCTS에는 자기만의 사각지대가 있다. 통계적 표본추출에 의존하는 탓에, 드물지만 결정적인 한 수(예: 좁은 외통 경로)를 충분히 표집하지 못하면 그 갈래를 과소평가하고 지나칠 수 있다. 이것도 결국 “탐색 예산이 특정 결정적 갈래를 못 비춘다”는 점에서 지평선 효과와 사촌뻘인 실패다 — 다만 원인이 깊이 절단이 아니라 표본 배분이라는 점이 다르다.⁴

5. 여담 — 지평선 너머 던지기[편집]

지평선 효과의 얄궂은 변종으로, 엔진이 나쁜 결과를 지평선 밖으로 미룰 뿐 아니라 아예 더 큰 손해를 무릅쓰고 작은 손해를 지평선 너머로 밀어내는 경우가 있다. 예컨대 곧 잃을 폰을 지키겠다고 그보다 값진 말을 헌납하는 식이다. 지평선 안의 평가함수는 “폰을 지켰다”는 국소적 이득만 보고 흡족해하지만, 판 전체로는 재앙이다. 인간 초보가 “당장 눈앞의 손해만 막으려다 판을 그르치는” 실수와 심리적으로 똑같아서, 지평선 효과는 기계의 근시안을 보여주는 대표 사례로 자주 인용된다.

6. 관련 문서[편집]

이 용어는 1970년대 체스 프로그래밍 문헌에서 자리 잡았다. 한스 벌리너 등이 초기 탐색기의 이 병리를 명확히 지적했고, 이후 모든 진지한 게임 엔진이 이걸 다루지 않고는 강해질 수 없다는 게 상식이 되었다. ↩
그래서 “체크는 공짜 텀포”라는 격언은 인간에게만 유효하다. 순진한 엔진에게 연속 체크는 파멸을 지평선 밖으로 밀어내는 마약이나 다름없다 — 잠깐 기분은 좋지만 국면은 더 망가진다. ↩
정적 탐색이 없으면 엔진은 “교환 한복판”에서 평가를 멈추는 참사를 저지른다. 상대가 방금 내 퀸을 잡았는데 내가 되잡기 직전에 탐색을 끊으면, 평가함수는 “퀸 하나 손해”로 기록한다. 되잡으면 본전인데도. 그래서 quiescence는 옵션이 아니라 필수다. ↩
알파고류가 정책·가치망으로 갈래 선택과 국면 평가를 학습해 이 표집 편향을 상당히 눌렀지만, “충분히 안 본 결정적 갈래는 여전히 놓칠 수 있다”는 근본 한계는 남는다. 탐색은 결국 유한한 예산을 어디에 쓸지의 문제이고, 공짜 점심은 여기에도 없다. ↩