[Из песочницы] Стратегические крестики-нолики (Starategic Tic-Tac-Toe)15.05.2017 13:06

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

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

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

Игра 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 будем называть Тактическими крестиками-ноликами.
• Клетка — место на игровом поле в которое игроки могут поставить крестик или нолик, также называемая Оперативная клетка.
• Оперативное поле — игровое поле Оперативных крестиков-ноликов, также называемая Тактическая клетка — 3×3 решётка из Клеток.
• Тактическое поле — игровое поле Тактических крестиков-ноликов, также называемая Стратегическая клетка — 9×9 решётка из Клеток, 3×3 решётка из Тактических клеток.
• Стратегическое поле — игровое поле Стратегических крестиков-ноликов — 27×27 решётка из Клеток, 9×9 решётка из Тактических клеток, 3×3 решётка из Стратегических клеток.
• Оперативный уровень — игра в Оперативные крестики-нолики — правила ходов, условия выигрыша и ограничения.
• Тактический уровень — игра в Тактические крестики-нолики — правила взаимодействия между Клетками и Тактическими клетками, условия выигрыша и ограничения.
• Стратегический уровень — игра в Стратегические крестики-нолики представленная с помощью понятий Тактического уровня — правила взаимодействия между Тактическими клетками и Стратегическими клетками, условия выигрыша и ограничения.
• Клетка текущего хода — Клетка в которую текущий игрок ставит, в зависимости от того за какую сторону он играет, крестик или нолик.

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

Правила игры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Игровые поля

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

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

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

Анализ игры

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

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

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

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

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

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

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

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

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

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

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

Послесловие

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

© Geektimes