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
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?
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)"
maddenvvs: Поздравляю всех с завершением соревнования! Как обычно, чат был очень познавательным и доброжелательным! Спасибо и удачи всем!
