최소최대 알고리즘 (Minmax Algorithm)

바둑과 체스같은 게임에서는 상대방이 다음에 어떤 자리에 수를 놓을것인가 까지 생각을 하며 게임을 진행해야 합니다. 이런 게임에 인공지능을 투입한다면, 이 인공지능도 사람이 어디에 놓게 될것인가를 생각하도록 코드를 구현해야 합니다. 이 때 사용하는 알고리즘이 바로 최소최대 알고리즘입니다.

최소최대 알고리즘 (Minmax Algorithm)

바둑과 체스같은 게임에서는 상대방은 내가 제일 불리한 곳에 수를 두게 될 것입니다. 그래서 내 차례에는 내게 제일 유리한 수, 상대방 차례에는 내게 제일 불리한 수가 선택될 것이며, 단지 다음 턴만이 아니라 그 이후의 수까지도 바라보며 탐색을 해가는 과정입니다. 정리하자면, 최대와 최소를 번갈아가며 선택해 가장 좋은 경우를 선택하는 것이 최소최대 알고리즘의 답이 됩니다. 

 위의 트리를 예로 들겠습니다. 제가 선이라고 하면 4번째 단계인 가장 아래는 상대방이 선택할 곳입니다. 그 위 3단계는 제가 선택할 곳으로 제 이익이 가장 큰 곳을 선택해야겠죠? 따라서 4단계의 자식 노드들 중에 가장 큰 이익을 선택합니다. 그러면 2단계에서는 상대가 놓을 차례이므로 3단계의 자식 노드들 중 가장 작은 이익을 선택할 것입니다. 그리고 1단계인 저는 제 이익이 가장 큰 것을 선택해야겠죠? 따라서 저는 c의 이익 3을 선택할 것입니다. 따라서 최대최소 알고리즘이 적용된 인공지능은 a -> c -> f -> i 로 게임이 흘러가도록 할 것입니다. 만약 제가 인공지능의 생각대로 노드를 선택하지 않고 다른 곳을 선택했다면, 인공지능은 그 자리에서의 최대최소 알고리즘을 적용해 또 다른 경로를 찾아갈 것입니다. 이런식으로 최대값과 최소값을 번갈아가며 선택하게되는 알고리즘이 최대최소 알고리즘입니다. 

 그런데 탐색에서 가장 중요한 것은 시간입니다. 인공지능이랑 게임을 하는데 인공지능이 다음 수를 놓는데까지 2시간이 걸린다면 아무도 게임을 하지 않겠죠? 이 알고리즘은 인공지능이 내다볼 수를 늘리면 늘릴수록 시간은 기하급수적으로 증가합니다. 탐색해야하는 노드가 증가하기 때문입니다. 따라서 시간을 줄이기 위해 이 알고리즘에서 사용하는 기법은 알파베타 가지치기입니다. 

알파베타 가지치기(alpha beta pruning)를 적용하자

알파베타 가지치기의 목적은 굳이 더 탐색할 필요없는 노드들은 가지치기를 해 시간을 줄이는 것입니다. 위의 트리를 예로 보겠습니다. d의 경우에는 자식 노드 중 최대값인 2를 선택했습니다. d의 형제 노드인 e 또한 자식들 중 최대값을 선택할 것입니다. e의 첫번째 자식인 j의 이익값은 4입니다. e에 올라올 이득값은 4이거나 4보다 큰 값이 올라갈 것입니다. (최대값이 올라갈 것이기 때문에 4보다 작은 값은 올라갈 수 없습니다.) 그런데 이 이익값 4는 d의 이익값인 2보다 큽니다. d 와 e의 부모인 b는 두 명의 자식의 이익값 중 최소를 선택할 것이기 때문에 어차피 d를 선택할 것입니다. 따라서 k와 k 이외의 e의 자식들은 살펴볼 필요도 없겠죠. 어차피 걔네를 살펴본 후 최대값을 올리더라도 d가 선택될 것이기 때문입니다. 이런식으로 굳이 더 이상 탐색할 필요없는 노드들을 가지치기 해버리는게 알파베타 가지치기 방식입니다.