крестики нолики в блокноте код
Небольшое вступление
Вместо того, чтобы долго изучать программирование по статьям и лекциям, которые скучно описывают какие-то непонятные действия с числами и строками, лучше изучать программирование на красочных примерах, таких, как создание игр!
Структура игры
Эта игра состоит из нескольких частей, которые написаны на HTML, CSS и JavaScript.
Общий принцип такой: на веб-страничке (HTML) делаются ссылки на файл с JavaScript-ом и CSS файл со стилями. Так же, в HTML размечаются те места, где будут элементы игры отображаться. А так же вставлена одна функция на JavaScript, которая запускается сразу после загрузки страницы, и задаёт параметры языка для игры, и даёт команду на создание нового игрового поля.
В CSS файле содержатся стили элементов игры, такие, как обводка клеток, и тип курсора мыши, при наведении на клетку.
В JS файле содержится основной код, который и управляет игрой.
Раз мы изучаем на примере, то практически каждая строчка будет содержать комментарий – подробное описание того, чего делает данная команда.
Исходный код CSS файла
CSS (каскадные таблицы стилей) – описывает стиль для отображения игрового поля на HTML страницы. Исходный код CSS приведу без подробных объяснений, только с комментариями, которые начинаются символами /* и заканчиваются символами */.
Код на HTML странице
HTML. Следующий код необходимо вставить на веб-страницу. Каждый фрагмент кода подписан.
Так же, нужно прописать параметр onload=»initGame();» в тег BODY.
внутрь BODY – туда, где будет управление игрой:
внутрь BODY – туда, где будет игровое поле:
Код JavaScript игры
Самый большой код. И самый главный. В нём есть и ИИ соперника, и функции отображения и построения поля, и проверка победы. Но, так как разбор программы сходу, думаю, будет немного сложноват, то сначала я опишу вкратце, какой фрагмент и функция программы за что отвечает.
После того, как мы изучили основные принципы игры, теперь можно смотреть весь исходный код файла gamescript.js. Все основные моменты кода даны с комментариями (комментарии в JS идут после двойного слеша //).
// (C) www.AlexeyK.com, 2012.
var gameImgDir=»data/»;
var gTexts=[]; // Для многоязычности.
gTexts[‘win1’]=’Win ‘; gTexts[‘win2′]=’!’;
gTexts[‘playing’]=’. ‘
gTexts[‘start’]=’Begin game!’
var gField=[]; // игровое поле
function createField(w,h) < // Задаёт размер игрового поля.
gField=new Array(w); // создание нового массива.
for (i=0;i // теперь переделаем массив в матрицу.
var hT=»
| «; hT+=» «; hT+=» |
«; // вставка таблицы на страницу.
document.getElementById(‘gameinfo’).innerText=gTexts[‘start’]; // отобразить сообщение
>
function setCell(x,y,t) < // Поставить крестик или нолик
gField[x][y]=t; // Запомнить t в массиве
var imgsrc=gameImgDir+’c_null.gif’; // изображение по умолчанию
if (t==’x’) imgsrc=gameImgDir+’c_x.gif’; // картинка для крестика
if (t==’o’) imgsrc=gameImgDir+’c_o.gif’; // картинка для нолика
var oName=»c»+x+»_»+y; // составление имени картинки
document.getElementById(oName).src = imgsrc; // замена изображения
if (t!=null) document.getElementById(oName).alt = t; // если картинки выключены, то игра будет в текстовом режиме 🙂
>
Прочие файлы
Вот и всё. Попробуйте попрактиковаться в создании html-страничек, и попробуйте запустить эту игру, собрав её самостоятельно. Если получилось, то я специально недоделал сообщение о нечьей. Попробуйте самостоятельно сделать проверку на нечью, и добавить её в игру.
Простой алгоритм проверки победы в крести-нолики на не стандартном поле
Столкнулся с такой проблемой, что молодым программистам, которые только начинают изучение языков, алгоритмы вызывают больше трудностей, чем синтаксис языка. Если сам синтаксис и концепцию объяснит преподаватель по конкретному языку, то алгоритмы вам придется придумывать самим. Исключением из правил могут быть только специализированные технические специальности в ВУЗах, где преподают именно алгоритмы.
При том, что алгоритм решения может быт очень простым многие не знают как подойти к решению задачи. Я рассмотрю пример проверки победы в игре крестики-нолики, но на поле 6х6 и блоком подряд заполненных значений равному 4-м.
На самом деле, здесь представлен универсальный алгоритм, только вместо переменных я использовал константы. И это практически не зависит от языка, котором эта проверка осуществляется. Я предлагаю начинающим программистам сначала решить задачу графически, а затем уже перевести ее на тот или иной язык. Для создания этого алгоритма подойдет листок в клетку и ручка.
Итак, у нас есть поле 6х6.
Блок последовательно заполненных элементов, который достаточен, чтобы выиграть, равен 4-м.
Думаю, что теперь (всего лишь поле двух рисунков) стало намного понятнее, как решить эту задачу.
Фактически мы должны решить 2 независимые задачи:
1. Найти все заполненные последовательности в блоке 4х4
Почему проверяем блок 4х4? Все просто в нем возможно только 2 диагонали такой размерности, которая нам нужна.
Используя двоичную логику (1&1=1 и 1&0=0) мы можем легко сделать проверку циклами. Для этого нам нужна 1 переменная для каждой диагонали. Пусть toright – логическая переменная в которую пишем результат проверки диагонали сверху слева вниз направо. И toleft для проверки диагонали сверху справа вниз налево.
Первоначально выставим значение true для этих переменных. Дальше мы сравниваем каждую клетку в диагонали с символом «Х» или «О». Конечно, мы делаем это 2-мя вызовами либо все сравниваем с «Х», либо все с «О».
Каждую клеточку диагонали мы сравниваем с нашим символом и получаем результат (true) или (false). Затем делам логическую операцию (&) между полученным результатом и нашей toright. Результат этой операции пишем опять в toright. Если на каком-то этапе мы получим результат (false), то все дальнейшие toright всегда будут равны (false). Это следует из правила логических операций (1&0=0).
Напишем это на Jave:
Собственно вот в этой строчке
Краткая запись выглядит так:
Получаются только 2 результата работы условия:
Для 2-х диагоналей, полный код функции будет выглядеть так:
Полный аналог делается для проверки вертикалей и горизонталей, только циклы меняются.
Собственно это и есть решение для блока 4х4. Как видно из кода, для другого блока нужно только поменять 4 в цикле на другое число, или написать вместо числа имя переменной. Причем эту переменную вы можете сделать как глобальной видимости, так и передать в функцию, например так:
2. Найти все квадраты 4х4 в квадрате 6х6
Собственно, их не так много. Начиная с позиции [0,0], [1,0] и [2,0] для первой строки квадрата, [0,1], [1,1] и [2,1] для второй, [0,2], [1,2] и [2,2] для третьей. Дальше квадрат 4х4 выйдет за границы квадрата 6х6.
Такой перебор координат вполне можем сделать циклами:
Тут нам придется немного модифицировать методы checkDiagonal и checkLanes, поскольку мы должны проверять квадрат 4х4 с соответствующим смещением.
Начинающим программистам я бы рекомендовал самим модифицировать код checkDiagonal, т.к. это позволит лучше понять принцип работы.
И еще один совет. В настоящий момент имеется огромное количество реализаций различных алгоритмов в сети на разных языках. Если вы хотите научиться думать, то смотрите именно принципы решений (алгоритмы), не привязанные к языкам. Готовые решения не позволят вам быстро научиться выбирать наиболее оптимальный вариант решения. Очень часто, переписать готовое решение с одного языка на другой, можно не понимая принципа решения задачи. Где-то это вам поможет, а где-то может сделать дальнейшее развитие программы невозможным без изменения ее логики.
Сначала я рекомендую попробовать написать проверку самостоятельно. Шаблон игры можно забрать здесь. Там уже есть заголовки функций, которые я описал в статье. Осталось скопировать в шаблон часть моего кода и чуть-чуть его модифицировать. А вот здесь можно скачать полный рабочий код на Java. Рекомендую смотреть его уже после того, как вы написали свои функции на основе этой статьи.
Реализация алгоритма Минимакс на примере игры «Крестики-Нолики»
Недавно я написал непобедимую игру «Крестики-Нолики». Это был интересный и поучительный проект, который многому меня научил. Если у вас есть желание посмотреть результат — это можно сделать здесь.
Для того чтобы сделать игру непобедимой, было необходимо создать алгоритм, который может рассчитать все возможные ходы для «компьютерного» игрока. Далее, нужно использовать некоторую метрику, чтобы определить, какой ход является предпочтительным. После долгих исследований стало понятно, что алгоритм Минимакс, был тем, что мне нужно.
Понимание основ алгоритма и реализация игры заняли некоторое время. Я нашел много примеров кода и объяснений, тем не менее это оказалось не такой уж простой затеей. Надеюсь этот пост поможет некоторым из читателей оценить элегантность этого алгоритма.
Описание «Идеальной» игры «Крестики-Нолики»
Для начала давайте опишем, что мы понимаем под «идеальной» игрой — если я играю идеально, я или побеждаю в игре, или играю вничью. В случае если я играю против другого «идеального» игрока, я всегда играю вничью.
Можно ли описать эти требования количественно? Давайте для всех возможных вариантов конечного состояния игры назначить какое-то количество очков:
Давайте рассмотрим короткий пример.
На картинке изображено состояние игрового поля, и мой черед ходить. Я играю за «Х». Моя цель, очевидно, максимизация количества очков, которые я получу.
Верхняя часть картинки показывает состояние игры, и, в зависимости от моего выбора, я могу попасть в одно из трех состояний из нижней части картинки. Очевидно, что состояние, в котором я побеждаю (снизу слева) является наилучший. Если я не сделаю этот ход, игрок «О» может легко победить, и я не хочу, чтоб он победил. Таким образом, выберу ход, который принесет мне наибольшее число очков.
Но что мы знаем о втором игроке? Мы можем предположить, что он тоже играет с целью победить в игре. Игрок «О» хочет выбрать ход, который приведет к наименьшему выигрышу для нас, он хочет минимизировать наш выигрыш. Давайте посмотрим на вещи с точки зрения игрока «О» начиная с двух других состояний игры из предыдущего примера, тех, в которых я не побеждаю:
Описание алгоритма Минимакс
Суть алгоритма Минимакс это поочередный перебор возможных ходов двух игроков, при котором мы считаем, что игрок «чья очередь» выберет ход, приносящий максимальное количество очков. Предположим, что мы играем за игрока «Х», тогда описание алгоритма будет примерное таким:
Реализация алгоритма Минимакс
Надеюсь теперь у вас есть общее представление, как алгоритм Минимакс определяет наилучший ход. Давайте рассмотрим имплементацию алгоритма, чтоб закрепить наше понимание.
Вот функция, которая производит оценку состояния:
Достаточно просто, вернуть +10 если текущий игрок побеждает в игре, -10, если проигрывает и 0 в случае ничьи. Вы также можете отметить, что с точки зрения алгоритма нет разницы, какой это игрок (»Х» или «О»), важно лишь чей ход.
А теперь собственно сам алгоритм; обратите внимания что в приведенном варианте выбор хода это просто адрес ячейки на поле, т.е. [0,2] это правая верхняя ячейка на игровом поле размером 3×3.
Когда алгоритм выполняется в классе PerfectPlayer, выбор наилучшего ходя сохраняется в переменной choice, которая впоследствии используется для того, чтобы вернуть новое состояние игры в которое мы попадаем в результате выбранного игроком хода.
Идеальный игрок-самоубийца
Эта имплементация алгоритма позволит вам создать игру в «крестики-нолики», в которую вы не сможете победить. Но есть маленький нюанс, который я обнаружил в процессе тестирования игры. В случае, если мой «идеальный игрок» обнаружит состояние, в котором он или проиграет, или закончит вничью, его ход будет самоубийственным. Проще говоря, алгоритм говорит «я все равно проиграю, поэтому без разницы сейчас, или через 6 ходов».
Я обнаружил это когда передал явно некорректное состояние игрового поля и попытался выяснить, какой ход предложит алгоритм. Я ожидал, что «идеальный игрок» попытается помешать мне выиграть так долго, как сможет, но этого не произошло:
Давайте рассмотрим, что происходит здесь через призму возможных ходов (для простоты я удалил некоторые состояния)
Черт побери, что же мастер «крестиков-ноликов» должен сделать?
Даем противнику хороший бой: глубина
Наилучшим улучшением для алгоритма будет изменить его так, чтоб «идеальный игрок» играл «идеально» до самого конца, т.е. взять «глубину» (количество ходов до возможного проигрыша) в расчет при выборе хода. Простыми словами, идеальный игрок будет играть идеально, и постарается играть так долго, как только сможет.
Для того чтобы достигнуть такого результата мы будем отнимать глубину рекурсии\количество ходов от конечного состояния игры. Т.е. чем больше ходов до минимального выигрыша (и чем меньше ходов до максимального) — тем лучше.
Так, каждый раз при вызове алгоритма Минимакс глубина будет увеличена на 1, и когда мы наконец рассчитаем возможный выигрыш для конкретного конечного состояния игры мы введем поправку на глубину. Давайте посмотрим, как это выглядит на примере следующего дерева ходов:
В заключение
Я надеюсь все эти пояснения помогли вам получше понять алгоритм Минимакс, и, возможно, как можно всегда выигрывать в «крестики-нолики». Если у вас есть вопросы, или что-то вам кажется непонятным, напишите, пожалуйста, в комментариях и я улучшу статью. Полный код можно найти у меня на Github. А поиграть в получившуюся игру можно здесь: http://perfecttictactoe.herokuapp.com/.
От переводчика
Перевод сделан с разрешения автора. Мне понравилась эта статья тем, что она просто и наглядно описала алгоритм Минимакс. В статье присутствуют неточности и упрощения а также, местами, неточная терминология.
Возможно вам также будет интересен мой YouTube канал.
Быстрый старт с Java: пишем «крестики-нолики»
Перед прочтением данной статьи рекомендую ознакомиться с предыдущей, «Быстрый старт с Java: начало», поскольку ожидается, что читатель владеет материалом, изложенным в ней — знает о переменных, условиях, циклах и импорте классов. Сегодня мы углублим знания о Java, создавая игру «Крестики-нолики», которая работает в командной строке (консоли). В процессе будет рассмотрена работа с массивами, а также некоторые аспекты объектно-ориентированного программирования (нестатические методы, нестатические поля, конструктор).
Массивы
При написании игры используется массив, поэтому давайте для начала рассмотрим, что это. Массивы хранят набор однотипных переменных. Если переменная похожа на коробочку, с написанным на боку типом, именем и со значением внутри, то массив похож на блок таких коробочек. И тип, и имя у блока одно, а доступ к той или иной коробочке (значению) происходит по номеру (индексу).
Методы
Решение одно — создать объект на основании класса. И затем вызывать метод через точку после имени объекта. В этом случае метод может быть нестатическим. Представленный ниже код это иллюстрирует.
Поля класса
Переменные существуют в рамках лишь того метода, где они объявлены. А если нужна переменная, доступная во всех методах класса, то пришло время использовать поля. Поля объявляются подобно переменным, с указанием типа и имени. Но располагаются они не в методах, а прямо в теле класса. Подобно методам, они могут быть статическими и нестатическими. Нестатические поля, как и методы, доступны только после создания объекта.
Крестики-нолики. Шаблон класса
Приступим к написанию кода игры. Начнём с шаблона класса и определения нужных полей. Именно это содержит приведённый ниже код. Первые две строки — импорт классов. Первыми в теле класса идут описания полей, затем методов. Метод main() используется для создания объекта (так как поля и методы нестатические) и вызова метода game() с игровой логикой.
Имена методов принято писать с маленькой буквы. Однако в коде мы видим метод TicTacToe() — есть ли тут нарушение? Нет, поскольку этот метод особенный и в объектно-ориентированном программировании называется конструктор. Конструктор вызывается сразу после того, как объект создан. Его имя, как видим, должно совпадать с именем класса. Мы используем конструктор для инициализации полей.
Игровая логика
Реализация вспомогательных методов
Заключение
На всякий случай прилагаю мой telegram — @biblelamp. Если вас заинтересовала тема, рекомендую почитать «Java-программирование для начинающих» Майка МакГрата и «Изучаем Java» Кэти Сьерра и Берт Бейтс.
Другие статьи из серии «Быстрый старт с Java»:
Если язык Java вас заинтересовал — приглашаем на факультет Java-разработки. Если ещё не совсем уверены — посмотрите истории успеха наших Java-выпускников:
Перед прочтением данной статьи рекомендую ознакомиться с предыдущей, «Быстрый старт с Java: начало», поскольку ожидается, что читатель владеет материалом, изложенным в ней — знает о переменных, условиях, циклах и импорте классов. Сегодня мы углублим знания о Java, создавая игру «Крестики-нолики», которая работает в командной строке (консоли). В процессе будет рассмотрена работа с массивами, а также некоторые аспекты объектно-ориентированного программирования (нестатические методы, нестатические поля, конструктор).
Массивы
При написании игры используется массив, поэтому давайте для начала рассмотрим, что это. Массивы хранят набор однотипных переменных. Если переменная похожа на коробочку, с написанным на боку типом, именем и со значением внутри, то массив похож на блок таких коробочек. И тип, и имя у блока одно, а доступ к той или иной коробочке (значению) происходит по номеру (индексу).
Методы
Решение одно — создать объект на основании класса. И затем вызывать метод через точку после имени объекта. В этом случае метод может быть нестатическим. Представленный ниже код это иллюстрирует.
Поля класса
Переменные существуют в рамках лишь того метода, где они объявлены. А если нужна переменная, доступная во всех методах класса, то пришло время использовать поля. Поля объявляются подобно переменным, с указанием типа и имени. Но располагаются они не в методах, а прямо в теле класса. Подобно методам, они могут быть статическими и нестатическими. Нестатические поля, как и методы, доступны только после создания объекта.
Крестики-нолики. Шаблон класса
Приступим к написанию кода игры. Начнём с шаблона класса и определения нужных полей. Именно это содержит приведённый ниже код. Первые две строки — импорт классов. Первыми в теле класса идут описания полей, затем методов. Метод main() используется для создания объекта (так как поля и методы нестатические) и вызова метода game() с игровой логикой.
Имена методов принято писать с маленькой буквы. Однако в коде мы видим метод TicTacToe() — есть ли тут нарушение? Нет, поскольку этот метод особенный и в объектно-ориентированном программировании называется конструктор. Конструктор вызывается сразу после того, как объект создан. Его имя, как видим, должно совпадать с именем класса. Мы используем конструктор для инициализации полей.
Игровая логика
Реализация вспомогательных методов
Заключение
На всякий случай прилагаю мой telegram — @biblelamp. Если вас заинтересовала тема, рекомендую почитать «Java-программирование для начинающих» Майка МакГрата и «Изучаем Java» Кэти Сьерра и Берт Бейтс.
Другие статьи из серии «Быстрый старт с Java»:
Если язык Java вас заинтересовал — приглашаем на факультет Java-разработки. Если ещё не совсем уверены — посмотрите истории успеха наших Java-выпускников:
Крестики нолики «Без границ»
Крестики-нолики… в них играли все, я уверен. Игра притягательна своей простотой, особенно когда ты тянешь часы где-нибудь на уроке, паре, а под рукой нет ничего, кроме тетрадного листа и простого карандаша. Уж не знаю, кто первым когда-то догадался рисовать кресты и кружки в 9 квадратах, но с тех пор игра нисколько не потеряла в востребованности, тем более, что народ придумал огромное множество её вариаций.
Эта статья про процесс разработки ИИ на javascript для игры в одну из таких вариаций крестиков-ноликов: получилось довольно много материала, но я разбавил его анимацией и картинками. В любом случае, хотя бы стоит попробовать поиграть в это.
Отличия этого варианта игры от оригинала в следующем:
Перед тем, как начнем
Вынужден извиниться заранее за объем статьи и местами не совсем доходчивое изложение мысли, однако у меня не получилось сжать стаю без потери в содержании и качестве.
Рекомендую сначала ознакомиться с результатом. Код
Горячие клавиши и команды:
Начнем
Начать нужно с реализации самой игры, т.е. написать приложение для двух игроков, пока без бота. Для своих целей я решил использовать javascript + jquery + bootstrap4, хотя он там практически не используется, но его лучше оставить – или таблица поплывет. Тут рассказывать особо нечего, материала по js, jquery и bootstrap на хабре полно. Скажу лишь, что использовал MVC. Да и вообще, объяснять абсолютно весь код я не буду – материала и без того получилось много.
Итак, игровое поле было готово. Можно устанавливать фигуры в клетки. Но победа кого-либо из игроков никак не фиксировалась.
Сканирование «конца игры»
Игра заканчивается, когда один из игроков поставит 5 фигур в ряд. «Все просто!» — подумал я. И начал сканировать абсолютно все клетки поля: сначала все горизонтали, потом вертикали и, наконец, диагонали.
Это тупой способ, но он работал. Однако, его можно было значительно улучшить, что я и сделал: Большая часть клеток будет оставаться пустой на протяжении всей игры – игровое поле слишком большое, чтоб его можно было заполнить целиком. Поскольку сканировать его нужно было каждый ход, а за один ход ставится только одна фигура — то можно сосредоточиться только на этой фигуре (клетке): просканировать только одну горизонталь, вертикаль и две диагонали клетки, которым принадлежит та самая клетка.
Плюс ко всему, не нужно сканировать все клетки линий. Поскольку конец игры – это 5 фигур в ряд, то фигуры, удаленные друг от друга на 6 клеток нас не интересуют. Достаточно сканировать по пять клеток в каждую из сторон. Не понятно? Смотри анимацию ниже.
Приступим к самому боту
Итак, мы уже написали страницу с крестиками-ноликами. Переходим к основной задаче – ИИ.
Нельзя просто так взять и написать код, если ты не знаешь как: нужно продумать логику бота.
Суть заключается в анализе игрового поля, хотя бы его части, и просчета цены (веса) каждой клетки на поле. Клетка с наибольшим весом – самая перспективная – туда бот и поставит фигуру. Основная сложность именно в просчете веса одной клетки.
Терминология
Крестики и нолики – это фигуры.
Атакой будем называть несколько одинаковых фигур, стоящих рядом, на одной линии. По сути, это множество. Количество фигур в атаке – её мощность. Одна отдельная фигура – тоже атака (мощностью 1).
На соседних клетках атаки (на концах) могут быть пустые клетки или фигуры противника. Логично думать, что атаку с двумя пустыми клетками на «концах», мы можем развивать в двух направлениях, что делает ее более перспективной. Количество пустых клеток на «концах» атаки будем называть её потенциалом. Потенциал может принимать значения 0, 1 или 2.
Атаки обозначаем так: [ мощность атаки, потенциал ]. Например, атака [4:1].
Рис 1. Атака [4:1]
В ходе анализа мы будем оценивать все клетки, которые входят в определенную область. У каждой клетки будет просчитываться её вес. Он вычисляется на основе весов всех атак, на которые влияет данная клетка.
Суть анализа
Представим, что на игровом поле уже есть несколько атак одного и второго игрока. Кто-то из игроков делает ход (пускай крестики). Естественно ход он делает в пустую клетку – и тем самым он может:
Суть анализа в следующем:
По сути, таким алгоритмом мы проверяем, что будет, если мы пойдем так… а что будет если так пойдет оппонент. Мы смотрим на один ход вперед и выбираем наиболее подходящую клетку – с наибольшим весом.
Если какая-то клетка имеет больший вес, нежели другая, значит она приводит к созданию более опасных атак, либо к блокировке сильных атак противника. Все логично… мне кажется.
Если зайти на страницу и написать в консоли SHOW_WEIGHTS = true, можно визуально прочувствовать работу алгоритма (Будут показаны веса клеток).
Веса атак
Пораскинул я мозгами и привел такое соответствие атак и весов:
Подобрано эмпирически – возможно это не оптимальный вариант.
Я добавил в массив атаки мощностью 5 с запредельно большим весом. Объяснить это можно тем, что бот анализирует игру, смотря на шаг вперед (подставляя фигуру в клетку). Пропуск такой атаки есть ни что иное, как поражение. Ну или победа… смотря для кого.
Атаки с большим потенциалом ценятся выше.
Атака [4:2] в большинстве случаев решает исход игры. Если игроку удалось создать такую атаку, то оппонент уже не сможет ее заблокировать. Однако это еще не победа. Противник может быстрее завершить игру, даже при наличие у нас на поле атаки [4:2], поэтому ее вес ниже, чем у атак мощностью 5. Смотри пример ниже.
Рис 2. Атака [4:2]
«Рваные» атаки
В этом абзаце код не представлен. Здесь мы вводим понятие делителя атаки и объясняем суть «рваных атак».
Рассмотрим такую ситуацию: при подстановке фигуры на удалении нескольких пустых клеток, но не более 5-и, расположена еще одна.
И вроде бы, две одинаковые фигуры, на одной линии… визуально это похоже на атаку, а по факту нет. Не порядок, так как такие «рваные» атаки также несут в себе потенциальную угрозу.
Специально для таких случаев, для каждой атаки будем просчитывать делитель. Изначально его значение равно 1.
Таким образом, «рваные» атаки так же будут учитываться ИИ. На самом деле, это будут обычные атаки, но чем они дальше находятся от сканируемой клетки, тем меньшее влияние на нее оказывают и, соответственно, имеют меньший вес (благодаря делителю).
Алгоритм поиска атак
Во-первых, создадим класс атаки. У атаки будет 3 атрибута, о которых я писал ранее:
И один метод, который будет возвращать вес данной атаки:
Далее. Поиск всех атак для одной клетки мы разделим на:
Однако, нам не нужно проверять всю линию целиком. Максимальная мощность атаки, которая нас интересует – 5. Безусловно, создать атаку мощностью, скажем, 6 – возможно. Но для ИИ, который анализирует игровую ситуацию следующего хода, все равно, что 6, что 5. Перспектива получить одну из этих атак говорит о конце игры на следующем ходу. Соответственно, вес анализируемой клетки будет в обоих случаях будет одинаковым.
Здесь надо остановиться, так как может возникнуть вопрос: зачем проверять 6-ую клетку, если максимальная мощность атаки – 5. Ответ – это нужно для определения потенциала удаленной от центра атаки.
Вот пример: атака мощностью 1 на картинке находится на границе сканируемой области. Чтобы узнать потенциал этой атаки нужно «заглянуть за границу».
Рис. 3. Сканирование 6-ых клеток. Если не просканировать 6-ую клетку, можно неправильно определить потенциал атаки.
Для завершения некоторых атак может просто не хватать места. Посчитав attackplace мы заранее можем понять, какие из атак бесперспективны.
Рис. 4. Место для атаки
1) Начнем с центральной клетки. Она должна быть пустой (мы ведь собираемся сделать в нее ход, не так ли? Однако мы не забываем, что наш ИИ должен подставлять фигуры в данную клетку для анализа следующего хода. Фигура, которую мы подставляем – this.subfig – по умолчанию крестик. Поскольку центральная клетка изначально будет содержать в себе какую-либо фигуру после подстановки, то она будет принадлежать какой-то атаке this.curAttack:
Все эти пункты мы отобразили в значениях конструктора по умолчанию – смотри код выше.
2) Далее, уменьшая итератор, перебираем 5 клеток с одной стороны от сканируемой. За это отвечает функция getAttacks( cellX, cellY, subFig, dx, dy ), где:
cellX, cellY – координаты проверяемой клетки
subFig – фигура, которую мы подставляем в проверяемую клетку
dx, dy – изменения координат x и y в циклах – так мы задаем направление поиска:
Обратите внимание, что если checkCell() что-то вернет, то выполнение цикла прекращается.
3) Проверяем фигуры данных клеток.
За это отвечает функция checkCell( x, y ):
Для начала запишем фигуру в переменную fig:
Model.Field – наше игровое поле.
fig может быть ‘x’, ‘o’, ‘b’ (граница), 0 (пустая клетка).
4) Если на 5-ой клетке фигура совпадает с центральной клеткой, значит атака «уперлась» в границу и для определения потенциала атаки придется «проверить границу» ( this.checkEdge = true).
Функция checkCell – готова. Однако продолжаем работать над классом checkLine.
5) После выполнения первого цикла, надо «развернуться». Переводим итератор в центр и центральную атаку, с индексом 0, убираем из массива атак и устанавливаем как текущую.
6) Далее идем в другую сторону от текущей клетки, увеличивая итератор.
Абсолютно такая же проверка фигур. (Код уже написан – функция getAttacks)
7) Все, мы собрали все атаки, что были на линии в один массив.
На этом с классом checkLine всё… закончили.
Ну а дальше все просто – создаем объект checkLine для каждой из линий (2 диагонали, горизонталь и вертикаль) и вызываем функцию getAttacks. То есть, для каждой линии — свой объект checkLine и, соответственно, свой набор атак.
Пусть за все это отвечает функция getAllAttacks() – уже отдельно от описанных выше классов;
На выходе имеем объект со всеми атаками для проверяемой клетки
Однако вы, возможно, заметили некую функцию-фильтр. Ее задача – отсеивать «бесперспективные» атаки:
Да соберем, наконец, все воедино
Итак, основной ад позади — описан выше. Пора слепить из него что-то рабочее. Функция countWeight( x, y ) — принимает на вход координаты клетки, а возвращает ее вес. Что же у нее под капотом?
Во-первых, получим массив всех атак, которым клетка принадлежит. ( getAllAttacks( x, y ) ). Перебирая все линии, мы считаем количество брейкпоинтов. Если 2 брейкпоинта – вспоминаем, что такая ситуация может решить исход игры, и увеличиваем вес клетки на 100.
Однако все брейкпоинты должны принадлежать одному игроку, поэтому пришлось реализовать проверку в 2 шага: сначала крестики, потом нолики.
Поскольку в массиве весов атак ( ATTACK_WEIGHTS[] ) я не предусмотрел атаки мощностью 6 и больше, мне пришлось заменить их на атаки мощностью 5. Разницы никакой – все они приводят к концу игры.
Ну и суммируем веса атак – к этому все и шло.
Еще небольшой момент: чтобы бот в конце игры не тупил, когда он уже построил атаку мощностью 4 и думает над текущем ходом, необходимо значительно увеличить вес клетки для завершения такой атаки. Без этого, ИИ, просто на просто, может начать защищаться от «опасных» атак оппонента, хотя игра, казалось бы выиграна. Последний ход важен.
Теперь при вызове этой функции для конкретной клетки мы получим ее вес. Проводим эту операцию для всех клеток и выбираем наилучшую (с наибольшим весом). Туда и ходим)
Остальной код вы сможете найти на github. Материала уже предостаточно, и его изложение, как я не пытался, оставляет желать лучшего. Но если ты смог дочитать до этого момента, дорогой читатель, то я тебе благодарен.
Мое мнение о полученном результате
Сойдет! Да, его можно обыграть, однако сделать это немножко проблематично лично для меня. Возможно я просто недостаточно внимателен. Попробуйте и вы свои силы.
Знаю, что можно проще, но не знаю как. Хотелось бы выслушать людей знающих или посмотреть на иные реализации такого бота.
Знаю, что можно лучше. Да… можно воспользоваться известными алгоритмами, вроде минимакса, но для этого нужно обладать некоторой базой знаний в области теории игр, чем похвастать увы не могу.
В будущем планирую добавить анализ брейкпоитов на несколько шагов вперед, что сделает бота еще более серьезным соперником. Однако сейчас не имею четкого представления о реализации сего; лишь имею предстоящую сессию и недописанный диплом – что меня огорчает.