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

    Большое спасибо всем участникам конкурса по программированию! Приём решений ещё не закончен, но в полночь на 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: Число сеансов, прерванных данным участником (по причине исключений или некорректных результатов)

    Разумеется, до окончания конкурса ещё осталось время, за которое расстановка сил может измениться. Дерзайте!
    Hola 62,13
    Компания
    Поделиться публикацией
    Комментарии 122
      0
      Четкого лидера не видать пурква-то…
        0
        Это просто меня в таблице нет )))
          0
          Ну это нормально. В спорте тоже часто бывает, что второе место отстаёт от первого на долю секунды.
            0
            Более того, лидер показывает результат всего на 20% лучше, чем example.js
            Конечно, при реальных переговорах, 20% в денежном выражении совсем не мало, но от конкурса алгоритмов интуитивно ожидаешь большего результата
              0
              Проблема example.js в том, что он не умеет договариваться, он только выбирает брать ли то, что само плывет ему «в руки». Если два example.js будут торговать друг с другом, то их среднее количество очков будет стремиться к нулю.
            +2
            Что-то маловато участников для такой-то простой задачки. В позапрошлом (про классификацию слов) за двести было.
            Привет, FlameStorm!
              0
              Не такая уж и простая. И еще далеко не все кто участвует отправил свое решение. Например, я.
                +1
                Привет, justanotherusername! Этот конкурс довольно любопытный, но конечно мне намного больше по душе предыдущий про предка Supaplex'а. Gamedev forever in my heart. Ну и кроме того интуитивно понятно было, чего должен добиться алгоритм и какие примерно решения могут быть :)

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

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

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


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

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

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

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

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

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

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

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

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


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

                                      0
                                      Я искал по всем присланным исходникам, там реально Math.random есть.
                    +3
                    Кстати, в игре с полной информацией (когда известен набор полезностей оппонента) каждый может получить по $7.414496 в среднем за сеанс.
                      0
                      Ваш идентификатор — в автоматическом письме, которое Вы получили после отправки решения.

                      Хм, а я ни какого письма не получил, хотя решение отправлял. Что делать?
                        +1
                        Возможно, опечатались в адресе электронной почты? Посмотрите в форме (она помнит последние значения).
                        0
                        Было бы интересно посмотреть на статистику торговли с собой — насколько скрипт способен торговаться против себя же. В таких случаях скрипты «хочу всё, отдам только ненужное» будут по нулям (за редкими значениями, когда «ненужное» окажется тем самым, на что сам же бот в таком случае согласится).

                        А то как-то грустно смотреть на одностороннюю торговлю, когда свой бот торгуется, а противник всегда выставляет одно и то же предложение.
                          0
                          С собой-то легко — просто запустить haggle.js script.js script.js
                            0
                            я про общую статистику, своего бота я так уже потестировал :)
                            0
                            Думаю, после опубликования решений (числа так 28-го) очень быстро появятся неофициальные результаты. И потестировать в режиме «сам с собой» можно будет, и что угодно.
                            0
                            Что-то я себя в списке не вижу. ID на почту пришел, хотя я 17 отправлял. Т.е. получается, у 82 человек теперь явное преимущество против тех кто не спешил торопиться с отправлением?
                              0
                              Значит, заслали после снапшота.
                                +1

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

                                  0

                                  Больше промежуточных не будет.

                                0
                                Какое преимущество?
                                  0
                                  Неужели это не очевидно: все кто попал в тестирование теперь видят, сколько их боты набрали очков, соревнуясь друг с другом, а не с той ограниченной выборкой, которая участвует на арене, и могут предпринять соответствующие меры, например, подкрутить коэффициенты и т.д., а если участники отправили по несколько ботов с разными стратегиями — так у них теперь просто кладезь полезной статистики, потому что они могут сравнить результаты алгоритмов.
                                    0
                                    > видят, сколько их боты набрали очков
                                    > сравнить результаты алгоритмов

                                    Эти результаты в зачёт не пойдут. В зачёт пойдут результаты игр top50 между собой. Эрго, промежуточные результаты бесполезны (разве что могут намекнуть, попадёшь в первую полусотню или нет — но туда попасть довольно просто.)
                                      0
                                      Вы так рассуждаете, будто номер победитель определяется случайным образом. Не хочу с вами спорить.
                                        +1
                                        А так и будет — лотерея среди сильных решений.
                                0
                                При попытке залить код сегодня:
                                Submissions are no longer accepted after the deadline

                                0
                                Может быть не буду первым, кто это предлагает, но, кажется, стоит запретить посылать нулевые предложения. Это бестолковая растрата статистики. Встречаю сегодня очень часто.
                                  0
                                  Разумеется, за неделю до окончания конкурса правила менять не будем.
                                    0
                                    Вряд ли в top50 попадёт много таких решений.
                                    0
                                    Submissions are no longer accepted after the deadline
                                    0
                                    Один человек может отправлять толко одно решение? Нельзя ли отправить два или три(не в «сговоре»)?
                                      0
                                      По духу правил — нельзя. На практике, разумеется, у нас нет никакого способа это «вычислить».
                                      0
                                      А ТЫ опубликовал(а) своё решение на GitHub?
                                      github.com/indutny/haggling_rl
                                      github.com/morozec/HolaHaggling
                                        +2
                                        Как показывает практика, с этим иногда лучше повременить )))
                                          0
                                          было бы забавно, если бы половина участников выложила исходники
                                          0
                                          Все, кто зашлёт дубликаты этих решений (кроме их изначальных авторов, разумеется), будут дисквалифицированы.
                                            0
                                            Не раскроете детали «технического инцидента»? Простое любопытство, у каждого из нас найдется такая история.
                                              0
                                              Решения хранились в Instance Storage, по своей сути временном. Стали переконфигурировать виртуалку и — фьють!
                                          0
                                          Ну что, ждем очередной анонс продления на неделю?
                                            0
                                            Не надо ))
                                            Я уже устал думать. За лишние две недели все равно ничего не улучшил, зато мозг поизносился.
                                              0
                                              Ну, базовый алгоритм у всех сильных ботов скорее всего одинаковый будет. Как мне кажется, тут вообще единственное решение, вопрос только в дополнительных вариациях.
                                                0
                                                Гораздо интереснее будет встретить совершенно непредсказуемый и нестандартный алгоритм, который оставит все наши решения далеко позади. Если же такого не найдется, то как бы интрига уже не та :)
                                                  0
                                                  Предварительно тестирование показало, что шансы на такое чудо невысокие.
                                                  0
                                                  Так какой он, базовый алгоритм? Почему никто не делится идеями? Все боятся раскрыть тайну своего алгоритма до предварительных результатов )))
                                                    +2
                                                    Мое видение «базового» алгоритма: имеется набор предполагаемых цен для противника и конечное число возможных предложений. В таком случае можно сформировать список предложений, которые выгодны нам и хоть сколько-то выгодны противнику, т.е. сразу можно выбросить варианты, где один из игроков получит, например, меньше 30% в любом раскладе. Сортируем такой список по некоторой функции (например, по суммарной выгоде) и предлагаем верхнюю позицию оппоненту. Если оппонент отказывается, то либо наше предположение о ценах неверное, либо противник рассчитывает на большую выгоду для себя. Производим коррекцию и выдаем следующий по списку вариант. Дополнительные выводы делаются на основе предложений противника и отдельно обрабатывается последний ход.

                                                    Параметры:
                                                    — список предложений сортируется по правилу F. Например, {F=max(S1+S2); F >= 0.6}
                                                    — предложение оппонента мы оцениваем с точки зрения «он бы не отдал нам то, что дает ему в сумме более N денег» и перестраиваем предположение о ценах
                                                    — отказ оппонента мы воспринимаем как «для него ценность этих вещей меньше M» и снова перестраиваем предположение о ценах
                                                    — если нам предлагают вариант больше L, то соглашаемся
                                                    — последним ходом соглашаемся на все, что выгоднее K, вне зависимости от того, сколько получит противник

                                                    Функция F + набор коэффициентов (N,M,L,K) и определяет поведение алгоритма — «жадный», «наивный», «рисковый», «сбалансированный» и т.д. По большому счету, задача сводится к нахождению идеальных коэффициентов на арене и собственных тестах.

                                                    Конечно же, алгоритм может включать какие-то небольшие улучшения, которые и могут перетянуть чашу весов. Частные случаи вроде «никогда не соглашаться последним ходом» это на самом деле вырожденные значения каких-то из коэффициентов. Поведение example.js тоже можно выразить этим алгоритмом с коэффициентами (L = 0.5; K = 0; M = 1; N = 1) и отсутствием продвижения по списку вариантов.

                                                    Код на C#, включая транслированный в JS вариант через Bridge.Net с ручной чисткой:
                                                    github.com/Nomad1/Detective

                                                    А вот что хочется увидеть, так это совершенно нестандартное решение, без предсказаний и поисков компромиссов. Может с обучаемой нейросетью, может с непонятной логикой, дающей отличный результат, может с продвинутым блефом или угадыванием карт противника странными ходами.
                                                      +1
                                                      Во-во, практически мой алгоритм, только конкретные подходы немного другие, а абстрактная теория именно такая.
                                                        0
                                                        Вы чертовы гении! У меня сошлось только то, что нужно коэффициенты подбирать и обрабатывать последний ход ))
                                                        И вообще думать над этой задачей долго не хотелось, поэтому сделал решение простое как валенок.

                                                        Соглашаюсь сразу на 8 и более баксов. Тут я пожадничал, наверное ))
                                                        Сортирую все предложения по максимальной выгоде для себя. Предполагаю в начале одинаковую ценность объектов для противника и предлагаю вариант, максимальный для меня и не нулевой для него. После каждого хода уточняю ценности объектов противника. Для этого в два раза уменьшаю ценности объектов, от которых он отказался. Сумма при этом станет меньше 10, поэтому остаток распределяю поровну между объектами. При такой манипуляции ценности объектов будут нецелыми, поэтому ищу в списке ценностей вариант максимально близкий к вычисленному. Опять сортирую список предложений, выкинув предыдущие предложения и учтя новые ценности объектов противника.

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

                                                        Были еще идеи улучшений, но не рискнул их использовать в условиях, когда невозможно определить, какой эффект они дают. На серверах рейтинг в течение дня прыгал очень сильно. Алгоритм вроде бы точно должен был улучшиться, а ты опускаешься вниз. Или наоборот, ничего не менял, а стою первым в рейтинге.
                                                          0
                                                          Кстати, наблюдая за тем, как торгуется мой бот, заметил, что он почти всегда получает меньше на последнем раунде. А получить выгодное предложение сразу получается редко, поэтому до последнего раунда доходит очень часто.
                                                          Отсюда возник вопрос. Можно ли выиграть у всех, проигрывая каждому в отдельности? В теории, конечно, можно. Но каковы шансы сделать это на практике.
                                                          0
                                                          Не понял как это «сразу можно выбросить варианты, где один из игроков получит, например, меньше 30% в любом раскладе». Допустим, у нас по одному объекту каждого типа. Варианты получаются: 001, 010, 011, 100, 101, 110. Где здесь меньше 30% в любом раскладе?
                                                            0
                                                            Предположим, игра началась с такими правилами:
                                                            предметы: 1,1,1
                                                            наши цены: 0,4,6
                                                            цены противника: 3,3,4

                                                            Это весьма неприятный случай и мы можем сказать, только что у противника цена каждого предмета от 0 до 10 и единственное, что можно выбросить это набор цен 0,4,6, потому что он уже занят нами. Но из таблицы ходов сразу можно убрать то, что гарантированно дает нечестный результат — «все мне», «все противнику» и «я не получаю ничего».

                                                            Существующие варианты ходов:
                                                            011: my income 10, enemy average 3.384615, enemy median 3, range [0, 10] — валидный ход, выглядит замечательно
                                                            111: my income 10, enemy average 0, enemy median 0, range [0, 0] — не валидный ход, «мне все, ему ничего»
                                                            001: my income 6, enemy average 6.707692, enemy median 6, range [0, 10] — хороший компромиссный вариант
                                                            101: my income 6, enemy average 3.323077, enemy median 3, range [0, 10] — плохой вариант, но в целом можно попробовать
                                                            010: my income 4, enemy average 6.676923, enemy median 7, range [0, 10] — мы получим 4, а противник с большой вероятностью 6-7. это валидный ход, но желательно оставить его на крайний случай
                                                            110: my income 4, enemy average 3.292308, enemy median 4, range [0, 10] — скорее всего, все получат мало.
                                                            000: my income 0, enemy average 10, enemy median 10, range [10, 10] — мой доход 0, не валидный ход
                                                            100: my income 0, enemy average 6.615385, enemy median 7, range [0, 10] — мой доход 0, не валидный ход

                                                            Тут и к гадалке не ходи, надо пробовать ходить 011 (точнее, отдать 100, т.е. то, что нам не нужно). Если противник откажется, значит мы можем спокойно выбросить варианты, в которых цена его первого предмета составляет 8, 9, 10 (предположение зависит от коэффициентов).
                                                            Встречное предложение было 000 (скрипт example.js), оно нам ничего не говорит.

                                                            Таким образом на второй ход уже имеем такую таблицу:
                                                            001: my income 6, enemy average 6.440678, enemy median 3, range [0, 10]
                                                            101: my income 6, enemy average 3.59322, enemy median 0, range [0, 10]
                                                            010: my income 4, enemy average 6.40678, enemy median 10, range [0, 10]
                                                            110: my income 4, enemy average 3.559322, enemy median 7, range [0, 10]

                                                            Посылаем предложение 001 (противнику достается 110).

                                                            Если он отказывается, то получается такая таблица:
                                                            101: my income 6, enemy average 2.285714, enemy median 3, range [0, 7] — уже точно известно, что оппонент получит не больше 7
                                                            010: my income 4, enemy average 7.714286, enemy median 7, range [3, 10] — гарантированно знаем, что оппонент получит не меньше 3
                                                            110: my income 4, enemy average 5.314286, enemy median 5, range [3, 10]

                                                            Но т.к. это был example.js, то он согласился и получил 6 баллов, мы получили столько же.
                                                            Конечно же, у противника цены могли быть 5,5,0 либо 0,10,0 и тогда бы второй ход закончил игру со счетом 6/10, но наша цель не обставить противника как можно больше, а уйти с максимумом дохода. Бывают случаи, когда вообще все предположения ошибочны, а реальная цена где-то на краю диапазона, но у нас нет данных для других предсказаний, ничего поделать с этим нельзя.

                                                              0
                                                              Теперь понятно.
                                                              А вот это откуда следует: «единственное, что можно выбросить это набор цен 0,4,6, потому что он уже занят нами»? В условиях такого не видел. Разве не могут быть одинаковые ценности?
                                                                0
                                                                Если посмотреть github организаторов, то там видно, что одинаковые цены не назначаются. Это не очень сильно помогает, но хоть что-то.
                                                          +1
                                                          Следуя простейшей логике выгоды:

                                                          1. Исключаем все предметы с нулевой ценностью для нас, т.к. смысла торговаться за них нет, будем отдавать их сразу.
                                                          2. Из оставшихся предметов генерируем все возможные комбинации, группируем по суммарной ценности (например, все комбинации, которые дают $10, $9, $8...), сортируем группы в порядке убывания
                                                          3. Начинаем торговаться, начиная с максимально выгодных комбинаций

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

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

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

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

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

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

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

                                                          Например, у нас 4 позциции товаров [A, B, C, D] с количеством [2, 3, 1, 2] и общая сумма $12.
                                                          Предложения, поступившие от оппонента [0, 0, 0, 1], [0, 0, 0, 2], [0, 0, 1, 0].
                                                          По логике, описанной выше, если бы первым предложением было [0, 0, 0, 2], то товар D получил бы нулевую стоимость. Но т.к. первым предложением была часть товара, поэтому стоит предположить, что товар имеет не нулевую ценность (но нельзя сказать, что он стоит 1). Поэтому товару D присваиваем 0.001, а товару C — 0.002. Теперь надо вычислить примерную стоимость товаров A и B. Увеличиваем минимальную стоимость товаров C, D до 1, умножаем на количество, получаем $3.
                                                          $12 — $3 = $9. Именно столько приходится на оставшиеся два товара по нашим предположениям. У нас осталось 2 товара A и 3 товара B. У товара A предполагаемая стоимость будет 9 / 2 = $4, у товара B ~ 9 / 3 = $3.

                                                          Итого примерная оценка товаров противника для сортировки будет [4, 3, 0.002, 0.001]

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

                                                          Всё просто
                                                            0
                                                            И почти полностью соответствует моему методу, описанному выше, методу тов @BingiBongo и наверняка другим «стандартным» решениям. Т.е. по-сути, наши решения будут соревноваться лишь в мелких оптимизациях, коэффициентах, ну и удачливости. Что хочется увидеть, так это, решение-победитель, где алгоритм в 5 строк, но есть простыня каких-то чисел. Или совершенно не предсказуемую логику, в общем забеге вырывающуюся на корпус вперед.
                                                              0
                                                              Типо того. Но, боюсь, что текущие ограничения сильно уменьшают шансы «на корпус вперёд». Мне больше понравилась площадка LARGE, там было интереснее торговаться. Хотя практически все решения сводятся к конечной логике, которую проще реализовать без использования нейронных сетей и супер алгоритмов.
                                                                0
                                                                Т.е. по-сути, наши решения будут соревноваться лишь в мелких оптимизациях, коэффициентах, ну и удачливости.

                                                                Как и в прошлых конкурсах.
                                                                В jsdash надо было просчитывать ходы и строить оптимальный маршрут. Было два варианта алгоритмов: считать и передвигаться на каждый ход или считать, пропуская ходы, а потом ходить по рассчитанному. Ожидаемо победил второй вариант.
                                                                В классификаторе слов тоже было два варианта алгоритмов — одни честно пытались ужать словарь, другие считали повторы слов. Ожидаемо победил второй вариант ))
                                                                Здесь пока все описывают один алгоритм. Хотелось бы конечно увидеть что-то особенное.
                                                      0
                                                      Письмо «JS challenge: please resubmit your solution» сегодняшним числом, означает, что предыдущий submission снова потерян? Или это просто напоминалка, сделанная левой ногой без проверок, залито обновленное решение или нет?
                                                        0
                                                        Напоминалка. Мы не потеряли решения снова. Просто до сих пор ещё 77 человек не прислали заново.
                                                          0
                                                          Я боюсь, и не пришлют.
                                                          Тут бы очень не помешала еще статья на хабре с извинениями и объяснениями, рассылка с человеческим текстом (текущая похожа на робота или спам), ну и все-таки фильтрация, есть ли от конкретного человека апдейт или нет.
                                                            0
                                                            С последнего комментария прислали 10.
                                                              0
                                                              А насколько изменилось количество не присланных? )
                                                                0
                                                                Я это и имею в виду. Теперь уже 65 не хватает.
                                                                  0
                                                                  Таки решения приняты? Не потерялись? Уже можно начать обсуждать решения, не боясь выдать секреты? ))
                                                                    0
                                                                    Да, приём решений окончен, резервная копия в надёжном месте сделана, идёт тестирование.
                                                            0
                                                            Т.е. предварительных результатов еще неделю ждать?
                                                          0
                                                          Ну что там — сегодня же должны быть предварительные результаты?
                                                            0
                                                            Досчитывается ещё. Поставили на 250 сидов первый тур.
                                                              +1
                                                              Публикация будет по той же ссылке, что и предыдущие?
                                                                0
                                                                На GitHub + пост здесь.
                                                                0
                                                                Хорошее субботнее настроение натолкнуло на некоторые расчеты в ожидании результатов :)

                                                                На 17 июля было 82 решения. Логично предположить, что они были забекаплены во время промежуточного теста. Затем была информация, что осталось прислать заново еще 77 решений. Таким образом мы можем предположить, что в первом туре не меньше 82 решений, а всего в конкурсе порядка 159 участников (+-50)*.
                                                                Просчитаем разумный максимум, например с 201 решением (число с потолка, для удобства подсчетов), тогда есть всего 40200 комбинаций участников и для 250 сидов надо провести 100500 * 10^2 игр. Если считать, что каждая игра идет до 10 ходов и каждый ход занимает секунду, мы получим время тестирования в ~100 миллионов секунд, т.е. около трех лет (1161.2 дней).
                                                                Теперь просчитаем по минимуму: 82 решения, время на партию около 0.1с (примем инициализацию и запись результата бесплатными). Время такого теста 166 050 секунд, это ~2 дня.
                                                                Попробуем просчитать средний вариант: 159 решений, время на партию 0.5с (включая не-бесплатную инициализацию и запись результата). Получается весь тест займет 3 140 250 секунд, это ~872 часа (около 36 дней).
                                                                Задача отлично распараллеливается по сидам, тогда последний вариант на 8 ядрах будет считаться 109 часов, т.е. четыре с половиной дня + некоторое время на синхронизацию и накладные расходы.

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

                                                                * мы не знаем, насколько числа 77 и 82 пересекаются между собой и не знаем, сколько человек не попало в оба списка, поэтому это все гадание на кофейной куще. Собственно, как и сама суть конкурса.
                                                                  +2
                                                                  Было бы странно предположить, что организаторы будут ждать 36 дней
                                                                  Не факт )
                                                                    0
                                                                    Может опять все «пожрал долгоносик» =)
                                                                      +1
                                                                      Осталось 22 часа обсчёта. Плюс ещё время мне написать пост.
                                                                        +1
                                                                        Итого 36 дней.
                                                                          0
                                                                          Какие 36 дней? Приём решений закрылся 3 августа.
                                                                            +1
                                                                            Это была одна шутка юмора.
                                                              0
                                                              5b6194a3adb0280402fd774c
                                                              5b6194d9adb0280402fd774d
                                                              5b6194f3adb0280402fd774e

                                                              Вот жеж лидеры мыслили одинаково :D
                                                                0
                                                                И это только первый раунд. Еще 36 дней ждать?
                                                                  0
                                                                  Как получена цифра 36 дней?
                                                                0
                                                                В финал проходят первые 50, несмотря на незначительно измененные копии одинаковых решений?
                                                                  0
                                                                  Первые 50 прошли.

                                                                  Если вы видите признаки сговора между несколькими решениями, пожалуйста, сообщите об этом. Если информация подтвердится, нарушители будут дисквалифицированы.
                                                                  +1
                                                                  5b61b487adb0280402fd7751
                                                                  5b61aac7adb0280402fd774f
                                                                  и выше я писал
                                                                  Очевидно — решения из одной головы
                                                                  Очевидно — все они повлияли на тех, кто мог бы быть в 50.
                                                                  Я могу продолжить дальше охоту на ведьм, но нужно ли это?

                                                                  Я просто поиском по коду нашел уже 5 скриптов жуликов :)
                                                                    0
                                                                    Эти выглядят как самостоятельные, достаточно сильные решения, а не «спойлеры», созданные для продвижения других.

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

                                                                      Это два идентичных решения которые различаются только в настройках коэффициентов. Автор мог заслать таким образом еще сотню вариантов пробуя разные настройки. Никогда не видел чтобы при выступлении команды ее участники отсылали индивидуальные решения, это немного противоречит смыслу командного выступления.
                                                                        0
                                                                        Я выбрал такое правило, потому что, если бы запретил, то не смог бы на практике контролировать соблюдение запрета. Пришлось бы определять какую-то метрику «достаточной похожести», а люди обходили бы её, внося искажения в свои версии. Короче, нафиг нужна такая забота.
                                                                          +1
                                                                          Комьюнити справилось бы с поиском, да и проверить надо не всех, а только лидеров, как в спорте. Да и внести искажения так, чтобы стало полностью по-другому, весьма не просто даже для одного клона, а сделать 3-4 версии полностью визуально различных, но с одной логикой, и вовсе задача сравнимая по сложности с исходной. Идеального решения этой проблемы наверное нет, но видеть абсолютные клоны прошедшими во 2-й тур все же странно.
                                                                    0
                                                                    5b64ba5badb0280402fd77cd
                                                                    5b646019adb0280402fd779c
                                                                      0
                                                                      То же самое и здесь.
                                                                        0
                                                                        Именно :) То же самое.
                                                                        594,595d593
                                                                        <     const bestJokerOfferSoFar = this.joker.history.offers
                                                                        <       .reduce((acc, elm) => Math.max(acc, elm.batmanValue), 0);
                                                                        600c598
                                                                        <     if (batmanValueToJokerOffer >=  5) {
                                                                        ---
                                                                        >     if (batmanValueToJokerOffer >= 1) {
                                                                        605,611d602
                                                                        <     if (batmanValueToJokerOffer >= this.config.acceptableThresholdForLastPlay * this.total) {
                                                                        <       this.log(`accept offer. value ${batmanValueToJokerOffer} worth more than ${this.config.acceptableThresholdForLastPlay * 100}% of ${this.total}`);
                                                                        <       this.counterOfferRoot = "JTYOL_AC";
                                                                        <       return;
                                                                        <     }
                                                                        <     this.log(`reject offer. too lower offer ${batmanValueToJokerOffer} for last round תמות נפשי עם פלשתים`);
                                                                        <     this.counterOfferRoot = "JTYOL_RJ";
                                                                        
                                                                      +1
                                                                      Что значит самостоятельные решения? Это решения, в которых немного отличается настройка аппетита и уровня согласия. Это решения, которые дают автору (авторам) колоссальные преимущества.

                                                                      Но если так можно было… Значит все честно :) Снимаю шляпу (по три). И укатываю свой мяч.
                                                                        0
                                                                        Один «спойлер», даже полностью поддающийся своему «боссу», никак не может дать ему преимущество больше, чем в 10 очков. Если оно сыграет 0–0 со всеми, кроме «босса», а «боссу» сольёт 10–0, то итоговый счёт «босса» в результате этого будет всего на 10 очков выше, чем был бы без «спойлера». Колоссальным преимуществом это не назовёшь. Таких «спойлеров» нужны десятки, чтобы подняться хотя бы на одно место, и они не имеют шансов пройти в финал.

                                                                        Здесь же мы видим просто два похожих решения. Каждое из них попало бы в финал и без другого.
                                                                          +1
                                                                          Наверное я не совсем очевидно формулирую свое возмущение :)
                                                                          Я не имею ввиду «спойлеры», «помогаторы», «прочее».
                                                                          Я вижу, что в списке топ-50 встречаются скрипты практически одинаковые. И недоумеваю. Почему автор самого сильного на данный момент решения не догадался прислать его 10 раз и утереть всем нос. Он же тоже может быть «команда».
                                                                          Да и если по существу — такое условие, как разрешить плодить решения, которые согласны либо на 70%, либо 80% и тд от всей возможной суммы и только этим — не было оговорено в основном описании условия задачи.
                                                                          Работает команда — приз на команду. Хорошо, что не было(а может и была, я не все проверил) команды из 40 человек.
                                                                            +1
                                                                            Можно делать проще: каждый участник отправляет любое свое решение в трех экземплярах. Тогда кто бы не победил, весь призовой фонд достанется одному человеку. Кроме мб мини-наград по 400$.
                                                                          +1
                                                                          А вот еще решения, у которых подозрительно много одинакового кода:
                                                                          17 — 5b64e7f2adb0280402fd77ea
                                                                          26 — 5b64eb06adb0280402fd77f3
                                                                          27 — 5b64e7baadb0280402fd77e8
                                                                          35 — 5b64eaabadb0280402fd77f2
                                                                          39 — 5b64e9c6adb0280402fd77ef
                                                                          71 — 5b64e93badb0280402fd77ee
                                                                          Глазками тяжело искать, устал. Вот бы инструмент, который ищет похожесть и показывает степень похожести.
                                                                            +1
                                                                            И вот еще копии с точностью до опечаток в комментариях:
                                                                            31 — 5b646257adb0280402fd779e
                                                                            66 — 5b645263adb0280402fd7790
                                                                              +1
                                                                              И еще
                                                                              36 — 5b64575dadb0280402fd7794
                                                                              63 — 5b648f06adb0280402fd77af
                                                                                +1
                                                                                Аж целых 4 копии:
                                                                                46 — 5b649223adb0280402fd77b3
                                                                                51 — 5b649339adb0280402fd77b5
                                                                                58 — 5b64b128adb0280402fd77c8
                                                                                62 — 5b5f368eadb0280402fd7705
                                                                                  0
                                                                                  Что все так удивились, что много похожих и одинаковых решений? Правилами конкурса было обозначено, что можно отправлять столько решений сколько людей. Было сразу понятно, что будут и полные копии и несколько модификаций одного решения. Не вижу в этом проблемы, пока все решения играют честно.

                                                                                  И как сразу все говорили, будет решать рандом, если даже одинаковые/похожие решения раскидало на 10-30 позиций.
                                                                                    +2
                                                                                    можно отправлять столько решений сколько людей

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


                                                                                      По правилам именно «физических людей», а не почтовых аккаунтов.

                                                                                      • Один участник может использовать для отправки решения только один адрес электронной почты. Отправка множества решений, находящихся в «сговоре», с разных адресов запрещена; все решения, участвующие в такой схеме, будут дисквалифицированы.
                                                                                      • Нам нужно знать Ваше полное имя, но если Вы хотите, мы опубликуем вместо него псевдоним. Мы сохраним Ваш адрес электронной почты в тайне.
                                                                                        0
                                                                                        Да, но это, к сожалению, технически невозможно проконтролировать. Было бы возможно, если бы на конкурс была предварительная регистрация, и кто не успел зарегистрироваться до дня публикации задачи, тот не может участвовать.
                                                                              0
                                                                              Некоторые решения так похожи, что у них даже место одинаковое:
                                                                              21 5b64e9e0adb0280402fd77f0 1202516
                                                                              21 5b64cb2dadb0280402fd77d8 1202516
                                                                              Код при этом существенно отличается, но мы знаем, что чудес не бывает
                                                                              =)
                                                                                0
                                                                                В этом случае, кстати, нет заметного сходства скриптов.
                                                                                  0
                                                                                  Мы все программисты и понимаем, что вариантов получить разный код достаточно, включая трансляцию в другие языки или даже реализацию с нуля. Но чего точно не бывает, так это двух одинаковых результатов разных алгоритмов за 185000 игр.
                                                                                    0
                                                                                    Когда админ выложит 2.2-гигабайтный архив с логами каждого сеанса, вы сможете увидеть, действительно ли эти два скрипта всегда играли одинаково (с одними и теми же детерминированными партнёрами), или же у них именно сумма случайно сошлась.
                                                                                      0
                                                                                      My bad. Там таки все ок, это просто совпадение результата — другие столбцы показывают, что конкретные игры прошли по-разному.

                                                                                      0
                                                                                      Ну вообще-то, если прикинуть, то в таблице присутствует 16471 пар решений. Если поделить на максимально набранное число очков 16471/1242729=0.013. Вероятность совпадения очков у какой-либо пары 1.3%, что не так уж и мало.
                                                                                        0
                                                                                        Да, все верно. Я сначала подумал, что у решений совпали не только суммарные результаты, но и общая статистика, но это не так.
                                                                                  0
                                                                                  Клоны клонами, а всё равно эти «командные» решения вытесняют алгоритмы из нижней части top50. Между тем все призёры будут из верхней десятки первого раунда (хотя пара решений из десятки и упадёт значительно в финальном рейтинге). Я это к тому, что никто не лишается заслуженного приза из-за клонов.

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

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