20.06.2018 16:36
feldgendler 95 14400 Источник
Компания Hola вновь объявляет конкурс по программированию! Победителей ожидают призы:

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

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



Правила


Условия конкурса на английском языке размещены на GitHub. Ниже — перевод на русский язык.
  • Отправляйте решения с помощью этой формы. По электронной почте решения не принимаются.
  • Решения принимаются до 20 июля 2018, 23:59:59 UTC.
  • Предварительные результаты будут опубликованы 27 июля 2018, а окончательное объявление победителей — 3 августа 2018.
  • Можно отправлять решения многократно, но от каждого участника будет рассмотрено только самое последнее решение, отправленное до окончания срока приёма работ.
  • Для тестирования мы будем использовать Node.js v10.4.1 (текущая версия на момент публикации). Можно использовать любые возможности языка, поддерживаемые интерпретатором в стандартной конфигурации.
  • Весь код решения должен находиться в единственном файле на JS.
  • Решение должно быть на JS. Если Вы предпочитаете CoffeeScript или подобные языки, необходимо оттранслировать решение в JS перед отправкой.
  • Если Ваш JS-файл — продукт генерации, минификации и/или компиляции с других языков вроде CoffeeScript, пожалуйста, приложите архив с исходниками, а также, желательно, описанием подхода. Содержимое этого архива будет опубликовано, но мы не будем его тестировать.
  • Нельзя загружать никаких модулей, даже тех, что входят в стандартный комплект Node.js.
  • Один участник может использовать для отправки решения только один адрес электронной почты. Отправка множества решений, находящихся в «сговоре», с разных адресов запрещена; все решения, участвующие в такой схеме, будут дисквалифицированы.
  • Нам нужно знать Ваше полное имя, но если Вы хотите, мы опубликуем вместо него псевдоним. Мы сохраним Ваш адрес электронной почты в тайне.
  • Нынешние и бывшие сотрудники Hola и их ближайшие родственники могут принимать участие лишь вне конкурса, не претендуя на призы.
  • Задавайте вопросы по условию задачи в комментариях к этой публикации или по электронной почте.

Торговля


Допустим, у нас есть книга, две шляпы и три мяча. Вы и ещё один участник должны решить, как разделить это добро между вами двоими. Для вас книга имеет ценность $4, каждый мяч — $2, а шляпы ценности не имеют. Для партнёра эти же объекты могут иметь другую ценность, но вам известно, что все объекты вместе для него ценны настолько же, насколько и для вас — в данном случае это $10.

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

Вот пример того, как могут пройти переговоры:

  1. Вы: Я хочу книгу и два мяча; ты получишь один мяч и обе шляпы.
  2. Партнёр: Не согласен. Я хочу все мячи и одну шляпу; ты получишь книгу и одну шляпу.
  3. Вы: Не согласен. Я хочу книгу и один мяч; ты получишь два мяча и обе шляпы.
  4. Партнёр: Согласен.

Вам это не было известно, но для партнёра ценность предметов была такой: по $2 за мяч, по $2 за шляпу, книга не имеет ценности. Соглашение принесло $6 вам и $8 партнёру.

В общем случае есть два или более типов объектов и целое положительное число объектов каждого типа. Ценность каждого типа объектов для каждого из партнёров — целое неотрицательное число. Суммарная ценность всех объектов для обоих партнёров одинакова, хотя ценности отдельных предметов разнятся. Предложение о разделе должно распределять между партнёрами все объекты без остатка; отдельные объекты не дробятся.

Ваша задача — написать скрипт, стремящийся заключить сделку с максимально возможной ценностью (для себя).

Решения


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

module.exports = class {
    constructor(me, counts, values, max_rounds, log){
        ..
    }
    offer(o){
        ...
    }
}

Экземпляр этого класса будет создан один раз и использован в течение сеанса переговоров. Конструктору передаются следующие аргументы:

  • me — 0, если ваша очередь первая, или 1, если вторая.
  • counts — массив целых чисел, содержащий количество объектов каждого типа. Он содержит от 2 до 10 элементов.
  • values — массив целых чисел такой же длины, что и counts, описывающий ценность объекта каждого из типов для вас.
  • max_rounds — число раундов переговоров (каждый раунд состоит из двух реплик).
  • log — функция, которую можно вызывать для отладочного вывода (console.log работать не будет).

Метод offer вызывается каждый раз, когда наступает ваша очередь. Его аргумент o — это массив целых чисел такой же длины, как counts. Аргумент описывает, сколько объектов каждого из типов вам предлагает партнёр. Если ваша очередь первая, и это самый первый раунд, то o равно undefined.

Метод offer должен вернуть undefined, если вы принимаете предложение (кроме случая, когда o равно undefined). В противном случае он должен вернуть массив целых чисел такой же длины, как counts, описывающий, сколько объектов каждого типа вы хотите оставить себе. Обратите внимание, что и аргумент o, и возвращаемое значение offer описывают раздел предметов с вашей точки зрения.

Время работы скрипта ограничивается 1 секундой на ход. Если время истекает, или же скрипт возбуждает исключение или возвращает недопустимое значение, считается, что участник прервал переговоры, и ни один из партнёров не получает ничего.

Окружение, в котором запускается скрипт, не предоставляет возможности накопления информации между сеансами.

В файле example.js приведён простой пример скрипта, удовлетворяющего правилам. Он принимает любое предложение, по которому ему отходит не менее половины суммарной ценности всех объектов; в противном случае он просто требует для себя все объекты, имеющие ненулевую ценность. Скрипт также демонстрирует применение функции log.

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


Скрипт haggle.js позволяет организовать переговоры между двумя участниками-людьми, между человеком и скриптом или между двумя скриптами. Запустите его с параметром --help, чтобы узнать обо всех его возможностях. (Чтобы установить все необходимые модули, запустите npm install в директории src.)

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

Для окончательного тестирования мы будем использовать параметры тестовой системы по умолчанию: 3 типа объектов, в сумме до 6 объектов, суммарная ценность всех объектов для каждого из партнёров $10, лимит в 5 раундов. Мы рекомендуем писать решения так, чтобы они поддерживали любую комбинацию параметров, которую поддерживает тестовая система.

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

Мы исправлем баги в тестовой системе, о которых нам сообщают участники; следите за обновлениями (история). Сообщая о багах, передавайте нам, пожалуйста, протокол сеанса переговоров (его можно записать с помощью опции --log).

Переговоры онлайн


Мы предоставляем сервер, который позволяет вашему скрипту вести переговоры с другими участниками. Он устроен наподобие серверов онлайн-игр: можно подключиться к «арене», и сервер организует сеанс между вами и другим участником.

Изначально мы создали одну арену с настройками по умолчанию (3 типа объектов, в сумме до 6 объектов, суммарная ценность всех объектов для каждого из партнёров $10, лимит в 5 раундов). Эта арена не контролирует предел времени в 1 секунду, чтобы дать возможность и людям участвовать вручную. Вот адрес арены:

wss://hola.org/challenges/haggling/arena/standard

Используйте haggle.js, чтобы подключаться к серверу как участник-человек или же со своим скриптом. В этом режиме нужно также передавать параметр командной строки --id: это уникальный идентификатор, по которому система будет отслеживать успехи вашего скрипта. Мы рекомендуем использовать в качестве идентификатора ваш адрес электронной почты плюс случайную строку. Мы не будем публиковать идентификаторы. Позже мы запустим «живую» таблицу лучших результатов, где будут приведены средние исходы сделок и хэши идентификаторов.

Сервер и таблица лучших — к вашему сведению и для развлечения. Очки в таблице никак не повлияют на результаты конкурса, а пользование сервером для участия не обязательно. Однако онлайн-переговоры могут не только позволить неформально сравнить своё решение с другими, но и предоставить вам ценную информацию о стратегиях других участников.

Если ваш скрипт работает, мы рекомендуем, чтобы он постоянно участвовал в онлайн-сеансах, например, с помощью такой команды UNIX shell:

while true; do node haggle.js --id me@example.com:1234abcd myscript.js wss://hola.org/challenges/haggling/arena/standard; done


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


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

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

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

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

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

Комментарии (95)


  1. vermilion1
    20.06.2018 20:21
    #18798485
    +1

    Наконец-то новое задание :)


  1. TiesP
    20.06.2018 22:20
    #18798771
    +2

    Как всегда, что-то необычное


    анекдот в тему

    -Прибыль будем делить 50 на 50
    -Яков Моисеевич, я хотел бы 70 процентов
    -Хорошо, давай 70 на 70


    1. feldgendler Автор
      21.06.2018 01:16
      #18799075

      Именно так. Хотя каждый может выиграть до $10, это не означает, что оба не могут выиграть по $7.


    1. Dreyk
      21.06.2018 12:21
      #18800193
      +1

      и другой анекдот в тему

      -Пятачок, там нам пчелы меду прислали. 10 горшков. По 8 каждому получается
      -Но Винни, 10 на двоих — это же по 5
      -Не знаю, может и по 5, но свои 8 я уже съел


      1. Zagrebelion
        21.06.2018 12:31
        #18800233

        всё верно, 0x10 горшков на двоих — как раз по восемь.


        1. mwizard
          22.06.2018 03:13
          #18803615

          9600 бод и все-все-все…


  1. u1d
    20.06.2018 23:51
    #18798961

    max_rounds — это наибольшее количество вызовов метода offer, верно? Если max_rounds == 1, me == 1, то offer уже не может ничего предложить, только принимать условия полученного предложения? Если в этом случае offer вернет не undefined (не согласен), то оба контрагента получат по 0?
    Полагаю, в описание следует добавить уточнение про конец игры при достижении лимита раундов.


    1. feldgendler Автор
      21.06.2018 01:17
      #18799077

      Верно. Так и сказано:

      Если же соглашение не достигнуто, то есть последнее слово в последнем раунде — встречное предложение, а не согласие, — то никто не получает ничего.


  1. acupofspirt
    21.06.2018 09:18
    #18799507

    Позже мы запустим «живую» таблицу лучших результатов, где будут приведены средние исходы сделок и хэши идентификаторов.

    MD5?


    1. feldgendler Автор
      21.06.2018 12:02
      #18800103

      Да. Добавил в скрипт вывод этого хэша на консоль.


  1. meduzik
    21.06.2018 09:31
    #18799537

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


    2. Критерий победы — сумма очков, набранная по результатам переговоров против всех/большинства остальных присланных решений? Будут ли какие-либо туры с выбыванием, или все финальное тестирование проводится в один этап?


    3. Будут ли откровенно "плохие" решения сниматься с участия в финальном тестировании?


    4. Если все работает так, как я думаю, что помешает мне отправить "решения" от имени выдуманных людей (попросить друзей, хм), против алгоритмов которых мое решение умеет торговаться оптимальным образом, а другие игроки, разумеется, с ними не знакомы, и таким образом увеличить собственный результат на финальном тестировании?



    1. ainu
      21.06.2018 10:02
      #18799615

      Другие игроки могут "спалить" необычное поведение, пообщавшись по api через haggle.js. Это теория игр в чистом виде:)


      1. meduzik
        21.06.2018 10:26
        #18799709

        А разве я не могу отправить фейковые решения на проверку в последний момент времени и нигде не светить их раньше?


    1. feldgendler Автор
      21.06.2018 12:07
      #18800123

      1. Да.
      2. «Мы надеемся, что сможем провести не менее двух сеансов для каждой возможной пары, однако, если решений окажется слишком много, то нам, возможно, придётся выбрать другую систему проведения чемпионата. О конкретной системе будет объявлено позже».
      3. Только если мы обнаружим попытку взлома тестовой системы или какое-то другое жульничество.
      4. Вам придётся ещё и как-то распознавать «своих» партнёров. Ну и если мы поймём (статистическим анализом), что вы вытворяете что-то такое, а потом почитаем исходники, и подозрения подтвердятся, то дисквалифицируем все решения, участвовавшие в схеме.


      1. Aniro
        21.06.2018 15:33
        #18801495
        +1

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


        1. Aniro
          21.06.2018 15:44
          #18801581

          Четвертый пункт имелся в виду, прошу прощения.


          1. feldgendler Автор
            21.06.2018 16:55
            #18802021

            Написал.


  1. Shedar
    21.06.2018 09:55
    #18799591

    Время на ход ограничено 1 секундой, а есть ли ограничение на время работы конструктора?


    1. u1d
      21.06.2018 10:26
      #18799705

      Ага, и какое ограничение по памяти? Известно ли какие будут максимальные суммы values * counts?


      1. feldgendler Автор
        21.06.2018 12:14
        #18800159

        Ваш скрипт будет запускаться в Node.js с параметрами по умолчанию, отсюда и размер кучи около 2 ГБ.

        «Суммарная ценность всех объектов для каждого из партнёров $10».


    1. feldgendler Автор
      21.06.2018 12:12
      #18800147

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


  1. Mitch
    21.06.2018 16:00
    #18801671
    +2

    В текущем виде задания, очевидной стратегией будет использовать «подсадных ботов».
    Их задача не выиграть, а улучшить очки «своего игрока», которого они должны суметь отличить по первым 4м раундам торговли и отдать ему все предметы, а со всеми чужими ботами сыграть в отказ, чтобы ухудшить их стату.
    Также, чтобы избежать анализа «алгоритма определения свой-чужой» со стороны конкурентов, своих подсадных ботов надо заливать в последний момент, и сразу кучу, но тут всплывет нюанс, что и сервак может лечь как под ддосом.

    Чтобы сделать эту стратегию не эффективной нужно сделать цену 1го бота ненулевой, например просить к заданию прилагать 1$.
    Или просить уникальный скан паспорта или еще какую идентефикацию.


    1. feldgendler Автор
      21.06.2018 16:56
      #18802031
      +2

      Вы же понимаете, что, если вы таким способом займёте призовое место, то мы прочитаем исходник вашего решения. Если увидим такую схему, то дисквалифицируем все решения, участвовавшие в ней. Короче, запрещено. Добавил в правила такое уточнение, а то не всем это очевидно.


      1. Suntechnic
        21.06.2018 17:36
        #18802275
        +1

        А исходник решения может не содержать «ответа», по крайней мере очивидного. Весь функционал распознавания и слива может быть сосредоточен в подставных ботах, которые проиграют и их анализировать никто не будет.
        Примерная схема такая — мой бот играет честно, по достаточно средненькой стратегии, но угадываемой по патернам. Мои подставные боты имеют ту же самую стратегию чтобы уметь востанавливать патерн и играют «почти» по ней (почти чтобы они не спутали друг-друга с главным ботом), но угадав главного бота в последнем раунде сливают ему «почти» всё (почти чтобы хуже детектится статистикой).
        В этом случае против чужих ботов наши боты (и сливщики, и главный бот) будут играть вполне средненько, а в отношении друг-друга так как нужно нам.
        В итоге проигравшие боты играли чуть ниже среднего — они никому не интересны и их много для анализа. Выигравший бот играл абсолютно честно. Он даже не знал что ему поддавались — там нечего анализировать.
        Бороться с этим можно как мне кажется только одним способом — проводить по несколько круговых турниров и по их результатам отсеевать половину худших, а половину лучших брать в следующую серию круговых турниров, и учитывать внутри серий только результаты достигнутые внутри них.
        В таком случае мне придется написать несолько ботов, которые должны будут не просто сливать все главному, но при этом еще и играть лучше остальных чтобы постоянно оставаться в строю и не быть отсеяными.
        В идеальном варианте в последней серии турниров должны остаться только мои боты. Но тогда тот из них который играет наихудшим образом может победить даже без участия остальных моих ботов. Следовательно мне уже не надо писать никаких ботов, кроме одного самого простого.
        Как-то так.


        1. feldgendler Автор
          21.06.2018 17:39
          #18802301

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


          1. Suntechnic
            21.06.2018 17:41
            #18802321
            +2

            Именно моих — нет. Я тоже пока не буду рассказывать как имеенно они будут прятаться, пусть это будет сюрпризом )))


            1. zBit
              22.06.2018 11:54
              #18804655

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


              1. feldgendler Автор
                22.06.2018 11:57
                #18804681

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


        1. Nomad1
          21.06.2018 18:26
          #18802509

          На самом деле не обязательно даже, чтобы боты поддавались кому-то.
          В игре есть всего три варианта действий противника:
          — Рандом (слишком сложный для анализа алгоритм, обучение нейросети, неверно работающий алгоритм, ГСЧ и т.д.)
          — Расчет (калькуляция по какому-то алгоритму)
          — Блеф (заранее невыгодный вариант, чтобы сбить с толку анализатор)

          Подавляющее большинство «адекватных» программ будет делать расчет. Некоторое количество программ будет делать рандом, несколько уникальных будет делать блеф. Для удобства скажем, что это соотношение 80/15/5. Предположим, что какой-то супер-алгоритм дает шансы 75/50/30, что делает его лучшим среди расчетных, равным с рандомными вариантами и слабее не-анализируемого по своей сути блефа. Достаточно полусотни блефующих и рандомных программ, чтобы все честные алгоритмы потеряли баллы и стали «середнячками», просто потому, что мы сместили фокус соревнования с битвы алгоритмов. Да что говорить, одним этим сообщением я уже смещаю фокус игры, потому что читающие спросят себя «а что такое блеф и как от него защититься?»


          1. Suntechnic
            21.06.2018 18:41
            #18802551

            Идею блефа я уже обдумывал… Как защититься? Да никак — слишком мало раундов. Их достаточно чтобы попытатья раскусить расчет, но мало чтобы раскусить блеф (ну если он не очевидный — первым ходом предлагать худшую для себя комбинацию, вторым и третьим лучшую и вторую с конца). Поэтому я сразу отбросил идею раскусить блеф — мне думается что стратегию нужно строить либо на идеи «все блефуют» (тогда вообще лучше отказаться от анализа), либо на идеи «все играют честно».


            1. Nomad1
              21.06.2018 18:46
              #18802555

              Вот я и говорю, что злоумышленник может сместить суть конкурса с «все играют честно» на «все блефуют» или наоборот. Или вообще добавить столько рандома, что победит рандом :)


              1. Suntechnic
                21.06.2018 18:55
                #18802585

                Быть лучше рандома по видимому достаточно легко.


      1. Mitch
        21.06.2018 23:46
        #18803367

        Нет, это не было очевидным, до вашего ответа.
        Откуда мне знать, чего вы добиваетесь этим конкурсом и какие скилы вам интересно выявить у претендентов на работу.

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

        А самому просто выкатить тупой алгоритм, типа:
        — просим ценные нужные предметы
        (отказываемся от любых встречных предложений)
        — просим мешьше на 1 самый менее ценный
        (отказываемся от любых встречных предложений)
        — просим еще меньше на 1 самый менее ценный
        (отказываемся от любых встречных предложений)
        …
        соглашаемся на любое предпоследнее предложение
        — Вообще, в вашей задаче — нет идеального решения.
        Тк под каждое поле алгоритмов — будет своя наилучшая (эксплутационная) стратегия.
        Значит победит тот, кто лучше сможет оценить поле (угадать?), какие стратегии доминируют в момент перед закрытием приема заявок.

        Или вы ищите тех кто просто равновесие по нэшу сможет найти? (к этой мысли подталкивает то что вы позволяете улучшать разработчикам алгоритмы но в тесте финальном участвует только самый последний).
        Ну так в подобных играх нэш является лучшей стратегией только если все поле играет по нэшу и некого эксплотировать.

        Если думать так глубоко, то надо собирать пул алгоритмов вкинутых в поле и писать анализатор этих алгоритмов, задача которого сгененировать оптимальный под текущее поле эксплутационный алгоритм и вкинуть его прямо перед закрытием приема заявок.
        Такое решение мне правда видится слишком сложным, чтоб кто то стал заморачиваться ради 5к$.


        1. feldgendler Автор
          21.06.2018 23:51
          #18803375

          > Ессно под каждого конкурента — свой билд.

          Как это? Ваша программа не знает, с кем играет. Одна и та же версия скрипта встретится со всеми возможными партнёрами.


        1. feldgendler Автор
          22.06.2018 11:41
          #18804605
          +1

          Ещё раз: этот момент вызывает недопонимание. Заливая решение хоть сегодня, вы не сообщаете никакой информации никому кроме, разве что, организаторов. Другие смогут его «пощупать» и получить о нём какую-либо информацию, только если вы запускаете своё решение у себя дома в режиме онлайн-торговли.

          Отправка решения и запуск его в онлайн-режиме — два независимых действия. Можно отправлять и ни разу не запускать онлайн. Можно и наоборот (но тогда шансов на приз не будет). Можно отправлять одну программу, а онлайн запускать другую, или запускать онлайн несколько версий. Весь этот онлайн-сервер — just for fun.


    1. SayLovePlz
      21.06.2018 17:18
      #18802169

      .


    1. haldagan
      21.06.2018 17:26
      #18802219
      +3

      Вы не заглянули чуточку дальше:

      Необязательно плодить ботов (за это вроде как будут банить, правда, не совсем понятно, как).
      Достаточно «всего лишь» постоянно мониторить «рынок» решений 24/7, выделить основные стратегии других игроков и подстраиваться уже под них. Если участников будет достаточно много, то многие из стратегий будут наивными — играть нужно именно на этом.

      Поскольку игроки играют друг против друга, плюс стратегии наиболее рьяных участников конкурса постоянно эволюционируют — не существует «оптимальной стратегии в вакууме». Конкурс выиграет тот, кто максимально оптимизирует стратегию под текущую ситуацию на рынке решений.

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

      Сплошные mind games в общем, а не конкурс.


      1. feldgendler Автор
        21.06.2018 17:33
        #18802263

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


        1. haldagan
          21.06.2018 17:44
          #18802349
          +2

          Я немного про другое:

          Давайте представим, что в вашем конкурсе решили поучаствовать Вася, Коля и 98 тестировщиков.

          Тестировщики просто скопировали и запостили example.js.

          Если я правильно понял условия конкурса (все играют со всеми, в учет идет общаяя сумма выигрыша по каждому из торгов), то
          Вася, собравший статистику и знающий про example.js в выигрыше: он знает, что его выигрыш по 98 сделкам из 99 может быть сколь угодно большим, если он предложит хотя бы пять монет оппоненту (ему даже не нужно соревноваться с Колей, ему просто нужно знать эту статистику).
          Коля, пишущий суперумный алгоритм по оптимизации «сделок», обязательно выиграет у Коли 1х1, но, скорее всего проиграет в конкурсе, т.к. не собирал статистики и не знает, что (в силу ситуации на рынке) нужно не искать компромисс, а давить на «тебе 5, мне сколько выйдет, но побольше».

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


          1. ads83
            22.06.2018 01:43
            #18803535

            А как Вася поймет, где какой бот? Допустим, кроме Коли и Васи есть 48 ботов example.js, 48 all-in.js, который согласен менять только "все за все" и 2 evil.js, которые. За 4 хода Васе надо понять, кто против него, и не отдать слишком много.


            Как Вася узнает, какие у оппонента цены? Он может предложить предметы, которые ему стоили пятерку, но бот-то за них получит десятку! И получит Вася не "сколь угодно большой выигрыш", а случайную цену. И бот с ботом тоже случайно сыграют. Получается рулетка, а не стратегия.
            Написать стратегию, которая будет гарантированно превосходить 98 ботов даже примитивного example.js — нетривиально, если вообще возможно.
            Update: Example.js — это "случайный игрок" из https://ncase.me/trust/. Его победить можно в серии игр, но при определенных условиях


            1. haldagan
              22.06.2018 09:30
              #18804001
              +2

              Поясните пожалуйста поведение ваших example.js и all-in.js на текущем примере.

              ...
              Example js — случайный игрок" из ncase.me/trust


              Что он делает в контексте текущей задачи? Выбирает случайную стратегию и следует ей? Случайно соглашается/отказывается от предложений? Выставляет случайные предложения?

              который согласен менять только «все за все»

              Что подразумевается под «все за все»? Он согласен только менять 10 на 10 или не согласен давать выгоду оппоненту? Или согласен на любой равный исход?


      1. Suntechnic
        21.06.2018 17:40
        #18802307

        Боюсь все так и будет, как и в тот раз когда надо было анализировать статистику словаря. Но я все равно попробую «честное» решение, которое не анализирует чужую стратегию, а играет с широко закрытыми глазами. Интересно же, ну.


      1. Sayonji
        21.06.2018 19:12
        #18802637

        Более того, будет еще второй этап перед дедлайном. Это когда все проанализируют рынок и найдут наивные стратегии, против которых топовые алгоритмы играют неоптимально, а потом, в самом конце, зальют тонны ботов, реализующие эти стратегии. И начинаются еще игры: сейчас надо для анализа заливать проги, которые не палят свои последние ходы, чтобы их нельзя было анализировать другим людям.

        Интересно, а что будут делать организаторы, если быстро придет куча решений, против которых легко победить тупой программой? Например, что если 90% залитых решений будут всё время предлагать противнику 1 самый дешевый предмет и в конце принимать такое предложение, если оно приходило всё время? Тогда они друг против друга будут получать по 5$ в среднем. Против них, когда их ход последний, будет приходить так и так 0-1$, а вот когда ваш ход последний, можно будет либо получить 0, если умничать, либо 9-10$, если реализовать такую же тупую тактику. И конкурс выродится.


        1. feldgendler Автор
          22.06.2018 11:40
          #18804599

          Ещё раз: этот момент вызывает недопонимание. Заливая решение хоть сегодня, вы не сообщаете никакой информации никому кроме, разве что, организаторов. Другие смогут его «пощупать» и получить о нём какую-либо информацию, только если вы запускаете своё решение у себя дома в режиме онлайн-торговли.

          Отправка решения и запуск его в онлайн-режиме — два независимых действия. Можно отправлять и ни разу не запускать онлайн. Можно и наоборот (но тогда шансов на приз не будет). Можно отправлять одну программу, а онлайн запускать другую, или запускать онлайн несколько версий. Весь этот онлайн-сервер — just for fun.


    1. feldgendler Автор
      21.06.2018 19:02
      #18802607

      Кстати, не имеет значения, в последний момент отправлять решение или не в последний. Сама по себе отправка решения ещё не означает участие этого решения в онлайн-сеансах на сервере. В них участвуют только те решения, чьи авторы решили запускать их в онлайн-режиме.


    1. Welran
      22.06.2018 06:59
      #18803747

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


  1. PQR
    21.06.2018 16:41
    #18801943

    А на PHP можно?


    1. feldgendler Автор
      21.06.2018 16:56
      #18802035

      Нет, исключительно JS.


    1. mr_molodoy
      21.06.2018 17:23
      #18802195

      Если Вы транспилируете его в рабочий javascript, то полагаю можно.


  1. BingoBongo
    21.06.2018 18:19
    #18802483

    А не будет такого, что кто первый ходил, тот просто тянет до последнего раунда и делает максимально выгодное для себя предложение, т.е. забирает себе все кроме одной вещи. Тогда у оппонента будет два варианта или получить почти ничего, или вообще нечего, и придется соглашаться на объедки с барского стола. А т.к. сессии независимы, то запомнить «ублюдка» оппоненту не удастся.


    1. vlreshet
      21.06.2018 18:34
      #18802535

      ИМХО, если мы на последнем ходе получаем очень невыгодное для себя предложение — лучше от него отказаться. Так мы, например, не продвинемся в таблице никуда, но и противник тоже. А в противном случае мы поднимемся на совсем чуть-чуть, но противник подскочит повыше. Иными словами — получить копейки нет смысла.


      1. BingoBongo
        21.06.2018 18:47
        #18802559

        Иными словами — получить копейки нет смысла.

        Хехехе, хорошо, что вы так думаете )
        Скрытый текст
        image


      1. riky
        21.06.2018 19:29
        #18802703

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


        1. vlreshet
          22.06.2018 08:48
          #18803883

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


    1. feldgendler Автор
      21.06.2018 18:38
      #18802543

      Даже в вырожденном случае (см. так называемую Ultimatum game) всё не так очевидно.


      1. BingoBongo
        21.06.2018 19:17
        #18802649

        Ну да, пишут, чтобы такой случай был очевидным, надо делить $10 млн реальных денег )


  1. riky
    21.06.2018 19:27
    #18802693

    а стоимости так и будут только целыми числами как на тестовом сервере?


    1. feldgendler Автор
      21.06.2018 19:28
      #18802701

      «Ценность каждого типа объектов для каждого из партнёров — целое неотрицательное число».


  1. SinsI
    21.06.2018 19:37
    #18802727

    Проблема этой «торговли» — целью является не максимизация прибыли, а выигрыш, что возможно и если всем остальным оставить ноль, а себе получить только $1.

    Если существенная доля ботов будет от одного хозяина — то, сговорившись, они могут использовать это для победы своего кандидата, оставив всех остальных ни с чем.


    1. feldgendler Автор
      21.06.2018 19:40
      #18802733

      Правилами такой «сговор» запрещён, все участвующие в нём решения будут дисквалифицированы.


      1. SinsI
        21.06.2018 20:13
        #18802813

        Его ещё надо доказать.
        А ведь самому писать все боты — совершенно необязательно, достаточно просто опубликовать часть своего алгоритма.


    1. vermilion1
      21.06.2018 19:41
      #18802735

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


    1. Welran
      22.06.2018 07:26
      #18803777

      Вопрос в том как вы определите союзника за 5 раундов с неизвестным в начале набором предметов и неизвестной ценностью для соперника во время торговли с кучей ограничений на возможные предложения (нельзя например в качестве теста предлагать все предметы или просто много предметов так как посторонние боты могут просто сразу согласится и закончить торговлю). так что даже если бы этого правила не существовало, задача определения союзника весьма не тривиальна (если вообще возможна).


      1. SinsI
        22.06.2018 07:47
        #18803793

        Так 100% определения не требуется. Достаточно чего-нибудь простого, например предложения в первые 2 раунда числа предметов, делящегося на 3.


  1. FlameStorm
    21.06.2018 20:20
    #18802819
    +2

    Ура, новый конкурс! Хм… О_о… В предыдущем конкурсе было явное соревнование алгоритмов, действующих в мире детерминированных правил.


    Тут же… хм… я конечно понимаю, что все вспомнили, ну или сейчас узнали, про весёлых человечков с шапочками, но они-то хотя бы статистику по каждому сопернику ведут.


    пикча


    1. FlameStorm
      21.06.2018 20:29
      #18802847
      +1

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


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


      1. haldagan
        21.06.2018 22:52
        #18803259

        … исключительно против одного или нескольких ботов организатора...


        Если организатор предоставит возможность поторговать с этими ботами в тестовом режиме — задача сводится все к тому же: собрать статистику и попробовать отреверсить ботов организатора, если нет — задача сведется к «натыкать пальцем в небо».

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

        Организатор устраивает некий «свободный рынок», при этом, когда особо хитрые товарищи спрашивают насчет ботов, организатор заявляет «нет, ну не настолько свободный, такое мы будем отсеивать».

        Я не планирую участвовать в конкурсе, но уже подумываю «попросить друзей» засабмитить 100-500 относительно непредсказуемых стратегий. Четверть — однозначно играющих себе в убыток, четверть — соглашающихся на любой второй-третий-четвертый оффер(случайно), четверть постоянно отказывающих и еще четверть рандомно раздающих офферы (независимо от выгоды).
        В этом случае победителя выберет исключительно рандом, ибо построить оптимальную стратегию на псевдослучайных данных (с шумом в виде реальных соперников) невозможно.

        Мне вот интересно — «моих» игроков орги тоже побанят в таком случае? Они же никому не подыгрывают, хоть и играют не на победу.

        З.Ы.: Подобный саботаж можно устроить и со стратегиями, играющими «на победу». Просто наводнить рынок «средненькими трейдерами», чтобы среди топовых было невозможно выделить однозначно выдающихся.


        1. feldgendler Автор
          21.06.2018 22:54
          #18803271

          Просто слабое решение, которое всем «сливает», в одинаковой степени поможет всем сильным набрать очки.


          1. haldagan
            22.06.2018 08:34
            #18803857

            Слабое решение не обязано всем сливать — оно может, например, соглашаться только на 9+.

            100 таких решений, естественно, потонут, но они помогут выплыть тем, кто при каких-то условиях способен регулярно предлагать оппоненту 10 монет выгоды.

            И, опять же, если вкинуть эти 100 решений заранее, то игроки, ясное дело, приспособятся к наличию такого количества сверхжадных стратегий, но, если сделать это перед самым стартом — результат такого вброса сложно предсказать, т.к. (ИМХО) большинство стратегий будут нацелены именно на компромисс, то есть искать вариант с максимизацией одновременно и своей выгоды и выгоды оппонента.


        1. Suntechnic
          21.06.2018 22:57
          #18803281

          > построить оптимальную стратегию на псевдослучайных данных невозможно.
          Чой-то? Есть даже строгое доказательство, что можно, даже для более жесткого случая.


          1. haldagan
            22.06.2018 08:16
            #18803835

            Извиняюсь, коряво написал. Естественно можно запилить оптимальную стратегию, если заранее известно, что все на рынке — рандом.
            Сложно будет адекватно оценить лучшую стратегию, если все стратегии готовились честно/компромиссно торговать и, внезапно, непосредственно перед стартом «официального турнира» кто-то закинет рандомные стратегии в большом количестве (в разы превышающем честных игроков).
            Единственный вариант — поудалять стратегии, закинутые перед стартом.


            1. Suntechnic
              22.06.2018 10:47
              #18804337

              Не совсем. Дажер резкий рост количества рандома не должен повлиять на результаты торговли — лучшая стратегия без них и с ними на рынке должна оказаться одной и той же. Вряд ли произойдет перестановка.
              Вообще, учитывая малое количество раундов и рандом в ценах, уметь торговать с рандомом должны все.
              Если же удалить «закинутые перед стартом» и объявить об это заранее (а и наче это нечестно), то злоумышленник закинет их чуть раньше старта. Вобщем выйдет классическая задача с неказнимым преступником.


    1. feldgendler Автор
      21.06.2018 22:28
      #18803173

      Всё как в жизни. Бывает, что переговоры приходится вести с партнёром, о котором заранее ничего неизвестно. И что? И ничего. Всё равно стараемся оптимизировать исход.


      1. FlameStorm
        21.06.2018 22:50
        #18803247

        Это в наше-то время, когда зачатки Матрицы под собирательным названием "Биг дата" знают в каком кафе вчера вы были, с кем встречались в городке который и не помните три года назад, куда и когда собираетесь в отпуск, что у вас болит, знают какого цвета бельё у жены и помнит все ваши реплики в соцсетях и мессенджерах и далее далее?


        И тем более, в случае сколь нибудь значимой сделки разве не рассматривается деловая репутация, ваши прошлые сделки, биография и иные параметры прежде чем её совершить? Сложно представить реальную ситуацию, при которой с только что подвернувшимся неизвестным надо тут же заключить сделку с серьёзными лицами, не заглянув и банально в гугл, без юр. проверки документов, безникто.


        О котором (почти*, см.гугл, по городу фио телефону почте отзывы) ничего неизвестно бывает, при встречах из рук в руки по типу авито, но боюсь представить себе экономическую реальность только на таких сделках. :)


        Конкурсная условность понятна, ок.


        1. feldgendler Автор
          21.06.2018 22:53
          #18803263

          Я имею в виду торговлю на базаре, куда вы приехали как турист.


          1. FlameStorm
            21.06.2018 23:01
            #18803287

            Предпочитаю супермаркеты у которых под продуктом чёткий ценник, кассовый аппарат всё такое. А даже если пользуясь рынком, заранее знать что сколько должно стоить и как свежесть проверить, и торговаться более 20 секунд не люблю. Ох, не восточный похоже я человек… )


      1. SinsI
        21.06.2018 23:59
        #18803383

        В жизни у торговых партнёров чаще всего нет стимула сделать так, чтобы ты получил как можно меньше выгоды.
        Тут же скриптам есть смысл торговаться и за совершенно ненужный им хлам даже если им уже предложили товаров на все $10.


    1. Welran
      22.06.2018 07:33
      #18803787

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


      1. FlameStorm
        22.06.2018 09:28
        #18803995

        Не не, там только изначально не было известно ничего каждому о других игроках. Но после старта игры каждый копил индивидуальную статистику по каждому, типа игрок 3 меня обманул в прошлый ход, игрок 5 обманул более одного раза, игрок 2 никогда не обманывал, игрок 6 обманул именно на 1 ходу — и т.д. Можно было собирать предыдущую статистику сделок по каждому сопернику. Так что не в масках, а с открытыми но изначально незнакомыми лицами.


  1. FlameStorm
    21.06.2018 22:29
    #18803181

    > node haggle.js -m 10 -M 10 -V 2000000 ...


    haggle.js падает по нехватке памяти. В условии задачи нет лимита на общую цену товаров: $2 000 000 скрипт принимает как валидное значение, но не тянет. Пропустили лимит или так и задумано?


    1. feldgendler Автор
      21.06.2018 22:36
      #18803199

      Мы не будем запускать с такими дикими параметрами, поэтому поведение скрипта на них не имеет значения.

      «Для окончательного тестирования мы будем использовать параметры тестовой системы по умолчанию: 3 типа объектов, от 1 до 5 объектов каждого типа, суммарная ценность всех объектов для каждого из партнёров $10, лимит в 5 раундов».


      1. FlameStorm
        21.06.2018 22:54
        #18803267

        А в той которая "попарная система тестирования чемпионата", что до "окончательного тестирования", там как-либо V определено? Тоже $10 или что-то иное и до какого лимита, если он есть?


        1. feldgendler Автор
          21.06.2018 22:59
          #18803285

          Я не понимаю, о чём Вы говорите. Какая попарная система тестирования чемпионата? Можно цитату из поста?


          1. FlameStorm
            21.06.2018 23:18
            #18803313

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

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


            Попарные переговоры, о которых речь идёт в этом абзаце — с какими параметрами? Не понятно.


            А далее, как излагает отдельный следующий абзац, будет проведён прогон "окончательного тестирования с параметрами по умолчанию" (скриптов каждого участника с — какими скриптами? ).


            Что тут ещё подумать, кроме как что итоговый результат будет равен сумме прогона с "попарных переговоров" (с неизвестными параметрами) и "окончательного тестирования (кого с кем?) с параметрами по умолчанию".


            Может у меня одного нейроны не в порядке и не вижу чёткого условия. :) Как-то ясности не хватает в методике проведения чемпионата в общем.


            1. feldgendler Автор
              21.06.2018 23:22
              #18803323

              Да это одно и то же. Окончательное тестирование и заключается в проведении попарных переговоров. Параметры — по умолчанию.


              1. FlameStorm
                21.06.2018 23:24
                #18803329

                Теперь понятно, спасибо.


      1. feldgendler Автор
        22.06.2018 13:26
        #18805143

        Поправка: не «от 1 до 5 объектов каждого типа», а «в сумме до 6 объектов».


  1. SinsI
    22.06.2018 03:31
    #18803629

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


    1. haldagan
      22.06.2018 08:37
      #18803863
      +1

      Ценность каждого типа объектов для каждого из партнёров — целое неотрицательное число



  1. Welran
    22.06.2018 08:15
    #18803833
    +1

    А вообще при такой маленькой общей стоимости и набору предметов по идее можно составить же все варианты распределения цен между ними?


    1. feldgendler Автор
      22.06.2018 11:43
      #18804613

      А вы загляните в generate.js.


      1. Nomad1
        22.06.2018 12:58
        #18805013

        В примере у вас 6 предметов (книга, 2 мяча, 3 шляпы), а генератор с параметрами по-умолчанию (3, 1, 5, 10, 5) генерирует максимум 5. Строка
        let max = this.max_obj-total_count-this.types+i+1;
        Дает max не больше 3 с такими параметрами.


        1. feldgendler Автор
          22.06.2018 13:15
          #18805095

          Вы правы, это ошибка в документации. То есть изначально предполагалось, что это будет возможно.

          Я исправил текст поста. Параметры --min-objects и --max-objects ограничивают не число объектов каждого типа, а суммарное число всех объектов. Значение по умолчанию (которое мы будем использовать при тестировании решений) для --max-objects увеличилось до 6.

          Прошу прощения! Хорошо, что это заметили всего лишь на второй день.


  1. SH42913
    22.06.2018 13:43
    #18805221

    Звучит интересно, даже жаль, что я не знаком с JS :(


    1. zBit
      22.06.2018 15:35
      #18805609

      Никогда не поздно познакомиться :)