알파-베타 가지치기

분류	검색 알고리즘
최악 시간복잡도	${\displaystyle O(b^{d})}$
최선 시간복잡도	${\displaystyle O\left({\sqrt {b^{d}}}\right)}$

알파-베타 가지치기(Alpha–beta pruning)는 탐색 트리에서 최소극대화(미니맥스) 알고리즘을 적용할 때 평가(evaluate)하는 노드의 수를 줄이기 위한 알고리즘이다. 이 알고리즘은 적대탐색 알고리즘의 일종으로, 기계가 플레이하는 2인용 게임(틱택토, 체스, 바둑)에 주로 사용된다. 이 알고리즘은 이전에 평가한 노드보다 현재 평가하는 노드가 더 좋지 않을 가능성이 존재하면 평가를 중단한다. 이 노드의 남은 형제(sibling) 노드와 모든 후손 노드는 가지치기되어 평가하지 않는다. 이 알고리즘을 일반적인 미니맥스에 적용하면 동일한 결과를 얻게 된다. 최종 결정에 영향을 미치지 않는 가지들을 쳐낼 뿐이다.^[1]

앨런 뉴얼과 허버트 사이먼에 따르면 1958년 당시에도 알파-베타는 여러 번 재발명되었다.^[2] 아서 새뮤얼(Arthur Samuel)이 알파-베타 프루닝의 초기 버전을 발표했고, Richards, Hart, Levine, Edwards는 미국에서 독립적으로 알파-베타 가지치기의 기초를 세웠다.^[3] 존 매카시도 비슷한 아이디어를 1956 다트머스 회의에서 제안하면서 "근사치"^[4]라는 용어를 사용했고, 1961년에 MIT에 다니는 앨런 코톡(Alan Kotok)에게도 가르쳤다.^[5] Alexander Brudno도 1963년에 독자적으로 발표하였다.^[6] 도널드 커누스와 로널드 W. 무어는 1975년에 알고리즘을 재정립하였고,^[7] 1982년 유디 펄이 이 방법이 최적임을 증명하였다.

알파-베타 가지치기의 장점은 탐색 트리의 가지를 쳐낼 수 있다는 점이다. 이러한 경우 탐색은 ‘더 유망한’ 서브트리에 한해서 이루어지고, 같은 시간 안에 더 깊은 노드까지 탐색할 수 있다. 알파-베타 가지치기는 분기 한정법의 일종이다. 노드가 최적 또는 최적에 가까운 순서대로 평가된다면, 탐색 깊이가 기본적인 미니맥스의 반 정도가 되도록 최적화할 수 있다.

분기 계수를 b라고 하고, 검색 깊이를 d라고 한다면, (이동순서가 최악이라면) 평가된 잎 노드 위치는 ${\displaystyle O(b\times b\times \cdots \times b)=O(b^{d})}$이므로 기본적인 미니맥스 검색과 같다. 만약 검색의 이동순서가 최적이라면, 평가된 잎 노드의 수는 홀수 깊이일 때 약 ${\displaystyle O(b\times 1\times b\cdots \times b),}$ 즉 ${\displaystyle O(b^{\frac {d}{2}})}$이고, 짝수깊이일 때 ${\displaystyle O(b\times 1\times b\cdots \times 1)}$ 즉, ${\displaystyle O(b^{\frac {d}{2}})}$이다. 후자의 경우 사실상의 분기 계수는 제곱근으로 줄어든다. 다시 말해 같은 양의 연산 작업으로 거의 두 배 만큼 더 깊게 탐색할 수 있다. ${\displaystyle b\times 1\times b\cdots }$ 식의 설명은 최적의 이동을 찾기 위해서는 첫 번째 플레이어의 이동은 반드시 연구돼야 하지만, 사실은 두 번째 플레이어의 최적의 움직임은 첫 번째 플레이어의 첫 번째 움직임을 제외한 모든 움직임을 쳐내기 위해 필요하다. 노드 순서가 랜덤하다면, 평균적으로 평가하는 노드의 수는 약 ${\displaystyle O(b^{\frac {3d}{4}})}$이다.

알파-베타 가지치기의 페일 소프트(fail-soft) 버전 의사코드는 다음과 같다:

01 function alphabeta(node, depth, α, β, maximizingPlayer)
02      if depth = 0 or node is a terminal node
03          return the heuristic value of node
04      if maximizingPlayer
05          v := -∞
06          for each child of node
07              v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
08              α := max(α, v)
09              if β ≤ α
10                  break (* β cut-off *)
11          return v
12      else
13          v := ∞
14          for each child of node
15              v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
16              β := min(β, v)
17              if β ≤ α
18                  break (* α cut-off *)
19          return v

페일 소프트 알파-베타에서는 알파와 베타값 범위를 넘는 v값을 반환할 수 있다. (v < α or v > β) 반면에 페일 하드 알파-베타는 반환하는 값을 알파와 베타의 범위로 제한한다. (${\displaystyle \alpha \leq v\leq \beta }$)

• 최소극대화
• 분기 한정법
• 조합 최적화

• George T. Heineman, Gary Pollice, and Stanley Selkow (2008). 〈Chapter 7: Path Finding in AI〉. 《Algorithms in a Nutshell》. 오라일리 미디어. 217–223쪽. ISBN 978-0-596-51624-6.  CS1 관리 - 여러 이름 (링크)
• 유디 펄, Heuristics, Addison-Wesley, 1984
• John P. Fishburn (1984). 〈Appendix A: Some Optimizations of α-β Search〉. 《Analysis of Speedup in Distributed Algorithms (revision of 1981 PhD thesis)》. UMI Research Press. 107-111쪽. ISBN 0-8357-1527-2.