미니맥스 알고리즘

게임 개발 마지막 수정: 2026-07-21 05:07:21

1. 개요[편집]

미니맥스 알고리즘 Minimax Algorithm
분야	게임 AI × 적대적 탐색(adversarial search)
전제	완전 정보, 제로섬, 턴제 2인 게임
핵심 가지치기	알파-베타 가지치기
대표 사례	체스, 체커, 오목, 커넥트4
후계	몬테카를로 트리 탐색(MCTS)

미니맥스 알고리즘(minimax algorithm)은 두 플레이어가 번갈아 두며 한쪽의 이득이 곧 다른 쪽의 손해가 되는(제로섬) 턴제 게임에서, “나는 점수를 최대화하려 하고 상대는 나를 최소화하려 한다”는 가정 아래 게임 트리를 끝까지 — 또는 정해진 깊이까지 — 탐색해 최선의 수를 고르는 탐색 알고리즘이다.

행동 트리나 유틸리티 AI가 실시간 액션 게임에서 NPC 한 명의 행동을 매 프레임 고르는 도구라면, 미니맥스는 체스나 오목처럼 완전 정보(perfect information)를 가진 턴제 대결형 게임에서 “상대도 최선을 다한다”는 전제 아래 수학적으로 최적인 수를 계산하는 완전히 다른 문제를 푼다. 실시간 게임 AI가 “그럴듯한 행동”을 빠르게 고르는 것과 달리, 미니맥스는 시간과 메모리만 충분하면 이론상 완벽한 정답을 낸다는 점이 핵심 차별점이다.

2. 게임 트리와 기본 알고리즘[편집]

게임의 상태를 노드로, 가능한 수를 자식 간선으로 표현하면 게임 트리가 된다. 내 차례인 노드는 MAX 노드로 자식 중 가장 큰 값을 택하고, 상대 차례인 노드는 MIN 노드로 가장 작은 값을 택한다. 말단(게임 종료 또는 탐색 한계)에서는 평가 함수로 값을 매긴다.

\text{minimax}(s) = \begin{cases} \text{eval}(s) & s\text{가 말단}\\ \max_{a} \text{minimax}(\text{result}(s, a)) & s\text{가 MAX 차례}\\ \min_{a} \text{minimax}(\text{result}(s, a)) & s\text{가 MIN 차례} \end{cases}

이 재귀를 리프까지 전부 계산한 뒤 값을 거슬러 올리면, 루트에서 어느 수를 택해야 하는지가 정해진다. 분기 계수(branching factor)가 $b$ , 탐색 깊이가 $d$ 라면 전체 탐색 비용은 $O(b^d)$ 다. 체스는 $b \approx 35$ 수준이라 몇 수만 내다봐도 트리가 천문학적으로 커진다.

3. 평가 함수와 깊이 제한 탐색[편집]

게임 종료까지 트리를 전부 펼치는 건 체스·바둑 규모에서는 불가능하다. 그래서 실무에서는 정해진 깊이까지만 탐색하고, 거기서 게임이 끝나지 않았어도 평가 함수(evaluation function)로 그 국면의 유불리를 점수화한다. 체스라면 기물 점수 합, 위치 테이블, 킹 안전성 같은 요소를 가중합해 하나의 숫자로 뭉갠다.

문제는 딱 정해진 깊이에서 자른 국면이 사실 격변의 문턱일 수 있다는 점이다. 예컨대 다음 수에 내 퀸이 잡히기 직전인데 탐색이 거기서 멈추면, 평가 함수는 이 위험을 전혀 모른 채 좋은 점수를 매긴다. 이 문제를 완화하려면 “조용해질 때까지” 몇 수 더 파고드는 조치가 필요하다.

4. 알파-베타 가지치기[편집]

미니맥스의 실전 성능을 결정짓는 것이 알파-베타 가지치기(alpha-beta pruning)다. 탐색 도중 “이 가지를 더 파봐야 지금까지 찾은 최선의 대안보다 나을 수 없다”는 게 확정되는 순간, 나머지 자식들을 아예 펼쳐보지도 않고 잘라낸다.

구체적으로는 MAX 노드가 지금까지 확보한 최선값 $\alpha$ 와, MIN 노드가 지금까지 확보한 최선값 $\beta$ 를 재귀 호출 전체에 걸쳐 실어 나른다. 탐색 도중 어느 노드에서든 $\alpha \geq \beta$ 가 성립하면, 그 아래를 더 탐색해 봐야 부모의 선택에 영향을 줄 수 없다는 뜻이므로 즉시 가지치기한다.

가지치기 효과는 수 순서(move ordering)에 크게 좌우된다. 최선의 수를 먼저 시도할수록 잘라낼 수 있는 가지가 많아지며, 이상적인 순서에서는 탐색 복잡도가 $O(b^d)$ 에서 $O(b^{d/2})$ 로 떨어진다 — 사실상 같은 시간에 탐색 깊이를 두 배로 늘리는 것과 같은 효과다. 그래서 실전 체스 엔진은 반복 심화(iterative deepening)로 얕은 탐색의 결과를 힌트 삼아 깊은 탐색의 수 순서를 정하는 전략을 필수로 쓴다.¹

5. 게임 이론적 기반과 한계[편집]

미니맥스는 특정 게임에서만 통하는 임기응변이 아니라, 폰 노이만이 증명한 게임 이론의 미니맥스 정리에 뿌리를 둔다. 완전 정보·제로섬·유한 게임이라면 미니맥스 전략이 최적이라는 것이 수학적으로 보장된다.

다만 이 보장은 전제 조건이 깨지면 함께 무너진다. 카드 게임처럼 상대의 패를 모르는 불완전 정보 게임, 주사위가 낀 확률적 게임에는 순수한 미니맥스가 바로 적용되지 않는다. 확률적 게임에는 확률 노드를 추가한 엑스펙티미니맥스(expectiminimax) 변형이 쓰이고, 불완전 정보 게임은 아예 다른 이론 틀(베이지안 게임, 반사실 후회 최소화 등)로 넘어간다.

6. 몬테카를로 트리 탐색으로의 진화[편집]

체스의 분기 계수 35는 그럭저럭 버틸 만하지만, 바둑은 분기 계수가 약 250에 달한다. 여기에 “좋은 수인지 나쁜 수인지” 판단할 믿을 만한 평가 함수를 손으로 짜는 것 자체가 사실상 불가능하다는 문제까지 겹친다. 미니맥스와 알파-베타만으로는 도저히 승산이 없는 영역이다.

이 벽을 넘은 것이 몬테카를로 트리 탐색(MCTS)이다. 트리를 균등하게 전개하는 대신 유망한 가지를 선택적으로 더 깊이 파고들고, 말단 평가 대신 게임 끝까지 무작위(또는 정책망 기반) 플레이아웃을 굴려 승률을 추정한다. 몬테카를로 방법의 표본화 아이디어를 게임 트리 탐색에 이식한 셈. AlphaGo가 MCTS에 심층신경망 평가 함수를 결합해 이세돌을 이긴 사건은, “손으로 짠 평가 함수 + 완전 탐색”이라는 미니맥스 시대의 접근이 학습된 평가 + 선택적 탐색”으로 세대교체됐음을 상징적으로 보여줬다.² 다만 체스처럼 분기 계수가 감당할 만하고 평가 함수가 잘 정의된 게임에서는 알파-베타 미니맥스 기반 엔진이 여전히 최상급 성능을 낸다는 점도 기억해 둘 만하다.³

7. 관련 문서[편집]

알파-베타 가지치기는 1950~60년대에 여러 연구자가 독립적으로 재발견한 아이디어로 알려져 있다. 존 매카시가 1956년경 이미 착안했다는 기록도 있는데, 같은 발상이 여러 곳에서 동시다발적으로 떠올랐다는 건 그만큼 “당연히 필요한” 최적화였다는 뜻이기도 하다. ↩
1997년 딥블루가 카스파로프를 이긴 것은 미니맥스 + 알파-베타 + 방대한 오프닝북 + 전용 하드웨어의 승리였다. 2016년 알파고가 이세돌을 이긴 건 MCTS + 신경망의 승리였다. 두 사건 사이 약 20년의 간극이, 딱 “완전 탐색이 통하는 게임”과 “안 통하는 게임”의 경계선이었던 셈. ↩
“지평선 효과”라는 말 자체가 은유적으로 딱 맞다. 산 너머에 뭐가 있는지 안 보이는 것처럼, 탐색 깊이라는 지평선 너머에서 벌어질 재앙을 엔진이 못 보고 낙관적인 수를 두는 것. 체스 엔진이 갑자기 기물을 헐값에 내주는 이상한 수를 두면, 십중팔구 이 지평선 효과가 범인이다. ↩