개요
Minimax 알고리즘은 상대방의 해는 최소화 하면서 나의 해는 최대화 하는 것을 말한다. 게임에서, 상대방은 항상 상대방이 내릴 수 있는 최선의 결과를 도출할 것이라고 가정을 한다면, 내가 다음에 Greedy하게 어떠한 행위를 하더라도, 상대방의 응수로 인하여 더 큰 손실을 얻을 수 있는 것이다. 따라서 이번턴에서 나의 손해를 조금 감수하더라도 최종적으로 상대방의 이익은 최소화 하면서 나의 이득은 최대화 하는 방향으로 선택하는 알고리즘을 말한다.
미니맥스 알고리즘을 구현한다면 모든 가지에 대해서 경우의 수를 계산하여야 한다. 이러한 트리의 탐색은 DFS를 통해서 이루어지게 된다. DFS의 알고리즘의 복잡도는 깊이에 따라 지수적으로 증가하기 때문에 Complete한 솔루션을 찾을 수는 있지만, 연산 능력의 한계로 인하여 Pratical한 case는 사용하지 못한다. 따라서 이러한 경우에는 다양한 가지치기를 통해서 Optimal한 해답을 찾는 알고리즘들이 존재한다. 대표적인 것이 Alpha-Beta Pruning이다. 또한 Monte-Carlo Tree Search이러한 미니맥스 탐색을 어떻게 하면 최적으로 수행할 수 있을지에 대한 고민의 해답이다.
특징
- Complete (If tree is finite)
- Optimal (Against an optimal opponent)
- Time Complexity (O(b^n), b(number of node), n(number of depth)
- Space Complexity (O(bn), b(number of node), n(number of depth)