얼티메이트 틱택토

alt=궁극의 틱택토의 불완전한 보드.|섬네일|불완전한 궁극의 틱택토 게임 (큰 'X'와 'O'는 해당 플레이어가 이긴 작은 보드를 나타낸다). 이전 수는 오른쪽 아래 보드의 중앙 칸에 O가 놓여, X는 다음 수를 큰 보드의 중앙에 위치한 작은 보드(파란색으로 강조 표시됨)에 두어야 한다.
섬네일|X가 작은 보드의 오른쪽 상단 모서리에 놓았으므로, O는 다음 수를 큰 보드의 오른쪽 상단 작은 보드(빨간색으로 강조 표시됨)에 두어야 한다.
궁극의 틱택토, 얼티밋 틱택토(Ultimate tic-tac-toe), UTT, 슈퍼 틱택토, 메타 틱택토, (틱택토)², 전략적 틱택토, 메가 틱택토, 또는 궁극의 넛츠 앤 크로스로 알려짐)는 3 × 3 격자로 배열된 9개의 틱택토 보드로 구성된 보드 게임이다. 플레이어들은 그 중 한 명이 큰 보드에서 승리할 때까지 작은 틱택토 보드에 번갈아 가며 수를 둔다. 전통적인 틱택토에 비해 이 게임의 전략은 개념적으로 더 어려우며 컴퓨터에게 더 도전적인 것으로 입증되었다.

 규칙 
일반 틱택토와 마찬가지로 두 플레이어(X와 O)는 번갈아 가며 수를 두며, 게임은 X 또는 O가 81개의 빈 칸 중 어느 곳이든 원하는 곳에 두는 것으로 시작한다.

만약 일반 틱택토 규칙에 따라 작은 보드에서 승리하는 수를 둔다면, 해당 작은 보드 전체는 큰 보드에서 그 플레이어에 의해 승리한 것으로 표시된다. 작은 보드가 한 플레이어에 의해 승리하거나 완전히 채워지면, 더 이상 그 보드에는 수를 둘 수 없다. 게임은 한 플레이어가 큰 보드에서 승리하거나 더 이상 합법적인 수가 남아 있지 않을 때 종료되며, 후자의 경우 게임은 무승부가 된다.

 게임 플레이 
궁극의 틱택토는 다른 대부분의 틱택토 변형보다 훨씬 더 복잡하며, 명확한 플레이 전략이 없다. 이는 이 게임의 복잡한 게임 브랜치 때문이다. 비록 모든 수가 일반 틱택토 보드와 동일한 작은 보드에서 두어져야 하지만, 각 수는 여러 면에서 큰 보드를 고려해야 한다.
 다음 수 예측: 작은 보드에 두는 각 수는 상대방이 다음 수를 어디에 둘 수 있는지를 결정한다. 이는 일반 틱택토에서 나쁜 수로 간주되는 수를 실행 가능한 수로 만들 수 있다. 왜냐하면 상대방이 특정 보드에 수를 두도록 강요되기 때문이다. 이런 식으로 플레이어는 상대방이 응답할 수 없이 같은 작은 보드에 연속으로 여러 번 수를 둘 수 있다. 따라서 플레이어들은 단순히 작은 보드에 집중하는 대신 큰 게임 보드를 고려해야 한다.
 게임 트리 시각화: 게임 트리의 미래 브랜치를 시각화하는 것은 단일 보드 틱택토보다 어렵다. 각 수는 다음 수를 결정하므로, 미래 수를 예측하는 것은 훨씬 덜 선형적인 경로를 따른다. 미래 보드 위치는 더 이상 상호 교환될 수 없으며, 각 수는 극명하게 다른 가능한 미래 위치로 이어진다. 이는 게임 트리를 시각화하기 어렵게 만들고, 많은 가능한 경로를 간과하게 만들 수 있다.
 게임 승리: 궁극의 틱택토 규칙 때문에, 큰 보드는 직접적으로 영향을 받지 않는다. 그것은 작은 보드에서 발생하는 행동에 의해서만 결정된다. 이는 두는 각 수가 작은 보드를 이기기 위함이 아니라, 큰 보드를 이기기 위함이라는 것을 의미한다. 실제로, 더 중요한 작은 보드를 자신이 이기기 위해 상대방에게 작은 보드를 희생하는 것이 전략적일 수 있다. 이러한 복잡성의 추가적인 층은 수의 상대적 중요성과 의미를 분석하기 어렵게 만들고, 결과적으로 잘 플레이하기 어렵게 만든다.

 컴퓨터 구현 
틱택토는 깊이 우선 탐색을 사용하여 거의 즉시 해결할 수 있을 만큼 기초적이지만, 궁극의 틱택토는 무차별 대입 전술로는 합리적으로 해결할 수 없다. 따라서 이 게임을 플레이하려면 더 창의적인 컴퓨터 구현이 필요하다.

가장 일반적인 인공지능 (AI) 전술인 최소극대화는 궁극의 틱택토를 플레이하는 데 사용될 수 있지만, 어려움을 겪는다. 이는 비교적 간단한 규칙에도 불구하고 궁극의 틱택토에는 간단한 휴리스틱 평가 함수가 없기 때문이다. 이 함수는 최소극대화에 필수적이며, 특정 위치가 얼마나 좋은지를 결정한다. 비록 작은 보드 승리 수를 고려하여 궁극의 틱택토에 대한 기본적인 평가 함수를 만들 수 있지만, 이러한 함수는 정량화하기 훨씬 어려운 위치적 이점을 크게 간과한다. 효율적인 평가 함수가 없으면 대부분의 일반적인 컴퓨터 구현은 약하며, 따라서 인간을 꾸준히 능가할 수 있는 컴퓨터 상대는 거의 없다.

그러나 몬테카를로 트리 탐색 알고리즘과 같이 평가 함수가 필요 없는 인공지능 알고리즘은 이 게임을 플레이하는 데 문제가 없다. 몬테카를로 트리 탐색은 위치 평가 대신 게임의 무작위 시뮬레이션에 의존하여 위치가 얼마나 좋은지를 결정하므로, 현재 위치가 얼마나 좋은지를 정확하게 평가할 수 있다. 따라서 이러한 알고리즘을 사용하는 컴퓨터 구현은 최소극대화 솔루션보다 성능이 우수하고 인간 상대를 꾸준히 이길 수 있다.

 온라인 궁극의 틱택토 
온라인 UTT는 인터넷을 통해 플레이되며 전 세계 플레이어가 실시간으로 서로 대결할 수 있는 UTT이다. 게임의 인기 감소와 제한된 플레이어 수로 인해 온라인 UTT 플랫폼은 많지 않다. UTT의 오프닝과 승리 전략과 같은 이론을 공식화한 플레이어는 거의 없다. 그러나 이러한 목표를 위한 현재 커뮤니티가 존재한다.

 변형 

게임의 한 변형은 이미 결정된 칸에 빈 공간이 남아 있는 경우 플레이어가 계속 플레이하도록 요구한다. 이것은 게임이 더 오래 지속되고 더 많은 전략적 수를 포함하게 한다. 2020년에 이 규칙 세트는 첫 번째 수를 두는 플레이어가 항상 이길 수 있는 승리 전략을 허용한다는 것이 밝혀졌으며, 이는 완벽한 플레이를 가정할 때 첫 번째 플레이어가 항상 이길 수 있다는 것을 의미한다. 이 규칙 세트로 플레이하는 것이 여전히 선호된다면, 강제 승리 문제는 처음 4수를 무작위로 생성하여 실질적으로 해결할 수 있다. 이것은 5자리 숫자를 무작위로 생성한 다음 첫 번째 숫자를 사용하여 큰 보드를 선택하고 다음 네 자리를 사용하여 적절한 작은 보드에 "X"와 "O"를 놓는 방식으로 가장 효과적으로 수행된다.

또한 큰 보드 내부에 더 많은 층의 중첩된 틱택토 게임을 효과적으로 생성하여 궁극의 틱택토의 확장된 버전을 만들 수도 있다. 예를 들어, 한 층이 더 있는 게임은 81개의 기본 수준 틱택토 보드를 가질 것이다.

마크 아스퍼하임과 크리스 반 오스테룸이 발명한 게임인 틱택쿠는 궁극의 틱택토와 유사한 규칙을 가지고 있지만, 플레이어는 한 줄에 세 개가 아닌 최소 다섯 개의 작은 보드를 이겨야 게임에서 승리한다.

 같이 보기 
 재귀
 틱택토 변형

 각주 

 외부 링크 
 몬테카를로 트리 탐색 구현
 브라우저에서 궁극의 틱택토를 플레이하기 위한 AlphaZero-like AI 솔루션
 인공지능들이 서로 대결하는 궁극의 틱택토 게임
 온라인 멀티플레이어 및 AI와의 게임
 파이썬 구현

분류:수학 게임
분류:추상전략게임
분류:종이-연필 게임