최소극대화(MiniMax)
최적의 수를 선택하는 게임 AI의 핵심 전략
#️⃣ 들어가며
체스, 틱택토, 오목과 같은 턴제 전략 게임에서는 플레이어가 선택할 수 있는 모든 경우를 고려하여 최적의 수를 두는 것이 중요하다. 이러한 결정 과정을 효율적으로 수행하기 위해 사용하는 알고리즘이 바로 최소극대화(Minimax) 알고리즘이다. 최소극대화(Minimax)는 상대가 최선을 다할 것이라고 가정하고, 그 상황에서도 내가 최선을 선택할 수 있도록 해주는 전략으로, 인공지능 분야에서도 기본이 되는 핵심 알고리즘 중 하나이다.
1️⃣ 최소극대화 (Minimax)
📌 정의
최소극대화(Minimax)는 두 명의 플레이어가 번갈아 가며 게임을 진행할 때, 각 플레이어가 자신의 이득을 최대화(maximize)하려 하고, 상대의 이득은 최소화(minimize)하려 한다고 가정하고 게임 트리(Game Tree)를 구성한다. 트리의 말단 노드(Leaf Node)는 각 행동을 수행했을 때의 평가 점수 (Utility Value)를 가지고 있고, 각 노드에서는 그 점수를 바탕으로 자식 노드 중 최선의 값을 선택한다.
- MAX : 자신의 점수를 최대화
- MIN : 상대의 점수를 최소화 (즉, MAX의 손해를 극대화)
🔨 구현 예제
#include <vector>
#include <limits>
const int INF = std::numeric_limits<int>::max();
struct Node
{
std::vector<Node*> children;
int value; // Leaf Node라면 평가 점수, 그렇지 않은 경우 무시함
bool is_terminal;
};
int minimax(Node* node, int depth, bool is_maximizing_player)
{
if (node->is_terminal || depth == 0) return node->value;
if (is_maximizing_player)
{
int best = -INF;
for (Node* child : node->children)
{
int val = minimax(child, depth - 1, false);
best = std::max(best, val);
}
return best;
}
else
{
int best = INF;
for (Node* child : node->children)
{
int val = minimax(child, depth - 1, true);
best = std::min(best, val);
}
return best;
}
}
2️⃣ 알파-베타 가지치기 (Alpha-Beta Pruning)
최소극대화의 단점은 모든 경우의 수를 탐색하기 때문에 매우 느릴 수 있다는 점이다. 이를 해결하기 위해 알파-베타 가지치기(Alpha-Beta Pruning)라는 기법을 사용한다.
📌 정의
알파-베타 가지치기(Alpha-Beta Pruning)은 최소극대화(Minimax)의 성능을 향상시키기 위한 최적화 기법으로, 더 이상 유망하지 않은 가지는 탐색하지 않고 잘라내는 방식으로 작동한다.
- 좌측 MIN의 자식 5, 6 중 더 작은 5를 선택.
- 이후, 우측 MIN에서 자식 4까지 탐색.
- 그 다음 자식 노드를 탐색할 때,
- 4보다 큰 숫자가 나올 경우 : 최솟값을 선택해야 하므로 선택하지 않음.
- 4보다 작은 숫자가 나올 경우 : 0(max)에서 최댓값을 선택해야 하므로 좌측 MIN의 결과인 5를 선택.
- 따라서 굳이 탐색할 필요가 없는 가지이므로 탐색을 진행하지 않음.
이와 같이 현재까지의 최대/최소 값을 기준으로 남은 분기를 탐색하지 않아도 되는 상황이 발생하며, 이를 가지치기(pruning)라고 한다.
💡 핵심 아이디어
알파-베타 가지치기(Alpha-Beta Pruning)의 핵심은 필요없는 분기를 미리 배제함으로써 탐색 범위를 줄이는 것이다. 이를 위해 두 가지 값을 유지한다.
- Alpha : MAX가 현재까지 선택한 최댓값
- Beta : MIN이 현재까지 선택한 최솟값
트리를 탐색하면서 MAX는 Alpha 값을 갱신하고, MIN은 Beta 값을 갱신한다. 이후 Beta $\leq$ Alpha가 되는 시점부터 해당 노드의 탐색을 중지한다. 이 과정을 통해 전체 탐색 트리 중 많은 부분을 스킵할 수 있고, 시간 복잡도는 $O(b^{d \ / \ 2})$까지 개선할 수 있다. ($b$ : branching factor, $d$ : depth)
🔨 구현 예제
int alphabeta_minimax(Node* node, int depth, int alpha, int beta, bool is_maximinzing_player)
{
if (node->is_terminal || depth == 0) return node->value;
if (is_maximizing_player)
{
int max_eval = -INF;
for (Node* child : node->children)
{
int eval = alphabeta_minimax(child, depth - 1, alpha, beta, false);
max_eval = std::max(max_eval, eval);
alpha = std::max(alpha, eval);
if (beta <= alpha) break; // 가지치기
}
return max_eval;
}
else
{
int min_eval = INF;
for (Node* child : node->children)
{
int eval = alphabeta_minimax(child, depth - 1, alpha, beta, true);
min_eval = std::min(min_eval, eval);
beta = std::min(beta, eval);
if (beta <= alpha) break; // 가지치기
}
return min_eval;
}
}