Большой разбор: как ИИ играет в змейку
Большой разбор: как ИИ играет в змейку
Своя игра: создаём собственную «Змейку» Собираем змейку на Arduino

Помни­те, рань­ше была такая игра — змей­ка? Она появи­лась в 70-х, и в неё игра­ли на всём: от ком­пью­те­ров и при­ста­вок до кно­поч­ных теле­фо­нов. Напри­мер, если вы про­пу­сти­ли то вре­мя, это мог­ло выгля­деть вот так:

Смысл игры:

  1. Вы управ­ля­е­те змей­кой, кото­рая посто­ян­но в дви­же­нии, она может дви­гать­ся вверх, вниз, вле­во или впра­во. На экране в слу­чай­ном месте появ­ля­ет­ся кле­точ­ка — счи­тай­те, что это еда.
  2. Ваша зада­ча — собрать как мож­но боль­ше еды.
  3. Как толь­ко змей­ка съе­да­ет оче­ред­ную кле­точ­ку с едой, в слу­чай­ном месте появ­ля­ет­ся новая клет­ка. Так­же змей­ка удли­ня­ет­ся на одну клетку.
  4. Если змей­ка упрёт­ся в стен­ку или сама в себя, то игра заканчивается.

В нача­ле игры всё про­сто: поле пустое, змей­ка воль­гот­но по нему пол­за­ет и жрёт. Но даль­ше змей­ка посте­пен­но рас­тёт, зани­мая всё боль­шую пло­щадь экра­на, и в какой-то момент пере­дви­гать­ся ста­но­вит­ся супер­слож­но. И вот тогда нуж­на стра­те­гия и ловкость.

Австра­лий­ский про­грам­мист Эван, он же CodeBullet, научил искус­ствен­ный интел­лект играть в эту игру и сде­лал об этом видео:

Если вы зна­е­те англий­ский, про­сто смот­ри­те и полу­чай­те удо­воль­ствие, а если нет — мы при­го­то­ви­ли подроб­ный раз­бор того, что про­ис­хо­дит в ролике.

Начало: 5 разных алгоритмов

В самом нача­ле Эван экс­пе­ри­мен­ти­ро­вал с ней­ро­се­тью, что­бы най­ти луч­ший алго­ритм для игры в змей­ку. В ито­ге у него полу­чи­лось 5 раз­ных алго­рит­мов, каж­до­му из кото­рых он дал своё имя. Они отли­ча­лись сти­лем игры, пове­де­ни­ем в раз­ных ситу­а­ци­ях и результативностью.

Сте­пан. Это одна из пер­вых вер­сий алго­рит­ма, у кото­рой есть одна харак­тер­ная осо­бен­ность: Стё­па любит дви­гать­ся по диагонали.

Несмот­ря на то, что кажет­ся, что змей­ка дела­ет всё пра­виль­но, это самая худ­шая вер­сия ней­рон­ки, кото­рая полу­чи­лась у про­грам­ми­ста. При этом уме­ние Стёп­ки дви­гать­ся по диа­го­на­ли — уни­каль­но, оно силь­но при­го­дит­ся в будущем.

Лена. Она умнее Стё­пы, дви­га­ет­ся более пред­ска­зу­е­мо, а ещё у неё класс­но полу­ча­ет­ся избе­гать столк­но­ве­ния с собой. Это важ­ное уме­ние для змей­ки, пото­му что если голо­ва упрёт­ся в хвост или в тело — игра закончится.


Лена отлич­но уме­ет выби­рать­ся из слож­ных ситуаций. 

Миша. Быст­рая, эффек­тив­ная змей­ка почти без еди­но­го лиш­не­го дви­же­ния. Миша почти иде­а­лен, но это­го недостаточно.

Коля. Уме­ет соби­рать мно­го кусоч­ков, но когда ста­но­вит­ся совсем длин­ным, то раз­мер начи­на­ет ему мешать.

Сёма. Чем­пи­он сре­ди этих вер­сий, пото­му что толь­ко он смог набрать 136 очков — боль­ше, чем осталь­ные кандидаты.

Собираем в одно целое

Мож­но было оста­но­вить­ся на Сёме, но Эван решил пой­ти даль­ше и поду­мал: «А что если объ­еди­нить эти змей­ки в одну, что­бы вме­сте они рабо­та­ли мак­си­маль­но эффективно?»

Для это­го про­грам­мист сде­лал одну боль­шую ней­ро­сеть, в кото­рую поме­стил 5 зме­ек по тако­му алгоритму:

  1. Перед каж­дым сле­ду­ю­щим шагом каж­дая из пяти зме­ек гово­рит, как бы она посту­пи­ла в этой ситуации.
  2. Отдель­ная ней­ро­сеть смот­рит на вари­ан­ты и выби­ра­ет луч­ший из них.
  3. Змей­ка дела­ет шаг, и всё начи­на­ет­ся сначала.

Смысл в том, что­бы исполь­зо­вать силь­ные сто­ро­ны каж­дой змей­ки для наи­боль­ше­го эффекта.

Добавляем цвета

Что­бы сто­рон­не­му наблю­да­те­лю было понят­но, что про­ис­хо­дит на экране и о чём имен­но «дума­ет» ней­рон­ка, Эван при­ду­мал рас­кра­ши­вать змей­ку в раз­ные цвета:

  • зелё­ный озна­ча­ет, что змей­ка нашла оче­ред­ной кусо­чек, кото­рый мож­но съесть, и это ста­ло её целью;
  • синий — змея пред­ви­дит, что ско­ро она будет дви­гать­ся к еде;
  • белый — рядом со зме­ёй нет лег­ко­до­ступ­ных кусоч­ков, и её зада­ча — выжить и нику­да не врезаться.

Теперь мы тоже можем пони­мать, какие реше­ния при­ни­ма­ет искус­ствен­ный интел­лект в каж­дой ситу­а­ции. Самое инте­рес­ное, что ино­гда мы даже можем понять, какая из зме­ек сей­час взя­ла управ­ле­ние на себя.


Напри­мер, тут явно Степан. 

А вот тут Лена помо­га­ет Стё­пе не вре­зать­ся в само­го себя. 

Появил­ся синий цвет: это озна­ча­ет, что змей­ка видит еду и дума­ет, как бы подо­брать­ся к ней поближе.


Даже тут виден кусо­чек Стёпы 🙂 

Новая змей­ка поби­ла рекорд Сёмы, и даже с такой дли­ной она лег­ко дви­жет­ся дальше. 

Нача­лись пер­вые про­бле­мы: белый цвет озна­ча­ет, что змей­ке не до еды и нуж­но выби­рать­ся из такой ситуации. 

А вот отсю­да змей­ка уже выбрать­ся не суме­ет, хотя путь для выхо­да у неё есть. Рекорд — 204 очка. 

Запу­стим сно­ва и про­ве­рим, полу­чит­ся ли побить этот рекорд:


200 очков и почти ката­стро­фа, но змей­ка всё же нашла реше­ние. Поразительно. 


Набрав 228 очков, змей­ка вне­зап­но вре­за­ет­ся в свой хвост, хотя места в сере­дине доста­точ­но для трёх таких змеек. 

Рекорд побит, и, ско­рее все­го, не в послед­ний раз. С каж­дым запус­ком алго­ритм ста­но­вит­ся умнее, и змей­ка допус­ка­ет всё мень­ше и мень­ше ошибок.

Что дальше

Даль­ше как обыч­но — новые боль­шие раз­бо­ры, объ­яс­не­ние того, как рабо­та­ют ней­ро­се­ти и как это при­ме­нить на прак­ти­ке. Лайк, под­пис­ка, все дела.