알파-베타 가지치기 (alpha-beta pruning)
한 줄 정의: 결과에 영향을 줄 수 없는 게임 트리 가지를 건너뛰어 탐색량을 줄이는 기법입니다.
쉽게 풀면
게임 트리를 뒤지다 보면 “이 가지는 아무리 좋아 봐야 이미 찾은 수보다 나을 수 없다”는 판단이 서는 순간이 옵니다. 그러면 그 아래를 더 볼 필요가 없으니 통째로 잘라 냅니다. 최종 선택은 전부 뒤졌을 때와 완전히 동일하면서 계산량만 줄어드는, 손해가 전혀 없는 최적화입니다.
왜 중요한가
미니맥스 탐색의 지수적 비용을 실용 가능한 수준으로 낮춘 결정적 기법으로, 같은 시간에 두 배 가까운 깊이를 볼 수 있게 해 줍니다. 체스 엔진이 사람을 이기게 된 배경에는 이 가지치기와 수 순서 정렬 기법의 결합이 있었습니다. 탐색 알고리즘에서 정확성을 유지하면서 효율을 얻는 모범 사례로 자주 인용됩니다.
논문에서는 이렇게 쓰입니다
"수 순서 정렬과 함께 알파-베타 가지치기를 적용하자 동일한 최적 수를 유지하면서 탐색 노드 수가 87% 감소하였다."
결과는 그대로인 채 살펴본 경우의 수만 크게 줄었다는 뜻입니다.
조금 더 깊게 보면
탐색 중 현재까지 보장된 최댓값 α와 최솟값 β를 들고 다니다가 α가 β 이상이 되는 순간 남은 형제 노드를 잘라 냅니다. 가지치기의 효과는 좋은 수를 먼저 탐색할수록 커지며, 이상적인 순서로 정렬되면 탐색 노드 수가 제곱근 수준으로 줄어 같은 시간에 약 두 배 깊이를 탐색할 수 있습니다. 실전 엔진은 반복 심화와 전치표 같은 캐시, 킬러 무브 휴리스틱을 결합해 수 순서를 개선합니다.
주의할 점
모델 프루닝이 신경망의 연결을 실제로 제거해 근사 오차를 감수하는 압축 기법인 데 비해, 알파-베타 가지치기는 탐색 결과를 전혀 바꾸지 않는 정확한 최적화입니다. 최적 수만 같을 뿐 잘린 가지의 정확한 값은 계산되지 않는다는 점은 유의해야 합니다.