Участие в конкурсе JSDash

В начале июля представители компании Hola объявили об очередном конкурсе для JS-программистов. На этот раз требовалось написать бота для консольной версии игры Boulder Dash. Совсем в детском возрасте мне в руки попадалась одна из версий этой игры. Тогда она мне показалась слишком сложной и не очень интересной (ну да — стрелять нельзя, «экшена» нет, да еще и думать надо). Годы прошли и мое отношение к ней поменялось.

Кратко о правилах (с Хабра):

Клавишами-стрелочками можно перемещаться в четырёх направлениях. Зелёная буква A — это вы. Можно перемещаться через пустое пространство или землю (:), толкать камни (O) по горизонтали в пустое пространство и собирать алмазы (*). Через кирпичи (+) и сталь (#) пройти невозможно. Камни и алмазы падают, когда остаются без опоры, а также скатываются вбок друг с друга и с кирпичей. Падающие предметы убивают игрока. Бабочки (анимация /|\-) взрываются при соприкосновении с игроком, от удара падающим предметом, а также будучи запертыми без возможности передвижения. Взрыв бабочки поглощает любые материалы, кроме стали, и может убить игрока. После взрыва образуются алмазы, которые можно собрать.

За каждый взятый алмаз начисляется 1 очко. Если собрать 3 алмаза с промежутками менее 2 секунд, в дополнение к очкам за каждый из них, начисляется 3 призовых очка. Если продолжать быстро собирать алмазы, не делая промежутков в 2 секунды или длиннее, то начисляется 5 очков после пятого алмаза, 7 очков после седьмого (в дополнение ко всем предыдущим премиям), и так далее для каждого простого числа. За убитую бабочку начисляется 10 очков при условии, что игрока не убило взрывом.

Ограничение времени игры — 2 минуты. Можно прервать игру раньше, нажав Q, Esc или Ctrl-C; набранные очки при этом не теряются. Клавиша P позволяет приостановить игру.

Остаток времени, очки и сообщения о призовых цепочках (hot streak) отображаются в строке состояния под игровым полем.

Механика нашей игры в целом соответствует образцу 1984 года, однако для простоты мы решили использовать не все типы объектов. Самые большие отличия — описанная выше система начисления очков и то, что на уровне нет выхода. Цель игры — набрать как можно больше очков, прежде чем игра закончится смертью персонажа или по истечению времени.

Пример игрового процесса:

GIF

Помимо основных правил можно вывести еще ряд утверждений, необходимых для хорошего решения:

  • Надо собрать все бриллианты за один «hot streak»
  • Надо сбить все три бабочки (желательно отдельно, чтоб получить больше бриллиантов)
  • Надо избегать ситуаций, когда после хода какие-то бриллианты оказываются недоступны или же сам игрок оказывается в тупике

У меня получилось только стремиться к этим тезисам.

Опыта во всякого рода конкурсах или олимпиадах для программистов у меня ровно ноль (я сейчас не беру в учет большое количество веб-квестов — это немного другое).

За почти полтора месяца мой бот пережил несколько этапов развития. Его первый вариант опирался только на текущее состояние карты. Код содержал большое количество предопределенных ситуаций и варианты их прохождения. Например, падающие или скатывающиеся блоки в разных сторонах от игрока, бабочки в пределах двух ходов от игрока и т.д. Бот выбирал ближайший бриллиант просто высчитывая расстояние √((x₁ - x₂)² + (y₁ - y₂)²). При этом совершенно игнорировалось, что прямого пути между этими точками нет. Сам путь же прокладывался с помощью алгоритма Ли. Полученная последовательность ходов сохранялась и использовалась далее. На каждом ходу проверялось, что текущая цель все еще является бриллиантом и что следующий шаг из составленного ранее пути безопасен. Если хоть одно из этих условий не выполнялось, то выбиралась новая цель и прокладывался новый путь. Такой подход не мог показывать высоких результатов, так как не учитывал тупики, не оптимально выбирал цели, часто умирал от бабочек и т.д. Но для начала это было уже что-то.

Попытки улучшить бота сводились к более тщательному анализу возможных ситуаций вокруг позиции игрока. Но это приводило только к еще большему «хардкоду». В какой-то момент я уже начал теряться к этом коде. Мысль переписать все с нуля пришла чуть позже. Пока-что надо было разобраться с тупиками. Это оказалось немного легче, чем ожидалось. Идея чем-то похожа на алгоритм Ли, а вернее на его первую половину. От клетки, где находится игрок шлем «сигналы» на все проходимые соседние клетки. С каждой из них тоже шлем «сигнал» на соседние клетки, которые еще были затронуты ранее. Повторяем до тех пор, пока еще есть куда слать «сигнал». Далее проверяем, что хотя бы одна проходная клетка возле каждой стены доступна. У такого подхода есть один изъян — в теории, любая стена может быть заставлена O или #. В таком случае мы всегда будем в тупике. На практике же мне такой лабиринт не попадался. Теперь при каждом ходе проверялось, не окажемся ли мы в тупике после него. Если это так, то текущая цель переносилась в список целей с низким приоритетом и выбиралась новая.

В какой-то момент я понял, что вполне допустимо использовать алгоритм Ли для поиска путей до всех бриллиантов на карте. Речь идет о времени выполнения. В таком случае бот начал куда лучше выбирать ближайшую цель.

В игре можно было задавать произвольный размер лабиринта, но в «боевых» условиях использовалось поле размером 40х22. Чтоб не прерывался hot streak надо собирать бриллианты с интервалом не более 2 секунд. Это соответствует 20 ходам (в лучшем случае). Вообще, отведенных двух минут на каждую карту хватает с головой. Даже не очень качественный бот соберет все доступны бриллианты секунд за 40 максимум. Остальное время каждый в праве использовать так, как посчитает нужным. Я решил, что неплохо бы немного «подготовить» карту перед началом сбора. По вертикали лабиринт делится на две части. За первых 20 секунд бот старается сбросить бриллианты из верхней части в нижнюю. Бриллиант может упасть, если под ним пустота, а может соскользнуть вбок, если под ним стена, другой бриллиант или камень (при этом клетки сбоку должны быть пустыми). Чтоб добиться таких ситуаций мы можем убирать мешающие «куски земли» (:). В итоге первых 20 секунд игры бот ведет себя с ними так, как ведет себя с бриллиантами все остальное время.

И вот вроде бы уже и решение более-менее рабочее появилось, но бабочки по-прежнему были камнем преткновения. Их поведение нельзя предсказать только на основе текущего состояния карты. Надо еще знать предыдущее направление движения. Это можно сделать держа в памяти несколько предыдущих «экранов». А ведь можно держать в памяти и весь лабиринт со всеми объектами. В момент, когда ко мне пришла эта мысль, я решил переписать бота практически с нуля. У нас есть исходный код самой игры. А в нем уже есть классы для всех объектов лабиринта и самого лабиринта. А еще там есть функция, которая из отрисованного лабиринта генерирует его «программный» вариант. Никто не запрещает нам взять весь этот код и добавить его в бота. Теперь, в самом начале игры, внутри бота создается копия лабиринта, в которой проверяется возможность разных ходов. То есть, уже не надо «вручную» моделировать различные ситуации вокруг игрока. Достаточно сделать ход в нашей копии лабиринта, обновить его и посмотреть, что же произошло с игроком. Нас интересуют следующие ситуации:

  • Ход вообще возможен. Это актуально для ситуаций вида «ход влево, слева сверху O, а слева пустое поле». В таких случаях ход сделать не получится. Игра выполняет пересчет лабиринта построчно сверху вниз. Это значит, что блок O упадет раньше, чем выполнится ход игрока.
  • Игрок жив и легитимный. Если после хода игрок погибает, то это явно плохой ход.
  • Рядом нет бабочек. От них лучше держаться подальше.
  • Игроку есть куда ходить. Речь не о тупиках, а о ситуациях, когда все возможные следующие ходы либо недоступны, либо приводят к смерти игрока.
  • Игрок не в тупике. Стараемся избегать тупиков до последнего.

Всех ботов, участвующих в конкурсе, можно было разделить на две категори — агрессивные и мирные. Первые стараются сбить бабочек, а вторые — нет. Мой бот был мирным. Если получалось, что бабочки умирали, то хорошо, а если нет — то и не надо. При прокладывании пути к какой-угодно цели бабочки могли вносить определенные трудности. Это касается ситуаций, когда их траектория очень короткая (вплоть до четырех клеток). При попытке обойти такую бабочку бот мог зависать и дергаться между двумя клетками. Пришлось сохранять все ходы бота и каждый раз проверять последних 8. Если бот за эти 8 ходов перемещался только по двум клеткам, то маршрут перестраивался.

Может показаться, что мой бот умеет очень много всего и должен хорошо себя проявить в общем зачете. Но, увы, так не получилось. На то есть несколько причин:

  • Код не всегда работал так, как я того хотел изначально. В ряде ситуаций попытки не попасть в тупик приводили к зависанию бота. Из-за этого я как минимум на 2-х картах получил 0 баллов.
  • Прокладывание маршрута только до ближайшего бриллианта почти никогда не давало оптимальный путь в целом.
  • Время, отведенное на ход, не всегда было равно 100мс. Мой алгоритм оказался очень чувствительным к пропуску хода. Если таковой случался, то лабиринт в памяти бота уже отличался от реального.
  • Мой ноутбук оказался мощнее, чем амазоновские машины, на которых проверялись все решения. Это, опять-таки, привело к пропускам хода.
  • У меня не было никакой «синхронизации» внутреннего лабиринта с оригинальным.
  • ООП и прочие «красивости» кода должны идти лесом, когда встает вопрос производительности. Я просто перенес часть кода из игры в бота. В каждый из скопированных классов был добавлен метод clone, который создавал копию объекта. То есть, при создании копии всего лабиринта, копировались все его внутренние объекты. По-хорошему, можно было создать отдельную сущность типа «состояние лабиринта» и работать только с ней.

Как результат получилось только 42-е место с результатом 1766 балла. Само решение доступно по ссылке Submission. Прогнав своего бота с тем же набором сидов но на своем ноутбуке, получил результат 2951 балл (~25 место).

Выводы сделаны. Расти есть куда. Конкурс очень понравился и хочется еще 🙂

P.S. Все же, в ряде случаев бот показал себя очень достойно.

GIF
GIF
GIF
GIF
GIF

, ,

Оставить комментарий

Top ↑ | Main page | Back