Работая над своей реализацией Тетриса на 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:
Применение
Описанный бот позволил мне найти и устранить утечку памяти. Память утекала медленно и я не замечал этого при ручном тестировании. Оставив бота играть на час‑два, я обнаружил утечку, проанализировал причину и устранил ее. Кроме этой утечки бот помог выявить еще несколько багов.
Другое возможное применение бота — демо режим в самой игре в момент неактивности пользователя.
Использую бота для записи видео геймплея.
С помощью моего алгоритма легко можно подыгрывать, или, наоборот, препятствовать игроку. Оценивая предложенным способом игровую ситуацию, можно выдавать наиболее подходящие (имеющие решения максимального качество), или, наоборот, наиболее неподходящие (с минимальным качеством решения) фигурки. Ради интереса я это реализовал. Но в финальной игре, конечно, будет честная рандомизация, я же не читер.
