미니맥스 알고리즘

개념

미니맥스 알고리즘은 두 명이 번갈아 수를 두는 게임에서 사용하는 게임 탐색 알고리즘이다. 내 차례에는 점수를 최대화하고, 상대 차례에는 내 점수가 최소화된다고 가정한다.

핵심 가정

MAX 플레이어는 나에게 가장 유리한 수를 고른다. MIN 플레이어는 나에게 가장 불리한 수를 고른다. 두 플레이어가 모두 최선을 다한다고 가정한다.

$$V(s)=\{\begin{array}{ll}U(s),& s\text{가 종료 상태}\\ \underset{a\in A(s)}{\max }V(T(s,a)),& s\text{가 MAX 차례}\\ \underset{a\in A(s)}{\min }V(T(s,a)),& s\text{가 MIN 차례}\end{array}$$

평가 함수

틱택토에서는 가능한 수를 끝까지 탐색하고, 내가 이길 수 있는 줄 수에서 상대가 이길 수 있는 줄 수를 뺀 값을 평가 함수로 사용할 수 있다. 게임이 끝난 상태라면 승리는 +1 또는 큰 양수, 무승부는 0, 패배는 -1 또는 큰 음수로 평가할 수 있다.

한계

가능한 모든 수를 끝까지 탐색하면 노드 수가 급격히 증가한다. 그래서 큰 게임에서는 깊이 제한, 휴리스틱 평가 함수, 알파-베타 가지치기가 필요하다.