Interested Article - Супер крестики-нолики

An incomplete board of Ultimate Tic-Tac-Toe.
Игра в супер крестики-нолики (большие буквы «X» и «O» представляют малые доски, которые были выиграны соответствующим игроком).
Поскольку X сыграл в правом верхнем углу локальной доски, O вынужден делать свой следующий ход на правой верхней локальной доске.

Супер крестики-нолики (также известные как ультимативные крестики-нолики , мега крестики-нолики, крестики-нолики в квадрате ) — настольная игра, состоящая из поля размером 9x9 клеток, разделенного на девять досок для игры в крестики-нолики . По сравнению с традиционными крестиками-ноликами, стратегия в этой игре концептуально сложнее и оказалась более сложной для компьютеров.

Правила

Каждое маленькое поле (3 × 3) называется малой доской, а большое (9 × 9) — глобальной доской.

Первыми ходят крестики. Они могут сыграть в любую из 81 клеток. Своим ходом они «отправляют» нолики на одну из малых досок. Например, если крестики сходили в правый нижний угол малого поля, нолики должны сделать ход на правой нижней доске, в свою очередь, «отправляя» крестики на одно из полей.

Если ход сделан так, что он должен выиграть малую доску по правилам обычных крестиков-ноликов , она отмечается соответствующим знаком (X или O) как победа игрока. Как только малое поле выиграно игроком или полностью заполнена, на нем больше не может быть сделано ни одного хода. Если игрок отправлен на такую доску, то он может играть на любой другой доске.

Игра заканчивается, когда либо игрок выигрывает глобальную доску, либо не остается ни одного законного хода; в этом случае побеждает тот игрок, который победил на большем количестве малых досок (если игроки победили на одинаковом количестве полей, объявляется ничья).

Альтернативные правила

Другая версия игры позволяет игрокам продолжать игру на уже выигранных досках, если там еще есть свободные места. Это позволяет игре длиться дольше и включает в неё дополнительные стратегические ходы. В 2020 году было показано, что этот набор правил игры допускает выигрышную стратегию для первого игрока, делающего ход, что означает, что первый игрок, делающий ход, всегда может выиграть при условии идеальной игры . Если игра с этим набором правил все еще предпочтительна, проблема вынужденного выигрыша может быть практически решена путем случайной генерации первых 4 ходов.

Игровой процесс

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

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

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

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

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

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

Варианты

Тик-Так-Ку — игра, придуманная Марком Асперхаймом и Крисом Ван Оостерумом. Правила игры такие же, как и в супер крестиках-ноликах, единственное исключение — игрок побеждает, выиграв как минимум пять малых досок.

Примечания

  1. . web.archive.org (29 июля 2021). Дата обращения: 11 июня 2023. Архивировано 29 июля 2021 года.
  2. . arxiv.org . Дата обращения: 11 июня 2023. 14 декабря 2022 года.
  3. . arxiv.org . Дата обращения: 11 июня 2023. 19 апреля 2023 года.
  4. . web.archive.org (24 февраля 2020). Дата обращения: 11 июня 2023. Архивировано из 24 февраля 2020 года.
  5. . arxiv.org . Дата обращения: 11 июня 2023. 22 декабря 2017 года.
  6. blog.theofekfoundation.org . Дата обращения: 11 июня 2023. 11 июня 2023 года.
  7. . www.173zy.com . Дата обращения: 11 июня 2023. 4 марта 2016 года.
  8. . web.archive.org (10 июня 2012). Дата обращения: 11 июня 2023. Архивировано 10 июня 2012 года.

Ссылки

Источник —

Same as Супер крестики-нолики