미니맥스 알고리즘 계산기

번갈아 두는 두 사람 게임에서, 내가 둘 차례에는 내게 가장 유리한 수를 고르고 상대가 둘 차례에는 상대가 내게 가장 불리한 수를 고른다고 가정해 최적의 수를 찾는 탐색 방법입니다. 체스·틱택토처럼 완전정보 게임의 AI가 기본으로 쓰는 알고리즘입니다.

이 계산기의 루트는 "지금 수를 두려는 나"를 뜻합니다. 나는 내게 유리한(값이 큰) 수를 고르므로 최대화이고, 한 단계 내려가 상대 차례가 되면 상대는 내게 불리한(값이 작은) 수를 고르므로 최소화입니다. 이렇게 최대화·최소화가 매 단계 번갈아 나옵니다.

트리 전체를 다 보지 않아도 같은 답이 나온다는 걸 이용해 일부 가지의 평가를 건너뜁니다. 지금까지 확보한 최선의 값(알파·베타)을 기준으로, 남은 가지를 봐도 결과가 절대 안 바뀐다는 게 확실해지면 그 가지는 평가하지 않고 넘어갑니다.

네, 같습니다. 알파-베타 가지치기는 트리의 값을 하나도 바꾸지 않습니다. 순수 미니맥스와 항상 같은 루트 값을 내면서, 그 값을 구하는 데 굳이 안 봐도 되는 리프만 건너뜁니다.

네. 이 계산기는 자식을 왼쪽부터 순서대로 본다고 가정합니다. 같은 트리라도 자식의 순서를 바꾸면 어느 리프가 잘리는지는 달라질 수 있습니다(단, 최종 루트 값은 바뀌지 않습니다). 유리한 수를 먼저 살펴볼수록 더 많이 잘립니다.