Окончательные крестики-нолики
Ultimate крестики-нолики (также известные как супер крестики-нолики , мета крестики-нолики или (крестики-нолики)² [1] ) — настольная игра, состоящая из девяти досок для игры в крестики-нолики, расположенных в сетке 3 × 3. [2] [3] Игроки по очереди играют на маленьких досках для крестиков-ноликов, пока один из них не выиграет на большой доске. По сравнению с традиционными «крестиками-ноликами» стратегия в этой игре концептуально более сложна и оказалась более сложной для компьютеров. [4]
Правила
[ редактировать ]Как и в обычных играх «крестики-нолики», два игрока (X и O) ходят по очереди, начиная с X. Игра начинается с того, что X играет где хочет, в любом из 81 пустого места. Далее играет противник, однако он вынужден играть на маленькой доске, указанной относительным местоположением предыдущего хода. Например, если X играет в правом верхнем углу маленькой доски (3 × 3), то игрок O должен играть на маленькой доске, расположенной в правом верхнем углу большой доски. Игра на любом из доступных мест определяет, на какой маленькой доске будет играть следующий игрок.
Если ход сделан так, чтобы выиграть небольшую доску по правилам обычных крестиков-ноликов , то вся маленькая доска помечается как выигранная игроком на большей доске. Как только маленькая доска выиграна игроком или она полностью заполнена, на этой доске больше нельзя делать ходы. Если игрока отправляют на такую доску, то он может играть на любой другой доске. Игра заканчивается, когда игрок выигрывает большую доску или когда не остается допустимых ходов, и в этом случае игра завершается вничью. [3]
Геймплей
[ редактировать ]Супер-крестики-нолики значительно сложнее, чем большинство других разновидностей крестиков-ноликов, поскольку в игре нет четкой стратегии. Это связано со сложным ветвлением в этой игре. Несмотря на то, что каждый ход должен выполняться на маленькой доске, эквивалентной обычной доске для крестиков-ноликов, каждый ход должен учитывать большую доску несколькими способами:
- Предвидение следующего хода: каждый ход, сыгранный на маленькой доске, определяет, где может быть сделан следующий ход противника. Это может сделать ходы, которые считаются плохими в обычных играх в крестики-нолики, жизнеспособными, поскольку противник вынужден играть на определенной доске. Таким образом, игрок мог играть на одной и той же доске меньшего размера несколько раз подряд, при этом его противник не мог ответить. Таким образом, игроки вынуждены рассматривать игровое поле большего размера, а не просто сосредотачиваться на досках меньшего размера.
- Визуализация дерева игры: Визуализировать будущие ветки дерева игры сложнее, чем крестики-нолики на одной доске. Каждый ход определяет следующий ход, и поэтому чтение вперед (предсказание будущих ходов) идет гораздо менее линейным путем. Будущие позиции на доске больше не являются взаимозаменяемыми, каждый ход приводит к совершенно различным возможным будущим позициям. Это затрудняет визуализацию дерева игры, в результате чего многие возможные пути могут быть упущены из виду.
- Победа в игре: согласно правилам супер-крестиков-ноликов, большая доска никогда не затрагивается напрямую. Он регулируется только действиями, которые происходят на небольших досках. Это означает, что каждый сыгранный ход предназначен не для выигрыша маленькой доски, а для выигрыша на большей доске. На самом деле, может быть стратегически выгодно пожертвовать небольшую доску вашему оппоненту, чтобы самому выиграть более важную маленькую доску. Этот дополнительный уровень сложности затрудняет анализ относительной важности и значимости ходов и, следовательно, затрудняет хорошую игру.
Компьютерные реализации
[ редактировать ]Пока крестики-нолики решить элементарно [5] и может быть выполнено почти мгновенно с помощью поиска в глубину , окончательные крестики-нолики не могут быть разумно решены с использованием какой-либо тактики грубой силы. Следовательно, для этой игры необходимы более творческие компьютерные реализации.
Самая распространенная тактика искусственного интеллекта (ИИ), минимакс , может использоваться для игры в «крестики-нолики», но при этом у нее возникают трудности. Это связано с тем, что, несмотря на относительно простые правила, в Ultimate Tic-Tac-Toe отсутствует какая-либо простая эвристическая функция оценки . Эта функция необходима в минимаксе, поскольку определяет, насколько хороша конкретная позиция. Хотя элементарные функции оценки могут быть созданы для окончательной игры в крестики-нолики, принимая во внимание количество небольших побед на доске, они в значительной степени упускают из виду позиционное преимущество, которое гораздо труднее измерить количественно. Без какой-либо эффективной функции оценки большинство типичных компьютерных реализаций являются слабыми, и поэтому существует мало компьютерных противников, которые могут постоянно переигрывать людей. [4]
Однако алгоритмы искусственного интеллекта, которым не нужны функции оценки, такие как алгоритм поиска по дереву Монте-Карло , без проблем играют в эту игру. Поиск по дереву Монте-Карло основан на случайном моделировании игр, чтобы определить, насколько хороша позиция, а не на позиционной оценке, и, следовательно, позволяет точно оценить, насколько хороша текущая позиция. Следовательно, компьютерные реализации, использующие эти алгоритмы, имеют тенденцию превосходить минимаксные решения и могут постоянно побеждать оппонентов-людей. [2] [6]
Варианты
[ редактировать ]Вариант игры позволяет игрокам продолжать игру в уже выигранных ящиках, если там еще остались пустые места. Это позволяет игре длиться дольше и предполагает дальнейшие стратегические ходы. В 2020 году было показано, что этот набор правил игры допускает выигрышную стратегию для первого игрока, который сделает ход, а это означает, что первый игрок, который сделает ход, всегда может выиграть при условии идеальной игры . [7] Если игра с этим набором правил по-прежнему предпочтительна, проблему принудительного выигрыша можно практически решить, сгенерировав первые 4 хода случайным образом. Наиболее эффективно это делается путем случайной генерации пятизначного числа, затем использования первой цифры для выбора доски большего размера, а следующих четырех цифр для размещения букв «X» и «O» на соответствующей маленькой доске. [8]
«Тик-Так-Ку» — игра, изобретенная Марком Асперхаймом и Крисом Ван Остерумом. [9] [10] [11] имеет те же правила, что и «Крестики-нолики», однако игрок выигрывает игру, выиграв как минимум пять маленьких досок вместо трех в линию.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Конфорти, Николь; Эпштейн, Дэйв. «NP-полнота в современных настольных играх» . [ мертвая ссылка ]
- ^ Jump up to: а б Уитни, Джордж; Яноски, Джанин (26 ноября 2016 г.). «Действия группы при победе в супер-крестиках-ноликах». arXiv : 1606.04779 [ math.CO ].
- ^ Jump up to: а б Орлин, Бен (1 июня 2013 г.). «Окончательные крестики-нолики» . Математика с плохими рисунками . Архивировано из оригинала 30 августа 2021 года . Проверено 18 октября 2016 г.
- ^ Jump up to: а б Лифшиц, Эйтан; Цурел, Давид (26 декабря 2016 г.). «Подходы искусственного интеллекта к совершенству крестиков-ноликов» (PDF) . Бенинская школа компьютерных наук и инженерии Рэйчел и Селима . Архивировано из оригинала (PDF) 29 июля 2021 года.
- ^ Шефер, Стив (2002). «MathRec Solutions (Крестики-нолики)» . Архивировано из оригинала 24 февраля 2020 года . Проверено 18 октября 2016 г.
- ^ Гила, Офек (2 июня 2016 г.). «Что такое поиск по дереву Монте-Карло?» . Мы ведем блог . Проверено 18 октября 2016 г.
- ^ Бертолон, Гийом; Жеро-Стюарт, Реми; Кугельманн, Аксель; Ленуар, Тео; Наккаче, Дэвид (3 июня 2020 г.). «Не более 43 ходов, не менее 29: оптимальные стратегии и границы для идеальных крестиков-ноликов». arXiv : 2006.02353v2 [ cs.GT ].
- ^ Даймонд, Джастин (13 июля 2022 г.). «Практический метод предотвращения вынужденных побед в игре в крестики-нолики». arXiv : 2207.06239 [ math.HO ].
- ^ Эрик Арнесон. «Победители премии Mensa Select» . Архивировано из оригинала 26 июня 2015 года . Проверено 19 мая 2012 г.
- ^ «Объявлена награда Mensah за лучший выбор мозга в 2009 году» [Объявлена награда Mensah за лучший выбор мозга за 2009 год] www.boardgamenews.com (на китайском языке, 29 апреля 2009 г. Архивировано из оригинала 4 марта 2016 г. Проверено 19 мая 2012 г. ). через 173zy.com.
- ^ «Тик-Так Ку» . шарики – хранилище мозга . Архивировано из оригинала 10 июня 2012 года . Проверено 19 мая 2012 г.
