Конкурс по программированию: Торговля (промежуточные результаты и объявления) +11


Большое спасибо всем участникам конкурса по программированию! Приём решений ещё не закончен, но в полночь на 17 июля мы взяли тот набор решений, который был на тот момент, и провели между ними мини-турнир. В него попали 82 решения.

Но сначала — несколько объявлений.

Конкурс продлевается на неделю


Срок приёма решений продлевается до 27 июля 2018, 23:59:59 UTC. Также на неделю вперёд сдвигаются сроки, в которые будут объявлены результаты конкурса. Мы продлили конкурс для того, чтобы улучшить охват в сезон отпусков.

Уточнения по окончательному тестированию


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

Затравочные значения


Мы публикуем способ, который обещаем использовать для выбора затравочных значений для финального тестирования. Этот способ должен быть однозначным и легко проверяемым, но непредсказуемым. Итак, мы возьмём первый твит из этого Твиттера, который появится там после наступления дедлайна. Трудно поверить, что мы сговорились с Джерри Спрингером, правда? Из твита берём только текст, без картинок и видео. Если в твите нет текста, а только картинка, то берём следующий твит. Ретвиты считаются. Имя ретвитнутого аккаунта не берётся.

Из текста твита мы получим затравочные значения так:

const random_js = require('random-js');
const text = 'The tweet goes here';
const bytes = Array.from(new Buffer(text));
const random = new random_js(random_js.engines.mt19937().seedWithArray(bytes));
for (let i = 0; i<200; i++) // сгенерируем столько, сколько потребуется
    console.log(random.uint32());

Элементы получшившейся последовательности с нечётными номерами, при нумерации начиная с 1 (то есть первый, третий, пятый и так далее) будут использованы как затравочные значения для первого раунда, а с чётными — как дополнительные затравочные значения для финала.

В первом раунде каждая упорядоченная пара решений будет запущена на каждом из не менее 100 затравочных значений (больше, если успеем). В финале будет использовано не менее 100 дополнительных затравочных значений. Сеансы, проведённые в первом раунде между решениями, вышедшими в финал, будут использованы и в финале (но не сеансы между финалистом и решением, не вышедшим в финал). Таким образом, исход финала решат не менее 200 затравочных значений.

Отбор финалистов


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

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

  • Не более половины решений.
  • Не более 50 решений.
  • Только решения, показавшие лучший результат, чем example.js.

Промежуточные результаты


Для промежуточного тестирования мы использовали в качестве затравочных значений натуральные числа от 1 до 50 включительно. Каждая упорядоченная пара, состоящая из различных решений, была запущена на каждом из этих значений. Таким образом, для 82 участников турнир состоял из 332100 сеансов; каждое из решений поучаствовало в 8100 сеансах.

Пока что вместо имён участников — идентификаторы решений. Ваш идентификатор — в автоматическом письме, которое Вы получили после отправки решения. Не возбраняется в комментариях к этому посту раскрывать, что такое-то решение — Ваше.

Обратите внимание, что на 59, 60 и 61 местах расположились копии скрипта example.js. Интересно, что 21 из 82 решений показали более низкий результат, чем наш примитивный пример. (Почему три копии одного и того же скрипта показали слегка разные результаты? Потому что некоторые решения используют Math.random, и результаты сеансов с их участием не воспроизводимы.)

Таблицу промежуточных результатов можно увидеть на GitHub. Условные обозначения:

  • S: Сумма набранных очков (это и есть предмет соревнования)
  • S/N: Средний результат сеанса
  • A: Число сеансов с достигнутым соглашением
  • A/N: Процент сеансов с достигнутым соглашением
  • S/A: Средний результат сеанса с достигнутым соглашением
  • X: Число сеансов, прерванных данным участником (по причине исключений или некорректных результатов)

Разумеется, до окончания конкурса ещё осталось время, за которое расстановка сил может измениться. Дерзайте!

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (36):

  1. datacompboy
    /#18900417

    Четкого лидера не видать пурква-то…

    • Spiceman
      /#18902393

      Это просто меня в таблице нет )))

    • feldgendler
      /#18902935

      Ну это нормально. В спорте тоже часто бывает, что второе место отстаёт от первого на долю секунды.

  2. justanotherusername
    /#18901695

    Что-то маловато участников для такой-то простой задачки. В позапрошлом (про классификацию слов) за двести было.
    Привет, FlameStorm!

    • Spiceman
      /#18902383

      Не такая уж и простая. И еще далеко не все кто участвует отправил свое решение. Например, я.

    • FlameStorm
      /#18902687 / +1

      Привет, justanotherusername! Этот конкурс довольно любопытный, но конечно мне намного больше по душе предыдущий про предка Supaplex'а. Gamedev forever in my heart. Ну и кроме того интуитивно понятно было, чего должен добиться алгоритм и какие примерно решения могут быть :)

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

      • justanotherusername
        /#18902781

        всё сильно зависит от остальных решений, с которыми будет вести диалог твоё.

        Как и в жизни.

      • feldgendler
        /#18902793

        Но в прошлый раз тоже было меньше участников, чем в позапрошлый. Пока что классификатор слов — самый массовый конкурс. Хотя там чуть ли не треть решений была фуфельных, типа return false.

        • FlameStorm
          /#18902833 / +1

          Суровые однако решения. Ладно хоть не выиграли. ) Я кстати читал, что в том конкурсе происходило, были и решения наоборот с другой стороны хардкорности.


          Кстати по лимитам тут озвученным — а example.js гарантированно будет участвовать? И если вдруг все сторонние участники закинут решения отличные (по принимаемым решениям о сделках) от example.js, этот пункт ограничений будет снят с рассмотрения, или таки если никто не отправит клон экзампла, то он будет отправлен by Alexey (вне конкурсной таблицы)?

          • feldgendler
            /#18902851

            Сейчас уже есть три копии example.js. Их «авторы», конечно, могут закачать на их место что-нибудь новое — в этом маловероятном случае, да, добавлю одну копию от себя.

            • FlameStorm
              /#18902907

              Могло быть и 4 копии, если б не успел увидеть в телеграм канале сообщение о пробном забеге) Текущая версия не всегда уже отправлена как решение. Вполне вероятно, что из этих трёх останется меньше трёх. Но добавят новых example.js подоспевшие участники ))

              • feldgendler
                /#18902929

                А какая, собственно, у людей мотивация заливать копию example.js? Никогда этого не понимал, но в каждом конкурсе несколько человек это делают.

            • FlameStorm
              /#18902915

              Кстати вопрос — если сиды идентичные и у всех абсолютно равные условия забега, как вообще хоть на 1 очко разницы могло получиться у тех трёх копий example.js из таблицы?

              • feldgendler
                /#18902933

                Я же там написал — потому что в некоторых решениях используется Math.random.

                • FlameStorm
                  /#18902971

                  Не понятно. Так копии или не копии example.js? Те которые на строчках 59, 60 и 61

                  • feldgendler
                    /#18902977

                    Эти три — точные копии. Но есть ещё другие решения, в которых встречается Math.random. Из-за них у всех чуть колеблются результаты, ведь они дают вклад в итоговый счёт каждого решения.

                    • FlameStorm
                      /#18903011

                      А, спасибо, теперь ясно. Что-то сразу не догнал до этого момента.


                      У меня кстати у самого используется рандом, но не Math'овский, а собственная копия простейшего из генераторов. Уже не помню почему сделал именно так, наверное для хоть и похожести на случайное поведение, но предсказуемости — сид задаётся на основе входных данных торгов, потому при том же первом ходящем, том же количестве раундов и тех же количествах и ценах вещей мой бот сыграет всегда одинаково. Так что если что, я рандома остальным не насыпал, то был кто-то ещё. :)

                      • feldgendler
                        /#18903459

                        Я искал по всем присланным исходникам, там реально Math.random есть.

  3. justanotherusername
    /#18902827 / +3

    Кстати, в игре с полной информацией (когда известен набор полезностей оппонента) каждый может получить по $7.414496 в среднем за сеанс.

  4. CrazyNiger
    /#18902981

    Ваш идентификатор — в автоматическом письме, которое Вы получили после отправки решения.

    Хм, а я ни какого письма не получил, хотя решение отправлял. Что делать?

    • feldgendler
      /#18903145 / +1

      Возможно, опечатались в адресе электронной почты? Посмотрите в форме (она помнит последние значения).

  5. Gromo
    /#18904649

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

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

    • feldgendler
      /#18904677

      С собой-то легко — просто запустить haggle.js script.js script.js

      • Gromo
        /#18904687

        я про общую статистику, своего бота я так уже потестировал :)

  6. BingoBongo
    /#18904683

    Что-то я себя в списке не вижу. ID на почту пришел, хотя я 17 отправлял. Т.е. получается, у 82 человек теперь явное преимущество против тех кто не спешил торопиться с отправлением?

    • feldgendler
      /#18904685

      Значит, заслали после снапшота.

      • Spiceman
        /#18905707 / +1

        А еще будут предварительные результаты? Или теперь уже только окончательное тестирование?

  7. Nomad1
    /#18906023

    При попытке залить код сегодня:

    Submissions are no longer accepted after the deadline

  8. AndrewIl
    /#18906345

    Может быть не буду первым, кто это предлагает, но, кажется, стоит запретить посылать нулевые предложения. Это бестолковая растрата статистики. Встречаю сегодня очень часто.

    • feldgendler
      /#18906347

      Разумеется, за неделю до окончания конкурса правила менять не будем.

  9. RJA
    /#18906487

    Submissions are no longer accepted after the deadline

  10. NoOn3
    /#18906569

    Один человек может отправлять толко одно решение? Нельзя ли отправить два или три(не в «сговоре»)?

    • feldgendler
      /#18906571

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