알파-베타 가지치기

알파-베타 가지치기는 수와 응수를 비교하는 프로그램인 체스 엔진의 탐색을 빠르게 한다. 탐색은 트리로 생각할 수 있다. 각 노드는 포지션이고 각 가지는 합법적인 수다. 가지치기가 없다면 프로그램은 결국 관련이 없다고 판명될 많은 변형을 살펴봐야 한다.

이 방법은 탐색 중 두 개의 경계를 유지한다. 알파는 현재 경로에서 한쪽이 이미 보장할 수 있는 최선의 결과다. 베타는 상대에게 이미 가능한 대안이 만들어 놓은 한계다. 어떤 변형이 합리적인 선수라면 절대 선택하지 않을 만큼 나쁘다는 사실이 확인되면, 그 변형을 더 깊이 탐색해도 상위 노드의 결정을 바꿀 수 없다.

가지는 단지 수가 보기 나빠서가 아니라 트리 안의 논리적 경계 때문에 중단된다. 같은 깊이와 탐색 한계에서 같은 평가값을 사용하면, 알파-베타는 양쪽이 최선의 응수를 둔다고 가정하는 완전 탐색과 같은 선택을 반환한다.

절약되는 양은 수의 순서에 크게 좌우된다. 강한 수를 먼저 시험하면 유용한 경계를 더 일찍 세울 수 있어 더 많은 가지를 깊이 살피지 않고 멈출 수 있다. 포지션에 수치 추정값을 부여하는 평가 함수가 유한 탐색이 끝나는 지점의 값을 제공한다.