Comments 124
Четкого лидера не видать пурква-то…
Это просто меня в таблице нет )))
Ну это нормально. В спорте тоже часто бывает, что второе место отстаёт от первого на долю секунды.
Более того, лидер показывает результат всего на 20% лучше, чем example.js
Конечно, при реальных переговорах, 20% в денежном выражении совсем не мало, но от конкурса алгоритмов интуитивно ожидаешь большего результата
Конечно, при реальных переговорах, 20% в денежном выражении совсем не мало, но от конкурса алгоритмов интуитивно ожидаешь большего результата
Что-то маловато участников для такой-то простой задачки. В позапрошлом (про классификацию слов) за двести было.
Привет, FlameStorm!
Привет, FlameStorm!
Не такая уж и простая. И еще далеко не все кто участвует отправил свое решение. Например, я.
Привет, justanotherusername! Этот конкурс довольно любопытный, но конечно мне намного больше по душе предыдущий про предка Supaplex'а. Gamedev forever in my heart. Ну и кроме того интуитивно понятно было, чего должен добиться алгоритм и какие примерно решения могут быть :)
Точнее, тут просто не видно никакой возможности существования алгоритма, работающего лучше всех и могущего взять призовое место, — всё сильно зависит от остальных решений, с которыми будет вести диалог твоё.
Точнее, тут просто не видно никакой возможности существования алгоритма, работающего лучше всех и могущего взять призовое место, — всё сильно зависит от остальных решений, с которыми будет вести диалог твоё.
всё сильно зависит от остальных решений, с которыми будет вести диалог твоё.
Как и в жизни.
Но в прошлый раз тоже было меньше участников, чем в позапрошлый. Пока что классификатор слов — самый массовый конкурс. Хотя там чуть ли не треть решений была фуфельных, типа
return false.Суровые однако решения. Ладно хоть не выиграли. ) Я кстати читал, что в том конкурсе происходило, были и решения наоборот с другой стороны хардкорности.
Кстати по лимитам тут озвученным — а example.js гарантированно будет участвовать? И если вдруг все сторонние участники закинут решения отличные (по принимаемым решениям о сделках) от example.js, этот пункт ограничений будет снят с рассмотрения, или таки если никто не отправит клон экзампла, то он будет отправлен by Alexey (вне конкурсной таблицы)?
Сейчас уже есть три копии
example.js. Их «авторы», конечно, могут закачать на их место что-нибудь новое — в этом маловероятном случае, да, добавлю одну копию от себя.Могло быть и 4 копии, если б не успел увидеть в телеграм канале сообщение о пробном забеге) Текущая версия не всегда уже отправлена как решение. Вполне вероятно, что из этих трёх останется меньше трёх. Но добавят новых example.js подоспевшие участники ))
Кстати вопрос — если сиды идентичные и у всех абсолютно равные условия забега, как вообще хоть на 1 очко разницы могло получиться у тех трёх копий example.js из таблицы?
Я же там написал — потому что в некоторых решениях используется
Math.random.Не понятно. Так копии или не копии example.js? Те которые на строчках 59, 60 и 61
Эти три — точные копии. Но есть ещё другие решения, в которых встречается
Math.random. Из-за них у всех чуть колеблются результаты, ведь они дают вклад в итоговый счёт каждого решения.А, спасибо, теперь ясно. Что-то сразу не догнал до этого момента.
У меня кстати у самого используется рандом, но не Math'овский, а собственная копия простейшего из генераторов. Уже не помню почему сделал именно так, наверное для хоть и похожести на случайное поведение, но предсказуемости — сид задаётся на основе входных данных торгов, потому при том же первом ходящем, том же количестве раундов и тех же количествах и ценах вещей мой бот сыграет всегда одинаково. Так что если что, я рандома остальным не насыпал, то был кто-то ещё. :)
Кстати, в игре с полной информацией (когда известен набор полезностей оппонента) каждый может получить по $7.414496 в среднем за сеанс.
Ваш идентификатор — в автоматическом письме, которое Вы получили после отправки решения.
Хм, а я ни какого письма не получил, хотя решение отправлял. Что делать?
Было бы интересно посмотреть на статистику торговли с собой — насколько скрипт способен торговаться против себя же. В таких случаях скрипты «хочу всё, отдам только ненужное» будут по нулям (за редкими значениями, когда «ненужное» окажется тем самым, на что сам же бот в таком случае согласится).
А то как-то грустно смотреть на одностороннюю торговлю, когда свой бот торгуется, а противник всегда выставляет одно и то же предложение.
А то как-то грустно смотреть на одностороннюю торговлю, когда свой бот торгуется, а противник всегда выставляет одно и то же предложение.
Что-то я себя в списке не вижу. ID на почту пришел, хотя я 17 отправлял. Т.е. получается, у 82 человек теперь явное преимущество против тех кто не спешил торопиться с отправлением?
Значит, заслали после снапшота.
Какое преимущество?
Неужели это не очевидно: все кто попал в тестирование теперь видят, сколько их боты набрали очков, соревнуясь друг с другом, а не с той ограниченной выборкой, которая участвует на арене, и могут предпринять соответствующие меры, например, подкрутить коэффициенты и т.д., а если участники отправили по несколько ботов с разными стратегиями — так у них теперь просто кладезь полезной статистики, потому что они могут сравнить результаты алгоритмов.
При попытке залить код сегодня:
Submissions are no longer accepted after the deadline
Может быть не буду первым, кто это предлагает, но, кажется, стоит запретить посылать нулевые предложения. Это бестолковая растрата статистики. Встречаю сегодня очень часто.
Submissions are no longer accepted after the deadline
UFO just landed and posted this here
А ТЫ опубликовал(а) своё решение на GitHub?
github.com/indutny/haggling_rl
github.com/morozec/HolaHaggling
github.com/indutny/haggling_rl
github.com/morozec/HolaHaggling
Как показывает практика, с этим иногда лучше повременить )))
Все, кто зашлёт дубликаты этих решений (кроме их изначальных авторов, разумеется), будут дисквалифицированы.
Не раскроете детали «технического инцидента»? Простое любопытство, у каждого из нас найдется такая история.
Решения хранились в Instance Storage, по своей сути временном. Стали переконфигурировать виртуалку и — фьють!
Ну что, ждем очередной анонс продления на неделю?
Не надо ))
Я уже устал думать. За лишние две недели все равно ничего не улучшил, зато мозг поизносился.
Я уже устал думать. За лишние две недели все равно ничего не улучшил, зато мозг поизносился.
Ну, базовый алгоритм у всех сильных ботов скорее всего одинаковый будет. Как мне кажется, тут вообще единственное решение, вопрос только в дополнительных вариациях.
Гораздо интереснее будет встретить совершенно непредсказуемый и нестандартный алгоритм, который оставит все наши решения далеко позади. Если же такого не найдется, то как бы интрига уже не та :)
Так какой он, базовый алгоритм? Почему никто не делится идеями? Все боятся раскрыть тайну своего алгоритма до предварительных результатов )))
Мое видение «базового» алгоритма: имеется набор предполагаемых цен для противника и конечное число возможных предложений. В таком случае можно сформировать список предложений, которые выгодны нам и хоть сколько-то выгодны противнику, т.е. сразу можно выбросить варианты, где один из игроков получит, например, меньше 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
А вот что хочется увидеть, так это совершенно нестандартное решение, без предсказаний и поисков компромиссов. Может с обучаемой нейросетью, может с непонятной логикой, дающей отличный результат, может с продвинутым блефом или угадыванием карт противника странными ходами.
Параметры:
— список предложений сортируется по правилу 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
А вот что хочется увидеть, так это совершенно нестандартное решение, без предсказаний и поисков компромиссов. Может с обучаемой нейросетью, может с непонятной логикой, дающей отличный результат, может с продвинутым блефом или угадыванием карт противника странными ходами.
Во-во, практически мой алгоритм, только конкретные подходы немного другие, а абстрактная теория именно такая.
Вы чертовы гении! У меня сошлось только то, что нужно коэффициенты подбирать и обрабатывать последний ход ))
И вообще думать над этой задачей долго не хотелось, поэтому сделал решение простое как валенок.
Соглашаюсь сразу на 8 и более баксов. Тут я пожадничал, наверное ))
Сортирую все предложения по максимальной выгоде для себя. Предполагаю в начале одинаковую ценность объектов для противника и предлагаю вариант, максимальный для меня и не нулевой для него. После каждого хода уточняю ценности объектов противника. Для этого в два раза уменьшаю ценности объектов, от которых он отказался. Сумма при этом станет меньше 10, поэтому остаток распределяю поровну между объектами. При такой манипуляции ценности объектов будут нецелыми, поэтому ищу в списке ценностей вариант максимально близкий к вычисленному. Опять сортирую список предложений, выкинув предыдущие предложения и учтя новые ценности объектов противника.
На последнем раунде соглашаюсь сразу на все, что больше 0. Если же мой ход первый, то смотрю, не предлагали ли мне раньше что-то повыгодней и если да, предлагаю этот же вариант в ответ. Или же предлагаю вариант, в котором противник получит 5 и более баксов (исходя из моих предположений), а я получу хоть что-то. Тут я расщедрился ))
Были еще идеи улучшений, но не рискнул их использовать в условиях, когда невозможно определить, какой эффект они дают. На серверах рейтинг в течение дня прыгал очень сильно. Алгоритм вроде бы точно должен был улучшиться, а ты опускаешься вниз. Или наоборот, ничего не менял, а стою первым в рейтинге.
И вообще думать над этой задачей долго не хотелось, поэтому сделал решение простое как валенок.
Соглашаюсь сразу на 8 и более баксов. Тут я пожадничал, наверное ))
Сортирую все предложения по максимальной выгоде для себя. Предполагаю в начале одинаковую ценность объектов для противника и предлагаю вариант, максимальный для меня и не нулевой для него. После каждого хода уточняю ценности объектов противника. Для этого в два раза уменьшаю ценности объектов, от которых он отказался. Сумма при этом станет меньше 10, поэтому остаток распределяю поровну между объектами. При такой манипуляции ценности объектов будут нецелыми, поэтому ищу в списке ценностей вариант максимально близкий к вычисленному. Опять сортирую список предложений, выкинув предыдущие предложения и учтя новые ценности объектов противника.
На последнем раунде соглашаюсь сразу на все, что больше 0. Если же мой ход первый, то смотрю, не предлагали ли мне раньше что-то повыгодней и если да, предлагаю этот же вариант в ответ. Или же предлагаю вариант, в котором противник получит 5 и более баксов (исходя из моих предположений), а я получу хоть что-то. Тут я расщедрился ))
Были еще идеи улучшений, но не рискнул их использовать в условиях, когда невозможно определить, какой эффект они дают. На серверах рейтинг в течение дня прыгал очень сильно. Алгоритм вроде бы точно должен был улучшиться, а ты опускаешься вниз. Или наоборот, ничего не менял, а стою первым в рейтинге.
Кстати, наблюдая за тем, как торгуется мой бот, заметил, что он почти всегда получает меньше на последнем раунде. А получить выгодное предложение сразу получается редко, поэтому до последнего раунда доходит очень часто.
Отсюда возник вопрос. Можно ли выиграть у всех, проигрывая каждому в отдельности? В теории, конечно, можно. Но каковы шансы сделать это на практике.
Отсюда возник вопрос. Можно ли выиграть у всех, проигрывая каждому в отдельности? В теории, конечно, можно. Но каковы шансы сделать это на практике.
Не понял как это «сразу можно выбросить варианты, где один из игроков получит, например, меньше 30% в любом раскладе». Допустим, у нас по одному объекту каждого типа. Варианты получаются: 001, 010, 011, 100, 101, 110. Где здесь меньше 30% в любом раскладе?
Предположим, игра началась с такими правилами:
предметы: 1,1,1
наши цены: 0,4,6
цены противника: 3,3,4
Это весьма неприятный случай и мы можем сказать, только что у противника цена каждого предмета от 0 до 10 и единственное, что можно выбросить это набор цен 0,4,6, потому что он уже занят нами. Но из таблицы ходов сразу можно убрать то, что гарантированно дает нечестный результат — «все мне», «все противнику» и «я не получаю ничего».
Тут и к гадалке не ходи, надо пробовать ходить 011 (точнее, отдать 100, т.е. то, что нам не нужно). Если противник откажется, значит мы можем спокойно выбросить варианты, в которых цена его первого предмета составляет 8, 9, 10 (предположение зависит от коэффициентов).
Встречное предложение было 000 (скрипт example.js), оно нам ничего не говорит.
Посылаем предложение 001 (противнику достается 110).
Но т.к. это был example.js, то он согласился и получил 6 баллов, мы получили столько же.
Конечно же, у противника цены могли быть 5,5,0 либо 0,10,0 и тогда бы второй ход закончил игру со счетом 6/10, но наша цель не обставить противника как можно больше, а уйти с максимумом дохода. Бывают случаи, когда вообще все предположения ошибочны, а реальная цена где-то на краю диапазона, но у нас нет данных для других предсказаний, ничего поделать с этим нельзя.
предметы: 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, не валидный ход
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] — скорее всего, все получат мало.
Тут и к гадалке не ходи, надо пробовать ходить 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]
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]
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, но наша цель не обставить противника как можно больше, а уйти с максимумом дохода. Бывают случаи, когда вообще все предположения ошибочны, а реальная цена где-то на краю диапазона, но у нас нет данных для других предсказаний, ничего поделать с этим нельзя.
Следуя простейшей логике выгоды:
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]
Переоценка товаров происходит после каждого предложения от оппонента, как и пересчёт порядка комбинаций внутри ценовых групп.
Всё просто
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]
Переоценка товаров происходит после каждого предложения от оппонента, как и пересчёт порядка комбинаций внутри ценовых групп.
Всё просто
И почти полностью соответствует моему методу, описанному выше, методу тов @BingiBongo и наверняка другим «стандартным» решениям. Т.е. по-сути, наши решения будут соревноваться лишь в мелких оптимизациях, коэффициентах, ну и удачливости. Что хочется увидеть, так это, решение-победитель, где алгоритм в 5 строк, но есть простыня каких-то чисел. Или совершенно не предсказуемую логику, в общем забеге вырывающуюся на корпус вперед.
Типо того. Но, боюсь, что текущие ограничения сильно уменьшают шансы «на корпус вперёд». Мне больше понравилась площадка LARGE, там было интереснее торговаться. Хотя практически все решения сводятся к конечной логике, которую проще реализовать без использования нейронных сетей и супер алгоритмов.
Т.е. по-сути, наши решения будут соревноваться лишь в мелких оптимизациях, коэффициентах, ну и удачливости.
Как и в прошлых конкурсах.
В jsdash надо было просчитывать ходы и строить оптимальный маршрут. Было два варианта алгоритмов: считать и передвигаться на каждый ход или считать, пропуская ходы, а потом ходить по рассчитанному. Ожидаемо победил второй вариант.
В классификаторе слов тоже было два варианта алгоритмов — одни честно пытались ужать словарь, другие считали повторы слов. Ожидаемо победил второй вариант ))
Здесь пока все описывают один алгоритм. Хотелось бы конечно увидеть что-то особенное.
Письмо «JS challenge: please resubmit your solution» сегодняшним числом, означает, что предыдущий submission снова потерян? Или это просто напоминалка, сделанная левой ногой без проверок, залито обновленное решение или нет?
Напоминалка. Мы не потеряли решения снова. Просто до сих пор ещё 77 человек не прислали заново.
Я боюсь, и не пришлют.
Тут бы очень не помешала еще статья на хабре с извинениями и объяснениями, рассылка с человеческим текстом (текущая похожа на робота или спам), ну и все-таки фильтрация, есть ли от конкретного человека апдейт или нет.
Тут бы очень не помешала еще статья на хабре с извинениями и объяснениями, рассылка с человеческим текстом (текущая похожа на робота или спам), ну и все-таки фильтрация, есть ли от конкретного человека апдейт или нет.
Т.е. предварительных результатов еще неделю ждать?
Ну что там — сегодня же должны быть предварительные результаты?
Досчитывается ещё. Поставили на 250 сидов первый тур.
Публикация будет по той же ссылке, что и предыдущие?
Хорошее субботнее настроение натолкнуло на некоторые расчеты в ожидании результатов :)
На 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 пересекаются между собой и не знаем, сколько человек не попало в оба списка, поэтому это все гадание на кофейной куще. Собственно, как и сама суть конкурса.
На 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 пересекаются между собой и не знаем, сколько человек не попало в оба списка, поэтому это все гадание на кофейной куще. Собственно, как и сама суть конкурса.
5b6194a3adb0280402fd774c
5b6194d9adb0280402fd774d
5b6194f3adb0280402fd774e
Вот жеж лидеры мыслили одинаково :D
5b6194d9adb0280402fd774d
5b6194f3adb0280402fd774e
Вот жеж лидеры мыслили одинаково :D
В финал проходят первые 50, несмотря на незначительно измененные копии одинаковых решений?
5b61b487adb0280402fd7751
5b61aac7adb0280402fd774f
и выше я писал
Очевидно — решения из одной головы
Очевидно — все они повлияли на тех, кто мог бы быть в 50.
Я могу продолжить дальше охоту на ведьм, но нужно ли это?
Я просто поиском по коду нашел уже 5 скриптов жуликов :)
5b61aac7adb0280402fd774f
и выше я писал
Очевидно — решения из одной головы
Очевидно — все они повлияли на тех, кто мог бы быть в 50.
Я могу продолжить дальше охоту на ведьм, но нужно ли это?
Я просто поиском по коду нашел уже 5 скриптов жуликов :)
Эти выглядят как самостоятельные, достаточно сильные решения, а не «спойлеры», созданные для продвижения других.
Несколько человек спрашивали, можно ли двум или более участникам, работавшим в команде над одним и тем же решением, закачать разные его варианты. Я сказал, что каждый, кто работал над решением, может закачать его вариант, но не третьи лица (друзья, родственники).
Несколько человек спрашивали, можно ли двум или более участникам, работавшим в команде над одним и тем же решением, закачать разные его варианты. Я сказал, что каждый, кто работал над решением, может закачать его вариант, но не третьи лица (друзья, родственники).
Эти выглядят как самостоятельные, достаточно сильные решения
Это два идентичных решения которые различаются только в настройках коэффициентов. Автор мог заслать таким образом еще сотню вариантов пробуя разные настройки. Никогда не видел чтобы при выступлении команды ее участники отсылали индивидуальные решения, это немного противоречит смыслу командного выступления.
Я выбрал такое правило, потому что, если бы запретил, то не смог бы на практике контролировать соблюдение запрета. Пришлось бы определять какую-то метрику «достаточной похожести», а люди обходили бы её, внося искажения в свои версии. Короче, нафиг нужна такая забота.
Комьюнити справилось бы с поиском, да и проверить надо не всех, а только лидеров, как в спорте. Да и внести искажения так, чтобы стало полностью по-другому, весьма не просто даже для одного клона, а сделать 3-4 версии полностью визуально различных, но с одной логикой, и вовсе задача сравнимая по сложности с исходной. Идеального решения этой проблемы наверное нет, но видеть абсолютные клоны прошедшими во 2-й тур все же странно.
5b64ba5badb0280402fd77cd
5b646019adb0280402fd779c
5b646019adb0280402fd779c
То же самое и здесь.
Именно :) То же самое.
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";
Что значит самостоятельные решения? Это решения, в которых немного отличается настройка аппетита и уровня согласия. Это решения, которые дают автору (авторам) колоссальные преимущества.
Но если так можно было… Значит все честно :) Снимаю шляпу (по три). И укатываю свой мяч.
Но если так можно было… Значит все честно :) Снимаю шляпу (по три). И укатываю свой мяч.
Один «спойлер», даже полностью поддающийся своему «боссу», никак не может дать ему преимущество больше, чем в 10 очков. Если оно сыграет 0–0 со всеми, кроме «босса», а «боссу» сольёт 10–0, то итоговый счёт «босса» в результате этого будет всего на 10 очков выше, чем был бы без «спойлера». Колоссальным преимуществом это не назовёшь. Таких «спойлеров» нужны десятки, чтобы подняться хотя бы на одно место, и они не имеют шансов пройти в финал.
Здесь же мы видим просто два похожих решения. Каждое из них попало бы в финал и без другого.
Здесь же мы видим просто два похожих решения. Каждое из них попало бы в финал и без другого.
Наверное я не совсем очевидно формулирую свое возмущение :)
Я не имею ввиду «спойлеры», «помогаторы», «прочее».
Я вижу, что в списке топ-50 встречаются скрипты практически одинаковые. И недоумеваю. Почему автор самого сильного на данный момент решения не догадался прислать его 10 раз и утереть всем нос. Он же тоже может быть «команда».
Да и если по существу — такое условие, как разрешить плодить решения, которые согласны либо на 70%, либо 80% и тд от всей возможной суммы и только этим — не было оговорено в основном описании условия задачи.
Работает команда — приз на команду. Хорошо, что не было(а может и была, я не все проверил) команды из 40 человек.
Я не имею ввиду «спойлеры», «помогаторы», «прочее».
Я вижу, что в списке топ-50 встречаются скрипты практически одинаковые. И недоумеваю. Почему автор самого сильного на данный момент решения не догадался прислать его 10 раз и утереть всем нос. Он же тоже может быть «команда».
Да и если по существу — такое условие, как разрешить плодить решения, которые согласны либо на 70%, либо 80% и тд от всей возможной суммы и только этим — не было оговорено в основном описании условия задачи.
Работает команда — приз на команду. Хорошо, что не было(а может и была, я не все проверил) команды из 40 человек.
Можно делать проще: каждый участник отправляет любое свое решение в трех экземплярах. Тогда кто бы не победил, весь призовой фонд достанется одному человеку. Кроме мб мини-наград по 400$.
А вот еще решения, у которых подозрительно много одинакового кода:
17 — 5b64e7f2adb0280402fd77ea
26 — 5b64eb06adb0280402fd77f3
27 — 5b64e7baadb0280402fd77e8
35 — 5b64eaabadb0280402fd77f2
39 — 5b64e9c6adb0280402fd77ef
71 — 5b64e93badb0280402fd77ee
Глазками тяжело искать, устал. Вот бы инструмент, который ищет похожесть и показывает степень похожести.
17 — 5b64e7f2adb0280402fd77ea
26 — 5b64eb06adb0280402fd77f3
27 — 5b64e7baadb0280402fd77e8
35 — 5b64eaabadb0280402fd77f2
39 — 5b64e9c6adb0280402fd77ef
71 — 5b64e93badb0280402fd77ee
Глазками тяжело искать, устал. Вот бы инструмент, который ищет похожесть и показывает степень похожести.
И вот еще копии с точностью до опечаток в комментариях:
31 — 5b646257adb0280402fd779e
66 — 5b645263adb0280402fd7790
31 — 5b646257adb0280402fd779e
66 — 5b645263adb0280402fd7790
И еще
36 — 5b64575dadb0280402fd7794
63 — 5b648f06adb0280402fd77af
36 — 5b64575dadb0280402fd7794
63 — 5b648f06adb0280402fd77af
Аж целых 4 копии:
46 — 5b649223adb0280402fd77b3
51 — 5b649339adb0280402fd77b5
58 — 5b64b128adb0280402fd77c8
62 — 5b5f368eadb0280402fd7705
46 — 5b649223adb0280402fd77b3
51 — 5b649339adb0280402fd77b5
58 — 5b64b128adb0280402fd77c8
62 — 5b5f368eadb0280402fd7705
Что все так удивились, что много похожих и одинаковых решений? Правилами конкурса было обозначено, что можно отправлять столько решений сколько людей. Было сразу понятно, что будут и полные копии и несколько модификаций одного решения. Не вижу в этом проблемы, пока все решения играют честно.
И как сразу все говорили, будет решать рандом, если даже одинаковые/похожие решения раскидало на 10-30 позиций.
И как сразу все говорили, будет решать рандом, если даже одинаковые/похожие решения раскидало на 10-30 позиций.
можно отправлять столько решений сколько людей
Скорее сколько почтовых аккаунтов. Я последние две недели парился с подбором коэффициентов и незначительными правками кода. Оказалось, зря, надо было всего-лишь на создавать аккаунтов и отправить все свои решения, которые вызывали сомнения.
Скорее сколько почтовых аккаунтов.
По правилам именно «физических людей», а не почтовых аккаунтов.
- Один участник может использовать для отправки решения только один адрес электронной почты. Отправка множества решений, находящихся в «сговоре», с разных адресов запрещена; все решения, участвующие в такой схеме, будут дисквалифицированы.
- Нам нужно знать Ваше полное имя, но если Вы хотите, мы опубликуем вместо него псевдоним. Мы сохраним Ваш адрес электронной почты в тайне.
Некоторые решения так похожи, что у них даже место одинаковое:
21 5b64e9e0adb0280402fd77f0 1202516
21 5b64cb2dadb0280402fd77d8 1202516
Код при этом существенно отличается, но мы знаем, что чудес не бывает
=)
21 5b64e9e0adb0280402fd77f0 1202516
21 5b64cb2dadb0280402fd77d8 1202516
Код при этом существенно отличается, но мы знаем, что чудес не бывает
=)
В этом случае, кстати, нет заметного сходства скриптов.
Мы все программисты и понимаем, что вариантов получить разный код достаточно, включая трансляцию в другие языки или даже реализацию с нуля. Но чего точно не бывает, так это двух одинаковых результатов разных алгоритмов за 185000 игр.
Когда админ выложит 2.2-гигабайтный архив с логами каждого сеанса, вы сможете увидеть, действительно ли эти два скрипта всегда играли одинаково (с одними и теми же детерминированными партнёрами), или же у них именно сумма случайно сошлась.
Ну вообще-то, если прикинуть, то в таблице присутствует 16471 пар решений. Если поделить на максимально набранное число очков 16471/1242729=0.013. Вероятность совпадения очков у какой-либо пары 1.3%, что не так уж и мало.
Клоны клонами, а всё равно эти «командные» решения вытесняют алгоритмы из нижней части top50. Между тем все призёры будут из верхней десятки первого раунда (хотя пара решений из десятки и упадёт значительно в финальном рейтинге). Я это к тому, что никто не лишается заслуженного приза из-за клонов.
Ну что же, результаты известны, freewayrider'у хочется пожелать сохранять оптимизм :)
п.с. Навскидку, судя по использованию предвычисленных комбинаций и обфускации первые два места будто занял один и тот же человек. Сами алгоритмы не изучал.
п.с. Навскидку, судя по использованию предвычисленных комбинаций и обфускации первые два места будто занял один и тот же человек. Сами алгоритмы не изучал.
Во! О чем и я говорю. Если это обфускация, то очень интересная. Хотелось бы, конечно подробностей про эти решения.
Sign up to leave a comment.
Конкурс по программированию: Торговля (промежуточные результаты и объявления)