알파-베타 가지치기

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

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

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

분기 계수를 b라고 하고, ply(한 턴의 1/2)의 검색 깊이를 d라고 한다면, (이동순서가 최악이라면) 평가된 잎 노드 위치는 O(b*b*...*b) = O(b**d)이므로 기본적인 미니맥스 검색과 같다. 만약 검색의 이동순서가 최적이라면, 평가된 잎 노드의 수는 홀수 깊이일 때 약 O(b*1*b*1*...*b) 이고, 짝수깊이일 때 O(b*1*b*1*...*1) 즉, O(b**d/2)이다. 후자의 경우 사실상의 분기 계수는 제곱근으로 줄어든다. 다시 말해 같은 양의 연산 작업으로 거의 두 배 만큼 더 깊게 탐색할 수 있다. b*1*b*1... 식의 설명은 최적의 이동을 찾기 위해서는 첫 번째 플레이어의 이동은 반드시 연구돼야 하지만, 사실은 두 번째 플레이어의 최적의 움직임은 첫 번째 플레이어의 첫 번째 움직임을 제외한 모든 움직임을 쳐내기 위해 필요하다. 노드 순서가 랜덤하다면, 평균적으로 평가하는 노드의 수는 약 O(b**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 > β) 반면에 페일 하드 알파-베타는 반환하는 값을 알파와 베타의 범위로 제한한다. ()

각주

참고 문헌 
 
 유디 펄, Heuristics, Addison-Wesley, 1984
 

검색 알고리즘
그래프 알고리즘
게임 인공지능
최적화 알고리즘