Искусственный интеллект (почти) идеально проходит змейку

YouTube-блогер Code Bullet сделал идеальный (на самом деле нет) искусственный интеллект для змейки. Алгоритм собирает блок за блоком, стараясь не врезаться головой змеи в бока. Выглядит завораживающе.

Гифка выше показывает результат, которого добился автор канала. Он, конечно, не совсем идеален. Если протестировать алгоритм на большем игровом поле, то в конце могут остаться пара блоков, до которых змейка (занимающая весь остальной экран) так и не доберется. Это, кажется, лишило автора ролика последних остатков рассудка, ведь он потратил долгие часы разработки и сделал несколько подходов, чтобы сделать идеальный искусственный интеллект для змейки.

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

Затем блогер решил использовать так называемый гамильтонов цикл. В применении к «проблеме змейки» это значит, что на весь игровой экран заранее накладывается путь для змейки, который пролегает через все клетки и замыкается. А чтобы змейка двигалась пошустрее, в некоторых местах алгоритм разрешает змейке срезать углы. Этот способ решения, пусть и менее хаотичный и похожий на настоящую игру, всё же более безопасный — змейке удалось растолстеть так, что она заполнила всё игровое поле, кроме двух ячеек.

Если вы хоть немного погружены в тему, то видео целиком с объяснениями и примерами работы можно посмотреть ниже. А если нет, и ваша кнопочная Nokia опять куда-то запропастилась — что ж, тогда просто наберите слово snake в поиске Google и сыграйте в бесплатную версию великой игры.