Русская Википедия:Ultimate крестики-нолики
Стратегические крестики-нолики (также известные как ultimate tic-tac-toe, ten-tac-toe, super tic-tac-toe, strategic tic-tac-toe, meta tic-tac-toe, tic-tac-tic-tac-toe-toe, (tic-tac-toe)² или uttt) это настольная игра, состоящая из девяти досок для игры в крестики-нолики, расположенных в сетке 3 × 3.[1][2] Игроки по очереди играют на меньших досках крестиков-ноликов до тех пор, пока один из них не выиграет на большей доске крестиков-ноликов. По сравнению с традиционными крестиками-ноликами, стратегия в этой игре концептуально сложнее и оказалась более сложной для компьютеров.[3]
Правила
Каждая маленькая доска 3 × 3 называется локальной доской, а большая доска 3 × 3 — глобальной доской.
Игра начинается с того, что X играет, куда захочет, в любое из 81 пустого места. Этот ход «отправляет» своего противника в его относительное место. Например, если X сыграл в правом верхнем квадрате своей локальной доски, то O должен сыграть следующим в локальной доске в правом верхнем углу глобальной доски. Затем О может сыграть на любом из девяти доступных мест на этой локальной доске, каждый ход отправляя Х на другую локальную доску.
Если ход сделан так, что он должен выиграть локальную доску по правилам обычного крестиков-ноликов, то вся локальная доска отмечается как победа игрока на глобальной доске. Как только локальная доска выиграна игроком или полностью заполнена, на этой доске больше не может быть сыграно ни одного хода. Если игрок отправлен на такую доску, то он может играть на любой другой доске. Игра заканчивается, когда либо игрок выигрывает глобальную доску, либо не остается ни одного законного хода, в этом случае игра заканчивается вничью.
Другая версия игры позволяет игрокам продолжать игру на уже выигранных клетках, если там еще есть свободные места. Это позволяет игре длиться дольше и включает в себя дополнительные стратегические ходы. Какому правилу следовать, решают сами игроки. В 2020 году было показано, что этот набор правил игры допускает выигрышную стратегию для первого игрока, делающего ход, что означает, что первый игрок, делающий ход, всегда может выиграть при условии идеальной игры.[4] Если игра с этим набором правил все еще предпочтительна, проблема вынужденного выигрыша может быть практически решена путем случайной генерации первых 4 ходов.[5]
Игровой процесс
Стратегические крестики-нолики значительно сложнее, чем большинство других разновидностей крестиков-ноликов, поскольку в ней нет четкой стратегии игры. Это происходит из-за сложного игрового разветвления в этой игре. Несмотря на то, что каждый ход должен быть сыгран на локальной доске, эквивалентной обычной доске для игры в крестики-нолики, каждый ход должен учитывать глобальную доску несколькими способами:
- Предвидение следующего хода: Каждый ход, сделанный на локальной доске, определяет, куда может быть сделан следующий ход противника. Это может сделать ходы, которые в обычных крестиках-ноликах считаются плохими, жизнеспособными, поскольку противник отправляется на другую локальную доску и не может немедленно отреагировать на них. Таким образом, игроки вынуждены рассматривать большую игровую доску, вместо того чтобы просто сосредоточиться на локальной доске.
- Визуализация дерева игры: Визуализация будущих ветвей дерева игры сложнее, чем в оригинальных крестиках-ноликах. Каждый ход определяет следующий ход, и поэтому чтение вперед — предсказание будущих ходов — идет по гораздо менее линейному пути. Будущие позиции на доске больше не взаимозаменяемы, каждый ход приводит к разительно отличающимся возможным будущим позициям. Это делает дерево игры трудным для визуализации, и, возможно, многие возможные пути остаются незамеченными.
- Победа в игре: В соответствии с правилами игры в крестики-нолики, глобальная доска никогда не подвергается прямому воздействию. Она управляется только действиями, происходящими на локальных досках. Это означает, что каждый локальный ход делается не для победы на локальной доске, а для победы на глобальной доске. Местные победы не имеют ценности, если они не могут быть использованы для победы на глобальной доске — фактически, стратегически может быть выгодно пожертвовать местную доску противнику, чтобы самому выиграть более важную местную доску. Этот дополнительный слой сложности затрудняет анализ относительной важности и значимости ходов, и, следовательно, затрудняет хорошую игру.
Компьютерные реализации
В то время как «крестики-нолики» элементарно решаются[6] и могут быть сделаны почти мгновенно с помощью поиска в глубину, стратегические крестики-нолики не могут быть разумно решены с помощью тактики грубой силы. Поэтому для игры в эту игру необходимы более творческие компьютерные реализации.
Наиболее распространенная тактика искусственного интеллекта (ИИ), минимакс, может быть использована для игры в стратегические крестики-нолики, но при этом возникают трудности. Это связано с тем, что, несмотря на относительно простые правила, в конечной тактике отсутствует простая эвристическая функция оценки. Эта функция необходима в минимаксе, поскольку она определяет, насколько хороша та или иная позиция. Хотя для стратегических крестиков-ноликов можно сделать элементарные оценочные функции, принимая во внимание количество локальных побед, они в значительной степени упускают из виду позиционное преимущество, которое гораздо труднее оценить количественно. Без какой-либо эффективной функции оценки большинство типичных компьютерных реализаций слабы, и поэтому существует мало компьютерных противников, которые могут последовательно обыгрывать людей.[3]
Однако алгоритмы искусственного интеллекта, которым не нужны функции оценки, такие как алгоритм поиска по дереву Монте-Карло, без проблем играют в эту игру. Поиск по дереву Монте-Карло опирается на случайное моделирование игр для определения того, насколько хороша позиция, вместо позиционной оценки и поэтому способен точно оценить, насколько хороша текущая позиция. Поэтому компьютерные реализации, использующие эти алгоритмы, как правило, превосходят минимаксные решения и могут последовательно побеждать человеческих оппонентов.[1][7]
Вариант
Тик-Так-Ку — игра, придуманная Марком Асперхаймом и Крисом Ван Оостерумом.[8][9] Правила игры такие же, как и в стратегических крестиках-ноликах, единственное исключение — игрок побеждает в игре, выиграв как минимум пять локальных досок.
Примечания
Ссылки
- Monte Carlo tree-search implementation
- AlphaZero-like AI solution for playing Ultimate Tic-Tac-Toe in the browser
- Ultimate Tic-Tac-Toe game where artificial intelligences confront each other
