Minimax 알고리즘과 알파-베타 가지치기
Minimax 알고리즘이란?
체스, 오목, 틱택토와 같은 1:1 턴제 게임에서 쉽게 적용할 수 있는 트리 구조의 알고리즘입니다. Minimax 알고리즘에서는 상대방이 항상 최고의 선택을 한다고 가정합니다. 하지만 컴퓨터는 게임의 흐름을 읽을 수 없기 때문에, 평가 규칙을 만들어 게임의 현재 상태를 절대적인 수치로 나타내주어야 합니다. 일반적으로는 AI가 유리하면 큰 점수, 상대가 유리하면 작은 점수가 되도록(상대가 유리하다는 것은 AI에게는 불리한 상태이기 때문) 평가 규칙을 정해줍니다. 지금 상태에서 모든 다음 수를 평가하고, 그 중 가장 높은 점수를 내는 수를 찾아가도록 해줍니다.
하지만 실제 게임에서는 AI가 선택할 수 있는 수들이 너무 많기 때문에, 불필요한 연산을 가지치기 하듯이 버려주어야 합니다. 이것이 알파-베타 가지치기입니다.
알파-베타 가지치기
기본 Minimax 알고리즘에서는 모든 노드를 방문해서 평가해야 하지만, 실제로는 평가하지 않아도 확정되는 부분이 존재합니다. 알파 값은 상위 상태들 중에서 AI에게 가장 유리한 상태의 점수를 말하고(최대값), 베타 값은 상위 상태들 중에서 상대방에서 가장 유리한 상태의 점수(최소값)를 의미합니다.
따라서 이전 상태들 중에서,
상대방에게 가장 유리한 점수 기준으로 가지치기를 하는 것을 알파 컷이라고 하고,
AI에게 가장 유리한 점수 기준으로 가지치기를 하는 것을 베타 컷이라고 합니다.
알파-베타 가지치기의 수도코드입니다.
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
Plain Text
복사
출처 : 위키피디아
