Работая над своей реализацией Тетриса на Javascript, я столкнулся с необходимостью тестирования игры. Тестировать хотелось в условиях, максимально приближенных к реальности, т. е., играя в него. Самому тратить часы на игру не было ни желания, ни времени. Я решил разработать бота, который будет играть в тетрис вместо меня. Такого бота можно оставить играть на несколько часов и отловить редкие ошибки, которые слишком трудно воспроизвести вручную. Кроме того, мне было просто интересно написать такого бота.
Сразу оговорюсь — я ничего не знаю о существующих алгоритмах игры в тетрис. Я не изучал специально этот вопрос, я просто сам придумал алгоритм и представляю его здесь. Он может быть не самым лучшим, не самым быстрым и оптимальным. Но он отлично работает, просто реализуется и полностью меня устраивает. Вполне возможно, что кто‑то уже реализовал похожий алгоритм. Решение вполне очевидное и могло прийти в голову не только мне.
Описание алгоритма
Предлагаемый алгоритм не связан с нейронным сетями, глубоким обучением и т. д. Он очень простой, это алгоритм грубой силы, брутфорса. Вариантов сброса фигурки в стакан совсем немного. Суть моего алгоритма — рассмотреть все возможные варианты, оценить каждый вариант по некоторым критериям и выбрать лучший. Программного кода к статье не будет, он тесно интегрирован в игру и его слишком сложно отделить, я расскажу только основную идею. Есть видео на ютуб:
Всего в классическом тетрисе семь фигур. Они названы по буквам, начертания которых они напоминают — O, I, S, Z, J, L, T:
Ширина стакана составляет десять ячеек. Каждая фигурка имеет до четырех состояний, в зависимости от поворота. Разные фигурки имеют одну (O), две (I, Z и S) и четыре (J, L, T) возможных ориентации. Таким образом, нам надо рассмотреть всего не более 40 разных вариантов хода — менее десяти возможных положений по горизонтали, умноженные на четыре (или меньше) возможных ориентации фигурки в каждом положении. Это совсем немного и отлично подходит для брутфорса, особенно если учесть, что расчеты нужно запустить только один раз на каждую новую фигурку, а не в каждом кадре.
Алгоритм запускается в момент появления новой фигурки в верхней части стакана, ищет лучшее решение и далее уже посылает игре команды управления, как это делал бы игрок.
Сначала двигаем фигурку максимально влево (только виртуально, реального движения на экране не происходит). Виртуально сбрасываем ее и оцениваем, как изменилось бы поле после ее падения, насколько это улучшит или ухудшит ситуацию для игрока. Потом поворачиваем фигурку и снова бросаем, оцениваем. Перебрав все возможные повороты фигурки, двигаем ее вправо на один шаг и снова рассматриваем сброс фигурки при всех возможных поворотах. Повторяем процесс до тех пор, пока не дойдем до крайней правой позиции. Так мы рассмотрим все возможные ходы (за исключением «подныривания» фигуркой под нависающие блоки, мой алгоритм это не поддерживает, но и без этого все хорошо работает).
Для каждого возможного варианта сброса фигурки я рассчитываю качество этого решения. Это скалярная величина, чем она выше, тем более предпочтительно данное решение. По сути это числовая оценка того, насколько игроку станет лучше или хуже после этого хода.
Качество я рассчитываю по нескольким критериям:
Сколько линий убралось бы в результате этого хода. Каждая убранная линия повышает значение качества.
Как низко упадет фигурка. Чем ниже она упадет, тем выше качество решения. Этот критерий стимулирует алгоритм не создавать слишком высоких башен, так как они могут привести к преждевременному окончанию игры.
Сколько новых полостей образовалось бы в результате этого хода. Полость — пустая изолированная клетка, которая препятствует исчезновению ряда. Рассчитывается количество полостей до исследуемого хода и после него. Чем больше новых полостей образовалось, тем хуже решение.
Сколько новых клеток «колодцев» образовалось в результате этого хода. Колодец — узкая (шириной в одну клетку) яма, высотой более двух клеток. Такие колодцы создают проблемы, так как заполнять их без образования полостей можно только одной фигурой — палочкой I. А выпадает она редко, с вероятностью 1/7 (рандомизатор 7-bag, который гарантирует более‑менее скорое выпадение любой фигурки, я считаю читерством и не использую, в моей игре честная рандомизация).
Легко видеть, что указанные критерии иногда могут противоречить друг другу. Например, критерии 2 и 3. Можно сбросить фигурку пониже, но при этом образуется полость. А можно сбросить ее выше, без образования полости, но тогда может вырасти общая высота заполненной части стакана и приблизить конец игры. Другой пример: можно сбросить фигурку и убрать линию (хорошо), но при этом могут появиться новые полости (плохо).
Для регулирования влияния критериев на значение качества решения я использую весовые коэффициенты, подобранные опытным путем. Кроме того, эти весовые коэффициенты динамические, они изменяются в некоторых пределах по мере игры в зависимости от состояния игрового поля. Например, если стакан не сильно заполнен, то алгоритм старается не плодить полости и меньше внимания обращает на высоту, т. е. пакует кирпичики плотно, пока есть запас высоты. Если стакан значительно заполнен, то возрастает важность критерия высоты — алгоритм больше старается опускать фигурки ниже, дабы не достичь верха и не получить game over.
Рассчитав с помощью указанных критериев и их весовых коэффициентов значения качества для каждого решения, выбираем решение с максимальным качеством. Имея выбранное решение, посылаем в игру команды управления, которые приведут фигурку в нужное нам положение.
Бот играет гораздо лучше человека и доходит до уровней, недостижимых для реальных игроков. В этом видео
бот перевалил за трехсотый уровень, после чего мне просто надоело ждать и я остановил процесс. Кроме того, в моем тетрисе есть усложненный режим Pentix. В этом режиме не 7, а 29 возможных фигур (от одноблочной до пятиблочных пентамино), а размер колодца больше. Бот успешно играет и в Pentix:
Применение
Описанный бот позволил мне найти и устранить утечку памяти. Память утекала медленно и я не замечал этого при ручном тестировании. Оставив бота играть на час‑два, я обнаружил утечку, проанализировал причину и устранил ее. Кроме этой утечки бот помог выявить еще несколько багов.
Другое возможное применение бота — демо режим в самой игре в момент неактивности пользователя.
Использую бота для записи видео геймплея.
С помощью моего алгоритма легко можно подыгрывать, или, наоборот, препятствовать игроку. Оценивая предложенным способом игровую ситуацию, можно выдавать наиболее подходящие (имеющие решения максимального качество), или, наоборот, наиболее неподходящие (с минимальным качеством решения) фигурки. Ради интереса я это реализовал. Но в финальной игре, конечно, будет честная рандомизация, я же не читер.
Комментарии (32)
Ivnika
10.12.2023 22:33Интересная сторона любимой игры, спасибо :)
А ссылкой на реализацию не поделитесь?
DizzyRide Автор
10.12.2023 22:33ссылки нет, к сожалению. Проект еще нигде не выложен, работает только локально на моем компе. Если доведу до конца, то может опубликую в Яндекс.играх или еще где то
Germanjon
10.12.2023 22:33Несколько идей по доработке бота:
Один из важных элементов игры - "задвигание" в самом низу фигуры под другую или "переворот" падающей фигуры в самом низу.
Дополнительно нужно проверять - можно ли перевернуть фигуру. Если у вас есть башня посреди игрового поля, может просто не хватить места на вращение фигуры I.
Учёт не только текущей, но и следующей фигуры - может быть будет более выгодно использовать её.Ну и крейзи идея - добавить вероятность ошибки, чтобы бот намеренно ставил фигуры не туда, куда нужно, а потом пытался исправить ситуацию.
Желаю удачи в реализации и дальнейшем развитии.
DizzyRide Автор
10.12.2023 22:33Благодарю! Про "задвигание" фигурки тоже думал, но не стал пока реализовывать. Бот очень простой, я за день его написал. Это усложнило бы дело. Но на будущее да, можно подумать и об этом
Zara6502
10.12.2023 22:33Интересно, спасибо.
Писал когда-то для ATARI реверси на Бейсике, игра возможна была как со вторым игроком так и с компьютером. Алгоритм хода компа был простым, вес = число взятых фишек за вычетом потери фишек со следующим ходом человека. То есть может быть и хорошо своим ходом забрать 5 фишек, но если мы потом теряем 6 своих, то вес будет -1. А если я могу забрать 3, а потерять тоже 3, то вес 0, что уже лучше и ход производится по этому условию. Как бы просто не выглядел алгоритм, что для ребенка не особо задумывающегося о ходах, он был весьма продуктивным. Потом добавил еще 2 сложности, соответственно с просчётом на еще 1 и на 2 хода. Хоть это всё и работало на Бейсике и должно бы по идее быть долгим, но конечно было не так долго как в шахматах, всё же в реверси игрок обязан забирать камни если такой ход есть, а если такого хода нет, то пропускать ход. Так что в среднем ожидание было небольшим (скажем в шахматах ход компа мог длиться пару часов XD ).
Кстати во многих старых играх алгоритмы противников и демо игр в ожидании действий игрока (или монеты в автомате) смотрятся весьма неплохо и выглядят весьма умненько, хотя порой всё сделано очень и очень просто.
Zara6502
10.12.2023 22:33XD здрасипожалуйста, а минус-то за что? За то что 40 лет назад писал на бейсике?
Zara6502
10.12.2023 22:33Посмотрел видео, мне кажется вы слишком мелко сделали справа и слева окна и текст, там пустое пространство, можно увеличить
DizzyRide Автор
10.12.2023 22:33там у меня в пустом пространстве сейчас окно со статистикой по выпаданию фигур выводится, на видео его нет. А если увеличивать шрифты, то игра может не уместиться в экран смартфона. В первую очередь для десктопа разрабатываю, но и о смартфонах приходится думать. Буду потом еще подгонять все тщательно
perfect_genius
10.12.2023 22:33Впервые вижу, что кто-то закрыл сообщения, поэтому про опечатку придётся писать сюда.
А она простая - название игры идёт с заглавной буквы только в заголовке, в пером предложении и в названиях видео. Во всём остальном тексте "Тетрис" написан с маленькой буквы.
DizzyRide Автор
10.12.2023 22:33Благодарю, но это не опечатка. Везде пишут по разному, и с маленькой, и с большой - я проверял поиском в гугле. "Шахматы" и "шашки" пишут с маленькой, например, а тетрис уже не только название конкретной игры, но и целого класса головоломок. Впрочем, спорить не буду, может с большой будет правильнее, если придираться. Но я счел это несущественным и большой ошибкой не считаю.
savostin
Хм.
DizzyRide Автор
Искусственный интеллект это не только нейронные сети. В применении к играм это вообще любые алгоритмы, управляющие чем то в игре, хоть NPC, хоть фигурками в тетрисе, хоть шахматными фигурами на доске.
IvanPetrof
Интересно, тут в соседних темах про GPT обязательно находится пара заплюсованных комментов, что GPT это не ИИ.
Я запутался..
DizzyRide Автор
GPT это ИИ, конечно, но и мой алгоритм это тоже ИИ, только совершенно на другом принципе построенный, на четком алгоритме, а не нейронной сети. ИИ понятие широкое. Нейронные сети появились недавно, а понятие ИИ существует давно. В игре Pac-Man 1983-го года тоже был ИИ, а никаких GPT тогда не было
IvanPetrof
Ну как, недавно. Я ещё в детстве читал про них старые книжки. Щас погуглил - их ещё на лампах пытались замутить. Куда уж раньше?
DizzyRide Автор
большого практического значения они тогда не имели и широкие массы ими не пользовались, только в последние годы они произвели революцию. Но это уже не по теме моей статьи
Dynasaur
ИИ это вообще маркетингово-журналистский термин. Технический термин это "Машинное обучение". По тому, что наличие интеллекта у того или иного алгоритма вопрос спорный, причём спорить можно сколько угодно, нет чётких критериев наличия интеллекта. А наличие обучения машин это объективная реальность, она бесспорна.
Zenitchik
ИИ - это удобный термин, используемый в отрасли. Но из-за любителей по своему интерпретировать чужие термины, приходится придумывать эвфемизмы.
Dynasaur
ну вот и спорят люди - тупой перебор это интеллект или не интеллект
Zenitchik
Ну я и говорю: этот спор происходит из-за желания неспециалистов влезть со свиным рылом в калашный ряд.
ИИ - есть ИИ, на каких алгоритмах он реализован - вопрос десятый.