Minimax algorithm, 미니맥스 알고리즘

이번 글에서는 미니맥스 알고리즘에 대해 알아보기 앞서 간단한 맛보기 개념으로 실제로 어떻게 진행되는지 알아보겠습니다. 

 

체스나 바둑같이 상대방과 번갈아 가며 하는 게임에 있어 상대방의 수를 미리 예측하고 플레이하는 것이 일반적일 것입니다. 그런데 상대방이 가장 최악의 플레이를 한다고 판단하지는 않을 것입니다. 상대방 역시 나와 같이 영리하기 때문에 최선의 결과가 예측되는 선택을 할 것이 분명합니다. 

 

이런 개념에서 상대방의 최고의 수가 나에게 가장 최소의 영향을 끼치게 만들자 라며 나온 것이 바로 MiniMax Algorithm, 미니맥스 입니다. 

 

 

 

위 그림을 통해 미니맥스 알고리즘이 어떻게 진행되는지 살펴 보겠습니다.  이 상황은 4수 앞을 예측한 트리 노드이며 0, 2, 4는 내 차례이며 1,3 은 상대방의 차례입니다. 그리고 각 노드 안에 들어가 있는 숫자는 휴리스틱에 의해 평가되어 각 선택에 따른 결과를 수치로 나타내고 있습니다. 

 

다시 말하자면 나 차례에서는 최선의 선택을 해야 하며 상대방의 차례에는 나에겐 최악의 선택을 하게 됩니다. 똑똑한 상대방이 나에게 유리한 선택을 할리가 없기 때문입니다.

 

1. 4번줄 차례에서 나는 나에게 유리한 경우(높은 숫자가 유리하고 낮은 숫자가 불리합니다.)를 택해 놓은 상태입니다. 

10, 무한대, 5, -10, 7, 5, -무한대, -7, -5 가 있습니다. 

 

2. 3번줄는 상대방의 차례입니다. 나에게 불리한 경우를 택할 것입니다. 10, 무한대 중 낮은 10을 택하며 5와 -10 은 다른 선택의 경우가 없기에 바로 택하게 됩니다. 7, 5 중에서 낮은 수 5를 택하게 됩니다. -무한대는 다른 경우가 없기에 택하게 되며 -7, -5중 더 낮은 수 -7이 선택됩니다. 

 

3. 2번줄은 나의 순서입니다. 최선의 결과를 선택해야 합니다. 10, 5 중 최선의 경우인 10을 택하겠습니다. -10은 역시 다른 경우가 없으니 택하겠습니다. 5와 -무한대 중 높은 수 5를 택하겠습니다. -7은 다른 선택이 없으니 택하겠습니다. 

 

4. 1번줄은 상대방의 차례입니다. 10과 -10 중 더 낮은 수 -10을 택하겠습니다. 5와 -7 중 더 낮은 수 -7을 택하겠습니다. 

 

5. 0번줄은 실제로 제 차례입니다. -10과 -7 중에서 높은 숫자 -7을 택하겠습니다. 

 

이렇게 미니맥스 알고리즘의 진행과정을 살펴보았습니다. 4수앞에 경우에는 10도 있고 무한대도 있지만 실제로 영리한 상대방 때문에 내가 택할 수 있는 최선의 경우는 고작 -7이 되었습니다. 

 

이번 글에서는 미니맥스의 개념?정도와 실제 트리노드에서 어떻게 진행되는지 알아봤습니다. 다음 글에서는 미니맥스 알고리즘에서 N수 앞을 예상할때 N이 늘어날수록 기하급수적으로 노드의 수가 늘어나 엄청난 공간과 시간을 차지하게 되는 단점을 극복하기 위한 알파-베타 가지치기 (Alpha-beta pruning) 에 대해 알아보겠습니다.