MiniMax(미니맥스)는 게임 이론과 인공지능 분야에서 사용되는 결정 규칙·알고리즘으로, 두 명의 완전 정보 제로섬 게임에서 한 플레이어가 자신의 최선의 수를 선택함과 동시에 상대가 자신의 최선의 수를 선택했을 때 자신의 손실을 최소화(또는 이득을 최대화)하도록 하는 전략을 의미한다.
1. 정의
- 미니맥스 원리:
- 플레이어 A(극대화자)가 가능한 모든 수를 고려해 각각의 경우에 대해 상대 플레이어 B(극소화자)가 최선의 반응을 할 때의 결과값(보상)을 계산한다.
- A는 그 중 가장 큰 값을 가진 수를 선택한다(“max”).
- 동시에 B는 A가 선택한 수에 대해 자신이 받을 손실을 최소화하도록 선택한다(“min”).
- 수학적으로는 게임 트리의 리프 노드에 평가값을 부여하고, 내부 노드에서는 자식 노드들의 값을 번갈아가며 max와 min 연산을 적용하여 루트 노드의 값을 결정한다.
2. 역사·배경
| 연도 | 사건 |
|---|---|
| 1944 | 존 폰 노이만이 “미니맥스 정리”(Minimax theorem)를 발표, 두 명의 플레이어가 동시에 행동하는 경우의 최적 전략 존재를 증명 |
| 1950‑60년대 | 체스, 다이아몬드와 같은 보드 게임 인공지능 연구에 미니맥스 알고리즘 적용 시작 |
| 1980년대 | 알파-베타 프루닝(Alpha‑Beta Pruning) 등 효율화 기법이 도입돼 실제 게임 AI에 널리 활용 |
3. 알고리즘 구조
- 게임 트리 생성: 현재 상태에서 가능한 모든 수(자식 노드)를 전개한다.
- 재귀적 평가:
- 깊이가 짝수(극대화 차례)일 때는 자식 노드 값 중 최대값을 반환.
- 깊이가 홀수(극소화 차례)일 때는 최소값을 반환.
- 트리 탐색 제한:
- 깊이 제한(Depth limit): 계산량을 제어하기 위해 탐색 깊이를 제한.
- 평가 함수(Evaluation function): 리프 노드가 아닌 경우 현재 보드 상태에 대한 추정 점수를 반환.
- 프루닝(가지치기): α(최대 하한)와 β(최소 상한) 값을 유지해 더 이상 탐색할 필요가 없는 서브트리를 일찍 삭제(알파‑베타 프루닝).
4. 주요 응용 분야
| 분야 | 구체적 활용 사례 |
|---|---|
| 보드 게임 AI | 체스, 바둑, 리버시, 틱택토 등에서 최적 수 탐색 |
| 전략 시뮬레이션 | 군사·경제 시뮬레이션에서 양측의 최적 행동 예측 |
| 네트워크 보안 | 공격자·방어자 모델링에 미니맥스 기반 전략 분석 |
| 멀티에이전트 시스템 | 경쟁적인 에이전트 간 의사결정 프로토콜 설계 |
| 수학·경제학 | 두 사람 zero‑sum 게임의 균형점(내시 균형) 계산 |
5. 변형·확장 알고리즘
- 알파‑베타 프루닝: 불필요한 노드 탐색을 크게 줄여 시간 복잡도를 O(b^(d/2)) 수준까지 개선.
- 넬소프 프루닝(NegaScout), MT‑Df 등: 알파‑베β와 비슷한 효율성을 가지면서 구현이 간단한 변형.
- 확률적 미니맥스(Expectiminimax): 운(확률) 요소가 있는 게임(주사위, 포커 등)에서 기대값을 고려.
- 다중 목표 미니맥스: 하나 이상의 평가 기준을 동시에 최적화하는 경우에 사용.
6. 구현 시 고려 사항
- 평가 함수 설계: 게임마다 특화된 휴리스틱이 필요하며, 좋은 평가 함수가 성능을 좌우한다.
- 메모리 관리: 재귀 호출 깊이가 깊어질 경우 스택 오버플로우 방지를 위한 반복적 구현 또는 메모리 풀 사용.
- 시간 제한: 실시간 게임에서는 제한된 시간 내에 최선 수를 도출해야 하므로, 깊이 제한과 프루닝 전략을 조절한다.
7. 한계와 비판
- 완전 탐색 불가능: 게임 트리 규모가 기하급수적으로 커서 실제 게임에서는 근사 탐색만 가능.
- 평가 함수 의존: 잘못된 평가 함수는 최적이 아닌 수를 선택하게 만든다.
- 다중 플레이어·비제로섬 게임에 직접 적용하기 어려워 다른 이론(내시 균형, 협력 게임)과 결합이 필요하다.
8. 참고 문헌·외부 링크
- John von Neumann, “Theory of Games and Economic Behavior”, 1944.
- J. R. Brookshire, “Computer Chess Programming”, 1991.
- Norvig, Peter, “Artificial Intelligence: A Modern Approach”, 3rd ed., 2010 (Chapter 5 – Game Playing).
- 《알파‑베타 프루닝: 효율적인 게임 트리 탐색》, 김태현, 2018.
- Wikipedia – Minimax algorithm (영문).
이 항목은 게임 이론·인공지능 분야에서 널리 인정받는 정의와 구현 방법을 기반으로 작성되었으며, 최신 연구 동향을 반영한다.