Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 게임 이론: 알파-베타 가지치기(Alpha-Beta Pruning)로 최적화한 미니맥스 알고리즘

알파-베타 가지치기란 무엇인가?

알파-베타 가지치기(Alpha-Beta Pruning)는 미니맥스(Minimax) 알고리즘의 탐색 성능을 크게 향상시키는 대표적인 최적화 기법입니다. 핵심 아이디어는 매우 단순합니다. 이미 더 좋은 수가 존재한다고 판단되는 게임 트리의 가지(branch)는 굳이 끝까지 평가하지 않고 탐색 자체를 중단하는 것입니다.

이 알고리즘은 탐색 과정에서 다음 두 가지 값을 함께 관리합니다.

  • Alpha(알파) – 최대화 플레이어(Maximizer)가 현재 레벨 또는 그보다 위 레벨에서 보장할 수 있는 최선의 값(최댓값)
  • Beta(베타) – 최소화 플레이어(Minimizer)가 현재 레벨 또는 그보다 위 레벨에서 보장할 수 있는 최선의 값(최솟값)

탐색 도중 beta <= alpha 조건이 만족되면, 해당 하위 트리에는 최종 결과에 영향을 주는 수가 없다고 확신할 수 있으므로 즉시 가지치기를 수행합니다. 덕분에 동일한 결과를 얻으면서도 탐색해야 할 노드의 수를 크게 줄일 수 있습니다.

예제 문제

다음과 같은 리프 노드 값을 갖는 게임 트리가 있다고 가정해 보겠습니다.

arr[] = {13, 8, 24, -5, 23, 15, -14, -20}

최대화 플레이어가 선공이라면, 이 게임 트리에서 얻을 수 있는 최적 값(optimal value)은 13입니다.

알고리즘 동작 과정

1. 게임 트리의 루트(root) 노드에서 DFS(깊이 우선 탐색)를 시작한다.
2. 알파와 베타의 초기값을 설정한다.
   - alpha = INT_MIN (−∞)
   - beta  = INT_MAX (+∞)
3. DFS 방식으로 트리를 순회한다.
   - 최대화 플레이어는 가능한 한 가장 높은 점수를 얻으려 한다.
   - 최소화 플레이어는 가능한 한 가장 낮은 점수를 만들려 한다.
4. 순회 중 조건에 따라 알파와 베타 값을 계속 갱신하며,
   beta <= alpha가 되는 순간 남은 형제 가지들을 잘라낸다(pruning).

C++ 전체 구현 코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int getHeight(int n) {
    return (n == 1) ? 0 : 1 + log2(n / 2);
}

int minmax(int height, int depth, int nodeIndex,
           bool maxPlayer, int values[], int alpha,
           int beta) {
    if (depth == height) {
        return values[nodeIndex];
    }
    if (maxPlayer) { // 최대화 플레이어 차례
        int bestValue = INT_MIN;
        for (int i = 0; i < height - 1; i++) {
            int val = minmax(height, depth + 1, nodeIndex * 2 + i, false, values, alpha, beta);
            bestValue = max(bestValue, val);
            alpha = max(alpha, bestValue);
            if (beta <= alpha)
                break; // 베타 가지치기
        }
        return bestValue;
    } else { // 최소화 플레이어 차례
        int bestValue = INT_MAX;
        for (int i = 0; i < height - 1; i++) {
            int val = minmax(height, depth + 1, nodeIndex * 2 + i, true, values, alpha, beta);
            bestValue = min(bestValue, val);
            beta = min(beta, bestValue);
            if (beta <= alpha)
                break; // 알파 가지치기
        }
        return bestValue;
    }
}

int main() {
    int values[] = {13, 8, 24, -5, 23, 15, -14, -20};
    int height = getHeight(SIZE(values));
    int result = minmax(height, 0, 0, true, values, INT_MIN, INT_MAX);
    cout << "Result : " << result << "\n";
    return 0;
}

위 프로그램을 컴파일하여 실행하면 다음과 같은 출력 결과를 확인할 수 있습니다.

Result : 13

코드 핵심 포인트

  • getHeight() 함수는 리프 노드의 개수로부터 게임 트리의 높이를 계산합니다.
  • minmax() 함수는 재귀적으로 트리를 순회하며, maxPlayer 플래그를 통해 현재 차례가 최대화 플레이어인지 최소화 플레이어인지 구분합니다.
  • 각 자식 노드의 평가가 끝날 때마다 alpha 또는 beta 값을 갱신하고, beta <= alpha 조건이 충족되면 반복문을 종료하여 불필요한 탐색을 건너뜁니다.

참고로 미니맥스 알고리즘만 사용할 때의 시간 복잡도는 O(b^d)(b는 분기 계수, d는 트리의 깊이)이지만, 알파-베타 가지치기를 적용하면 최선의 경우 탐색 노드 수가 크게 감소하여 사실상 O(b^(d/2)) 수준까지 성능이 향상됩니다. 즉, 같은 시간 안에 약 두 배 더 깊은 수준까지 탐색할 수 있다는 의미입니다.