Небольшая игра «Крестики-нолики» на JavaScript

Это пост про небольшую игру «Крестики-нолики», которая была написана в целях пополнения опыта программирования на JS. Здесь применяются canvas и DojoBase. Библиотека используется для работы с событиями и для нахождения элементов по id(это очень удобно). Сanvas используется для отрисовки игрового поля.
И сами «Крестики-нолики».

Правила «Крестиков-ноликов» из этой реализации простые: необходимо собрать ряд из пяти элементов(в любом направлении) раньше противника. Количество ходов одинаково, то есть, если нолики(они ходят первыми) собрали ряд, а у крестиков есть линия из четырех элементов, то раунд не заканчивается. Да, в этой реализации одна игра состоит из нескольких раундов. Игра заканчивается тогда, когда на поле не останется свободных клеток. Победителем становится тот, кто больше раундов выиграл. Клетки, которые были использованы в прошлых раундах заливаются и становятся не активными. Само же разрешение поля устанавливается в зависимости от разрешения окна браузера.

Создание AI

Тут самое интересное, конечно, это — AI. Я его «обучал» ходить более менее правильно в несколько этапов… Сначала, AI ставил свой значок на первой свободной клетке, которую находил. Немного потестировав, мне стало понятно, что это не интересно. Оно работает, но что-то тут не так. Поразмыслив, что лучше случай, чем такое, я прикрутил rand. После этого, стало чуточку по веселее, но все равно — не интересно.
Так, ладно, пусть сначала найдет все клетки, в которые можно(и нужно) сходить. То есть, что-то подобное(выделены синим).

Эти "нужные" клетки определяются по такому алгоритму"

Тут вся информация о игровом поле(что на нем происходит) содержится в двумерном глобальном массиве, значения элементов которого которого, показывают состояния клеток. Используется полный набор направлений, то есть проверяются все соседние клетки с данной. В массив_2 записываются результаты поиска «нужных» клеток.

Так, определили и что дальше с ними делать? Можно в любую из этих клеток ставить рандомно элемент. А можно и назначить каждой клетки оценки и на их основе выбрать наиболее лучший вариант, а затем его использовать. Звучит хорошо. Но, сначала надо решить другой вопрос.
При ходе AI за нолики, может возникнуть ситуация, что «нужных» клеток просто не будет. Например, при первом ходе раунда. Теперь надо придумать алгоритм по нахождению лучшего варианта в этой ситуации(или когда нет свободных клеток у крестиков или ноликов). И я считаю, что хорошо ходить туда, где наиболее просторно.

Поэтому тут реализован такой алгоритм

В м_отрезки записываются промежуточные данные, то есть ряды свободных клеток(вертикальных и горизонтальных) в определенном формате. В объект о_координата будет записан результат работы данной функции. Если отрезок является диаметром «пустого» квадрата, то это означает, что его центральная точка(клетка) — это центр квадрата свободных клеток, при том его стороны равны этому отрезку.

И настало время алгоритму, который выбирает ход на основе оценок.

Вот он

На вход этого алгоритма подается массив с «нужными» точками. Массив м_оценок, вспомогательный и суда записываются оценки клеток. Здесь, как и в предыдущем примере, используется полный перебор всех направлений вокруг клетки. Оценка осуществляется по двум параметрам: тип хода(блокирование или дополнение своего ряда) и длина линии элементов(1, 2, 3 или 4 клетки). Назначение происходит специальной функцией, где можно менять критерии. Эти оценки(критерии) суммируются по всем направлениям для данной клетки.

Заключение

Ну в итоге у меня у меня получилась небольшая игра с AI, который может обыгрывать новичков. Я его без труда выигрываю, не «в сухую», конечно, но все же. Стоит отметить, что когда играешь за «крестики», то как бы уровень сложности пониже, а вот за «ноликов» играть немного посложнее.
Режим нескольких раундов сделал задачу поинтереснее. Например, тут AI должен находить оптимальную клетку для превого хода. Еще возникла проблема с тем, что одиночные пустые клетки(в которых ходить бессмысленно), необходимо тоже было как-то «заштриховывать». Но, в конце концов я с этим справился.
GitHub

Автор: Arteben

Источник