얼티메이트 틱택토(Ultimate Tic-Tac-Toe, UTT)는 3×3 격자로 배열된 9개의 틱택토 보드로 구성된 보드 게임이다. 슈퍼 틱택토(super tic-tac-toe), 메타 틱택토(meta tic-tac-toe), (틱택토)², 전략적 틱택토(strategic tic-tac-toe), 메가 틱택토(mega tic tac toe), 얼티밋 넛츠 앤 크로스(Ultimate Noughts and Crosses) 등으로도 불린다.
규칙
두 플레이어(X와 O)가 번갈아 가며 수를 둔다. 첫 수는 X 또는 O가 81개의 빈 칸 중 어디든 원하는 곳에 둘 수 있다. 이후의 수는 직전에 둔 위치에 따라 결정된다. 즉, 한 플레이어가 작은 보드의 특정 칸에 수를 두면, 상대방은 그 칸에 해당하는 큰 보드 상의 작은 보드에 수를 두어야 한다. 예를 들어, 직전 수가 오른쪽 아래 작은 보드의 중앙 칸에 놓였다면, 다음 플레이어는 큰 보드의 중앙에 위치한 작은 보드에 수를 두어야 한다.
일반적인 틱택토 규칙에 따라 작은 보드에서 승리하는 수가 만들어지면, 해당 작은 보드 전체는 그 플레이어가 승리한 것으로 표시된다. 작은 보드가 한 플레이어에 의해 승리하거나 빈 칸 없이 가득 차게 되면, 더 이상 그 보드에는 수를 둘 수 없으며, 만약 플레이어가 그러한 보드로 보내졌을 경우 다른 보드를 선택하여 수를 둘 수 있다. 게임은 한 플레이어가 큰 보드(3×3 작은 보드 격자)에서 가로·세로·대각선 한 줄을 승리로 채우거나 더 이상 합법적인 수가 없을 때 종료되며, 후자의 경우 무승부가 된다.
게임 전략
얼티메이트 틱택토는 기존 틱택토보다 훨씬 복잡한 전략을 요구한다. 각 수는 상대방의 다음 수 위치를 결정하기 때문에, 기존 틱택토에서는 나쁜 수로 간주되는 움직임도 얼티메이트 틱택토에서는 전략적으로 사용될 수 있다. 플레이어는 작은 보드에서의 승리보다 큰 보드에서의 승리를 목표로 해야 하며, 필요에 따라 일부 작은 보드를 상대방에게 희생하는 전략도 사용된다.
컴퓨터 구현
일반 틱택토는 깊이 우선 탐색(DFS)으로 거의 즉시 해결될 수 있지만, 얼티메이트 틱택토는 무차별 대입 방식으로는 합리적으로 해결하기 어렵다. 가장 일반적인 인공지능 알고리즘인 미니맥스(minimax)는 간단한 평가 함수가 부족하여 이 게임에서 어려움을 겪는다. 반면, 몬테카를로 트리 탐색(MCTS) 알고리즘은 위치 평가 대신 무작위 시뮬레이션에 의존하므로 얼티메이트 틱택토에 효과적으로 적용될 수 있으며, 인간 상대를 일관되게 이길 수 있는 것으로 알려져 있다.
수학적 연구
2020년 발표된 연구(arXiv:2006.02353)에 따르면, 첫 번째 플레이어(X)에게 최대 43수 이내에 승리하는 전략이 존재하며, 두 번째 플레이어(O)는 최소 29수까지 패배를 지연시킬 수 있는 방어 전략을 가진다. 또한 최적 전략의 첫 두 수에 대한 분석 결과, X의 첫 수는 반드시 이중(double, 즉 (i,i) 형태의 칸)이어야 하며, O의 첫 수가 (i,j)일 경우 X는 (j,i)로 응수해야 최적의 전략이 성립한다는 것이 증명되었다.
변형
한 가지 변형 규칙은 이미 승패가 결정된 작은 보드에 빈 칸이 남아 있을 경우에도 플레이어가 계속해서 그 보드에 수를 두도록 하는 것이다. 이 규칙 하에서는 첫 번째 플레이어에게 항상 승리 전략이 존재하는 것으로 밝혀졌다. 또한 큰 보드 내에 더 많은 층의 중첩된 틱택토 게임을 추가하여 확장된 버전을 만들 수도 있다. 틱택쿠(Tic-Tac-Ku)는 마크 애스퍼하임(Mark Asperheim)과 크리스 반 오스테룸(Cris Van Oosterum)이 발명한 변형 게임으로, 한 줄에 세 개가 아닌 최소 다섯 개의 작은 보드를 이겨야 승리한다.
온라인 및 소프트웨어
얼티메이트 틱택토는 보드게임 아레나(Board Game Arena), 포키(Poki) 등의 온라인 플랫폼에서 플레이할 수 있으며, Flathub를 통해 리눅스용 데스크톱 앱도 배포되고 있다.
