미니맥스 알고리즘

Minimax algorithm; 미니맥스 알고리즘, 최소최대 알고리즘
두 사람이 번갈아 두는 게임에서 상대가 최선을 다한다고 가정하고, 내가 받을 수 있는 최악의 결과를 가장 좋게 만드는 수를 고르는 탐색 알고리즘

미니맥스 알고리즘은 틱택토, 체스, 오목처럼 두 사람이 번갈아 두고, 한쪽의 이득이 곧 다른 쪽의 손해인 게임(2인 제로섬 완전 정보 게임)에서 최선의 수를 찾는 방법이다. 나는 점수를 최대화(max)하고 상대는 그 점수를 최소화(min)한다고 보고, 게임 트리를 끝에서부터 거꾸로 계산해 올라간다. 이름은 "상대가 나에게 줄 수 있는 최대 손실을 최소화한다"는 뜻에서 왔다.

미니맥스 자체는 단순하지만, 실제 게임은 경우의 수가 너무 많아 그대로 쓸 수 없다. 그래서 평가 함수로 깊이를 제한하고, 결과를 바꾸지 않으면서 볼 필요 없는 가지를 잘라내는 알파-베타 가지치기를 함께 쓴다. 이 조합은 1950년대부터 컴퓨터 체스의 기본 틀이었고, 1997년 IBM 딥 블루가 세계 챔피언을 이긴 것도 이 방식이었다. 바둑처럼 경우의 수가 훨씬 많은 게임에서는 몬테카를로 트리 탐색이 이를 대신했다.

게임 트리

게임 트리는 게임의 상태를 노드로, 수(move)를 간선으로 나타낸 트리다. 루트는 현재 국면이고, 자식 노드는 한 수를 둔 뒤의 국면이며, 잎 노드는 게임이 끝난 국면(승, 패, 무승부)이다. 한 사람이 한 번 두는 것을 1플라이(ply)라 한다.

분기 계수(branching factor) $b$ : 한 국면에서 둘 수 있는 수의 평균 개수. 체스는 약 35, 바둑은 약 250으로 알려져 있다.
탐색 깊이 $d$ : 앞을 내다보는 플라이 수
살펴볼 노드 수: 약 $b^{d}$ . 깊이가 하나 늘 때마다 $b$ 배로 늘어난다.

미니맥스

정의

MAX(나)와 MIN(상대)이 번갈아 둘 때, 국면 $s$ 의 미니맥스 값은 다음과 같이 재귀적으로 정의한다.

$MINIMAX (s) = {\begin{matrix} UTILITY (s) & s 가 종료 국면 \\ \max_{a} MINIMAX (RESULT (s, a)) & MAX의 차례 \\ \min_{a} MINIMAX (RESULT (s, a)) & MIN의 차례 \end{matrix}$

잎 노드에 승리 +1, 패배 -1, 무승부 0 같은 값을 매기고, MIN 노드는 자식 중 최솟값을, MAX 노드는 자식 중 최댓값을 위로 올린다. 루트에서 값이 가장 큰 자식으로 가는 수가 최선의 수다. 이렇게 끝에서부터 거꾸로 푸는 방식은 게임 이론의 역진 귀납법(backward induction)과 같다.

예

깊이 2의 트리에서 MAX가 수 A, B, C 중 하나를 고른다고 하자. 각 수 뒤에 MIN이 고를 수 있는 결과 점수가 다음과 같다.

MAX의 수	MIN이 고를 수 있는 결과	MIN이 고르는 값(최솟값)
A	3, 12, 8	3
B	2, 4, 6	2
C	14, 5, 2	2

MAX는 세 값 3, 2, 2 중 최댓값인 3을 주는 A를 고른다. C에는 14라는 큰 점수가 있지만, 상대가 최선을 다하면 2밖에 얻지 못한다. 미니맥스는 상대의 실수를 기대하지 않는 보수적인 선택을 한다.

성질

완전성: 트리가 유한하면 반드시 답을 낸다.
최적성: 상대도 최선을 다한다는 가정 아래 최적이다. 상대가 실수하면 그 실수를 이용하는 더 좋은 수가 있을 수 있다.
시간 복잡도 $O (b^{d})$ , 공간 복잡도 $O (b d)$ (깊이 우선으로 탐색할 때). 깊이 우선 탐색과 같은 순서로 노드를 방문한다.

이론적 배경

존 폰 노이만은 1928년 2인 제로섬 게임에서 두 참가자가 각자 최적 전략을 쓰면 "내가 보장받을 수 있는 최대 이득"과 "상대가 나에게 허용하는 최소 손실"이 같아진다는 미니맥스 정리를 증명했다. 동시에 수를 내는 게임은 혼합 전략(확률적 선택)까지 허용해야 이 정리가 성립하고, 번갈아 두는 완전 정보 게임에서는 순수 전략만으로 성립한다. 클로드 섀넌은 1950년 논문 〈Programming a Computer for Playing Chess〉에서 평가 함수와 미니맥스를 이용한 체스 프로그램의 기본 설계를 제시했다.^[1]

깊이 제한과 평가 함수

체스에서 끝까지 탐색하는 것은 불가능하므로, 일정 깊이에서 멈추고 그 국면이 얼마나 유리한지 추정하는 평가 함수(evaluation function)로 잎 노드의 값을 대신한다.

$EVAL (s) = w_{1} f_{1} (s) + w_{2} f_{2} (s) + \dots + w_{n} f_{n} (s)$

체스라면 $f_{i}$ 는 기물 점수(폰 1, 나이트·비숍 3, 룩 5, 퀸 9 같은 관례적 값), 기물 활동성, 킹 안전, 폰 구조 같은 특징이고 $w_{i}$ 는 가중치다. 평가 함수의 질과 탐색 깊이가 함께 실력을 정한다. 최근 엔진은 이 부분을 신경망으로 바꾸었다.

깊이를 고정하면 생기는 문제가 수평선 효과(horizon effect)다. 탐색 한계 바로 너머에서 기물을 잃는 국면을, 쓸모없는 수로 시간을 끌어 한계 밖으로 밀어내고는 안전하다고 착각한다. 이를 줄이려고 기물을 잡고 잡히는 교환이 진행 중인 불안정한 국면은 조용해질 때까지 더 탐색하는 정지 탐색(quiescence search)과, 체크처럼 강제성이 큰 수를 더 깊이 보는 탐색 확장을 쓴다.

알파-베타 가지치기

알파-베타 가지치기(alpha-beta pruning)는 미니맥스와 같은 답을 내면서, 결과에 영향을 줄 수 없는 가지를 탐색하지 않는 방법이다. 두 값을 들고 내려간다.

α(알파): 지금까지 찾은, MAX가 보장받을 수 있는 최솟값(하한). 처음에는 $- \infty$
β(베타): 지금까지 찾은, MIN이 허용할 최댓값(상한). 처음에는 $+ \infty$

어떤 노드에서 $α \geq β$ 가 되면, 그 노드는 실제 대국에서 나오지 않으므로 남은 자식을 볼 필요가 없다. 위의 예에서 A의 값 3을 알고 나면 α=3이 된다. B의 첫 자식이 2로 나오는 순간 MIN은 B에서 2 이하만 허용하므로, B는 A보다 나쁘다는 것이 확정되고 B의 나머지 자식 4와 6은 볼 필요가 없다.

효율

수 정렬	평가하는 잎 노드 수	같은 시간에 볼 수 있는 깊이
최악(가장 나쁜 수부터)	$O (b^{d})$ , 미니맥스와 같음	미니맥스와 같음
최선(가장 좋은 수부터)	$O (b^{d / 2}) = O (\sqrt{b^{d}})$	약 2배
무작위	약 $O (b^{3 d / 4})$	약 4/3배

같은 시간에 두 배 깊이를 볼 수 있다는 점 때문에 실전에서는 좋은 수를 먼저 보도록 수를 정렬하는 것이 매우 중요하다. 도널드 커누스와 로널드 무어가 1975년 이 성능을 분석했고,^[2] 주데아 펄은 무작위 잎 값을 가진 트리에서 알파-베타가 기대 실행 시간 면에서 최적임을 보였다.^[3]

역사

존 매카시는 1956년 다트머스 회의 무렵 알파-베타 탐색을 고안해 IBM의 체스 프로그램 개발자 알렉스 번스타인에게 권했다고 회고했다.^[4] 앨런 뉴얼과 허버트 사이먼은 이 방법이 여러 번 독립적으로 재발견되었다고 썼다. MIT의 대니얼 에드워즈와 티머시 하트는 1961년 메모 〈The Alpha-Beta Heuristic〉을 남겼고,^[5] 소련의 알렉산드르 브루드노도 독자적으로 고안해 1963년 발표했다. 커누스와 무어가 1975년 알고리즘을 다듬고 분석했다.^[2]

탐색 개선 기법

기법	내용
반복 심화(iterative deepening)	깊이 1, 2, 3, …으로 탐색을 반복한다. 시간이 다 되면 마지막으로 끝난 깊이의 답을 쓸 수 있고, 얕은 탐색 결과로 다음 탐색의 수 정렬을 개선한다. 중복 계산은 마지막 깊이에 비해 작다
수 정렬 휴리스틱	기물을 잡는 수, 이전 반복에서 가장 좋았던 수(주 변화, PV)를 먼저 본다. 같은 깊이에서 가지치기를 일으킨 수를 먼저 보는 킬러 휴리스틱, 역사 휴리스틱 등
전치 테이블(transposition table)	다른 수순으로 같은 국면에 도달하는 경우가 많으므로 국면별 결과를 해시 테이블에 저장해 재사용한다. 국면 해시에는 조브리스트 해싱을 흔히 쓴다
열망 창(aspiration window)	이전 결과 근처의 좁은 α, β 범위로 탐색해 가지치기를 늘리고, 범위를 벗어나면 넓혀 다시 탐색한다
영 창 탐색, PVS(NegaScout)	첫 수만 정상 범위로 탐색하고 나머지는 "첫 수보다 나은가"만 묻는 폭 0의 창으로 빠르게 확인한다. 더 나은 수가 발견되면 다시 탐색
널 무브 가지치기	내 차례를 한 번 건너뛰어도 여전히 충분히 유리하면 그 가지를 얕게만 본다(손실 가능성이 있는 휴리스틱)
늦은 수 감축(LMR)	정렬 순서상 뒤쪽 수는 얕게 탐색하고 유망하면 다시 깊게 탐색

변형

네가맥스

$\max (a, b) = - \min (- a, - b)$ 라는 성질을 이용하면, MAX와 MIN을 따로 쓰지 않고 "현재 차례인 사람 기준 점수"의 부호만 바꿔 하나의 함수로 쓸 수 있다. 이것이 네가맥스(negamax)다. 평가 함수가 "지금 둘 사람 기준"으로 값을 돌려주어야 한다. 대부분의 엔진 구현이 이 형태다.

기댓값 미니맥스

주사위처럼 우연이 끼는 게임(백개먼 등)은 MAX, MIN 노드 사이에 확률 노드를 넣고, 확률 노드에서는 자식 값의 기댓값을 올린다. 이를 기댓값 미니맥스(expectiminimax)라 한다.

다인 게임과 불완전 정보 게임

세 명 이상이 하는 게임은 각 노드에서 그 차례 참가자의 점수를 최대화하는 벡터 값으로 확장한다(max^n). 포커처럼 상대의 패를 모르는 불완전 정보 게임에서는 미니맥스를 그대로 쓸 수 없고, 반사실적 후회 최소화(CFR) 같은 다른 방법을 쓴다.

파이썬 구현

아래는 알파-베타 가지치기를 적용한 네가맥스 의사코드다. evaluate는 현재 둘 사람 기준 점수를 돌려준다고 가정한다.

import math

def negamax(state, depth, alpha=-math.inf, beta=math.inf):
    """현재 차례인 사람 기준의 점수와 최선의 수를 돌려준다."""
    if depth == 0 or state.is_terminal():
        return state.evaluate(), None

    best_value, best_move = -math.inf, None
    for move in state.ordered_moves():          # 좋은 수부터 보면 가지치기가 늘어난다
        child = state.play(move)
        value, _ = negamax(child, depth - 1, -beta, -alpha)
        value = -value                           # 상대 기준 점수를 내 기준으로 바꾼다
        if value > best_value:
            best_value, best_move = value, move
        alpha = max(alpha, value)
        if alpha >= beta:                        # 상대가 이 국면을 허용하지 않는다
            break                                # 나머지 수는 볼 필요 없음
    return best_value, best_move

def iterative_deepening(state, max_depth):
    best_move = None
    for depth in range(1, max_depth + 1):        # 시간 제한이 있으면 여기서 중단
        _, best_move = negamax(state, depth)
    return best_move

틱택토는 전체 국면이 수천 개 수준이라 깊이 제한 없이 끝까지 탐색할 수 있고, 양쪽이 최선을 다하면 무승부라는 결과가 나온다.

사례

딥 블루와 체스 엔진

IBM의 딥 블루는 1997년 5월 6번기 재대결에서 세계 챔피언 가리 카스파로프를 이겨, 표준 대국 시간 규칙의 경기에서 현역 세계 챔피언을 이긴 첫 컴퓨터가 되었다. 32개 프로세서와 체스 전용 칩으로 초당 2억 개 국면을 평가했다.^[6] 기본 탐색 깊이는 약 12플라이였고, 강제 수순에서는 탐색 확장으로 약 40플라이까지 내다보았다.^[7] 핵심은 알파-베타 탐색과 사람이 설계한 평가 함수였다. 자세한 내용은 IBM 딥 블루 문서 참고.

오늘날 가장 강한 공개 체스 엔진인 스톡피시(Stockfish)도 알파-베타 계열 탐색을 쓴다. 2020년 8월에는 평가 함수에 효율적으로 갱신되는 신경망(NNUE)을 도입해, 사람이 설계한 평가 함수를 학습된 신경망으로 바꾸었다.^[8]

몬테카를로 트리 탐색과의 비교

바둑은 분기 계수가 크고 좋은 평가 함수를 손으로 만들기 어려워 알파-베타가 잘 통하지 않았다. 2000년대 중반부터는 무작위 대국 결과로 국면을 평가하는 몬테카를로 트리 탐색(MCTS)이 주류가 되었고, 알파고와 알파제로는 MCTS에 신경망 정책·가치 함수를 결합했다.

구분	미니맥스 + 알파-베타	몬테카를로 트리 탐색
탐색 방식	정해진 깊이까지 깊이 우선으로 모든 수를 고려(가지치기 제외)	유망한 수에 시뮬레이션을 더 배분하는 비대칭 트리 성장
국면 평가	평가 함수(수작업 또는 신경망)	무작위·정책 시뮬레이션 결과 또는 가치 신경망
잘 맞는 게임	분기 계수가 작고 전술적 수읽기가 중요한 게임(체스, 체커)	분기 계수가 크고 평가가 어려운 게임(바둑)
결과의 성질	주어진 깊이 안에서 정확한 미니맥스 값	시뮬레이션이 늘수록 미니맥스 값에 수렴하는 근사
중단 가능성	반복 심화로 언제든 답 가능	언제든 중단하고 가장 많이 방문한 수 선택

쓰임

보드게임 AI: 체스, 체커, 오셀로, 오목, 장기 등. 체커는 2007년 게임 트리 탐색과 대규모 종반 데이터베이스로 완전히 풀려, 양쪽이 최선을 다하면 무승부라는 것이 증명되었다.^[9]
교육: 탐색, 재귀, 가지치기를 가르치는 대표 예제로 인공지능 교과서에 실린다.
의사결정 이론: 최악의 경우 손실을 최소화하는 미니맥스 기준은 통계적 결정 이론, 강건 최적화, 적대적 학습(예: GAN의 생성자-판별자 목적 함수 $\min_{G} \max_{D}$ )으로 이어진다.

같이 보기

각주

↑ Claude E. Shannon, 〈Programming a Computer for Playing Chess〉, 《Philosophical Magazine》 41(314), 1950. doi:10.1080/14786445008521796
↑ ^2.0 ^2.1 Donald E. Knuth, Ronald W. Moore, 〈An analysis of alpha-beta pruning〉, 《Artificial Intelligence》 6(4), 1975. doi:10.1016/0004-3702(75)90019-3
↑ Judea Pearl, 〈The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and Its Optimality〉, 《Communications of the ACM》 25(8), 1982. doi:10.1145/358589.358616
↑ The Dartmouth Workshop: as planned and as it happened, John McCarthy, 2006.
↑ D. J. Edwards, T. P. Hart, 〈The Alpha-Beta Heuristic〉, MIT AI Memo 30, 1961. hdl:1721.1/6098
↑ Deep Blue, IBM Heritage.
↑ Feng-hsiung Hsu, 〈IBM's Deep Blue Chess Grandmaster Chips〉, 《IEEE Micro》 19(2), 1999. doi:10.1109/40.755469
↑ Introducing NNUE Evaluation, Stockfish, 2020-08-07.
↑ Jonathan Schaeffer 외, 〈Checkers Is Solved〉, 《Science》 317(5844), 2007. doi:10.1126/science.1144079

참고 문헌

Stuart Russell, Peter Norvig, 《Artificial Intelligence: A Modern Approach》 4판, 5장 "Adversarial Search and Games", Pearson, 2021.
Alpha-Beta, Chess Programming Wiki(참고)

[1] Claude E. Shannon, 〈Programming a Computer for Playing Chess〉, 《Philosophical Magazine》 41(314), 1950. doi:10.1080/14786445008521796

[knuth-2] 2.0 ^2.1 Donald E. Knuth, Ronald W. Moore, 〈An analysis of alpha-beta pruning〉, 《Artificial Intelligence》 6(4), 1975. doi:10.1016/0004-3702(75)90019-3

[3] Judea Pearl, 〈The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and Its Optimality〉, 《Communications of the ACM》 25(8), 1982. doi:10.1145/358589.358616

[4] The Dartmouth Workshop: as planned and as it happened, John McCarthy, 2006.

[5] D. J. Edwards, T. P. Hart, 〈The Alpha-Beta Heuristic〉, MIT AI Memo 30, 1961. hdl:1721.1/6098

[6] Deep Blue, IBM Heritage.

[7] Feng-hsiung Hsu, 〈IBM's Deep Blue Chess Grandmaster Chips〉, 《IEEE Micro》 19(2), 1999. doi:10.1109/40.755469

[8] Introducing NNUE Evaluation, Stockfish, 2020-08-07.

[9] Jonathan Schaeffer 외, 〈Checkers Is Solved〉, 《Science》 317(5844), 2007. doi:10.1126/science.1144079

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]