Программист учит компьютер играть в Тетрис

Наш ста­рый зна­ко­мый Эван Codebullet сно­ва дела­ет алго­ритм, кото­рый игра­ет в игры и ста­вит рекор­ды. На этот раз он будет играть в тет­рис. Если хоти­те луч­ше пони­мать логи­ку рабо­ты это­го алго­рит­ма, посмот­ри­те, как запро­грам­ми­ро­вать тет­рис на JavaScript само­му, а потом воз­вра­щай­тесь сюда.

Ори­ги­наль­ное видео Эва­на (если зна­е­те англий­ский, смот­реть будет интереснее):

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

👉 Искус­ствен­ный интел­лект — это не все­гда нейросети

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

Если хоти­те посмот­реть и оце­нить сам код алго­рит­ма, зай­ди­те в Гит­хаб Эвана.

Сначала нужно сделать саму игру

Эван начи­на­ет с про­сто­го — созда­ёт игро­вое поле, по кото­ро­му пада­ет крас­ный квадратик:

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

Как толь­ко Эван начал рисо­вать фигу­ры и воз­мож­ные вари­ан­ты их вра­ще­ния, то понял, что нуж­но най­ти схе­мы, как это дела­ет­ся в ори­ги­наль­ной игре:

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

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

Когда Эван это испра­вил и доба­вил авто­вра­ще­ние каж­дой фигу­ре на стар­те, полу­чи­лось такое:

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

Мно­го ите­ра­ций спу­стя Эван испра­вил все баги и смог-таки заста­вить бло­ки падать и вращаться. 

Проверка на пересечения и столкновения

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

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

Удаление целой линии

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

После обнов­ле­ния кода всё зара­бо­та­ло как нуж­но. Заод­но появи­лись окош­ки со сле­ду­ю­щей и удер­жи­ва­е­мой фигурами.

Удер­жи­ва­е­мая фигу­ра — это спе­ци­аль­ный эле­мент в совре­мен­ном тет­ри­се, кото­рый рабо­та­ет так:

  • там появ­ля­ет­ся какая-то фигу­ра из игро­вой последовательности;
  • игрок в любой момент может заме­нить теку­щую фигу­ру на эту, а обрат­но уже не может;
  • это поз­во­ля­ет наби­рать боль­ше очков и помо­га­ет игро­кам ста­вить боль­ше рекордов.

Обучаем алгоритм

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

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

Реше­ние — мы смо­де­ли­ру­ем для каж­дой фигу­ры все воз­мож­ные нажа­тия кла­виш. Это не опти­маль­ный вари­ант с точ­ки зре­ния исполь­зо­ва­ния машин­ных ресур­сов, но он даёт нам нуж­ный резуль­тат. Теперь ком­пью­тер может при­ки­нуть, куда поме­стить оче­ред­ную фигу­ру уже на стар­те. Неза­кра­шен­ная фигу­ра вни­зу — это Эван сде­лал види­мым про­цесс «мыш­ле­ния» алго­рит­ма, куда поста­вить новый элемент:

Выбираем оптимальное место

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

Чем мень­ше таких яче­ек оста­ёт­ся, тем более жела­е­мый ход. Теперь про­грам­ма луч­ше под­го­ня­ет фигу­ры друг к другу:

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

Ста­ло намно­го луч­ше: теперь ком­пью­тер ста­ра­ет­ся не остав­лять под собой пустых бло­ков и стре­мит­ся укла­ды­вать фигу­ры как мож­но ниже.

Используем удерживаемую фигуру

Сле­ду­ю­щее, чему Эван учит свой алго­ритм, это исполь­зо­вать удер­жи­ва­е­мую фигу­ру. Тре­тье пра­ви­ло, кото­рое он добав­ля­ет, такое: про­верь, что будет, если заме­нить фигу­ру на удер­жи­ва­е­мую, и если резуль­тат будет луч­ше — заме­ни фигуру.

Ста­ло ещё лучше:

Последняя проблема — пустые одиночные столбцы

Когда ком­пью­тер ста­вит фигу­ры по этим трём пра­ви­лам, то часто у него полу­ча­ют­ся пустые вер­ти­каль­ные столб­цы, куда мож­но поме­стить толь­ко пря­мую фигуру:

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

И это ста­ло реша­ю­щим момен­том в рабо­те алго­рит­ма. До это­го он с тру­дом соби­рал 1000 линий, а сей­час лег­ко наби­ра­ет 10 000 линий и не оста­нав­ли­ва­ет­ся на этом. 

Выво­ды простые:

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

Алго­ритм и иллю­стра­ции:
Эван CodeBullet

Текст:
Миша Поля­нин

Редак­тор:
Мак­сим Ильяхов

Худож­ник:
Даня Бер­ков­ский

Кор­рек­тор:
Ира Михе­е­ва

Вёрст­ка:
Маша Дро­но­ва

Соц­се­ти:
Олег Веш­кур­цев