MiniMax 미니맥스 알고리즘+JAVA 예제 코드

MiniMax 미니맥스 알고리즘+JAVA 예제 코드

MiniMax 알고리즘?

대전게임처럼 한번씩 턴이 돌아가며 게임을 할 경우,  나에게는 이점을 최대화 시키고, 상대에게는 이점을 최소화 시키는 방식의 알고리즘입니다. 장기, 체스 등 경쟁이 주가 되는 게임과 같은 인공지능 분야에서 자주 사용되는 개념으로, 머신러닝 중에서는 적대적 모델의 상호작용으로 이루어지는 GANs의 상호 경쟁에 사용됩니다.

 

■ 알고리즘의 목적

'예측'을 위한 것입니다.

어떠한 목적이 있으면, 그것을 위한 최적의 결정을 당시에 상정하고, 그 다음에 나올수 있는 최악의 수를 예측하여, 결국은 각 턴마다의 최적의 수를 찾아내는 것입니다.

 

■  2인 게임최 적합

A는, 뭔가 목표를 가져가기 위한 최적의 결정을 하고, B는, A가 목표에서 최대한 멀어지도록 방해하는 것입니다.

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

 

이런 개념에서 상대방의 최고의 수가 나에게 가장 최소의 영향을 끼치게 만들자 라며 나온 것이 바로 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이 되었습니다. 

 

 

자바구현코드

import java.io.*;
import java.util.*;
public class minimax
{
  public static int decide(int cur,int index,boolean max,int weight[],int height)
  {
    int num=0;
    //If we reach a leaf node
    if(cur==height)
      return weight[index];
    //If the node is a max one we find the max from sub-nodes
    if(max)
    num=Math.max(decide(cur+1,index*2,false,weight,height),decide(cur+1,index*2+1,false,weight,height));
      //If it is a min node we minimize the value under the sub-tree
      else
      num=Math.min(decide(cur+1,index*2,true,weight,height),decide(cur+1,index*2+1,true,weight,height));
      return num;
  }
  public static void main(String args[])
  {
    int scor[] = {3, 15, 2, 10, 12, 5, 2, 23};
    int n= scor.length;
    int h= (int)(Math.log(n) / Math.log(2));
    int a=decide(0,0,true,scor,h);
    System.out.println(a);
  }
}

 

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