Minimax algorithm은 체스나 장기, 틱택토 혹은 오목 처럼 두 명의 플레이어가 번갈아 가면서 턴을 주고받는 유한 제로섬 게임(Finite zero-sum game)에서 최적의 선택을 내리기 위해 사용 할 수 있는 결정 트리 탐색 알고 리즘이다. 다시말해, 내가 얻는 이득이 상대의 손실이 되고, 내가 보는 손실이 상대의 이득이 되는 구조에서, “상대방은 항상 자신에게 유리한 선택을 하고 나에게는 불리한 선택을 한다”는 가정하에 자기 자신의 손실을 최소화(minimize)하고 이득을 최대화(maximize)하는 전략을 찾는 것이다.

이 포스팅에서는 minimax algorithm의 개념을 이해하고 간단한 게임에 적용시켜 최적의 해법을 찾아내는 과정을 확인해 본다.

Max Player와 Min Player

Minimax 알고리즘에서는 두 플레이어를 각각 Max와 Min으로 정의한다.

• Max Player (컴퓨터): 자신의 점수를 maximize하려는 플레이어.
• Min Player (상대방): Max의 점수를 minimize하려는 플레이어.

이 그림은 Max와 Min 두 플레이어가 서로 턴을 바꿔가며 결정하는 예제를 단순화 해서 트리로 그린 것이다. 각 선택 들의 최종 결과 값이 3, 5, 2, 9로 귀결된다고 할 때, Min은 Max의 이득을 최소화 하는 결정을 선택을 하게 될 것이므로, 왼쪽 노드의 3과 5중에서는 3, 오른쪽 노드의 2와 9중에서는 2를 선택할 것이다. 그렇다면 Max 입장에서는 Min이 결정 할 3과 2중에 이득을 최대화 하는 3을 고르게 되는 것이다.

전체 트리 상에는 Max가 이 게임에서 얻을 수 있는 더 큰 이득인 5와 9가 있지만 이들은 Min에 의해 버려지게 될 것이므로, Max 입장에서는 3을 얻기위한 결정을 수행하는 것이 최적이라고 할 수 있다.

변형 Nim 게임에 적용

Nim game은 “베스킨라빈스31” 게임과 유사한 것인데 판에 올려진 물체(코인)을 1개, 2개 혹은 3개씩 돌아가면서 가져가서 결국 마지막 남은 하나를 가져가는 사람이 지게되는 게임이다.

이것을 약간 변형해서 7개의 코인을 가정하고 컴퓨터와 번갈아 가면서 1개, 2개 혹은 3개씩 가져가서 최종적으로 남은 코인을 0개로 만드는 쪽이 이기는 게임을 “변형 Nim 게임”이라고 하고 여기에 minimax를 적용해 보도록 하자.

결정 트리의 모든 노드를 그리면 공간이 부족하니 Max(컴퓨터)가 3개를 가져가는 경우를 탐색하는 상황을 살펴보자. Max와 Min은 각각 번갈아 가면서 코인을 1개, 2개 혹은 3개를 가져가는 상황에 대하여 남은 coin이 0이 되는 상황을 탐색한다.

Max 입장에서 남은 코인이 0개가 되도록 만드는 node가 Min이 되도록 하는 조건이 유리하다고 판단하고, 이 때 큰 점수 +1을 매겨서 결정을 유도하고, 그 반대의 경우에는 -1 점수를 매겨서 이 상황을 피하도록 한다.

구현코드

이러한 트리 탐색 과정을 재귀함수로 나타내면 다음과 같다.

실행 결과 및 결론

다음은 전체 코인의 갯수를 설정하는 total_coins의 값을 12로 해서 수행한 결과이다.

결과를 보면 12 / 8 / 4개를 남기도록 하는 규칙을 명시적으로 주지 않았음에도 컴퓨터는 minimax tree로 부터 이러한 값들이 승부에 유리하다는 것을 탐색해서 항상 이러한 값에 가장 가까운 선택을 하려하는 것 처럼 보이는 약간의 지능적(?) 결과를 볼 수 있다.