Конкурс по программированию: Торговля

    UPDATE: Объявления для участников.

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

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

    Желаем удачи всем участникам!
    Hola 100,27
    Компания
    Поделиться публикацией
    Комментарии 206
    • +1
      Наконец-то новое задание :)
      • +2

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


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

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

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

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

            • +5

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

              • 0
                9600 бод и все-все-все…
          • 0
            max_rounds — это наибольшее количество вызовов метода offer, верно? Если max_rounds == 1, me == 1, то offer уже не может ничего предложить, только принимать условия полученного предложения? Если в этом случае offer вернет не undefined (не согласен), то оба контрагента получат по 0?
            Полагаю, в описание следует добавить уточнение про конец игры при достижении лимита раундов.
            • 0
              Верно. Так и сказано:
              Если же соглашение не достигнуто, то есть последнее слово в последнем раунде — встречное предложение, а не согласие, — то никто не получает ничего.
            • 0
              Позже мы запустим «живую» таблицу лучших результатов, где будут приведены средние исходы сделок и хэши идентификаторов.

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


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


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


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


                • 0

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

                  • 0

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

                  • +1
                    1. Да.
                    2. «Мы надеемся, что сможем провести не менее двух сеансов для каждой возможной пары, однако, если решений окажется слишком много, то нам, возможно, придётся выбрать другую систему проведения чемпионата. О конкретной системе будет объявлено позже».
                    3. Только если мы обнаружим попытку взлома тестовой системы или какое-то другое жульничество.
                    4. Вам придётся ещё и как-то распознавать «своих» партнёров. Ну и если мы поймём (статистическим анализом), что вы вытворяете что-то такое, а потом почитаем исходники, и подозрения подтвердятся, то дисквалифицируем все решения, участвовавшие в схеме.
                    • +1
                      Вот третий пункт стоило бы обозначить в правилах отдельно, потому что в нынешней редакции ниоткуда не следует что так нельзя.
                      • 0
                        Четвертый пункт имелся в виду, прошу прощения.
                    • 0
                      По второму пункту — жаль что точно не известна система тестирования решений. Так как это может сильно повлиять на выбор стратегии.
                • +1
                  Время на ход ограничено 1 секундой, а есть ли ограничение на время работы конструктора?
                  • 0
                    Ага, и какое ограничение по памяти? Известно ли какие будут максимальные суммы values * counts?
                    • 0
                      Ваш скрипт будет запускаться в Node.js с параметрами по умолчанию, отсюда и размер кучи около 2 ГБ.

                      «Суммарная ценность всех объектов для каждого из партнёров $10».
                    • 0
                      Входит в первую секунду. Тестируйте свой скрипт нашей тестовой системой, мы и сами будем ею пользоваться.
                    • +2
                      В текущем виде задания, очевидной стратегией будет использовать «подсадных ботов».
                      Их задача не выиграть, а улучшить очки «своего игрока», которого они должны суметь отличить по первым 4м раундам торговли и отдать ему все предметы, а со всеми чужими ботами сыграть в отказ, чтобы ухудшить их стату.
                      Также, чтобы избежать анализа «алгоритма определения свой-чужой» со стороны конкурентов, своих подсадных ботов надо заливать в последний момент, и сразу кучу, но тут всплывет нюанс, что и сервак может лечь как под ддосом.

                      Чтобы сделать эту стратегию не эффективной нужно сделать цену 1го бота ненулевой, например просить к заданию прилагать 1$.
                      Или просить уникальный скан паспорта или еще какую идентефикацию.
                      • +2
                        Вы же понимаете, что, если вы таким способом займёте призовое место, то мы прочитаем исходник вашего решения. Если увидим такую схему, то дисквалифицируем все решения, участвовавшие в ней. Короче, запрещено. Добавил в правила такое уточнение, а то не всем это очевидно.
                        • +1
                          А исходник решения может не содержать «ответа», по крайней мере очивидного. Весь функционал распознавания и слива может быть сосредоточен в подставных ботах, которые проиграют и их анализировать никто не будет.
                          Примерная схема такая — мой бот играет честно, по достаточно средненькой стратегии, но угадываемой по патернам. Мои подставные боты имеют ту же самую стратегию чтобы уметь востанавливать патерн и играют «почти» по ней (почти чтобы они не спутали друг-друга с главным ботом), но угадав главного бота в последнем раунде сливают ему «почти» всё (почти чтобы хуже детектится статистикой).
                          В этом случае против чужих ботов наши боты (и сливщики, и главный бот) будут играть вполне средненько, а в отношении друг-друга так как нужно нам.
                          В итоге проигравшие боты играли чуть ниже среднего — они никому не интересны и их много для анализа. Выигравший бот играл абсолютно честно. Он даже не знал что ему поддавались — там нечего анализировать.
                          Бороться с этим можно как мне кажется только одним способом — проводить по несколько круговых турниров и по их результатам отсеевать половину худших, а половину лучших брать в следующую серию круговых турниров, и учитывать внутри серий только результаты достигнутые внутри них.
                          В таком случае мне придется написать несолько ботов, которые должны будут не просто сливать все главному, но при этом еще и играть лучше остальных чтобы постоянно оставаться в строю и не быть отсеяными.
                          В идеальном варианте в последней серии турниров должны остаться только мои боты. Но тогда тот из них который играет наихудшим образом может победить даже без участия остальных моих ботов. Следовательно мне уже не надо писать никаких ботов, кроме одного самого простого.
                          Как-то так.
                          • 0
                            Мы вычислим ваших ботов, не переживайте. Я не собираюсь сейчас подробно рассказывать, как именно, пусть это будет сюрпризом.
                            • +3
                              Именно моих — нет. Я тоже пока не буду рассказывать как имеенно они будут прятаться, пусть это будет сюрпризом )))
                              • 0
                                Скорее всего все решения, как и в прошлые разы, будут выложены в открытом доступе и участники конкурса сами вычислят недобросовестных конкурентов. Вычислят, докажут и сообщат об этом организаторам конкурса, а они уже будут принимать решение дисквалифицировать или нет.
                                • 0
                                  Решения и логи всех прогонов будут опубликованы.
                            • 0
                              На самом деле не обязательно даже, чтобы боты поддавались кому-то.
                              В игре есть всего три варианта действий противника:
                              — Рандом (слишком сложный для анализа алгоритм, обучение нейросети, неверно работающий алгоритм, ГСЧ и т.д.)
                              — Расчет (калькуляция по какому-то алгоритму)
                              — Блеф (заранее невыгодный вариант, чтобы сбить с толку анализатор)

                              Подавляющее большинство «адекватных» программ будет делать расчет. Некоторое количество программ будет делать рандом, несколько уникальных будет делать блеф. Для удобства скажем, что это соотношение 80/15/5. Предположим, что какой-то супер-алгоритм дает шансы 75/50/30, что делает его лучшим среди расчетных, равным с рандомными вариантами и слабее не-анализируемого по своей сути блефа. Достаточно полусотни блефующих и рандомных программ, чтобы все честные алгоритмы потеряли баллы и стали «середнячками», просто потому, что мы сместили фокус соревнования с битвы алгоритмов. Да что говорить, одним этим сообщением я уже смещаю фокус игры, потому что читающие спросят себя «а что такое блеф и как от него защититься?»
                              • 0
                                Идею блефа я уже обдумывал… Как защититься? Да никак — слишком мало раундов. Их достаточно чтобы попытатья раскусить расчет, но мало чтобы раскусить блеф (ну если он не очевидный — первым ходом предлагать худшую для себя комбинацию, вторым и третьим лучшую и вторую с конца). Поэтому я сразу отбросил идею раскусить блеф — мне думается что стратегию нужно строить либо на идеи «все блефуют» (тогда вообще лучше отказаться от анализа), либо на идеи «все играют честно».
                                • 0
                                  Вот я и говорю, что злоумышленник может сместить суть конкурса с «все играют честно» на «все блефуют» или наоборот. Или вообще добавить столько рандома, что победит рандом :)
                                  • 0
                                    Быть лучше рандома по видимому достаточно легко.
                            • +2
                              Нет, это не было очевидным, до вашего ответа.
                              Откуда мне знать, чего вы добиваетесь этим конкурсом и какие скилы вам интересно выявить у претендентов на работу.

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

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

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

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

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

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

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

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

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

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

                                  Сплошные mind games в общем, а не конкурс.
                                  • 0
                                    Против хорошей стратегии может быть трудно получить преимущество, даже имея доступ к её исходникам.
                                    • +2
                                      Я немного про другое:

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

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

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

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

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


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

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

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


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

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

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



                                          Как Вася узнает, какие у оппонента цены?


                                          Он может прикинуть это по первому же предложению от оппонента. Блефовать в текущем конкурсе скорее всего не стоит по следующим причинам:

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

                                          В таком случае блефовать можно/нужно только если рынок переполнен жадными стратегиями.
                                          • 0
                                            example все ходы каждый раз просит все предметы с ненулевой для него стоимостью. и принимает входящие предложения с сумомй для него 5+.

                                            на счет блефа — не так он и бесполезен. ведь чтобы победить нужно не конкретную игру выиграть а набрать общую сумму.

                                            хотя надо признать что скорее всего победители наберут основную сумму своего суммарного счета с тупыми ботами, тк их большинство.
                                            • 0
                                              … с сумомй для него 5+ ...


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

                                              … не так он и бесполезен...


                                              Блеф как раз вреден в долгосрочной перспективе.
                                              Для того, чтобы блеф сработал вам необходимо иметь определенную уверенность, что блеф необходим/полезен в данной конкретной ситуации, что мне представляется невозможным выяснить на пяти раундах торгов без сохранения истории/статистики.
                                              В этом и дело: использовать блеф, как основную стратегию — убыточно практически в любом случае (имеется в виду текущий конкурс).
                                            • 0
                                              1. example.js — бот, описанный в этой статье и доступный по скачке.
                                              Мне кажется, что за счет случайного распределения цен, его действия близки к стратегии «сделать случайный ход», именно поэтому написал
                                              Example js — случайный игрок из ncase.me/trust

                                              2. all-in.js, или «все за все» соглашается только на обмен «все мои вещи на все твои». Предлагает только такой обмен, отвергает любые другие предложения

                                              Я утверждаю, что при определенных раскладах example.js будет также предлагать все вещи, но может согласиться и на одну «шляпу». И различить двух ботов, за сессию из всего 5 offer, надежно нельзя.

                                              3.
                                              Как Вася узнает, какие у оппонента цены?

                                              Этот вопрос в в полном виде должен быть сформулирован так: «Допустим, мы знаем что оппонент — бот example.js из статьи. Как Вася узнает, какие у оппонента цены и что он оценит в 5 монет?».

                                              Вчера писал поздно ночью, поэтому вышло немного сумбурно.
                                              • 0
                                                example.js — он как раз не случайным образом собирает предложение, а в соответствии с ценностью: себе максимум по цене, остальное сопернику, и если соперник делает предложение с ценностью для example.js более 5 (полцены), то соглашается, иначе мочало сначала.
                                                Всё таки сделать случайный ход, без оглядки на ценность предметов для себя и действия соперника, и согласиться или нет на чужое предложение подбросив монетку это другое.

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

                                                Сложно уловить вашу нить рассуждений, когда не очень понятны предлагаемые стратегии.
                                                • 0
                                                  example.js — это не моя стратегия, она описана в статье. Возможно, я неправ в ее трактовке, не буду спорить, т.к. это отдельная тема
                                                  Вторую стратегию я тоже описал достаточно конкретно. Если в вашем понимании all-in должен означать что-то другое, это спор о названиях. Назовите стратегию хоть aaa.js, вопрос не в этом. Изначально haldagan утверждал
                                                  Вася, собравший статистику и знающий про example.js в выигрыше: он знает, что его выигрыш по 98 сделкам из 99 может быть сколь угодно большим,

                                                  Проблему, которую я поднял, и вопрос, на который хочу получить ответ:
                                                  Как Вася поймет, с какой из двух стратегий он торгует? Обе стратегии описаны, одна example.js из статьи, другая
                                                  соглашается только на обмен «все мои вещи на все твои». Предлагает только такой обмен, отвергает любые другие предложения

                                                  Подчеркну, я не хочу обсуждать насколько хороши обе стратегии. Вопрос, как Васе различить их? Для чего их различать и почему это зачастую затруднительно, я описал в п.2 в предыдущем комментарии
                                                  • +2
                                                    Вы до сих пор не пояснили, что делает all-in.js

                                                    все мои вещи на все твои


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

                                                    Как Вася поймет, с какой из двух стратегий он торгует?

                                                    как Васе различить их


                                                    Если Вася знает, что 99% игроков на рынке это поровну — аллин и example — ему не нужно различать их. Ему просто нужно поочередно предлагать выгодные ему сделки, на которые однозначно согласятся вышеупомянутые стратегии. Ну условно:

                                                    — Даю тебе 5, мне 10
                                                    — «отказ»
                                                    … Значит это НЕ екзампле…
                                                    — Даю тебе 6, мне 6
                                                    — «отказ»
                                                    … Значит это НЕ аллин и не екзампле — падаем в отказ, если соперник не предложит мне 10…

                                                    Таким образом Вася соберет максимум с екзампле и алл-ин и зарежет все сделки с реальными игроками. Если известные массовые стратегии могут быть эксплуатированы в пользу Васи — нет смысла торговать с единичными, но умными игроками.
                                                    • 0
                                                      Даю тебе 5, мне 10

                                                      Есть проблема: вы не знаете ценность предметов для оппонента.

                                                      • –1
                                                        >вы не знаете ценность предметов для оппонента

                                                        Хотел было опять возразить, что в большинстве случаев можно грубо, но прикинуть, но потом прочитал ваше
                                                        всех предметов вместе максимум 6, а не каждого типа в отдельности максимум 5


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

                                                        Как это нет понятия «твой на мой»? Вы почему-то рассуждаете в терминах монет, но обмен идет предметами. После торгов будет ясно, кто выиграл больше.
                                                        Вы до сих пор не пояснили, что делает all-in.js

                                                        Стратегия «ал-ин» меняет предметы по описанному, дважды, алгоритму. Он намеренно неоптимален, ведь цель моего примера — обсудить стратегию Васи.
                                                        — Даю тебе 5, мне 10
                                                        — «отказ»
                                                        … Значит это НЕ екзампле…
                                                        Вася предложил 5 предметов и просит 10. Это может быть example.js, у которого предложенные 3 фантика стоят 3 монеты, а 2 шляпы — ноль. Вывод Васи неверен.

                                                        Даю тебе 6, мне 6

                                                        И тут example.js соглашается. На этапе подсчета все узнают, что он получил, как и Вася, теоретический максимум — 10 монет. А мог бы 5, если бы его распознали.

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

                                                          Я немного исправил описание: всех предметов вместе максимум 6, а не каждого типа в отдельности максимум 5.

                                                          • +1
                                                            В гите пока всё по старому, стоит 5.
                                                            • 0
                                                              Забыл сделать git push.
                                                              • 0
                                                                Бывает. Теперь порядок.
                                                                • 0

                                                                  Алексей, а это случайно прокравшаяся мысль-идея, на строке 145 в haggle.js, что max_obj>100 параметр макс числа объектов поднять с 10 до 100, и будет поправлено обратно на макс 10 предметов, или таки грядёт лимит 100?


                                                                  Ну и тогда уж может определить лимит на $ total заодно? :)

                                                                  • 0
                                                                    Это я сделал возможность задать с командной строки до 100 предметов. Мы по-прежнему намерены придерживаться настройки по умолчанию (6).

                                                                    На total при задании с командной строки верхней границы нет. Мы всё равно будем использовать значение по умолчанию (10).
                                                                    • 0
                                                                      Ок, спасибо.
                                                                      (В сообщении про лимит 10 можно пофиксить, что теперь 100)
                                                                    • 0
                                                                      .
                                                              • 0
                                                                Стратегия «ал-ин» меняет предметы по описанному, дважды, алгоритму. Он намеренно неоптимален, ведь цель моего примера — обсудить стратегию Васи.


                                                                То ли я плохо читаю, то ли Вы плохо пишите.

                                                                — Алл-ин запрашивает все предметы с ненулевой для него ценностью
                                                                — На любое другое предложение следует отказ

                                                                Так?

                                                                В общем наш спор уже не имеет смысла: поскольку организатор поменял условия с «от 1 до 5 каждый предмет» на «6 предметов в сумме максимум», точно предсказать стоимость предмета для оппонента теперь практически невозможно за 5 раундов.
                                                                • 0
                                                                  Часто бывают игры и с раскладом вроде (1,1,1). В таком случае кое что рассчитать можно. Но все ломается, когда противник ведет себя непредсказуемо, отказывается от всех предложений и все 5 раундов предлагает (0,0,0). Я думаю, оптимальная стратегия будет не самая математически точная, а самая хитрая, ломающая все другие алгоритмы.
                                                                  • 0
                                                                    Теоретически точно предсказать стоимости для оппонента и не было возможности, из-за возможности стратегий «рандом», «блеф», «слив», а также ряда других.
                                                                    • 0

                                                                      Непонятно, почему именно это изменение делает такую большую разницу.

                                                                      • 0
                                                                        Непонятно


                                                                        Все достаточно просто: с предметами от 1 до 5 было около 120 раскладов по вариантам количества предметов.
                                                                        Из них чуть больше половины раскладов имела 6 и менее валидных раскладов по стоимости предметов.
                                                                        То есть в 50% случаев мы могли гарантированно заключить наивыгоднейшую сделку против example.js, просто предложив 5 сделок.
                                                                        Это, правда, с учетом того, что игроки не могут иметь абсолютно одинаковые ценности предметов. Если это не так — ситуация лишь чуть-чуть ухудшится.

                                                                        Для остальных 50% случаев пришлось бы более-менее наугад выбирать, это да. Основной подсказкой было бы то, что example.js никогда не запрашивает предметы с нулевой стоимостью.

                                                                        С нынешними «максимум 6 в сумме», у нас всего 20 вариантов раскладов по количеству, у каждого из которых не менее 14 возможных вариантов раскладов по ценам (около 24 в среднем).
                                                                        То есть, играя против example.js мы почти(?) никогда не сможем узнать наверняка ценность предметов для него, однако это не значит, что в текущих условиях невозможно создать стратегию, гарантированно побеждающую examle.js
                                                                      • 0
                                                                        — Алл-ин запрашивает все предметы с ненулевой для него ценностью
                                                                        Нет, не так.
                                                                        Запрашивает все предметы. Точка. Предлагает все предметы. Точка.

                                                                        Сразу соглашусь что это глупо. Я намеренно привел неоптимальный, но простой алгоритм действий — только для того, чтобы мы могли обсудить как Вася может отличать ее от example.js. Ошибившись, мы рискуем отдать example.js больше желаемого или не получить от all-in 10 монет.
                                                                        На любое другое предложение следует отказ.
                                                                        . Да, это верно
                                                                        • 0
                                                                          Договариваться с all-in имеет смысл, так как
                                                                          значение будут иметь не «победы» и «поражения», а сумма вознаграждений, полученных каждым скриптом во всех сеансах

                                                                          Есть соблазн последним ходом делать предложение, которое all-in примет, но… Тогда для выигрыша у example.js у нас остается четыре хода вместо пяти.
                                                                          • 0
                                                                            Запрашивает все предметы. Точка. Предлагает все предметы. Точка.


                                                                            Вроде понял. В других постах о стратегии «все в признательность за все» не фигурировало название «all-in», посему я не смог сопоставить эти два понятия.

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

                                                                            UPD: Уже понял, что ошибся (если Ваш алл-ин может предложить все и на последнем ходу, а не только на первом). Беру время на подумать.
                                                      • +2
                                                        Боюсь все так и будет, как и в тот раз когда надо было анализировать статистику словаря. Но я все равно попробую «честное» решение, которое не анализирует чужую стратегию, а играет с широко закрытыми глазами. Интересно же, ну.
                                                        • 0
                                                          Более того, будет еще второй этап перед дедлайном. Это когда все проанализируют рынок и найдут наивные стратегии, против которых топовые алгоритмы играют неоптимально, а потом, в самом конце, зальют тонны ботов, реализующие эти стратегии. И начинаются еще игры: сейчас надо для анализа заливать проги, которые не палят свои последние ходы, чтобы их нельзя было анализировать другим людям.

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

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

                                                            А на PHP можно?

                                                            • 0
                                                              Нет, исключительно JS.
                                                              • 0
                                                                Если Вы транспилируете его в рабочий javascript, то полагаю можно.
                                                              • 0
                                                                А не будет такого, что кто первый ходил, тот просто тянет до последнего раунда и делает максимально выгодное для себя предложение, т.е. забирает себе все кроме одной вещи. Тогда у оппонента будет два варианта или получить почти ничего, или вообще нечего, и придется соглашаться на объедки с барского стола. А т.к. сессии независимы, то запомнить «ублюдка» оппоненту не удастся.
                                                                • 0
                                                                  ИМХО, если мы на последнем ходе получаем очень невыгодное для себя предложение — лучше от него отказаться. Так мы, например, не продвинемся в таблице никуда, но и противник тоже. А в противном случае мы поднимемся на совсем чуть-чуть, но противник подскочит повыше. Иными словами — получить копейки нет смысла.
                                                                  • 0
                                                                    Иными словами — получить копейки нет смысла.

                                                                    Хехехе, хорошо, что вы так думаете )
                                                                    Скрытый текст
                                                                    image
                                                                    • 0
                                                                      противник в текущей игре может быть идет на самом последнем месте в общей таблице, а вы может быть наверху и вам не хватает всего 1 балла. так что и за 1 балл есть смысл бороться, скрипт ведь не знает ваше текущую позицию в таблице.
                                                                      • 0
                                                                        А может быть он на один ниже вас в таблице, и так он никуда не денется, а так обгонит вас. Тут, походу, однозначного ответа нет, рандом :)
                                                                    • 0
                                                                      Даже в вырожденном случае (см. так называемую Ultimatum game) всё не так очевидно.
                                                                      • 0
                                                                        Ну да, пишут, чтобы такой случай был очевидным, надо делить $10 млн реальных денег )
                                                                    • 0
                                                                      а стоимости так и будут только целыми числами как на тестовом сервере?
                                                                      • 0
                                                                        «Ценность каждого типа объектов для каждого из партнёров — целое неотрицательное число».
                                                                      • 0
                                                                        Проблема этой «торговли» — целью является не максимизация прибыли, а выигрыш, что возможно и если всем остальным оставить ноль, а себе получить только $1.

                                                                        Если существенная доля ботов будет от одного хозяина — то, сговорившись, они могут использовать это для победы своего кандидата, оставив всех остальных ни с чем.
                                                                        • 0
                                                                          Правилами такой «сговор» запрещён, все участвующие в нём решения будут дисквалифицированы.
                                                                          • 0
                                                                            Его ещё надо доказать.
                                                                            А ведь самому писать все боты — совершенно необязательно, достаточно просто опубликовать часть своего алгоритма.
                                                                          • 0
                                                                            В любом случае, значение будут иметь не «победы» и «поражения», а сумма вознаграждений, полученных каждым скриптом во всех сеансах.
                                                                            • 0
                                                                              Вопрос в том как вы определите союзника за 5 раундов с неизвестным в начале набором предметов и неизвестной ценностью для соперника во время торговли с кучей ограничений на возможные предложения (нельзя например в качестве теста предлагать все предметы или просто много предметов так как посторонние боты могут просто сразу согласится и закончить торговлю). так что даже если бы этого правила не существовало, задача определения союзника весьма не тривиальна (если вообще возможна).
                                                                              • 0
                                                                                Так 100% определения не требуется. Достаточно чего-нибудь простого, например предложения в первые 2 раунда числа предметов, делящегося на 3.
                                                                            • +3

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


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


                                                                              пикча

                                                                              А тут каждая торговля — торговля в масках, маски шоу блин…


                                                                              Можно было бы в функцию торга offer(o) ввести второй параметр traderId (с кем вы гости торг ведёте, и куда теперь плывёте..), но если, как сказано, торговать с одним и тем же товарищем в конкурсном забеге доведётся всего может пару раз, то смысл его анализировать и запоминать?..
                                                                              Пока выглядят условия так, что самая главная переменная — методика тестирования, неизвестна и соответственно подходящие черты стратегии которые надо закодить, тоже.


                                                                              Алексей, а логически предсказуемое решение существует вообще?
                                                                              В JSDash хотя бы понятно было, что да.

                                                                              • 0

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


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

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


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

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

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

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

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

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

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

                                                                                      И, опять же, если вкинуть эти 100 решений заранее, то игроки, ясное дело, приспособятся к наличию такого количества сверхжадных стратегий, но, если сделать это перед самым стартом — результат такого вброса сложно предсказать, т.к. (ИМХО) большинство стратегий будут нацелены именно на компромисс, то есть искать вариант с максимизацией одновременно и своей выгоды и выгоды оппонента.
                                                                                    • 0
                                                                                      > построить оптимальную стратегию на псевдослучайных данных невозможно.
                                                                                      Чой-то? Есть даже строгое доказательство, что можно, даже для более жесткого случая.
                                                                                      • 0
                                                                                        Извиняюсь, коряво написал. Естественно можно запилить оптимальную стратегию, если заранее известно, что все на рынке — рандом.
                                                                                        Сложно будет адекватно оценить лучшую стратегию, если все стратегии готовились честно/компромиссно торговать и, внезапно, непосредственно перед стартом «официального турнира» кто-то закинет рандомные стратегии в большом количестве (в разы превышающем честных игроков).
                                                                                        Единственный вариант — поудалять стратегии, закинутые перед стартом.
                                                                                        • 0
                                                                                          Не совсем. Дажер резкий рост количества рандома не должен повлиять на результаты торговли — лучшая стратегия без них и с ними на рынке должна оказаться одной и той же. Вряд ли произойдет перестановка.
                                                                                          Вообще, учитывая малое количество раундов и рандом в ценах, уметь торговать с рандомом должны все.
                                                                                          Если же удалить «закинутые перед стартом» и объявить об это заранее (а и наче это нечестно), то злоумышленник закинет их чуть раньше старта. Вобщем выйдет классическая задача с неказнимым преступником.
                                                                                          • +1
                                                                                            пример:
                                                                                            много ботов которые при предложении им всего — отказываются и в ответ сами отдают все. (признательность за признательность). всем остальным они всегда отказывают (сделка срывается 0-0).
                                                                                            тот кто знает что таких ботов будет большинство — победит. т.к. он с ними получает по 10, остальные с ними получают 0. т.к. их большинство — остальное не важно.

                                                                                            поэтому возможны ситуации когда при большом количестве неадекватов «лучшая» стратегия станет худшей.
                                                                                            и это самый банальный пример, естественно можно и хитрее придумать.
                                                                                            • 0
                                                                                              А это уже не рандом нифига. Я же отвечал на ситуацию когда рандома много.
                                                                                            • +1
                                                                                              Я чувствую, что у меня не хватает ни мозгов ни теоретической базы, чтобы внятно разложить по полочкам то, что я пытаюсь донести своими постами (их уже много в этой теме скопилось).

                                                                                              Попробую как смогу в последний раз:

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

                                                                                              То есть вы будете обучать свою нейронку торгам на ВЫДУМАННЫХ ВАМИ тестовых данных.

                                                                                              Далее:

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

                                                                                              Моя мысль:

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

                                                                                              Как результат — из всех «адекватных» нейронок победит одна самая лояльная к массово вкинутым стратегиям. Это может быть как умышленная так и неумышленная бага поведения.

                                                                                              Если до сих пор непонятно — я сдаюсь. Если кто-нибудь умнее меня почитает мои посты и сможет сформулировать эту мысль как-то более человекопонятно — мои ему благодарности.
                                                                                              • 0
                                                                                                В этом нет большого смысла с практической точки зрения, т.к. едва ли кто-то захочет и сумеет вбросить большое количество неадекватных стратегий.
                                                                                                • +1
                                                                                                  заходим на форум с школьниками и пишем «кто хочет выиграть 3000$ — заливайте туда вот этот файл и ждите приза». по теории игр опять же, школьникам, выгоднее залить непонятный файл и получить хотя бы мифический шанс, чем вообще ничего не залить и ничего не ждать.
                                                                                                  • 0
                                                                                                    Во-первых, не думаю, что школьники насколько внушаемые, что кинуться делать все что вы им скажете;
                                                                                                    Во-вторых, что это за форум такой со школьниками? пикабу? )
                                                                                                    В-третьих, как-то палевно 100 раз присылать идентичный файл с разных аккаунтов.
                                                                                                    • +1
                                                                                                      1) ну я сухо и коротко описал суть. конечно для них лучше покрасочней придумать легенду, например «я придумал самый крутой алгоритм, но создатели игры меня забанили и теперь я хочу их наказать. я сливаю свой алгоритм и ктото из вас выиграет 3000$».

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

                                                                                                      3) правилами это не запрещено. один чел не может присылать с разных ящиков, но тут присылают разные реальные люди, пусть алгоритм один, но это тоже не запрещено. Ну и все верят в то что победить должна именно сильная стратегия, поэтому не видят в этом проблемы.

                                                                                                      но все принимают допущение что все участники СТРЕМЯТСЯ ВЫИГРАТЬ. если будет много неадекватных алгоритмов одного типа, то это может быть решающим в том чей алгоритм победит.
                                                                                                      • 0
                                                                                                        правилами это не запрещено.
                                                                                                        Запрещено другое: «Отправка множества решений, находящихся в «сговоре», с разных адресов запрещена; все решения, участвующие в такой схеме, будут дисквалифицированы.».

                                                                                                        Но даже если все можно, вопрос в том — какой адекватный человек будет заниматься всей этой ерундой (искать школьников на форумах и т.д.)?
                                                                                                        • +1
                                                                                                          тот который хочет получить 3000$, например.

                                                                                                          «искать» = отправить сообщение на стену в пару групп. админы сами поддержат такую горячую тему и «эксклюзив».
                                                                                                  • 0
                                                                                                    >едва ли кто-то захочет
                                                                                                    Я уже выражал желание «попросить друзей» по ветке выше.

                                                                                                    >и сумеет
                                                                                                    Вы пытаетесь «на слабо» взять? Тогда я пас.

                                                                                                    Вы можете сказать на каком основании вы сможете отклонить, например, триста заявок с разной (легитимной) почтой, с разными IP, разным кодом, но примерно одинаковым поведением?
                                                                                                    • 0
                                                                                                      Я бы посмотрел как вы сделаете 300 скриптов с разной структурой и одинаковым поведением, и которые способны существенно повлиять на результат остальных игроков относительно друг друга. Также непонятно как вы их заливать будете.
                                                                                                      • 0
                                                                                                        300 скриптов с разной структурой и одинаковым поведением
                                                                                                        обфускация?
                                                                                                        • 0
                                                                                                          «Если Ваш JS-файл — продукт генерации, минификации и/или компиляции с других языков вроде CoffeeScript, пожалуйста, приложите архив с исходниками, а также, желательно, описанием подхода»
                                                                                                          • 0
                                                                                                            Вы со спамом никогда не сталкивались?
                                                                                                            Ну там

                                                                                                            var m = '123';
                                                                                                            var x = Math.random();
                                                                                                            return x>0.5;
                                                                                                            ...
                                                                                                            var k = '321';
                                                                                                            var xy = Math.random();
                                                                                                            return xy>0.5;
                                                                                                            ...
                                                                                                            var y='231';
                                                                                                            var pz = Math.random();
                                                                                                            return pz>0.5;
                                                                                                            


                                                                                                            пожалуйста, приложите архив с исходниками, а также, желательно, описанием подхода


                                                                                                            Эти стратегии НЕ выйдут в топ — они просто сместят распределение очков в непредсказуемую сторону. Вы/участники всех проверять будете?
                                                                                                            А после проверок удалите «залетных» и заново турнир проведете?
                                                                                                            • 0
                                                                                                              Кстати правилами не запрещена публикация идентичных решений от разных участников «школьников а дай ка поучаствую как тут зазывают».

                                                                                                              Особенно если заранее опубликовать сурс решения, который будет дан «школьникам». А лучше трёх с разными стратегиями, и все их дать «школьникам». Значит все участники будут в курсе и ни на какое конкретно решение из участников «масс-приглашённые» не могут быть объявлены работающими — ведь все были в курсе.
                                                                                                              • 0

                                                                                                                Да, придумаем, как такое отсеять.

                                                                                                    • +1
                                                                                                      именно так.
                                                                                                      суть в том что нет лучшей стратегии в этой игре. можно говорить лишь о лучшей стратегии против конкретной другой.

                                                                                                      я уже приводил пример, когда большое количество неадекватов сделает лучшую стратегию худшей, а худшую — лучшей (отдай все первым ходом и ты победишь) habr.com/company/hola/blog/414723/?reply_to=18806589#comment_18806445

                                                                                                      поэтому невозможно сделать лучшую стратегию в вакууме. победит тот кто подстроится под большинство. если же никто не сделает специальный вброс своих ботов с одной стратегией, то самая популярная стратегия будет example.js
                                                                                          • 0
                                                                                            Всё как в жизни. Бывает, что переговоры приходится вести с партнёром, о котором заранее ничего неизвестно. И что? И ничего. Всё равно стараемся оптимизировать исход.
                                                                                            • 0

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


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


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


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

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

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

                                                                                                  • 0
                                                                                                    О, тут мы оцениваем сознательно или бессознательно кучу параметров.
                                                                                                    Смотрим на человека, как он выглядит, во что одет, как пахнет, двигается, его национальность итп.
                                                                                                    Для себя оценочно выводим его социальный статус и вычисляем априорную вероятность насколько стоит доверять человеку «такого типа».
                                                                                                    • 0
                                                                                                      Уверяю вас, торговаться можно даже в чате.
                                                                                                      • 0
                                                                                                        Нет, разница в другом — на «базаре» как минимум одна из сторон принимает иррациональное решение. Т.е. в реальных условиях как минимум один из участников сделки не стремиться максимизировать свою прибыль от неё.
                                                                                                        • –1
                                                                                                          Почему? Вот покупаете вы машину или квартиру, вы не будете стараться заплатить как можно меньше при тех же условиях?
                                                                                                  • +1
                                                                                                    В жизни у торговых партнёров чаще всего нет стимула сделать так, чтобы ты получил как можно меньше выгоды.
                                                                                                    Тут же скриптам есть смысл торговаться и за совершенно ненужный им хлам даже если им уже предложили товаров на все $10.
                                                                                                    • +2
                                                                                                      Вроде за ненужный хлам торговаться, нет смысла, тк
                                                                                                      — можно и в пролете остаться, предложили на 10 надо забирать сразу
                                                                                                      — нету смысла пытаться еще опустить по рейтингу скрипт который отдает на 10$, в топ он и так не выйдет с такими предложениями
                                                                                                      • 0
                                                                                                        Т.е. вы предлагаете просто дарить противнику дополнительные очки, просто потому что для вас они ничего не стоят?
                                                                                                        • +1
                                                                                                          Не существует формулы определить, какой результат гарантированно лучше: 10/?, 10/10 или 0/0, ведь у скрипта нет никакой общей статистики, он не знает своего противника и т.д. Как поступить в этой ситуации (забрать сразу предложение с 10 баллами, отказаться, торговаться за мусор) решит каждый автор по-своему и видимо этим и будут отличаться наши скрипты — некими коэффициентами компромиссов, как шапочками в ролике по ссылке ниже.
                                                                                                          • 0
                                                                                                            Да вы не знаете (кроме вырожденных случаев «всё» и «ничего»), сколько стоит предложение для партнёра.
                                                                                                          • 0
                                                                                                            У вас — всего 5 кругов торговли.
                                                                                                            Если вам сделали весьма щедрое предложение, а вы отказались, возможно что такого щедрого предложения больше вам чужой скрипт не предложит.
                                                                                                            • 0
                                                                                                              Как мне кажется, если вам сделали щедрое предложение, очевидно, что ваши самые дорогие предметы, это самые дешевые у противника и наоборот, возможно стоимость дешевых вообще равна 0. Тут сделка точно будет обоюдовыгодной, поэтому борьба уже может идти за «копейки». Если ваш бот ходит первым, то я бы не точно не спешил соглашаться. Если ходит вторым, то пока непонятно что делать, потому что вашу ситуацию тоже могут просчитать и последним ходом предложить уже 9 или 8 и ничего не останется кроме как согласиться. Тут возможно вы и правы, что 10 надо брать сразу.
                                                                                                              • +2
                                                                                                                возможно что такого щедрого предложения больше вам чужой скрипт не предложит


                                                                                                                После небольших опытов с ареной скажу даже больше: некоторые стратегии не соглашаются на свои же сделки. Ну то есть оппонент предлагает сделки на «4, 6, 6, 6» в твою пользу, ты ему на последнем ходу «ладно, предложу тебе твою же последнюю сделку за 6» а он тебе «не хочу», и, как итог 0:0 вместо условных 6:7.
                                                                                                      • 0
                                                                                                        Вообще говоря эти люди в шапочках так же были в масках. Это только читающему статью было известно какой алгоритм использует конкретный человечек, а им действия соперника известны не были. А победа в конкурсе по такой торговле программы использующей определение союзника по паттерну использовала 2 критически важных для это свойства торговли — известные наборы действий (2 варианта) и известное всегда одинаковое количество шагов торговли. В нашем же случае не известны изначальные наборы предметов и торговля может прекратится в любой момент (весьма вероятно на невыгодных для вас условиях).
                                                                                                        • 0
                                                                                                          Не не, там только изначально не было известно ничего каждому о других игроках. Но после старта игры каждый копил индивидуальную статистику по каждому, типа игрок 3 меня обманул в прошлый ход, игрок 5 обманул более одного раза, игрок 2 никогда не обманывал, игрок 6 обманул именно на 1 ходу — и т.д. Можно было собирать предыдущую статистику сделок по каждому сопернику. Так что не в масках, а с открытыми но изначально незнакомыми лицами.
                                                                                                      • 0

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


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

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

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

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

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

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


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


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


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


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

                                                                                                                • 0
                                                                                                                  Да это одно и то же. Окончательное тестирование и заключается в проведении попарных переговоров. Параметры — по умолчанию.
                                                                                                          • 0
                                                                                                            Поправка: не «от 1 до 5 объектов каждого типа», а «в сумме до 6 объектов».
                                                                                                        • 0
                                                                                                          Кстати, в условии говорится про «целую» ценность предметов.
                                                                                                          Означает ли это, что она может быть и отрицательной?
                                                                                                          По-идее, это лучше, чем предметы с нулевой ценностью, так как даёт стимул отдать хоть что-то.
                                                                                                          • +1
                                                                                                            Ценность каждого типа объектов для каждого из партнёров — целое неотрицательное число


                                                                                                          • +2
                                                                                                            А вообще при такой маленькой общей стоимости и набору предметов по идее можно составить же все варианты распределения цен между ними?
                                                                                                            • 0
                                                                                                              А вы загляните в generate.js.
                                                                                                              • 0
                                                                                                                В примере у вас 6 предметов (книга, 2 мяча, 3 шляпы), а генератор с параметрами по-умолчанию (3, 1, 5, 10, 5) генерирует максимум 5. Строка
                                                                                                                let max = this.max_obj-total_count-this.types+i+1;
                                                                                                                Дает max не больше 3 с такими параметрами.
                                                                                                                • +1
                                                                                                                  Вы правы, это ошибка в документации. То есть изначально предполагалось, что это будет возможно.

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

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