미니맥스 알고리즘 (minimax algorithm)

한 줄 정의: 상대가 최선으로 둔다고 가정하고 게임 트리를 뒤져 자기 손해를 최소화하는 수를 고르는 방법입니다.

쉽게 풀면

체스나 오목처럼 두 사람이 번갈아 두는 게임에서, 앞으로 벌어질 수를 나무처럼 펼쳐 놓고 끝에서부터 거슬러 올라가며 값을 정합니다. 내 차례에서는 가장 좋은 값을, 상대 차례에서는 나에게 가장 나쁜 값을 고른다고 가정합니다. 상대가 실수하지 않는다고 가정하므로 최악의 경우에도 보장되는 결과를 얻습니다.

왜 중요한가

게임 인공지능의 기본 뼈대이자 적대적 탐색의 표준 기법으로, 오랫동안 체스 프로그램의 핵심이었습니다. 완전 정보 이인 제로섬 게임이라는 명확한 가정 위에서 최적 전략의 의미를 정의해 주기 때문에 이론적으로도 깔끔합니다. 여기에 가지치기와 평가함수를 얹는 확장이 실전 엔진의 구조를 이룹니다.

논문에서는 이렇게 쓰입니다

"탐색 깊이 6의 미니맥스 알고리즘에 휴리스틱 평가함수를 결합하여 종단 노드를 평가하였다."

끝까지 다 볼 수 없으므로 일정 깊이에서 멈추고 형세를 점수로 어림했다는 뜻입니다.

조금 더 깊게 보면

게임 트리의 단말 노드에 효용값을 부여한 뒤 깊이 우선으로 거슬러 올라가며 최대와 최소를 번갈아 취하므로, 분기 계수 b와 깊이 d에 대해 시간 복잡도가 b의 d제곱에 비례합니다. 현실의 게임은 끝까지 탐색할 수 없어 일정 깊이에서 멈추고 평가함수로 형세를 추정하며, 이때 탐색을 멈춘 시점이 불안정한 국면이면 오판이 생기는 지평선 효과가 문제가 됩니다. 두 참가자의 값을 하나로 통일한 네가맥스 형태로 구현하는 것이 일반적입니다.

주의할 점

게임이론의 미니맥스 정리가 혼합 전략 균형의 존재를 말하는 수학 정리인 반면, 이쪽은 게임 트리를 실제로 탐색하는 절차를 가리킵니다. 참가자가 셋 이상이거나 우연 요소가 있는 게임에는 그대로 적용할 수 없습니다.