틱택토는 왜 무승부로 끝날까: 경우의 수와 게임 트리

3x3 칸에서 나올 수 있는 게임은 몇 가지일까

틱택토는 9칸에 두 사람이 번갈아 표시를 놓다가 가로, 세로, 대각선 중 한 줄을 먼저 채우면 이기는 게임입니다. 9칸을 순서대로 채우는 방법만 따지면 9 곱하기 8 곱하기 7처럼 이어지는 9의 계승, 즉 362,880가지가 나옵니다. 하지만 실제 게임은 누군가 한 줄을 완성하면 그 자리에서 끝나기 때문에 이보다 훨씬 적습니다.

승부가 난 순간 멈추는 규칙까지 반영하면 가능한 게임은 255,168가지입니다. 여기서 판을 돌리거나 뒤집어 같은 모양이 되는 경우를 하나로 묶으면 26,830가지로 줄어듭니다. 사람이 외우기에는 많지만 컴퓨터에게는 순식간에 전부 확인할 수 있는 크기입니다.

게임 트리와 미니맥스

게임 트리는 지금 판에서 둘 수 있는 모든 수를 가지로 뻗고, 그 각각에서 상대가 둘 수 있는 모든 수를 다시 가지로 뻗어 끝까지 펼친 그림입니다. 틱택토는 한 판이 최대 9수로 끝나므로 이 나무를 끝까지 그릴 수 있습니다.

미니맥스는 이 나무를 거꾸로 읽는 방법입니다. 가장 끝에 있는 결과에 이기면 1, 비기면 0, 지면 -1 같은 값을 매기고, 내 차례에는 가장 큰 값을, 상대 차례에는 상대가 고를 가장 작은 값을 위로 올려 보냅니다. 이렇게 맨 위까지 값을 올리면 첫 수의 값이 0, 곧 무승부로 나옵니다. 양쪽이 최선을 다하면 결과가 무승부라는 뜻입니다.

지지 않는 기본 원칙

완벽한 수를 모두 외우지 않아도 지지 않는 원칙은 간단합니다. 우선 내가 바로 한 줄을 완성할 수 있으면 완성합니다. 그렇지 않으면 상대가 다음 수에 완성할 줄을 막습니다. 두 가지가 모두 없을 때는 두 줄을 동시에 노리는 자리, 흔히 포크라고 부르는 자리를 만들거나 상대의 포크를 미리 막습니다.

빈 판에서 첫 수를 둘 때는 가운데나 모서리가 유리합니다. 가운데는 네 줄에 동시에 걸쳐 있어 선택지가 가장 많고, 모서리는 세 줄에 걸쳐 있습니다. 변의 가운데 칸은 두 줄에만 걸쳐 있어 첫 수로는 가장 약합니다.

• 1순위: 내가 바로 이길 수 있는 칸
• 2순위: 상대가 바로 이길 칸 막기
• 3순위: 두 줄을 동시에 노리는 포크 만들기
• 4순위: 상대의 포크가 될 칸 미리 막기
• 5순위: 가운데, 그다음 모서리

모두게임 틱택토의 난이도 차이

모두게임 틱택토는 컴퓨터와 대결하며 난이도를 고를 수 있습니다. 어려움 난이도의 컴퓨터는 위에서 설명한 미니맥스 방식으로 모든 경우를 계산해 두기 때문에 결코 지지 않습니다. 이길 수 있는 상황에서는 가장 빨리 이기는 수를 고르고, 그렇지 않으면 무승부를 지킵니다.

따라서 어려움 난이도에서 목표는 이기는 것이 아니라 한 번도 지지 않는 것입니다. 쉬움과 보통 난이도에서 포크를 만드는 연습을 하며 승리 패턴을 익히고, 어려움에서는 지지 않는 원칙을 끝까지 지키는 연습을 해 보세요. 컴퓨터가 마지막으로 둔 칸에는 표시가 나타나서 상대의 의도를 읽기 쉽습니다.

작은 게임이 남긴 큰 의미

틱택토는 규칙이 단순하고 경우의 수가 적어서 컴퓨터가 게임을 두는 방법을 설명할 때 가장 먼저 쓰이는 예제입니다. 게임 트리, 미니맥스, 대칭을 이용한 계산 줄이기 같은 생각은 훨씬 복잡한 보드게임 인공지능의 출발점이 되었습니다. 한 판에 1분도 걸리지 않는 게임이지만, 그 안에 게임을 수학적으로 분석하는 기본 아이디어가 모두 들어 있습니다.