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

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

Создание AI(тут и далее под AI подрузмевается комплекс алгоритмов перебора)

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

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


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


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

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


Заключение

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