Конкурс по программированию: JSDash

UPDATE: Конкурс завершён. Итоги.

Компания Hola объявляет долгожданный летний конкурс по программированию! Победителей ожидают призы:

1. Первое место: 3000 USD.
2. Второе место: 2000 USD.
3. Третье место: 1000 USD.
4. Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите половину суммы приза (разумеется, не в ущерб награде победителя). За одного победителя такую награду может получить только один человек — тот, кто отправил ссылку первым.

Авторы интересных решений будут приглашены на собеседования.

Правила

Условия конкурса на английском языке размещены на GitHub. Ниже — перевод на русский язык.

• Отправляйте решения с помощью этой формы. По электронной почте решения не принимаются.
• Решения принимаются до 17 августа 2017, 23:59:59 UTC.
• Предварительные результаты будут опубликованы 24 августа 2017, а окончательное объявление победителей — 31 августа 2017.
• Можно отправлять решения многократно, но от каждого участника будет рассмотрено только самое последнее решение, отправленное до окончания срока приёма работ.
• Для тестирования мы будем использовать Node.js v8.1.3 (текущая версия на момент публикации). Можно использовать любые возможности языка, поддерживаемые интерпретатором в стандартной конфигурации.
• Весь код решения должен находиться в единственном файле на JS.
• Решение должно быть на JS. Если Вы предпочитаете CoffeeScript или подобные языки, необходимо оттранслировать решение в JS перед отправкой.
• Если Ваш JS-файл — продукт генерации, минификации и/или компиляции с других языков вроде CoffeeScript, пожалуйста, приложите архив с исходниками, а также, желательно, описанием подхода. Содержимое этого архива будет опубликовано, но мы не будем его тестировать.
• Нельзя загружать никаких модулей, даже тех, что входят в стандартный комплект Node.js.
• Нам нужно знать Ваше полное имя, но если Вы хотите, мы опубликуем вместо него псевдоним. Мы сохраним Ваш адрес электронной почты в тайне.
• Задавайте вопросы по условию задачи в комментариях к этой публикации или по электронной почте.

JSDash

Поиграем в текстовую игру! Несомненно, вы распознаете в ней клон классической видеоигры, впервые изданной в 1984 году.

Ваша цель — написать искусственный интеллект, который играет в эту игру, принимая решения вместо человека. Игра будет проходить в реальном времени, и у вашего скрипта будет столько же времени на принятие решений, сколько у человека.

Мы рекомендуем запустить скрипт game/jsdash.js и сыграть в игру несколько раз перед тем, как читать дальше. (Примечание: мы разрабатывали и тестировали игру под xterm в Linux. В других системах может работать, а может и не работать.)

Игра

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

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

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

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

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

Решения

Решение представляет собой модуль Node.js без зависимостей. Модуль должен экспортировать одну функцию:

play(screen)

Игра загрузит модуль и вызовет функцию play один раз, передав начальное состояние игры в качестве параметра screen. Оно представляет собой массив строк, по одной на каждую строку экрана с верхней до нижней, включая строку состояния. Строки будут содержать в точности то, что вы видите на экране, только без раскраски в ANSI-цвета (игру можно увидеть в таком режиме на консоли, если запустить её с параметром --no-color). Функция play должна быть генератором. Чтобы сделать ход, она должна сгенерировать (yield) значение 'u', 'd', 'r' или 'l' для шага вверх, вниз, вправо или влево соответственно. Ещё можно сгенерировать 'q' или просто завершить работу генератора (return), чтобы окончить игру досрочно (набранные очки при этом не теряются). Если сгенерировать любое другое значение, это означает ход «остаться на месте». Пытаться идти в направлении, в котором двигаться невозможно (например, в стену) не запрещено: персонаж просто останется на месте. После каждого yield содержимое массива screen обновляется, и ваш код может снова его проанализировать для принятия дальнейших решений.

Если ваша функция возбудит исключение, то игра закончится с результатом 0 очков. Это не помешает вашей программе играть и набирать очки на других уровнях.

Ваш скрипт будет запускаться в отдельном процессе. Даже если он зависнет, это не замедлит ход игры (при этом персонаж будет стоять на месте).

Состояние игры обновляется раз в 100 мс. Если функция play будет генерировать команды быстрее, то персонаж будет двигаться 10 раз в секунду. После каждой команды генератор будет блокироваться на инструкции yield до конца рануда длиной в 100 мс. Если функция «думает» над ходом дольше, чем 100 мс, она начинает пропускать ходы, и тогда персонаж будет оставаться на месте в те раунды, когда функция не успела сделать ход. В этом случае генератор также не увидит некоторых промежуточных состояний экрана. Например, если скрипт «задумается» на 250 мс между двумя инструкциями yield, то не увидит двух состояний экрана, а персонаж останется неподвижным на два раунда; таким образом, будут упущены две возможности сделать ход, которые были бы, если бы программа работала быстрее. После этого генератор будет заблокирован на 50 мс до конца раунда, и сгенерированная им команда будет выполнена.

Очень простой пример работающего скрипта искусственного интеллекта приведён в файле game/example.js. Каждый раунд он находит все возможные ходы (направления, в которых по соседству с позицией игрока находятся пустое пространство, земля, камень, который можно сдвинуть, или алмаз) и выбирает один из них случайным образом. Обычно этот скрипт убивается вскоре после начала игры.

Тестирование

Скрипт jsdash.js, который мы предоставляем на GitHub, — это не только интерактивная игра, но и мощный инструмент для тестирования. Запустите его с параметром --help, чтобы узнать обо всех его возможностях.

Каждое присланное нам решение будет запущено по меньшей мере на 20 автоматически сгенерированных уровнях. Участник, чьё решение наберёт наибольшую сумму очков на всех уровнях, будет признан победителем. Мы оставляем за собой право увеличить число уровней (для всех участников), если это потребуется для того, чтобы исключить «ничью» между лидерами; если и это не поможет, победит тот, кто прислал своё решение раньше.

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

jsdash.js --ai=submission.js --log=log.json --seed=N

Тем не менее, мы рекомендуем обратить внимание на весь набор доступных параметров командной строки, которые могут помочь вам в отладке.

По окончанию конкурса будут опубликованы записи игр каждого решения на каждом из тестовых уровней. Эти записи можно воспроизвести такой командой:

jsdash.js --replay=log.json

Тестирование всех решений будет происходить на виртуальном сервере c3.large (см. аппаратные характеристики по ссылке) на Amazon AWS под управлением Ubuntu 14.04 (amd64). Решения будут тестироваться одно за другим при отсутствии прочей нагрузки на машине.

Мы исправляем баги в тестовом скрипте, о которых нам сообщают участники. Следите за обновлениями в файле game/CHANGELOG.md!

Отправка решений

Для отправки решений пользуйтесь формой на нашем сайте. По электронной почте решения не принимаются!

Поскольку код решений часто бывает сгенерированным, минимизированным или оттранслированным с другого языка, форма содержит также поле для отправки архива с исходными тестами. Если код сгенерирован, включите туда генератор; если он минимизирован, включите исходную версию; если код переведён с CoffeeScript или другого языка, включите код на том языке, на котором он написан. Желательно также включить в архив файл README с кратким описанием подхода к решению (по-английски). Архив должен быть в формате tar.gz, tar.bz2 или zip. Содержимое архива будет опубликовано, но не будет протестировано (мы тестируем только JS-файл, который вы отправляете вне архива).

Максимальный размер JS-файла установлен в 64 МиБ. Это произвольно выбранная цифра, которая существует в основном для того, чтобы чьё-нибудь «решение» одномоментно не заполнило нам диск. Если ваше решение правда больше 64 МиБ, напишите нам, и мы увеличим ограничение.

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

Желаем удачи всем участникам!