미니맥스 알고리즘이 뭔지 5분 만에 이해하기 — 틱택토 무적 AI의 원리

틱택토 AI를 처음 상대해본 사람들이 공통적으로 하는 말이 있습니다. “어떻게 절대 못 이기죠?” 이기는 건 둘째 치고 무승부를 만드는 것조차 쉽지 않을 때가 있죠. 그 뒤에는 미니맥스(Minimax) 알고리즘이라는 개념이 있습니다. 코드나 수학 없이, 직관적으로 이해해봅시다.

게임 트리란 무엇인가

먼저 “게임 트리”라는 개념부터 잡아야 합니다.

틱택토 판이 비어 있다고 상상해보세요. 첫 번째 수를 두는 사람은 9칸 중 하나를 선택합니다. 그 다음 상대는 남은 8칸 중 하나를, 그 다음은 7칸 중 하나를… 이렇게 계속 이어집니다.

이 모든 가능성을 나뭇가지처럼 펼쳐 놓은 것이 게임 트리입니다. 뿌리(처음 상태)에서 출발해서 가지(수를 두는 선택)를 따라가면 결국 잎(게임 종료 상태 — 승, 패, 무승부)에 도달합니다.

틱택토의 경우 이론상 최대 9! = 362,880가지 경로가 있지만, 실제로는 이미 누군가 이긴 상태에서 게임이 끝나기 때문에 훨씬 적은 수가 됩니다. 컴퓨터 입장에서는 눈 깜짝할 사이에 탐색할 수 있는 양입니다.

미니맥스의 핵심 아이디어

미니맥스는 이름에서 힌트를 얻을 수 있습니다.

• Max (최대화): 내 점수를 최대한 높이려 한다
• Min (최소화): 상대의 점수를 최대한 낮추려 한다

AI 입장에서 생각해봅시다. AI가 수를 두는 차례가 되면 “이 수를 두면 게임이 어떻게 흘러갈까?”를 미리 계산합니다. 가능한 모든 경우를 탐색하고, 각 경우에 점수를 매깁니다.

• AI가 이기면: +1점
• 사람이 이기면: -1점
• 무승부면: 0점

그런데 핵심은 이겁니다. AI는 자기 차례에 점수를 최대화하는 수를 고릅니다. 하지만 상대(사람) 차례에서는 사람도 최선을 다해 AI 점수를 최소화할 것이라고 가정합니다.

틱택토 예시로 살펴보기

판에 수가 7개나 놓인 상태를 상상해봅시다. 빈 칸이 딱 2개 남았습니다.

AI가 왼쪽 빈 칸에 두면 → 게임이 끝나고 무승부(0점) AI가 오른쪽 빈 칸에 두면 → 3연속이 완성되어 AI 승리(+1점)

이 경우 AI는 당연히 오른쪽 칸을 선택합니다. +1이 0보다 크니까요.

조금 더 복잡한 경우는요? AI 차례에 두 가지 선택지가 있는데, 하나는 “나중에 사람이 최선을 다해도 내가 이기는 경로”이고, 다른 하나는 “사람이 잘 두면 무승부가 되는 경로”라면 AI는 첫 번째 경로를 선택합니다.

이걸 게임 트리 전체에 적용합니다. 모든 잎 노드에 점수를 매기고, 위로 올라오면서 AI 차례엔 최대값을, 사람 차례엔 최소값을 선택합니다. 뿌리까지 올라왔을 때 남은 선택지 중 점수가 가장 높은 수를 두면 됩니다.

왜 틱택토는 완전히 풀린 게임인가

수학적으로 “완전히 풀렸다(solved)“는 말은 어떤 상황에서든 최선의 수가 무엇인지 알려져 있다는 뜻입니다.

틱택토는 경우의 수가 약 26만 가지 정도(대칭 제거 후)라 컴퓨터가 순식간에 전체를 탐색할 수 있습니다. 그 결과, 양쪽 다 최선을 다하면 항상 무승부가 된다는 사실이 증명되어 있습니다.

즉, 어려움 모드 AI는 매 수마다 미니맥스로 계산된 최선의 수를 두기 때문에 사람이 이기는 것은 원리적으로 불가능합니다. AI가 실수를 하지 않기 때문입니다. 가능한 최선의 결과는 무승부뿐입니다.

실생활 미니맥스: 체스, 바둑과 어떻게 다를까

미니맥스는 체스나 바둑에서도 기본 원리로 쓰입니다. 하지만 차이가 있습니다.

체스의 경우 가능한 경우의 수는 약 10의 120승 정도로 추정됩니다. 우주에 있는 원자 수보다 훨씬 많습니다. 이걸 전부 탐색하는 건 불가능합니다. 그래서 체스 AI는 미니맥스를 일정 깊이까지만 탐색하고, 그 이후는 평가 함수로 대략적인 점수를 추정합니다.

바둑은 훨씬 더 복잡합니다. 경우의 수가 10의 360승 이상이고 평가 함수도 만들기 어렵습니다. 알파고 같은 현대 AI는 미니맥스 대신 몬테카를로 트리 서치와 딥러닝을 결합한 방식을 씁니다.

결국 틱택토가 AI에게 “완전히 풀린” 이유는 경우의 수가 작기 때문입니다. 그 작은 공간을 미니맥스로 완전히 탐색할 수 있으니, AI는 실수를 할 이유가 없습니다.

마치며

미니맥스는 “내 이익을 최대화하되, 상대도 최선을 다한다고 가정한다”는 단순한 아이디어입니다. 코드 한 줄 몰라도 이 개념을 이해하면 왜 게임 AI가 그렇게 행동하는지 납득이 갑니다.

틱택토 AI를 이길 수 없다는 사실이 억울하다면, 무승부를 꾸준히 만드는 것을 목표로 해보세요. AI의 원리를 알고 대전하면 또 다른 재미가 생깁니다.

틱택토 AI 대전에서 직접 미니맥스 AI를 상대해보세요.