얼티메이트 틱택토

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

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

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

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

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

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

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

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

## 변형

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

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

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

## 같이 보기
* 재귀
* 틱택토 변형

## 각주

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

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