Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Неполная доска Ultimate Tic-Tac-Toe.
Доска незавершенной окончательной игры в крестики-нолики (большие «X» и «O» обозначают местные настольные игры, выигранные этим игроком). Самым последним ходом O играл в среднем левом квадрате верхней средней сетки, заставляя X сделать свой следующий ход в средней левой сетке.

Окончательные крестики-нолики (также известные как супер крестики-нолики , стратегические крестики-нолики , мета-крестики-нолики , крестики-нолики-крестики-нолики или (крестики-нолики ) ² [1] ) - настольная игра, состоящая из девяти досок для игры в крестики-нолики, расположенных в сетке 3 × 3. [2] [3] Игроки по очереди играют на меньших досках в крестики-нолики, пока один из них не выиграет на большей доске для крестиков-ноликов. По сравнению с традиционными крестиками-ноликами, стратегия в этой игре концептуально более сложна и оказалась более сложной для компьютеров. [4]

Правила [ править ]

Поскольку X играл в правом верхнем углу локальной доски, O вынужден сделать свой следующий ход в правом верхнем углу локальной доски.

Каждая маленькая доска 3x3 для крестиков-ноликов называется локальной доской, а большая доска 3x3 - глобальной доской.

Игра начинается с того, что X играют где угодно на любом из 81 пустых мест. Этот ход «отправляет» противника в его относительное местоположение. Например, если X играл в правом верхнем квадрате своего локального поля, то O должен играть следующим на локальном поле в правом верхнем углу глобального поля. Затем O может играть в любом из девяти доступных мест на этом локальном поле, каждый ход отправляет X на другое локальное поле.

Если ход сделан так, чтобы выиграть локальную доску по правилам обычных крестиков-ноликов , то вся местная доска помечается как победа для игрока на глобальной доске.

После того, как игрок выиграл местную доску или она была полностью заполнена, больше нельзя делать ходы на этой доске. Если игрок попадает на такую ​​доску, то этот игрок может играть на любой другой доске.

Другая версия игры позволяет игрокам продолжить игру в уже выигранных боксах, если еще есть пустые места. Это позволяет игре длиться дольше и требует дальнейших стратегических ходов. Какому правилу следовать - зависит от игроков. В 2020 году было показано, что этот набор правил игры допускает выигрышную стратегию для первого игрока, который сделает ход, а это означает, что первый игрок, который сделает ход, всегда может выиграть при условии идеальной игры . [5]

Игра заканчивается, когда либо игрок выигрывает глобальную доску, либо не остается законных ходов, и в этом случае игра заканчивается вничью. [3]

Геймплей [ править ]

Окончательные крестики-нолики значительно сложнее, чем большинство других разновидностей крестиков-ноликов, поскольку нет четкой стратегии игры. Это из-за сложного ветвления игры в этой игре. Несмотря на то, что каждый ход должен выполняться на локальной доске, эквивалентной обычной доске для игры в крестики-нолики, каждый ход должен учитывать глобальную доску несколькими способами:

  1. Ожидание следующего хода: каждый ход, сделанный на местной доске, определяет, где может быть сделан следующий ход оппонента. Это может сделать ходы, которые могут считаться плохими в обычных крестиках-ноликах, жизнеспособными, так как противник отправляется на другую локальную доску и может быть не в состоянии немедленно ответить на них. Поэтому игроки вынуждены рассматривать более крупное игровое поле вместо того, чтобы просто сосредотачиваться на местном поле.
  2. Визуализация игрового дерева: Визуализировать будущие ветви игрового дерева сложнее, чем одинарные крестики-нолики. Каждый ход определяет следующий ход, и поэтому чтение вперед - прогнозирование будущих ходов - следует по гораздо менее линейному пути. Будущие позиции на доске больше не взаимозаменяемы, каждый ход ведет к совершенно разным возможным будущим позициям. Это затрудняет визуализацию игрового дерева и, возможно, оставляет без внимания многие возможные пути.
  3. Победа в игре: Из-за правил абсолютных крестиков-ноликов глобальная доска никогда не затрагивается напрямую. Это регулируется только действиями, которые происходят в местных советах. Это означает, что каждый сделанный локальный ход предназначен не для победы на локальной доске, а для победы на глобальной доске. Локальные победы не имеют ценности, если они не могут быть использованы для победы на глобальной доске - на самом деле, может быть стратегическим решением пожертвовать локальную доску своему оппоненту, чтобы самому выиграть более важную локальную доску. Этот дополнительный уровень сложности усложняет людям анализ относительной важности и значимости ходов, и, следовательно, труднее хорошо играть.

Компьютерные реализации [ править ]

В то время как крестики-нолики элементарно решить [6] и могут быть выполнены почти мгновенно, используя поиск в глубину , окончательные крестики-нолики не могут быть разумно решены с помощью какой-либо тактики грубой силы. Следовательно, для этой игры необходимы более творческие компьютерные реализации.

Самая распространенная тактика искусственного интеллекта (ИИ), минимакс , может использоваться для игры в конечные крестики-нолики, но с ней трудно играть. Это потому, что, несмотря на относительно простые правила, в конечных крестиках-ноликах отсутствует какая-либо простая эвристическая функция оценки . Эта функция необходима в минимаксе, поскольку она определяет, насколько хороша конкретная позиция. Хотя элементарные функции оценки могут быть выполнены для окончательных крестиков-ноликов с учетом количества локальных побед, они в значительной степени упускают из виду позиционное преимущество, которое гораздо труднее измерить количественно. Без какой-либо эффективной функции оценки большинство типичных компьютерных реализаций слабы, и поэтому существует несколько компьютерных оппонентов, которые могут постоянно переигрывать людей. [4]

Однако алгоритмы искусственного интеллекта, которые не нуждаются в оценочных функциях, такие как алгоритм поиска по дереву Монте-Карло , не имеют проблем при игре в эту игру. Поиск по дереву Монте-Карло основан на случайном моделировании игр для определения того, насколько хороша позиция, а не на позиционной оценке, и поэтому может точно оценить, насколько хороша текущая позиция. Следовательно, компьютерные реализации, использующие эти алгоритмы, имеют тенденцию превосходить минимаксные решения и могут постоянно побеждать противников-людей. [2] [7]

Ссылки [ править ]

  1. ^ Эпштейн, Дэйв. «Полнота НП в современных настольных играх» .
  2. ^ a b Уитни, Джордж; Яноски, Жанин (26 ноября 2016 г.). «Групповые действия по выигрышу в играх Super Tic-Tac-Toe». arXiv : 1606.04779 . Bibcode : 2016arXiv160604779G . Цитировать журнал требует |journal=( помощь )
  3. ^ a b Орлин, Бен (1 июня 2013 г.). "Окончательные крестики-нолики" . Математика с плохими рисунками . Проверено 18 октября, 2016 .
  4. ^ a b Лифшиц, Эйтан; Цурел, Давид (26 декабря 2016 г.). «Подходы ИИ к идеальным крестикам-ноликам» (PDF) . Школа компьютерных наук и инженерии Рэйчел и Селим Бенин .
  5. ^ Бертолон, Гийом; Жеро-Стюарт, Реми; Кугельманн, Аксель; Ленуар, Тео; Наккаш, Дэвид (3 июня 2020 г.). «Максимум 43 хода, минимум 29: оптимальные стратегии и границы для идеальных крестиков-ноликов». arXiv : 2006.02353v2 [ cs.GT ].
  6. Перейти ↑ Schaefer, Steve (2002). «Решения MathRec (крестики-нолики)» . Проверено 18 октября, 2016 .
  7. ↑ Гила, Офек (2 июня 2016 г.). "Что такое поиск по дереву Монте-Карло?" . Мы Блог . Проверено 18 октября, 2016 .

Внешние ссылки [ править ]

  • Реализация поиска по дереву методом Монте-Карло
  • Реализация поиска по дереву Монте-Карло с открытым исходным кодом на C и Swift
  • Конечная игра в крестики-нолики, в которой искусственный интеллект противостоит друг другу