MINIMAX

MINIMAX (미니맥스)는 의사 결정 이론, 게임 이론, 인공지능 분야에서 사용되는 재귀적인 의사 결정 규칙이다. 주로 두 명의 플레이어가 번갈아 가며 수를 두는 완전 정보 게임에서, 한 플레이어는 자신의 이익을 최대화하려 하고 다른 플레이어는 상대방의 이익을 최소화하려 할 때, 각 플레이어가 최선의 수를 선택하도록 하는 전략을 찾는 데 사용된다.

미니맥스 알고리즘은 게임 트리를 탐색하여 각 노드에 점수를 할당한다. 한 플레이어(보통 "최대화 플레이어")는 자신의 점수를 최대화하는 수를 선택하려 하고, 다른 플레이어(보통 "최소화 플레이어")는 상대방의 점수를 최소화하는 수를 선택하려 한다. 게임 트리의 리프 노드(게임 종료 상태)에는 미리 정의된 평가 함수를 사용하여 점수를 할당한다.

알고리즘은 리프 노드에서 시작하여 위쪽으로 올라가면서 각 노드의 점수를 계산한다. 최대화 플레이어의 차례인 노드에서는 자식 노드 중 가장 높은 점수를 선택하고, 최소화 플레이어의 차례인 노드에서는 자식 노드 중 가장 낮은 점수를 선택한다. 이러한 과정을 반복하여 루트 노드(현재 게임 상태)의 점수를 계산하고, 루트 노드에서 가장 좋은 점수를 가진 자식 노드를 선택한다.

미니맥스 알고리즘은 완전 정보 게임에서 최적의 전략을 보장하지만, 게임 트리의 크기가 지수적으로 증가하기 때문에 복잡한 게임에서는 계산 비용이 매우 높아질 수 있다. 이러한 문제를 해결하기 위해 알파-베타 가지치기 등의 기법을 사용하여 탐색 공간을 줄일 수 있다.

주요 응용 분야로는 체스, 바둑, 틱택토와 같은 게임 인공지능 개발이 있다.