Chat:Ru/2021-05-17

From CG community
Revision as of 11:39, 15 June 2021 by Chat Log (talk | contribs) (Created page with "<img src=/a/8534620461135> miklla: пока медленно ползёт коммит, думаю. могу рассказать фишку своего бота, всё ра...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

miklla: пока медленно ползёт коммит, думаю. могу рассказать фишку своего бота, всё равно я эту его часть писал до рабочего вида 2 дня с чем-то

miklla: мне показалось, что основная трудность игры - решать, когда рубить деревья

miklla: так вот, взаимодействие между игроками сводится к теням и нутриентам

miklla: тени можно приблизить тем, что прибыль энергии e - e/C, где

e = t[1] + 2*t[2] + 3*t[3], C - констананта, а t[] - числа деревьев данной высоты

miklla: а зависимость последовательности нутриентов фиксирована, если фиксирована страта противника

miklla: поэтому я сначала запускаю свой алгоритм от противника против куклы - определяю времена его срубов, а потом себя против его срубов

miklla: так как же решить получающуюся соло-игру?

miklla: методов динамического программирования!

miklla: я ограничиваю t[0] <= C_0, t[1] <= C_1, t[2] <= C_2, t[]3 <= C_3, e <= const, заполнение идёт по смене дней и текущего нутриента

miklla: если делать это в лоб, то получится многомерный массив на миллионы элементов - за 1 ход проход не сделать

miklla: но я подменяю целевой аргумент score на пару (e, score), их храню списком

miklla: и постоянно при динамике чищу эти списки от доминированных опций

miklla: на практике в итоге за ход у меня обрабывается порядка 250К списков

miklla: пока жёстко не заоптимизировал и не применило ещё несколько хитростей, за 150 мс проход не успевал сделаться

miklla: 50мс *

miklla: на этом с основной идеей всё

miklla: хех, удачное начало сабмита https://www.codingame.com/replay/557408763

miklla: ну, касательно минусов моего подхода:

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

aangairbender: но чето как-то пару дней писал бим серч и совсем вылетело из головы

miklla: 1) если у одного из игроков энергии очень много, то он сильно выбивается из этой модели

aangairbender: в итоге за этот контест написал beam search и потом mcts duct

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

miklla: 2) иногда игра оказывается в ситуации, когда у одного игрока много 3-деревьев, а у другого всё срублено, в ней при хорошей расстановке своих деревьев эта константа в формуле e - e/C плохо приближает реальность

miklla: 3) часто оказывается, что в какой-то день один игрок сильно затеняет другого, а через 3 дня наоборот - это никак не учтено

aangairbender: можно считать что у тебя деревьев столько же сколько и соперника и тогда можно будет константу С менять в зависимости от суммы t[i], i 0..3

aangairbender: ну вот из-за непредсказуемости теней динамика и проседать должна

miklla: ну ради теней я симлю 2 хода, а потом запускаю эту динакику

aangairbender: выгодней бим серч для врага запустить на 15мс, а потом для себя и использовать ходы врага

aangairbender: на так тени потом новые ж появляются

aangairbender: я задачу оптимального роста деревьев вроде как линейно решил у себя, сортирую деревья по спаданию size * 10 + richness и потом считаю что буду рубить только некий префикс этого массива, за линейный проход нахожу оптимальный префикс

aangairbender: проблема что не учитываются будущие деревья (хотя их можно считать деревьями 0 размера и просто цикл еще на 10 итераций дольше запустить)

aangairbender: жаль что все эти идеи я только локально тестировал, на деле бим серч который я написал на 2ой день оказывается сильнее всего этого

miklla: а, да, в динамику везде подставил вместо richness её среднее значение (+2 score), но мысль гуляла и попытаться что-то такое с топовыми вариантами сделать

aangairbender: после соревнования, когда система тестирования успокоится, можно будет попробовать всякое разное

aangairbender: чтоб к следующему разу быть готовым (хоть раик, хоть кг)

miklla: 1.8к строчек :)

aangairbender: у меня 1.4к на арене, локально думаю под 2к

aangairbender: но одновременно используется я думаю 800 где-то

aangairbender: как вообще на плюсах, не было проблем?

miklla: как обычно, получал удовольствие от оптимизаций

aangairbender: я уже полгода как на раст пересел

aangairbender: та же скорость, то удобство и надежность имхо выше

aangairbender: *но

miklla: какой-то герой топ44 на питоне

aangairbender: эвристики наверное

aangairbender: да и вон у ейлера бимсерч на 10к посещеных стейтов обрубается

aangairbender: может такое и питон потянет

aangairbender: miklla а ты на плюсах как пишешь, умные указатели, RAII и вот это всё, или по старинке вручную?

miklla: по старинке, даже хеш-таблица своя

aangairbender: у меня когда-то задача не заходила с unordered_map, тоже свой писал

aangairbender: на codeforces зареган?

miklla: врчд ли

miklla: вряд*

Hamibar: miklla до футболки дошел?

miklla: вряд ли :(

miklla: скорее всего примерно 23ий как обычно

Hamibar: Обидно конечно

Hamibar: А в раике участвовал?

miklla: нет

miklla: там намного запарней разобраться, как запустить простейшего бота, чем тут

Hamibar: Можно было там футболку получить :grinning:

aangairbender: в последнем раике простого бота запустить было проще простого

miklla: мои места в последних контестах: 32, 95, 25, 17, 26, 6, ...

aangairbender: на кг?

miklla: в которых серьёзно участвовал

miklla: да

CyberEcho: Зато в раике футболку намного проще получить :grinning:

miklla: так что иногда в топ20 залетаю

aangairbender: я в парочке участвовал только)

aangairbender: но на дорешивании в легенду в poker chip race и ultimate tic tac toe зашел

miklla: ну мульти мне тоже нравятся, у меня топ1 в dots & boxes с большим отрывом

miklla: uttt мне должно было понравиться, но что-то я им не занялся

kurnevsky: Что есть раик?

aangairbender: russian ai cup

CyberEcho: https://russianaicup.ru/

CyberEcho: Ну или новый сайт https://cups.mail.ru

kurnevsky: А там до сих пор все правила игры не раскрывают? :)

kurnevsky: Помнется меня это оттолкнуло от него.

aangairbender: исходники не выкладывают, если ты об этом

Hamibar: Да с правилами в этом году тоже все было не очень хорошо

kurnevsky: Там была какая-то игра, где надо было сабмитами выяснять законы физики.

aangairbender: но если их правил какой-то момент не понятен, то всегда можно учточнить в телеграм канале, там сидят организаторы

aangairbender: а что в этом году с правилами было не так?

Hamibar: Ну что я припоминаю, что многое не было описано

aangairbender: хмм, мне казалось в этот раз все было норм

CyberEcho: Да в целом правила терпимо были описаны, но поначалу не хватало всяких деталей. Например, про одновременные ходы

CyberEcho: Это же не последний highload cup :grinning: Вот там да...

wlesavo: о, эулер уже выкатил пм

YurkovAS: https://www.codingame.com/forum/t/spring-challenge-2021-feedbacks-strategies/190849

Default avatar.png maddenvvs: Поздравляю всех с завершением соревнования! Как обычно, чат был очень познавательным и доброжелательным! Спасибо и удачи всем!

Arseny_Mask: индусы

Arseny_Mask: эй

Vindori: Сеня лох

Uljahn: ого, Агаде пытался нейронку замутить, нойс

Xanrum: yay! моя нейронка написанная за 2 часа при том что нейронки вижу первый раз в жизни - заняла 575 место

BorisZ: Xanrum поздравляю :clap:

BorisZ: приближаем восстание машин и судный день :rolling_eyes:

BorisZ: Xanrum напиши пм, интересно почитать, что и как использовал

Uljahn: у робо нейронка в топ-30

Uljahn: Automaton2000: что там у рекурса?

Automaton2000: По крайней мере у меня не было

BorisZ: а я золотую лигу кажется выиграю нынче

BorisZ: все к тому идет

Uljahn: угу, довольно напряжённая борьба в топе голды

Uljahn: http://cgstats.magusgeek.com/app/spring-challenge-2021/BorisZ

BorisZ: я тоже уже нашел, все думал, где найти рейтинг босса, в таблице не показывается же

YurkovAS: seed-ить только со стоимостью 0 локально показывает 60% вин.

BorisZ: оказывается у магуса довольно оперативно отображается - несколько минут может задержка от силы

BorisZ: YurkovAS вроде давно довольно это у всех

BorisZ: у меня костылем просто ( у крутых чуваков может само так считает

YurkovAS: и стейты эйлер нормально так обрабатывал, а я все в одну кучу добавлял

BorisZ: еще если день обрабатывать отдельно, то и дубликаты легко убрать

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

aangairbender: у меня бимсерч как у ейлера 1 в 1

aangairbender: жаль, что оценка далеко не 1 в 1

YurkovAS: и оценка тогда нужна не подействиям тут, а стейта

BorisZ: это смотря как хранить стейт, если в битах то просто

BorisZ: закиноло меня в легу, ура )

Uljahn: поздравляю

YurkovAS: :thumbsup:

Uljahn: last time submit?

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

BorisZ: кибернетика - точная наука )

BorisZ: если нет желудей - садим, если у нас деревьев больше двух а у врага больше 4 то не рубим и так далее

BorisZ: все в таком духе - смотрю реплеи, вижу осяк - прикручиваю костыль

Uljahn: heuristical action space pruning

Hamibar: BorisZ ты описал мой подход

Hamibar: НаКостыляли золотому боту:grimacing:

Chibikko: у меня ограничения на действия такие были: http://chat.codingame.com/pastebin/0ed7159b-27a4-49b0-b9c1-d981a659908e

Chibikko: ого, большие сообщения сами выносятся в ссылку.

Beard: BorisZ таки ворвался, поздравляю)

BorisZ: Beard спасибо )

aangairbender: Chibikko а почему на последнем дне резка деревьев от центра?

miklla: потому что может не хватить энергии срезать все

aangairbender: ну вот если я знаю, что с моей энергией хватит ровно на 2 дерева допусти

aangairbender: представим что нутриентов 1 осталось и у тебя 2 дерева, одно в центра (richness 4), а другое на краю (richness 1), тогда очевидно если резать с края, то будет 6, а если с центра то 5

kurnevsky: Еще могут нутриенты закончиться, и резать станет не выгодно.

miklla: там на самом деле на последнем ходу надо рубить деревья в порядке richness, пока nutrient + richness > 1

aangairbender: в центре все равно будет выгодно

YurkovAS: противник тоже будет резать

BorisZ: aangairbender с края тоже будет 5

BorisZ: но придется резать 2 дерева

BorisZ: а с центра только одно

BorisZ: в твоем примере

aangairbender: 1 за нутриенты + 1 за richness с первого 4 за richness со второго итого 6

BorisZ: с края бонус за ричнес = 0

aangairbender: ричнес 0 = пустая клетка же

aangairbender: серая которая

miklla: ой, не nutrient + richness> 1, а nutrient + bonus > 1

Hamibar: Да, но формула добавления очков (ричнесс - 1) * 2

aangairbender: лол а я просто ричнес плюсовал))

miklla: я у себя в коде на чтении сразу richness на bonus заменяю в очках

aangairbender: в общем надо до следующего соревнования везде взять легенду

Chibikko: richness != bonus

aangairbender: Chibikko моему боту не сказали:sweat_smile:

Uljahn: самое время перечитать правила, Automaton2000

Automaton2000: а тебе наоборот можно более строгое условие чтобы если не нашел лучше заново посчитать чем найти неправильное

nGragas: Проспал финал.. там в конце запускали заново пересчёт у всех или использовался старый рейтинг?

miklla: пока что старый, наверное будет ещё полный пересчёт леги

miklla: хех, BorisZ пролез, теперь не так скоро :)

miklla: какой героический сабмит

Uljahn: или полный, или топ-100

BorisZ: я не последний, за мной еще один пролез

BorisZ: у меня быстрее считается - ограничение 80мс стоит

BorisZ: хотя я думаю что хватило бы и 20 с тем же результатом )

Uljahn: а без огранчения таймит?

BorisZ: я просто считаю пока время не кончится

BorisZ: простой монтекарло - примерно так

wlesavo: BorisZ поздравляю)

Uljahn: в смысле, с более высоким лимитом, типа 95мс

BorisZ: ну да, вылетало там в какой-то реализации, я поставил поменьше с запасом

BorisZ: wlesavo спасибо)

miklla: что-то многие крутые чуваки не показали высокий результат, например Рояль, Смит, у них времени не хватило? И ПБ4 вообще не видать

Uljahn: pb4 в общаке вопросы задавал, видать не получилось вложиться

Uljahn: смитс наверное напишет пм

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

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

CyberEcho: Кто-то наверняка отпуск берет под соревнование

nGragas: Кто что скажет по "get a job" на этой платформе касательно нас? ) или это только для французов?

CyberEcho: Перезапустили легенду

Xyze: из топ 100 бы не вылететь

nGragas: хмм... а результаты фиксировать будут по тому что будет после перезапуска?

Xyze: ага

Xyze: после пересчета будет финальное место

Hamibar: Интересно, что самое высокое место у меня было в моем первом контесте, когда совсем ничего не понимал

BorisZ: Hamibar в твоем случае рано что-то говорить, слишком рано экстраполировать )

BorisZ: ну и контесты разные, понятно что всегда есть доля случая - наткнулся сразу на удачную идею - сразу приемущество

BorisZ: или выбрал удачный порядок реализации каких-то фич - от ключевой ко второстепенным а не наоборот

BorisZ: но наверное в этом что-то есть, у новичка нет страха, и он делает как может что-то, если считает что это нужно сделать

BorisZ: был бы опытный - ему бы растолковали в чате давно что так только лохи делают, и тут только супер крутой алгоритм Х может взлететь

BorisZ: вот и получается нормально, особенно если остальные звезды сошлись

Hamibar: Да нет. Тут все дело в потраченном времени. В первый раз ты просто 24/7 контест решаешь. Я помню на тренировке смотрел реплеи :grinning:

Hamibar: Ну и не знаешь особо, что писать

BorisZ: ну да, согласен, мотивация тоже важно, но неделю в себе ее поддерживать в общем не очень сложно, это если месяц например, то я точно сдуваюсь всегда

Hamibar: И это плюс получается. Сейчас думаешь ну надо это сделать, это и это. И смотришь такой на это все и идешь на соседнюю вкладку

Xanrum: у меня с каждым контестом все выше нагрузки на работе, и все ниже место : (

BorisZ: ну некоторые в промежутках между контестами пилят мульти, чтобы основные наработки были на пальцах

BorisZ: чтоб если решил что тут бимсерч может взлететь например, то у тебя уже есть пара бимсерчей реализованных, какие-то тонкости быстро вспомнятся

Hamibar: Я не сторонник каких то универсальных решений в контестах. Но понятно, чем больше ты этого делал, тем легче.

Hamibar: Xanrum и зачем нужна такая работа, на которой нельзя пилить контесты

Xyze: а почему в этот раз все бросились писать сетки?

Xyze: вышла какая-то статья как легко запихивать сети в CG?

Uljahn: не все, а те, кто натренился писать сетки в мульти

Uljahn: статьи не было, все обсуждения размазаны по логам чата

kurnevsky: А мульти - это что? :)

Uljahn: bot ai multiplayers

Uljahn: большинство бывших контестов оказывается в этом разделе после завершения

Uljahn: можно играть без ограничения по времени

Uljahn: https://www.codingame.com/multiplayer/bot-programming

Uljahn: теперь код из контеста автоматически сабмитится в мульти, когда его откроют сегодня-завтра

Uljahn: в ту же лигу

Xyze: Uljahn там где то был сайтик с логами чата, не помнишь?

Xyze: учитывая что люди успевают тренить сетки даже не в мульти, кажется уже нельзя просто игнорировать этот факт

Uljahn: https://cg.spdns.eu/wiki/Main_Page

Uljahn: чё-т не открывается у меня

Xyze: аналогично

ChadThundercode: я кажется догадываюсь почему лол

ChadThundercode: (у меня открывается)

Xyze: прокси надо?

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

CyberEcho: Интересно почему terry_u16 так долго считает? Возможно из-за rust :grinning:

kurnevsky: Мой раст быстро посчитал :)

kurnevsky: Вероятно, он использует все время ходов + все время первого хода.

kurnevsky: Для mcts.

Uljahn: https://cg.spdns.eu/wiki/Special:PrefixIndex?prefix=Ru%2F&namespace=3000

Uljahn: открылась вроде

Uljahn: "Game will be released soon (most likely tomorrow)"

Semenyutenko_Andrey: Привет, всем. Посоветуйте что почитать по сеткам. Такое чтоб для совсем простых ребят.

wlesavo: какого уровня? просто можно статью на хабре почитать, а можно книжку на 1к страниц

wlesavo: если хочется прямо хорошее представление об области составить то книжка лучше конечно

Semenyutenko_Andrey: да в общем никакого. с нуля чтобы.

Semenyutenko_Andrey: книжки отлично. есть какие-то личные фавориты?

Uljahn: если с инглишем и питоном хорошо, я бы посоветовал на coursera пройти бесплатные курсы, посмотреть видосы, поковырять питоновские ноутбуки

BorisZ: https://www.kaggle.com/learn

Semenyutenko_Andrey: инглиш такокй, что только на кодингейм и хватает, на целый курс не уверен.

wlesavo: а если прямо книжку хочется то я вот это читал, там очень подробно и с нуля, и очень прямо разные аспекты цепляются. но конечно инглиш https://hagan.okstate.edu/NNDesign.pdf

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

Semenyutenko_Andrey: братцы, а на русском ничего нет?

wlesavo: еще можно начать с того чтобы инглиш выучить :smiley:

BorisZ: начитать надо как известно с изучения трудов Аристотеля :rolling_eyes:

BorisZ: а то нахватаются по верхам )

Semenyutenko_Andrey: инглиш я учу. правда. но я старый и медленно соображаю. а вокруг так много интересного.

Uljahn: https://vas3k.ru/blog/machine_learning/

Uljahn: вот на русском

Semenyutenko_Andrey: оооот!!! с картинками!!!! Спасибо большое!

Uljahn: там правда не очень серьёзно, но зато и не загружает особо

Uljahn: с юморком

Semenyutenko_Andrey: да мне хотя бы вообще понять что это.

BorisZ: картинка смешная )

wlesavo: а ну если так то блог самое то

MelnikovIgor: Когда откроют рейтинг?

BorisZ: какой рейтинг?

BorisZ: https://www.codingame.com/contests/spring-challenge-2021/leaderboard/global

BorisZ: этот?

Chibikko: уже пересчитали всё? Места определились?

BorisZ: угу

Uljahn: http://chat.codingame.com/pastebin/4c72e35e-1d09-460b-b692-42cc8ffc0238

Chibikko: Место сейчас в топ-100, а почему-то ачивку не разблокировали? "Finish in the top 100, in any contest.".

Chibikko: или место засчиталось то что было до пересчёта?

BorisZ: завтра начислят все плюшки

BorisZ: ночью обновляют рейтинги, раз в день

Chibikko: Хорошо. Хоть бы опять место не пересчитывали. Чудом 95-ое получилось. Второй контест и первая легенда в них.

BorisZ: Chibikko поздравляю )

Uljahn: молодца

CyberEcho: Тоже первый раз легенду получил и в отличии от раика это было весело и совсем не выматывающе :grinning:

BorisZ: CyberEcho тебе отдельное спасибо за идею ролаутов без сида, хорошо придумал, я бы без этого точно не пролез бы )

BorisZ: я чего идею с монтекарло сначала забросил - оно генерило какую-то хрень, хотя вроде все правильно было с симуляцией

BorisZ: понятно теперь что это из-за сидов, несколько тысяч сим явно мало при таком количестве вариантов

BorisZ: а поскольку мы сравниваем два действия из одной позиции, то без сидов как раз нормальное приближение получается

Chibikko: У меня наоборот с mcts какая-то магия получается. Уже в трёх местах применяю и всегда с полпинка заводится, даже при отвратительно реализованной симе. Правда всегда в предел упирается где-то на уровне топ-золота, лоу-легенды.

Chibikko: Даже не знаю стоит ли что-то другое пробовать, если этот алгоритм такой простой и надёжный как молоток.

CyberEcho: У меня в финальной версии бота MC полноценно применялся с 18 дня. До 18 дня MC использовался только для поиска оптимальной последовательности GROW действий.

Chibikko: там ведь по сути надо только выбрать деревья, которые растить. А порядок всегда от большего к меньшему.

CyberEcho: Ну может быть выгоднее сначала вырастить дерево 1->2, если оно на следующем ходе закроет дерево 2 противника, а еще через один ход сможет закрыть дерево 3 противника. MC позволяет очень просто найти оптимальный ход.

Uljahn: MC же это рандом, или ты про MCTS?

Default avatar.png mraymun: во сколько рейтинг обновляется? как он считается для CoC?

Beard: гдето в 03 утра мск

CyberEcho: > MC же это рандом, или ты про MCTS?

Да, обычные рандомные ходы

Uljahn: хм, интересно

Uljahn: всегда казалось, что если рандом справляется хорошо, то можно подобрать более эффективный алгоритм

MelnikovIgor: Когда откроют контест?

ilt: А как MC работает?

ilt: просто доигрывать случайными ходами до конца на все время?

ilt: И выбирать вариант с максимальным счетом?

Uljahn: MelnikovIgor: в дискорде обещали сегодня-завтра

Uljahn: вернее, скоро

Uljahn: "Game will be released soon (most likely tomorrow)"