얼티메이트 틱택토
궁극의 틱택토, 얼티밋 틱택토(Ultimate tic-tac-toe), UTT, 슈퍼 틱택토, 메타 틱택토, (틱택토)², 전략적 틱택토, 메가 틱택토, 또는 궁극의 넛츠 앤 크로스[1]로 알려짐)는 3 × 3 격자로 배열된 9개의 틱택토 보드로 구성된 보드 게임이다.[2][3] 플레이어들은 그 중 한 명이 큰 보드에서 승리할 때까지 작은 틱택토 보드에 번갈아 가며 수를 둔다. 전통적인 틱택토에 비해 이 게임의 전략은 개념적으로 더 어려우며 컴퓨터에게 더 도전적인 것으로 입증되었다.[4]
규칙
[편집]일반 틱택토와 마찬가지로 두 플레이어(X와 O)는 번갈아 가며 수를 두며, 게임은 X 또는 O가 81개의 빈 칸 중 어느 곳이든 원하는 곳에 두는 것으로 시작한다.
만약 일반 틱택토 규칙에 따라 작은 보드에서 승리하는 수를 둔다면, 해당 작은 보드 전체는 큰 보드에서 그 플레이어에 의해 승리한 것으로 표시된다. 작은 보드가 한 플레이어에 의해 승리하거나 완전히 채워지면, 더 이상 그 보드에는 수를 둘 수 없다. 게임은 한 플레이어가 큰 보드에서 승리하거나 더 이상 합법적인 수가 남아 있지 않을 때 종료되며, 후자의 경우 게임은 무승부가 된다.[3]
게임 플레이
[편집]궁극의 틱택토는 다른 대부분의 틱택토 변형보다 훨씬 더 복잡하며, 명확한 플레이 전략이 없다. 이는 이 게임의 복잡한 게임 브랜치 때문이다. 비록 모든 수가 일반 틱택토 보드와 동일한 작은 보드에서 두어져야 하지만, 각 수는 여러 면에서 큰 보드를 고려해야 한다.
- 다음 수 예측: 작은 보드에 두는 각 수는 상대방이 다음 수를 어디에 둘 수 있는지를 결정한다. 이는 일반 틱택토에서 나쁜 수로 간주되는 수를 실행 가능한 수로 만들 수 있다. 왜냐하면 상대방이 특정 보드에 수를 두도록 강요되기 때문이다. 이런 식으로 플레이어는 상대방이 응답할 수 없이 같은 작은 보드에 연속으로 여러 번 수를 둘 수 있다. 따라서 플레이어들은 단순히 작은 보드에 집중하는 대신 큰 게임 보드를 고려해야 한다.
- 게임 트리 시각화: 게임 트리의 미래 브랜치를 시각화하는 것은 단일 보드 틱택토보다 어렵다. 각 수는 다음 수를 결정하므로, 미래 수를 예측하는 것은 훨씬 덜 선형적인 경로를 따른다. 미래 보드 위치는 더 이상 상호 교환될 수 없으며, 각 수는 극명하게 다른 가능한 미래 위치로 이어진다. 이는 게임 트리를 시각화하기 어렵게 만들고, 많은 가능한 경로를 간과하게 만들 수 있다.
- 게임 승리: 궁극의 틱택토 규칙 때문에, 큰 보드는 직접적으로 영향을 받지 않는다. 그것은 작은 보드에서 발생하는 행동에 의해서만 결정된다. 이는 두는 각 수가 작은 보드를 이기기 위함이 아니라, 큰 보드를 이기기 위함이라는 것을 의미한다. 실제로, 더 중요한 작은 보드를 자신이 이기기 위해 상대방에게 작은 보드를 희생하는 것이 전략적일 수 있다. 이러한 복잡성의 추가적인 층은 수의 상대적 중요성과 의미를 분석하기 어렵게 만들고, 결과적으로 잘 플레이하기 어렵게 만든다.
컴퓨터 구현
[편집]틱택토는 깊이 우선 탐색을 사용하여 거의 즉시 해결할 수 있을 만큼 기초적이지만[5], 궁극의 틱택토는 무차별 대입 전술로는 합리적으로 해결할 수 없다. 따라서 이 게임을 플레이하려면 더 창의적인 컴퓨터 구현이 필요하다.
가장 일반적인 인공지능 (AI) 전술인 최소극대화는 궁극의 틱택토를 플레이하는 데 사용될 수 있지만, 어려움을 겪는다. 이는 비교적 간단한 규칙에도 불구하고 궁극의 틱택토에는 간단한 휴리스틱 평가 함수가 없기 때문이다. 이 함수는 최소극대화에 필수적이며, 특정 위치가 얼마나 좋은지를 결정한다. 비록 작은 보드 승리 수를 고려하여 궁극의 틱택토에 대한 기본적인 평가 함수를 만들 수 있지만, 이러한 함수는 정량화하기 훨씬 어려운 위치적 이점을 크게 간과한다. 효율적인 평가 함수가 없으면 대부분의 일반적인 컴퓨터 구현은 약하며, 따라서 인간을 꾸준히 능가할 수 있는 컴퓨터 상대는 거의 없다.[4]
그러나 몬테카를로 트리 탐색 알고리즘과 같이 평가 함수가 필요 없는 인공지능 알고리즘은 이 게임을 플레이하는 데 문제가 없다. 몬테카를로 트리 탐색은 위치 평가 대신 게임의 무작위 시뮬레이션에 의존하여 위치가 얼마나 좋은지를 결정하므로, 현재 위치가 얼마나 좋은지를 정확하게 평가할 수 있다. 따라서 이러한 알고리즘을 사용하는 컴퓨터 구현은 최소극대화 솔루션보다 성능이 우수하고 인간 상대를 꾸준히 이길 수 있다.[2][6]
온라인 궁극의 틱택토
[편집]온라인 UTT는 인터넷을 통해 플레이되며 전 세계 플레이어가 실시간으로 서로 대결할 수 있는 UTT이다. 게임의 인기 감소와 제한된 플레이어 수로 인해 온라인 UTT 플랫폼은 많지 않다. UTT의 오프닝과 승리 전략과 같은 이론을 공식화한 플레이어는 거의 없다. 그러나 이러한 목표를 위한 현재 커뮤니티가 존재한다.
변형
[편집]게임의 한 변형은 이미 결정된 칸에 빈 공간이 남아 있는 경우 플레이어가 계속 플레이하도록 요구한다. 이것은 게임이 더 오래 지속되고 더 많은 전략적 수를 포함하게 한다. 2020년에 이 규칙 세트는 첫 번째 수를 두는 플레이어가 항상 이길 수 있는 승리 전략을 허용한다는 것이 밝혀졌으며, 이는 완벽한 플레이를 가정할 때 첫 번째 플레이어가 항상 이길 수 있다는 것을 의미한다.[7] 이 규칙 세트로 플레이하는 것이 여전히 선호된다면, 강제 승리 문제는 처음 4수를 무작위로 생성하여 실질적으로 해결할 수 있다. 이것은 5자리 숫자를 무작위로 생성한 다음 첫 번째 숫자를 사용하여 큰 보드를 선택하고 다음 네 자리를 사용하여 적절한 작은 보드에 "X"와 "O"를 놓는 방식으로 가장 효과적으로 수행된다.[8]
또한 큰 보드 내부에 더 많은 층의 중첩된 틱택토 게임을 효과적으로 생성하여 궁극의 틱택토의 확장된 버전을 만들 수도 있다. 예를 들어, 한 층이 더 있는 게임은 81개의 기본 수준 틱택토 보드를 가질 것이다.[9]
마크 아스퍼하임과 크리스 반 오스테룸이 발명한 게임인 틱택쿠[10][11]는 궁극의 틱택토와 유사한 규칙을 가지고 있지만, 플레이어는 한 줄에 세 개가 아닌 최소 다섯 개의 작은 보드를 이겨야 게임에서 승리한다.
같이 보기
[편집]각주
[편집]- ↑ Konforti, Nicole; Epstein, Dave. “NP Completeness in Contemporary Board Games”.
- ↑ 가 나 Whitney, George; Janoski, Janine (2016년 11월 26일). “Group Actions on Winning Games of Super Tic-Tac-Toe”. arXiv:1606.04779 [math.CO].
- ↑ 가 나 Orlin, Ben (2013년 6월 1일). “Ultimate Tic-Tac-Toe”. 《Math with Bad Drawings》. 2021년 8월 30일에 원본 문서에서 보존된 문서. 2016년 10월 18일에 확인함.
- ↑ 가 나 Lifshitz, Eytan; Tsurel, David (2016년 12월 26일). “AI Approaches to Ultimate Tic-Tac-Toe” (PDF). 《The Rachel and Selim Benin School of Computer Science and Engineering》. 2021년 7월 29일에 원본 문서 (PDF)에서 보존된 문서.
- ↑ Schaefer, Steve (2002). “MathRec Solutions (Tic-Tac-Toe)”. 2020년 2월 24일에 원본 문서에서 보존된 문서. 2016년 10월 18일에 확인함.
- ↑ Gila, Ofek (2016년 6월 2일). “What is the Monte Carlo tree search?”. 《We Blog》. 2016년 10월 18일에 확인함.
- ↑ Bertholon, Guillaume; Géraud-Stewart, Rémi; Kugelmann, Axel; Lenoir, Théo; Naccache, David (2020년 6월 3일). “At Most 43 Moves, At Least 29: Optimal Strategies and Bounds for Ultimate Tic-Tac-Toe” (영어). arXiv:2006.02353v2 [cs.GT].
- ↑ Diamond, Justin (2022년 7월 13일). “A Practical Method for Preventing Forced Wins in Ultimate Tic-Tac-Toe” (영어). arXiv:2207.06239 [math.HO].
- ↑ Chandler Swift. “(meta-)*tic-tac-toe”.
- ↑ “2009年度门萨最佳动脑奖揭晓” [2009 Mensah Best Brain Picking Award Announced] (중국어). 《www.boardgamenews.com》. 2009년 4월 29일. 2016년 3월 4일에 원본 문서에서 보존된 문서. 2012년 5월 19일에 확인함 – 173zy.com 경유.
- ↑ “Tic Tac Ku”. 《marbles – the brain store》. 2012년 6월 10일에 원본 문서에서 보존된 문서. 2012년 5월 19일에 확인함.
