개인 공부용이라 설명 뒷받침이 부족할 수 있습니다.

아래는 Minimax 알고리즘의 단점을 극복하기 위한 Alpha-Beta 가지치기를 적용한 모습이다.

여기서 Alpha는 자신(AI)에게 유리한(Max), Beta는 상대(사람)에게 유리한(Min) 것을 말한다.

Alpha-cut

(루트노드에서 DFS로 탐색하며 각 노드의 (alpha, Beta)값을 갱신하는 과정을 나타냄)

위 그림에서 핵심은 노드(10)의 왼쪽 자식에서 계산한 값을 갱신한 뒤, (alpha >= Beta)가 되었을 때이다.

이 때는 노드(10)의 오른쪽 자식 노드에 어떤 값이 오든간에 노드(13) 결과에 전혀 영향을 주지 않는다.

자세히 설명하자면, 노드(10)은 AI 기준 자신에게 유리한(Max) 값만을 담는반면 부모 노드(13)에서는 AI 기준 자신에게 불리한(Min) 값만을 담는다.

즉, 노드(10)에서 (alpha >= beta)인 이상 더이상 계산할 필요가 없으므로 가지치기를 하여 불필요한 연산을 제거한다.

의사 코드

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

위키백과 (의사코드)

의사 코드에서 볼 수 있듯이 alpha-cut은 사람에게서 (Min node), Beta-cut은 AI에게서 (Max node) 일어난다.