알파-베타 가지치기

개요

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

알고리즘

알파 베타 가지치기에서 알파는 Maximizing할 노드가 가질 최소한의 값을 말하며 베타는 Minimizing할 노드가 가질 최대한의 값을 말한다. Maximizing단계에서 만약 평가된 값이 알파보다 작으면 무시하며 더이상 그 가지를 치지 않고, Minimizing단계에서 베타보다 값이 크면 그 이후의 가지는 무시해 버린다. 알고리즘의 시작에서, 알파는 -무한대 베타는 +무한대 부터 시작하게 된다. 그리고 각각의 단계에서 현재 평가된 베타값과 알파값을 업데이트하고 가지치기를 수행한다. 최종 결과값이 Player1은 최대가 되도록 하여야 하고 Player2는 최소가 되어야 된다고 하자. Player1과 Player2가 합리적인 상황을 찾는 다면 Player1은 결과 값이 최대가 되도록 Player2는 결과값이 최소가 되도록 움직일 것이다. 알파와 베타는 지금까지 구해논 Player1과 Player2가 가질 수 있는 제일 합당한 선택이다.

<현재 상황> 알파 - player1이 취할 수 있는 최대한의 값 (즉 Maximizing해야할 노드의 최소값) -> 최대가 되어야 승리 베타 - player2가 취할 수 있는 최소한의 값 (즉 Minimizing해야할 노드의 최대값) -> 최소가 되어야 승리

<Player1의 턴일 경우> 만약 알파 값이 베타값보다 커지면, 이 말은 만약 내가 이 노드로 움직인다면 Player2은 반드시 이경로로 갈 것이다. 왜냐하면 내가 지금까지 구해놓은 알파보다 베타가 작아지는 순간이 있기 떄문이다. 즉 이 경로로 가면 Player1이 Player2를 반드시 이기는 경로이다. 즉 Player2는 이 경로로 오지 않을 것이다. 따라서 이 노드 이후는 제거한다. 이를 Alpha-cut off라고 한다. 내가 지는 확실한 경로는 계산하지 않는다.

<Player2의 턴일 경우> 만약 알파 값이 베타값보다 커지면, 일 말은 내가 이 노드로 움직이면 Player2는 반드시 Player1를 이기는 경로인 것이다. 따라서 이 내가 이 쪽으로 가지 못하도록 Player1은 반대로 움직일 것이다. 따라서 이 경로는 생각할 필요가 없다. 이를 Beta-cut off라고 한다. 즉 상대방을 이기게 하는 경로로는 절대 가지 않는 것을 말한다.

http://egloos.zum.com/musicdiary/v/4274653

의사 코드

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if α ≥ β then
                break (* β cutoff *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if β ≤ α then
                break (* α cutoff *)
        return value