Конкурс по программированию: 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 МиБ, напишите нам, и мы увеличим ограничение.

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

    Желаем удачи всем участникам!
    Hola 110,34
    Компания
    Поделиться публикацией
    Комментарии 70
      0
      Добрый день, у меня проблема с запуском. В чем дело?

      image
        0
        Какая версия node.js?
          0
          Точно, я забыл, что версия последняя нужна
          0
          Вижу, что я забыл включить проверку версии. Добавил её. Теперь, если скрипт запускают на версии Node.js, отличной от 8.1.3, он выдаёт ошибку (можно обойти проверку параметром --force).
          +1
          «Эх, поучаствовать бы, но жаваскрипт не знаю»… тред стартует здесь! Кто как я — в комментарии.
          Заинтересовавшиеся — отвечайте вопрошающим :)



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

          Имеющиеся навыки: С# (Unity3D: 2 мини-игры, 1 AR через недокументированные возможности), PHP (работающий сайт на своём фреймворке на одной функции, без ООП, NoSQL, пре-рендер HTML). Js знаю на уровне «ctrl-ins», «shift-ins».
            0
            Состояние игры обновляется раз в 100 мс. Если функция play будет генерировать команды быстрее, то персонаж будет двигаться 10 раз в секунду. После каждой команды генератор будет блокироваться на инструкции yield до конца рануда длиной в 100 мс.

            Совсем не понятно сколько это реально вычислительной мощности дает "типа c3.large на Amazon AWS " — это сильная машина, или слабая? Как вообще такое оценить?

              0
              Это вполне конкретная аппаратура, смотрите спецификацию по ссылке. Собственно, Вы можете арендовать у Amazon такой сервер на час, чтобы потестировать своё решение.
                0
                Это вполне конкретная аппаратура
                Да я понимаю — но я совсем не знаком с тем насколько виртуализация жрет производительность.
                Вариант с арендой походе единственное решение
                  +1
                  Новый пользователь AWS может получить некоторое количество вычислительных ресурсов бесплатно. Для тестирования решения этой задачи хватит.
                  https://aws.amazon.com/ru/free/
                    +1
                    Пишут:
                    CPU — Intel Xeon E5-2680 v2, на vds доступно 2 ядра по 2,8 Ггц
                    RAM — 3,75 Гб
                    HDD — SSD 2x16 Гб, но винт тут вроде не пригодится в решении задачи
                      0
                      На самом деле вашему процессу доступно одно ядро (но их два, так что контролирующий процесс будет, скорее всего, на другом), 2 ГБ кучи (настройки Node.js по умолчанию) и никакого доступа к диску. Это всё следует из опубликованных условий тестирования.
                        +1
                        Спасибо за уточнения насчёт оперативки, и про одноядерность обработки скрипта тоже может быть полезным для остальных читателей комментарий.

                        Важный вопрос, есть ли оценки сколько миллисекунд из умолчальных 100 мс на фрейм будет доступно скрипту для «подумать»? Было б очень неприятно, если контролирующий процесс, он же сам движок игры с обёртками, тут бы как-то заметно мешал.
                          0
                          Все скрипты на Node.js — одноядерные. Задействовать более одного ядра можно было бы только с использованием системных модулей, которые условия конкурса включать запрещают.

                          Я таких измерений не делал. Кто-то говорил, что на первом ходу доступно 70 мс, а на последующих — больше.
                            +1
                            Ещё такой вопрос, допускает ли генератор уровней ситуацию, когда игрок ставится в изначально опасное положение, с которого он если не уйдёт немедленно, то погибнет? Посмотрел полсотни уровней, подобного не встретил.
                              0
                              См. исходный текст функции is_playable в файле game/generate.js. Если случайно сгненерированная карта не удовлетворяет этому предикату, она отбраковывается, и генерируется новая.
                    +1

                    А не планируете запустить онлайн сервер с таблицой лидеров? (А чтоб избежать нагрузки скажем запускать новое отправленное решение не раньше чем через 20 минут)


                    Сразу двух зайцев (и девы поймут производительность своего кода, и можно будет увидеть насколько далеко к лидерам)

                      +1
                      Такая возможность обсуждалась, но на этот раз решили не делать, так как это увеличивает трудоёмкость организации конкурса, причём во многом из-за сложности безопасного запуска кода, которому мы не доверяем, на наших серверах в автоматическом режиме.
                        +2
                        Простите за вмешательство в тред, но на самом деле это важная тема — соревновательный аспект. Сейчас по сути предлагается соревноваться с самим собой, и лишь через месяц можно будет узнать своё место в результатах.
                        Мотивация в случае понимания достижений остальных участников явно повышается
                        Может быть, стоит принимать решения в публичном пространстве, в виде github-repo? Приоритет тут бесспорен, то есть проблем с кражей решения нет. Зато появляется плюс в виде соревнования.
                          0

                          Решается публикацией в комментариях результатов для какого-то одного фиксированного рандом сида.

                            +3

                            Сразу предлагаю идеальный набор рандом сидов: 42, 31415926, 2719281929

                              +2
                              Для сида 31415926 у меня пока как-то так
                                0
                                Недурно. Даже подозреваю, что знаю, как работает :)))
                                  +3
                                  У меня в некоторых местах используется рандом, поэтому результаты нестабильны, но при небольшом везении получается так (406 очков; кажется, теоретически можно и чуть больше).
                                  Гифка 2.4 Мб


                                  В общем, есть ощущение, что решения победителей будут соревноваться не на уровне «кто больше алмазов соберёт», а «у кого хитрее комбо получается делать».
                                    +1
                                    Профессиональный убийца бабочек =)
                                      0

                                      Да уж… я и говорю — маленький экран). Классная работа. А рандом, видимо, используется для выбора бабочки?

                                        0
                                        В том числе.
                                        0
                                        Охренеть, апплодирую стоя. Мой бот убежать от бабочек не всегда способен, а ваш за ними охотится
                                          0
                                          У нас тут с коллегами на перекуре возникла идея поместить на одно поле двух ботов, и чтобы каждому из них другой виделся как бабочка. При соприкосновении оба взрываются. Можно попытаться убить другого камнем.

                                          Но это надо было бы менять условия конкурса. Просто забавная мысль.
                                            0
                                            Присылайте своё решение, даже если собираетесь его ещё улучшать. Проведём предварительное тестирование.
                                          +1
                                          Присылайте своё решение, даже если собираетесь его ещё улучшать. Проведём предварительное тестирование. Не live leaderbord, но компромисс.
                                            0
                                            А когда предварительное будет? В плане до какого числа прислать чтобы попасть
                                              +1
                                              Когда будет что тестировать. Пока только два решения прислали. Можно было бы сделать два раунда — 10 и 20 числа. В общем, зависит от активности участников.
                                                +1
                                                Уже два решения есть? Ого. А таблица рекордов будет?) Надежды выиграть особо нет, но интересно хоть глянуть на сколько смогу подобраться
                                            0
                                            У меня не так круто как у deNULL, но, впринципе, это довольно удачный сид

                                            Сид 31415926, гифка 800кб
                                            image
                                            0
                                            А вот, до кучи, с сидом 2719281929
                                              +1
                                              Здесь н етак шоколадно :)
                                                0
                                                Для этого же сида

                                                Гифка на пол метра
                                                image
                                                  0
                                                  Как по мне куда более ефективней будет охотиться за бабочками с самого начала. Потом можна нагенерить кучу hot steak'ow.
                                                    0
                                                    Мой пез… кхм… бот, пока что не умеет охотится на бабочек. Его убийства — не осознанные, он не ведает что творит :( Его поглотила бриллиантовая лихорадка
                                            +1
                                            В этот раз мы сняли запрет на публикацию своих решений до конца конкурса. Поэтому участники теперь могут самоорганизовываться для тестирования.
                                            +1
                                            Может, сделать промежуточный lightning-round? Т.е. однократно опубликовать результаты присланные на момент, например, 15 июля, а потом уже последние
                                              0
                                              Подумаем.
                                                +1
                                                Да, сделаем. Присылайте решения, даже если ещё будете их улучшать.
                                        0

                                        "Решения принимаются до 31 июля 2017, 23:59:59 UTC."
                                        Тут "до" это ")" или "]"?

                                          +2
                                          const deadline = new Date('2017-08-01 UTC');
                                          let now = new Date();
                                          if (now>=deadline)
                                              // reject submission
                                          


                                          Тут ещё можно спросить, по началу или концу аплоада смотрим. По концу.
                                          +4
                                          Воркеры это хорошо, конечно, но из-за них отлаживать код даже с опцией --unsafe как-то очень мучительно.

                                          Я сделал версию, которая запускает решение «совсем небезопасным» образом (например, ограничения по времени не проверяются — если решение зависнет, то зависнет всё вместе). Зато дебажить стало гораздо проще.

                                          Возможно, участникам конкурса пригодится: https://github.com/deNULL/challenge_jsdash.
                                          Запускать с опцией --no-workers (или -w).
                                            0
                                            Пользуясь случаем, хочу сказать, что Ваша среда разработки для DCPU-16 была самой лучшей и «устанавливала планку».
                                              +1
                                              Спасибо! В несколько изменённом виде добавил такую возможность (флаг --in-process).
                                              0
                                              Для тех кто впервые ставит node на win (как я) для решения вот таких вот проблем:
                                              Error: Cannot find module 'ANY_NAME'

                                              в cmd
                                              npm install ANY_NAME
                                                +1
                                                Собственно, совет для всех ОС: установить требуемые скрипту модули согласно файлу `package.json` позволяет команда `npm install` без имён пакетов.

                                                Ну и как, работает под Windows? Мне интересно. Ввод-вывод, вообще, рассчитан на xterm.
                                                  0
                                                  Неплохо, кстати.
                                                    0
                                                    Работает. Хотя немного прыгает
                                                      +1
                                                      Прекрасно работает и под Win7 x64. Там у ноды вполне себе нормальная консоль, видимо поддерживающая xterm. Не прыгает, всё плавно отрисовывается.
                                                    0
                                                    на 20 автоматически сгенерированных уровнях

                                                    Интересно, а размеры экранов всегда одинаковы(как в примере) или могут произвольно меняться при тестировании?

                                                      0

                                                      вообще нашел настройку — похоже они могут быть произвольного размера))

                                                        0
                                                        При запуске ваших решений мы будем использовать настройки по умолчанию
                                                        0
                                                        А можно ли узнать подробнее о механике скатываний камней и алмазов? Не понятно по каком принципу они решают покатиться им влево-вправо, или просто упасть вниз.
                                                          +2
                                                          Механика скатывания скопирована с исторического оригинала Boulder Dash. Смотрите код класса LooseThing. Объекты предпочитают падать, нежели скатываться, и скатываться влево, нежели вправо.
                                                            0
                                                            Да, я уже посмотрел, спасибо)
                                                          0
                                                          Если вас интересуют подробности игровой механики, читайте исходный код модуля game.js.
                                                            0
                                                            vlreshet ^. Сори, давно не пользовался хабром :)
                                                            0
                                                            По поводу реф. ссылок. А если я не пользуюсь почтой чтобы делиться таким (только мессенджерами по сути), ничего в зачет не пойдет? (просто интересно, потому что сомневаюсь что много людей используют почту для таких целей)
                                                              0
                                                              Вы можете сообщить человеку и почтой, и другим способом. Нам нужно документальное подтверждение отправки ссылки как основание для выдачи реферальной премии.
                                                              0
                                                              При тестировании каждого решения будет использоваться один и тот же набор затравочных значений (seeds) для генератора псевдослучайных чисел, чтобы программы всех участников получали одни и те же уровни. При запуске ваших решений мы будем использовать настройки по умолчанию

                                                              feldgendler, приветствую, и такой вопрос. При тестировании сколько раз прогоняется один и тот же сид? Ведь игрок появляется в разных местах рандомно, а значит идеально достижимый счёт в каждом из запусков будет разным. Если 1 раз или «мало» раз, то при тестировании каждому из игроков могут попасться одному стартовые позиции лучше, а другому позиции хуже, и результат замера будет недостаточно стабилен и пригоден для сравнения возможностей алгоритмов.

                                                              Может быть, стоит ещё добавить дополнительную опцию сида для постановки игрока? Чтобы условия были равные просто-таки абсолютно.

                                                              При конкурсных замерах для каждой из тестируемых карт можно брать несколько таких «player-start-seed». Или же брать один конкретный и публиковать его в таблице результатов — например, это может помочь тем участникам, у которых происходит крэш, ведь его сложно ловить с рандомом.
                                                                +1
                                                                Всмысле рандомно? На одинаковом сиде — и начальное положение игрока, вроде, одинаковое… Только что 6 раз запустил на одном сиде — всё идентично
                                                                  0
                                                                  Место появления игрока — часть уровня. Для одного и того же значения seed оно всякий раз будет одинаковым.
                                                                    +1
                                                                    Блин, тогда сорри, видимо меня поглючило.

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

                                                                    И ещё, Алексей, подскажите будет ли второй промежуточный прогон решений и когда? Выше в комментариях было предложение про 25.07, и «посмотрим по мере поступления» — есть ли какая-то определённость сейчас?
                                                                      0
                                                                      На каждом уровне каждое решение будет запускаться по одному разу. Использовать random мы не рекомендуем (и не видим в этом особого смысла).

                                                                      Да, скоро будут вторые промежуточные результаты.
                                                                        +1
                                                                        Интересно, каковы выходят предварительные результаты конкурса, кто оказывается героями комбинаторики и интеллекта в этом соревновании.
                                                                  0
                                                                  deleted

                                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                  Самое читаемое