Играть одну партию в крестики-нолики более двух часов — легко.


Hypermapped gamefield

В статье будет рассказано о том как можно привнести элементы "стратегии и тактики" в привычные всем крестики-нолики. Будут описаны и проанализированы правила игры, рассказано об игровых полях.



Что предлагается?


Игра Starategic Tic-Tac-Toe (STTT) или Стратегические крестики-нолики это, как и её прародитель, игра для двух участников для которой необходимы лишь карандаш и бумага. Она является надмножеством игры Ultimate Tic-Tac-Toe также как Ultimate Tic-Tac-Toe является надмножеством обычных крестиков-ноликов (Ordinary Tic-Tac-Toe). Задача игры — помочь игрокам приобрести навыки стратегического мышления.
Домашняя страница проекта




Содержание


  1. Термины и определения
  2. Правила игры
  3. Игровые поля
  4. Анализ игры
  5. Выводы и послесловие



Термины и определения


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


  • Обычные крестики-нолики будем называть Оперативными крестиками-ноликами.
  • Игру Ultimate Tic-Tac-Toe будем называть Тактическими крестиками-ноликами.
  • Клетка — место на игровом поле в которое игроки могут поставить крестик или нолик, также называемая Оперативная клетка.
  • Оперативное поле — игровое поле Оперативных крестиков-ноликов, также называемая Тактическая клетка — 3x3 решётка из Клеток.
  • Тактическое поле — игровое поле Тактических крестиков-ноликов, также называемая Стратегическая клетка — 9х9 решётка из Клеток, 3х3 решётка из Тактических клеток.
  • Стратегическое поле — игровое поле Стратегических крестиков-ноликов — 27х27 решётка из Клеток, 9х9 решётка из Тактических клеток, 3х3 решётка из Стратегических клеток.
  • Оперативный уровень — игра в Оперативные крестики-нолики — правила ходов, условия выигрыша и ограничения.
  • Тактический уровень — игра в Тактические крестики-нолики — правила взаимодействия между Клетками и Тактическими клетками, условия выигрыша и ограничения.
  • Стратегический уровень — игра в Стратегические крестики-нолики представленная с помощью понятий Тактического уровня — правила взаимодействия между Тактическими клетками и Стратегическими клетками, условия выигрыша и ограничения.
  • Клетка текущего хода — Клетка в которую текущий игрок ставит, в зависимости от того за какую сторону он играет, крестик или нолик.

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


Правила игры


Задавая и анализируя данный класс игр (надмножество игры Крестики-нолики) мы, для упрощения понимания и сравнения, разделим правила игры на три части: правила хода, правила выигрыша и ограничения. Рассмотрим игру Оперативные крестики-нолики согласно данному подходу.


Оперативные крестики-нолики


Правила хода:


  • Игроки ходят по очереди, один за другим.
  • Первым ходит игрок, который играет за крестик.
  • Текущий игрок совершает ход в любую из не занятых клеток.

Правила выигрыша:


  • Выигрывает тот игрок, символы которого образовали линию (горизонтальную, вертикальную, диагональную) из трёх символов.
  • Ничья назначается в случае, когда всё игровое поле заполнено и при этом невозможно назначить победителя.

Ограничения:


  • Игрок не может совершить ход в клетку, в которой уже находится его символ или символ другого игрока.
  • Нельзя продолжать совершать ходы после назначения ничьей или победителя.

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


Тактические крестики-нолики


Правила хода:


  • Игроки ходят по очереди, один за другим.
  • Первым ходит игрок, который играет за крестик в любую из 81-ой свободной клетки.
  • Каждый следующий ход определяется предыдущим следующим образом: следующий игрок должен ходить в ту Тактическую клетку, которая в Тактическом поле имеет тоже положение, что и Оперативная ячейка в текущем Оперативном поле в которую сходил текущий игрок. Данное положение хорошо проиллюстрировано картинкой с английской страницы игры в Википедии.

Картинка
image

Как видно первый игрок сходил в третью Оперативную клетку пятого Оперативного поля, поэтому второй игрок должен ходить в третью Тактическую клетку данного Тактического поля.


Правила выигрыша:


  • Тактическая клетка может иметь четыре игровых состояния: Игра, Победил Х, Победил О, Ничья. Состояние Ничья считается и за Х и за О.
  • Выигрывает тот игрок, который побеждает по правилам Оперативных крестиков ноликов на Тактическом поле.

Ограничения:


  1. Тактическая клетка может иметь два состояния заполнения: Есть места, Заполнена.
  2. Если ход игрока должен произойти в Тактическую клетку с состоянием заполнения Заполнена, то игрок может сделать ход в любую пустую Оперативную клетку Тактического поля.
    • Опциональное ограничение: Если ход игрока должен произойти в Тактическую клетку с игровым состоянием не Игра (т.е. Победил Х, Победил О или Ничья), то игрок может сделать ход в любую пустую Оперативную клетку Тактического поля.
  3. Опциональное ограничение: Нельзя направлять следующего игрока в Тактическую клетку, в которой он произвёл предыдущий ход.
  4. Ни кто не может выиграть линией из 3 тактических клеток с игровым состоянием Ничья, в случае наступления такой ситуации игра или заканчивается ничьей или продолжается до тех пор пока один из игроков не выиграет.
  5. Игрок не может совершить ход в Клетку, в которой уже находится его символ или символ другого игрока.
  6. Нельзя продолжать совершать ходы после назначения ничьей или победителя.

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


Настало время поговорить о самих Стратегических крестиках-ноликах. В первую очередь при создании новой игры была поставлена цель расширить текущее игровое поле за счёт увеличения количества "уровней" игры, в следствии этого возникла необходимость составить новые правила хода, поскольку старые, как мы увидим ниже, были полными и не могли предоставить новые пути задания ходов игроков. За столом обсуждений будущих правил данной игры родились три основных направления в последствии преобразовавшихся в наборы правил: Тактический, Функциональный и Гиперфункциональный. Опишем данные наборы правил.


Стратегические крестики-нолики


Общие правила


Все три набора правил сохраняют правила выигрыша и ограничения на Тактическим уровне и объявляют те же правила для Стратегического уровня. Таким образом правила выигрыша и ограничения для Стратегического уровня выглядят точно также как правила Тактических крестиков-ноликов с точностью до названий клеток. Читателю предлагается самому написать правила Стратегического уровня для проверки понимания текущих терминов и положений.


Тактический набор правил


Правила Тактических крестиков-ноликов задают отображение (mapping) из множества Клеток в множество Тактических клеток для определения того куда должен ходить текущий игрок в зависимости от хода предыдущего игрока или другими совами правила хода на Тактическом уровне. Тактический набор правил сохраняет отображение из множества Клеток предыдущего Оперативного поля в множество Тактических клеток текущего Тактического поля, при этом декларируя, что отображение из множества Тактических клеток предыдущего Тактического поля в множество Стратегических клеток Стратегического поля сохраняется таким же как и отображение из множества Клеток предыдущего Оперативного поля в множество Тактических клеток текущего Тактического поля или другими словами правила хода на Стратегическом уровне такие же как и на Тактическом уровне. Наглядную иллюстрацию данного положения можно найти под спойлером.


Иллюстрация

image На картинке игрок сходил в первую Оперативную клетку четвёртого Оперативного поля пятого Тактического поля, а это означает, что следующий игрок должен ходить любую из Оперативных клеток первой Тактической клетки (зелёная) четвёртого Тактического поля (красное), что в свою очередь определит ход следующего игрока.


Функциональный набор правил


Вторая идея заключалась в сопоставлении строкам 9х1 (или столбцам 1х9, как будет показано ниже это не столь значительно и выбор в пользу строк был сделан лишь из эстетики получающегося игрового поля) клеток номера Стратегической клетки, в которую должен быть произведён следующий ход. Данная идея была реализована путём помещения номеров Стратегических клеток, для следующего хода, слева в той же строке, что и Клетка текущего хода. Чтобы понять о чём идёт речь перейдите в раздел с игровыми полями. Особенности выбора номеров следующих Стратегических клеток будут раскрыты в разделе анализа игры. Правила отображения из множества Клеток текущего Оперативного поля в множество Тактических клеток следующего Тактического поля сохраняются неизменными.


Гиперфункциональный набор правил


Третья идея заключалась в определении номера Стратегической клетки следующего хода для каждой Клетки текущего хода. Данный набор правил определяет именно такое отображение, при этом правила отображения из множества Клеток текущего Оперативного поля в множество Тактических клеток следующего Тактического поля сохраняются неизменными. Особенности выбора номеров следующих Стратегических клеток будут раскрыты в разделе анализа игры.


Игровые поля


Вторая неотъемлемая составляющая игры — её игровое поле. В данном разделе будет рассказано о предлагаемых автором игровых полях и дополнительно будут включены и описаны предпосылки к полученному окончательному дизайну. Все описанные в разделе игровые и вспомогательные поля, а также их вариации, готовые к печати на листе формата А4, доступны для скачивания по ссылке .
Первым вызовом при разработке игровых полей стал тот факт, что их было необходимо разместить на одной стороне листа формата Folio (более известный как тетрадный лист) так, чтобы на листе осталось место для вспомогательных полей. Представим характеристики полей в виде сводной таблицы.


Название поля Размер в Клетках Можно ли
нарисовать от руки
Поместится ли на
половине
тетрадного листа
Игровые поля
Базовое 29х29 Да Да
Пронумерованное 31х31 Да Да
Функциональное 35х31 Да Да
Гиперфункциональное 35х31 Нет Да
Полное Да Нет
Вспомогательные поля
Поле помощи 11х15 Да Да
Поле записи ходов 6хN Да Да
Непрерывное поле
записи ходов
Да Да

Далее под соответствующими спойлерами расположены изображения полей и заметки о их дизайне и предназначении.


Базовое поле

image Базовое поле — то с чего начинается игра. Имея только его вы уже можете играть в любой вариант Стратегических крестиков-ноликов, состоит из девяти полей для игры в Тактические крестики-нолики.


Пронумерованное поле

image Пронумерованное поле — это Базовое поле, Тактические клетки которого пронумерованы для упрощения отслеживания деятельности игроков в ходе игры. Число рядом с Тактической клеткой отражает как номер Стратегической клетки (десятки) так и номер Тактической клетки (единицы).


Функциональное поле

image Функциональное поле — это Пронумерованное поле на котором возможна игра (проще следить за её ходом) с Функциональным набором правил. Для данного поля положение чисел, задающих следующую Стратегическую клетку определено слева от соответствующих строчек, что позволяет сохранять размеры поля такими, чтобы оно могло уместиться на половине тетрадного листа.


Гиперфункциональное поле

image Гиперфункциональное поле — на данном поле возможна игра с Гипперфункциональным набором правил, оно не может быть нарисовано от руки так как содержит градации цвета для задания чисел, обозначающих следующую Стратегическую ячейку.


Поле помощи

image Данное поле было создано для того чтобы игроки не путались при возобновлении игры и не вспоминали кому принадлежит какая клетка (Стратегическая или Тактическая). По ходу игры игроки могут отмечать свои успехи тем самым сохраняя прогресс партии.


Поле записи ходов

image Данное поле было разработано с целью помощи игрокам в запоминании прогресса игры, очерёдности хода, проверки правильности игрового поля. В предлагаемом варианте данного поля в течении своего хода необходимо записать номера Стратегической (S) Тактической (T) и Операционной (O) клетки, в которую игрок производит ход. Данный вариант поля преимущественно предназначен для игры с Функциональным и Гиперфункциональным набором правил, для Тактического же набора было специально разработано Непрерывное поле записи ходов. Для данного поля существует несколько вариантов исполнения, все они доступны для скачивания.


Непрерывное поле записи ходов

image Непрерывное поле записи ходов — специально разработанное поле записи ходов, предназначенное для игры с Тактическим набором правил. Необходимость его появления была обоснована непосредственным игровым опытом автора. В данном поле дополнительные записи и повторение чисел для Тактического набора правил было сведено к минимуму. Ниже в статье приведён пример игры происходившей с использованием данного поля. Для данного поля существует несколько вариантов исполнения, все они доступны для скачивания.


Полное поле

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


Анализ игры


В данном разделе будет рассказано о том как был обоснован выбор чисел, означающих следующую Стратегическую ячейку для Функционального и Гиперфункционального набора правил. Метод анализа игры заключается в следующем:


  1. Построить граф переходов игрового поля — то самое отображение заданное на удобных для анализа множествах, граф задаётся матрицей смежности.
  2. Исключить из матрицы и запомнить диагональные элементы.
  3. Применить к полученной матрице алгоритм Флойда-Уоршелла для нахождения кратчайшего пути от всех вершин ко всем вершинам.
  4. Запомнить все элементы, кроме диагональных, в диагональные занести ранее запомненные.
  5. Ещё раз применить к полученной матрице алгоритм Флойда-Уоршелла для нахождения кратчайшего пути из вершин в самих себя.
  6. К запомненным не диагональным элементам дописать полученные при втором проходе диагональные.
  7. Построить heatmap полученной матрицы.
  8. Вычислить среднее расстояние между вершинами.

Весь код, реализующий этапы анализа можно найти по ссылке. Код написан на Lua 5.1 и запустится как на интерпретаторе так и на JIT-компиляторе (второй более предпочтителен из-за вычислительной сложности предлагаемого метода). Оконечные этапы анализа — построение heatmap'ов и подсчёт среднего расстояния проводился в Excel.


Проанализируем полученные результаты. Как опорный возьмём результат для Тактического набора правил. И так для данного набора правил удобно взять отображение из множества Тактических клеток в него же, среднее расстояние между Тактическими клетками получилось равным 1.(8) хода. Не много, это означает, что для успешной игры в памяти стоит хранить последние два хода и думать как минимум на два хода вперёд. Heatmap можно увидеть под спойлером. Для всех heatmap'ов шкала идёт от красного к зелёному через жёлтый на увеличение.


Heatmap Тактического набора правил
image

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


Для данного набора правил было удобно взять отображение из множества триплетов Тактических клеток в него же (в триплеты объединены Тактические клетки 1-3, 4-6, 7-9 для каждой Стратегической ячейки). Взглянем на результаты: оптимальными были названы два набора чисел под кодовыми названиями map34 и map67, для данных наборов среднее расстояние между триплетами составило 2.(6) хода. Их особенностью является то, что расстояние от каждого триплета до самого себя составляет ровно 3 хода.


Heatmap'ы наборов

map34


image

map67


image

Для визуального сравнения представлены heatmap'ы других наборов:
map14


image

map42


image

Последним проанализируем Гиперфункциональный набор правил. При детальном рассмотрении игровых полей, созданных под данный набор правил читатель мог увидеть закономерность в расположении цифр, отвечающих за следующую Стратегическую клетку. Используя данную закономерность мы создали девять наборов чисел описывающих переходя для Гиперфункционального набора правил, из которых был найден оптимальный получивший кодовое имя hmap2. Его показатели составили 2.206 хода в среднем между Тактическими клетками и ровно 3 хода чтобы попасть в туже Тактическую клетку.


Heatmap'ы hmap1 и hmap2

hmap1


image

hmap2


image

Выводы и послесловие


В статье было рассказано о новой игре в своём типе — Стратегических крестиках-ноликах, дизайнерские решения в ходе создания игры были обоснованы путём анализа.


Направления будущих работ


Основными направлениями авторам представляются:


  • Создание приложений и сайтов кооперативной игры, основанных на данной Стратегических крестиках-ноликах.
  • Создание алгоритмов ИИ для игры с компьютером, по информации автора данных ИИ не существует и для Тактических крестиков-ноликов в виду их не тривиальности, многоуровневости игрового процесса и быстро ветвящегося игрового дерева.
  • Обобщение правил игры для создания её бесконечных, многомерных вариаций.

Послесловие


Историю создания и сведения об авторах можно найти на странице проекта, а также там можно найти возможные ограничения авторских прав на производную деятельность. Авторы будут рады помощи с переводом оставшегося русского текста на английский язык на главной странице проекта.

Поделиться с друзьями
-->

Комментарии (13)


  1. ingumsky
    15.05.2017 13:10
    +1

    С первого раза после прочтения вашей статьи у меня не получилось понять суть игры в таком формате. Пока всё выглядит очень сложно, но интересно. А вы в итоге играли в неё или это пока только теоретическая работа? Сколько, в среднем, уходит времени на одну партию в СКН?


    1. mikeademchenko
      15.05.2017 23:44
      +1

      Я с вами согласен, текстовый формат изложения получился запутанным, но как показала практика, игру достаточно просто освоить непосредственно играя в неё. А теперь немного статистики: мной и моим коллегой была сыграна одна полная игра по Тактическому строгому (без опциональных ограничений) набору правил, она заняла у нас 7 недель по 1,5 часа неспешной игры в неделю, была завершена за 487 ходов победой Х (хотя при более детальном анализе можно заключить что на 427 ходу О сдался, возможно в дополнительном комментарии или позже в статье я выложу строку игры).


    1. renardf0x
      15.05.2017 23:45
      +2

      Здесь описано гораздо проще:
      http://tesera.ru/article/Ultimate_Tic-Tac-Toe/


      1. sasha1024
        16.05.2017 09:04
        +1

        Там описаны тактические крестики-нолики (надстройка над обычными).
        Здесь описываются стратегические крестики-нолики (надстройка над тактическими).


  1. ooptimum
    15.05.2017 13:42

    Можно даже попробовать свои силы в написании бота и поучаствовать в соревнованиях по тактическим (по терминологии из данной статьи) крестикам-ноликам на поле 3х3 по 3х3 (всего 81 клетка). Вся информация есть здесь: http://theaigames.com/competitions/ultimate-tic-tac-toe


  1. Spaceoddity
    15.05.2017 13:57

    У М.Гарднера был большой разбор разновидностей крестиков-ноликов. С точки зрения математической сути — они очень просты. Может и у данной реализации есть математическое решение (оптимальная стратегия выигрыша для какого-либо из игроков)?


    1. LoadRunner
      15.05.2017 15:02

      Подозреваю, что начать с самого-самого центра — наиболее оптимальная стратегия даже в этой вариации.


  1. Eefrit
    15.05.2017 15:13

    Возможно, я как-то неправильно понял правила, но если играть стандартной стратегией — крестики побеждают на их третьем или четвёртом ходу гарантированно (если начинать не от края поля), разве не так?


    1. mikeademchenko
      15.05.2017 23:47

      Скорее всего вы не правильно поняли, попробуйте прочитать ещё раз или посмотрите ссылки в комментариях, чтобы выиграть в эту игру нужно совершить как минимум 27 ходов Х и 26 О(очень не строгая оценка нижней границы выведена из чистой логики и сильно на правила не опирается).


  1. webmasterx
    15.05.2017 15:28
    +2

    Мне нравится более простой вариант игры в крестики нолики:
    1) поле ограничивается лишь размером листа и занятыми клетками прошлой игры
    2) нужно выстроить линию из пяти фигур


    1. AVX
      15.05.2017 21:21

      +1
      Мы студентами так играли массово. В идеале — поле бесконечное считается (в реале — конечно, один лист, или часть — иногда отгораживали от других сражений или писанины/рисунков границами). Очень интересная игра! Приходится много продумывать, и достаточно далеко вперёд. Пробовал играть с компьютером — трудно, даже очень, но выигрывать можно.


      1. erty
        15.05.2017 23:49
        +1

        Вы играли в Гомоку
        Игре уже более 4000 лет


  1. Coercer
    16.05.2017 12:04

    Сделал шаблон для игры в Тактические крестики-нолики