Как выиграть в самой сложной игре мира

Самая слож­ная игра в мире — так офи­ци­аль­но назы­ва­ет­ся аркад­ная игра, где вы долж­ны прой­ти от одно­го без­опас­но­го места к дру­го­му. Слож­ность в том, что ваша ско­рость намно­го мень­ше, чем ско­рость дви­жу­щих­ся пре­пят­ствий. Когда они вас насти­га­ют — всё обну­ля­ет­ся и игра начи­на­ет­ся сна­ча­ла. Если хоти­те попро­бо­вать свои силы — попро­буй­те.

Выгля­дит это так:

Аркадная игра

Наш ста­рый зна­ко­мый Эван (он же CodeBullet) напи­сал ней­рон­ку, кото­рая научи­лась выиг­ры­вать в эту игру, и снял об этом видео. Если зна­е­те англий­ский, луч­ше посмот­ри­те видео, там доволь­но забав­но всё про­ис­хо­дит. Для осталь­ных мы при­го­то­ви­ли тек­сто­вую вер­сию того, что про­ис­хо­дит у Эвана:

Пишем саму игру

Что­бы мож­но было управ­лять крас­ным квад­ра­ти­ком и адек­ват­но реа­ги­ро­вать на про­ис­хо­дя­щее, мож­но пой­ти дву­мя путя­ми: напи­сать отдель­ную ней­рон­ку для рас­по­зна­ва­ния того, что про­ис­хо­дит на экране (это очень слож­но), или напи­сать саму игру, что­бы сра­зу отда­вать ней­рон­ке все дан­ные (это гораз­до про­ще). Эван выбрал вари­ант с игрой, поэто­му вот какие пра­ви­ла нуж­но было учесть:

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

Поэтап­но это выгля­де­ло вот так:


Рису­ем сте­ны, без­опас­ные зоны и игро­вое поле 

Шари­ки про­сто меня­ют своё направ­ле­ние на про­ти­во­по­лож­ное при отскоке 

А вот тут Эван доба­вил крас­ный квад­ра­тик, но забыл про­пи­сать, что нель­зя захо­дить за сте­ны и касать­ся синих шари­ков. Бывает 🙂 

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

Пишем нейронку

Сна­ча­ла Эван взял за осно­ву стан­дарт­ный алгоритм:

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

Посмот­рим, что из это­го получится:


Выгля­дит очень хаотично 

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

Новый алгоритм — дойти как можно дальше

Поме­ня­ем алго­ритм на такой:

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

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

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


Пер­вое поколение 

Два­дца­тое поко­ле­ние — совсем дру­гое дело 

Квад­ра­ти­ки научи­лись выхо­дить из зелё­ной зоны, но они пока не зна­ют, как вести себя с сини­ми шари­ка­ми. Нуж­на новая сту­пень обучения.

Избегаем синих шариков

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

Это самый дол­гий этап обу­че­ния, поэто­му мы его немно­го уско­рим и упро­стим — будем пока­зы­вать толь­ко один квад­ра­тик (луч­ший в каж­дом поко­ле­нии) и толь­ко основ­ные эта­пы. Поехали.


Нача­ло обу­че­ния. Пока всё плохо 

Уже намно­го луч­ше, но есть про­бле­ма с самым послед­ним шариком 

Ура, у нас есть победитель! 

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

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

Что дальше

Даль­ше мы попро­бу­ем напи­сать эту игру сами.

А потом напи­шем ней­рон­ку, кото­рую тоже научим сами.

Кру­то? Кру­то! Поэто­му под­пи­сы­вай­тесь, дели­тесь с дру­зья­ми и не про­пус­кай­те новые проекты.