틱택토

틱택토 규칙

틱택토(tic-tac-toe)는 두 사람이 3×3 격자의 칸에 O와 X를 번갈아 표시해, 자기 표시 세 개를 가로·세로·대각선 가운데 한 줄로 먼저 잇는 쪽이 이기는 종이와 연필 게임입니다. 한국어로는 삼목(삼목놓기)이라고도 부릅니다. 판이 작고 규칙이 단순해 종이 한 장이면 어디서든 할 수 있고, 경우의 수를 끝까지 셀 수 있을 만큼 작아서 게임 트리 탐색 같은 인공지능 개념을 가르치는 예제로도 자주 쓰입니다.

1. X가 먼저 두고, O와 번갈아 빈칸 하나에 자기 표시를 합니다. 한 번 표시한 칸은 바꾸지 않습니다.
2. 같은 표시 세 개가 가로 세 줄, 세로 세 줄, 대각선 두 줄 가운데 하나를 채우면 그 사람이 이깁니다. 이길 수 있는 줄은 모두 여덟 줄입니다.
3. 아홉 칸이 모두 찼는데 완성된 줄이 없으면 무승부입니다.

누가 먼저 둘지는 정하기 나름이며, 이 게임에서는 X가 먼저 둡니다. 가장 빨리 끝나는 게임은 X가 세 번째 수로 줄을 완성하는 5수입니다.

이 게임 하는 법

1. 설정에서 상대를 고릅니다. 컴퓨터와 하기는 내 표시(X는 먼저, O는 나중)와 난이도를 정하고, 둘이 하기는 한 기기에서 번갈아 둡니다. 누가 X를 잡을지는 동전 던지기로 정해도 됩니다.
2. 빈칸을 누르면 지금 차례의 표시가 놓입니다. PC에서는 마우스를 올린 칸에 흐린 표시가 미리 보이고, 방금 둔 칸은 옅은 노란색으로 표시됩니다.
3. 한 줄이 완성되면 그 줄에 초록 선이 그어지고 결과가 기록됩니다. 무르기는 컴퓨터와 할 때 내 수와 컴퓨터 수를 한 쌍으로 되돌립니다.
4. 키보드로도 둘 수 있습니다. Tab으로 판의 칸을 선택하고 방향키로 옮긴 뒤 Enter나 Space로 두거나, 숫자 1~9를 눌러 그 칸에 바로 둡니다. 칸 번호는 왼쪽 위 1번부터 오른쪽 아래 9번까지 글을 읽는 순서입니다.

이름과 역사

영어 위키백과에 따르면 틱택토는 미국식 이름이고, 영국·호주 등 영연방에서는 noughts and crosses(동그라미와 가위표), 캐나다와 아일랜드에서는 Xs and Os라고도 부릅니다. 인쇄물에 처음 나온 기록은 noughts and crosses가 1858년, tick-tack-toe가 1884년입니다.

세 개를 한 줄로 잇는 놀이판은 훨씬 오래되어, 고대 이집트의 기원전 1300년 무렵 지붕 기와에서 이런 판이 발견되었고, 기원전 1세기 무렵 로마 제국에는 테르니 라필리(terni lapilli, "한 번에 세 개의 돌")라는 비슷한 놀이가 있었습니다. 이 놀이는 각자 돌을 세 개만 가지고 있어서, 다 놓은 뒤에는 돌을 빈칸으로 옮겨 가며 계속 두었습니다.

틱택토는 컴퓨터 게임의 역사에도 이름을 남겼습니다. 1952년 영국 케임브리지 대학교의 A. S. 더글러스(Sandy Douglas)는 인간과 컴퓨터의 상호작용에 관한 논문 연구의 일부로, EDSAC 컴퓨터에서 사람과 틱택토를 두는 OXO라는 프로그램을 만들었습니다. 사람은 다이얼식 전화기 다이얼로 아홉 칸 가운데 둘 칸을 골랐고, 정의에 따라서는 최초의 비디오 게임 후보로 꼽힙니다(영어 위키백과 「OXO (video game)」).

게임 이론에서는 m×n 판에서 k개를 먼저 한 줄로 잇는 게임을 m,n,k-게임이라고 부르며, 틱택토는 그 가운데 3,3,3-게임입니다. 금수가 없는 자유룰 오목은 같은 계열의 15,15,5-게임입니다.

첫 수와 응수

서로 최선으로 두면 첫 수를 아홉 칸 어디에 두든 무승부입니다. 차이는 상대가 실수할 여지에 있습니다. 첫 수에 따라 O가 지지 않으려면 둘 수 있는 자리가 다음처럼 달라집니다(이 게임의 미니맥스로 모든 수순을 따져 확인).

• 모서리: O가 지지 않는 응수는 가운데 한 곳뿐입니다. 나머지 일곱 곳은 X가 끝까지 정확히 두면 모두 X가 이깁니다. 실수를 끌어내기 가장 좋은 첫 수라 흔히 권해집니다.
• 가운데: O는 모서리 네 곳에 두면 비기고, 변 네 곳에 두면 집니다.
• 변: O가 비기는 자리는 양옆 모서리 두 곳, 가운데, 맞은편 변의 네 곳이고, 나머지 네 곳은 집니다.

그림 보는 법: 초록 동그라미는 O가 두면 비기는 자리, 빨간 점은 두면 지는 자리(상대가 정확히 두는 경우), 노란 점선은 X가 다음 수에 이기는 자리입니다.

넷째 그림처럼 X가 모서리, O가 가운데에 둔 뒤 X가 맞은편 모서리를 잡으면, O는 남은 모서리가 아니라 변에 두어야 합니다. 모서리에 두면 X가 막는 수로 두 줄을 동시에 노리는 다섯째 그림의 포크가 만들어져 O가 집니다.

포크와 기본 전략

포크(fork)는 한 수로 이길 자리를 두 곳 동시에 만드는 수입니다. 상대는 한 번에 한 곳만 막을 수 있으므로 다음 차례에 남은 곳을 채우면 이깁니다. 막기만 하는 상대를 이기는 방법은 사실상 포크뿐이어서, 틱택토 전략은 "내 포크를 만들고 상대 포크를 미리 막는 것"으로 요약됩니다. 영어 위키백과에 정리된 뉴얼과 사이먼(1972)의 완벽한 수 선택 순서는 다음과 같습니다.

1. 이기기: 내 표시가 두 개 있는 줄의 남은 칸을 채웁니다.
2. 막기: 상대 표시가 두 개 있는 줄의 남은 칸을 막습니다.
3. 포크: 이길 자리가 두 곳 생기는 수를 둡니다.
4. 상대 포크 막기: 상대가 포크를 만들 수 있는 자리가 한 곳뿐이면 그 자리를 막습니다. 여러 곳이면 상대가 막을 수밖에 없는 두 개짜리 줄을 만들어 수를 빼앗되, 상대가 막는 자리가 곧 상대의 포크 자리가 되지 않게 합니다.
5. 가운데에 둡니다.
6. 맞은편 모서리: 상대가 모서리에 있으면 그 반대쪽 모서리에 둡니다.
7. 빈 모서리에 둡니다.
8. 빈 변에 둡니다.

사람끼리 할 때는 1·2번만 지켜도 쉽게 지지 않고, 3·4번까지 익히면 이길 기회를 만들면서 상대의 포크도 피할 수 있습니다. 이 게임의 보통 난이도가 1·2번은 항상 지키지만 가끔 엉뚱한 칸에 두므로, 포크를 연습하기에 알맞습니다.

게임 트리와 경우의 수

빈 판에서 시작해 둘 수 있는 수를 가지처럼 모두 펼친 그림을 게임 트리라고 합니다. 틱택토는 첫 수가 9가지, 둘째 수가 8가지로 줄어들다가 누군가 이기거나 판이 차면 가지가 끝나므로, 게임 트리 전체를 컴퓨터로 금방 셀 수 있습니다. 아래 수는 이 게임의 판정 코드로 모든 수순을 직접 세어 테스트로 확인한 값입니다.

게임 수를 끝난 수순의 길이로 나누면 다음과 같습니다. 홀수 번째 수로 끝나는 게임은 X가, 짝수 번째 수로 끝나는 게임은 O가 이긴 것이고, 무승부는 모두 9수입니다.

끝난 판 138가지(대칭 제외)를 결과별로 보면 X 승 91, O 승 44, 무승부 3입니다. 게임 수로 보면 X가 이기는 경우가 훨씬 많지만, 이는 X가 한 번 더 두기 때문에 실수를 받아 이길 가지가 많다는 뜻일 뿐, 서로 최선으로 두면 결과는 무승부입니다.

미니맥스: 컴퓨터가 지지 않는 이유

미니맥스(minimax)는 게임 트리의 끝, 곧 승·패·무가 정해진 판에 점수를 매긴 뒤 거꾸로 올라오며 값을 정하는 방법입니다. 내 차례인 판은 내가 고를 수 있는 수 가운데 가장 큰 값을, 상대 차례인 판은 상대에게 가장 좋은(나에게 가장 나쁜) 값을 가집니다. 이렇게 빈 판까지 올라오면 모든 판에 "서로 최선으로 두면 어떻게 끝나는가"가 적히고, 빈 판의 값이 무승부라는 것이 곧 "틱택토는 서로 최선이면 비긴다"는 말입니다.

어려움 난이도는 이 값이 가장 좋은 수만 둡니다. 어떤 판에서든 컴퓨터가 고른 수의 값은 그 판에서 얻을 수 있는 가장 좋은 결과이므로, 사람이 어떻게 두든 그보다 나빠지지 않습니다. 빈 판의 값이 무승부이니 컴퓨터는 적어도 비기고, 사람이 지는 자리에 두는 순간 값이 승리로 바뀌어 끝까지 이깁니다. 이 게임은 컴퓨터가 먼저 둘 때와 나중에 둘 때 각각, 사람이 둘 수 있는 모든 수순을 끝까지 따라가 컴퓨터가 한 번도 지지 않고 이길 수 있는 판은 모두 이기는 것을 테스트로 확인했습니다.

점수에는 게임이 끝날 때 남은 빈칸 수를 반영해, 이길 때는 빨리 이기는 수를, 질 수밖에 없을 때는 오래 버티는 수를 고르게 했습니다. 나올 수 있는 판이 5,478개뿐이라 한 번 계산한 판을 기억해 두면 처음부터 끝까지 전부 읽어도 눈 깜짝할 사이에 끝납니다. 체스처럼 경우의 수가 훨씬 많은 게임은 끝까지 읽을 수 없어서, 몇 수 앞까지만 읽고 그 판을 평가 함수로 어림하는 방식을 씁니다.

컴퓨터 난이도

• 쉬움: 대부분 빈칸 가운데 무작위로 둡니다. 한 수로 이길 자리나 막아야 할 자리가 있어도 절반쯤만 알아챕니다.
• 보통: 이길 자리가 있으면 반드시 이기고, 없으면 막아야 할 자리를 반드시 막습니다. 그 밖의 수는 네 번에 세 번은 어려움과 같은 수를, 한 번은 무작위로 둡니다. 그래서 포크에 걸리기도 합니다.
• 어려움: 미니맥스로 끝까지 읽어 가장 좋은 수만 둡니다. 결과가 같은 수가 여럿이면 상대가 두었을 때 지는 자리가 가장 많이 생기는 수를 고르고, 그래도 여럿이면 무작위로 고릅니다. 그래서 먼저 둘 때는 네 모서리 가운데 하나에 두고, 사람이 모서리에 먼저 두면 가운데로 받습니다.

무작위 선택은 컴퓨터 차례가 올 때마다 브라우저의 난수 생성기(crypto.getRandomValues)로 합니다. 어려움을 상대로는 무승부가 최선의 결과이고, 먼저 둔 컴퓨터를 상대로 비기려면 첫 응수부터 정확해야 합니다.

자주 묻는 질문

이름·역사와 전략 순서는 영어 위키백과 「Tic-tac-toe」·「OXO (video game)」·「m,n,k-game」, 나무위키 「틱택토」를 참고했고, 게임 수와 첫 수 분석은 이 게임의 판정·미니맥스 코드로 직접 계산했습니다. 게임과 컴퓨터 계산은 브라우저 안에서만 동작하며, 기록은 이 브라우저에만 저장되고 서버로 전송되지 않습니다.