mykeich: все чучуть не хватает чтоб пройти в следующую лигу по https://www.codingame.com/share-replay/530807536 есть подсказки?:)
mykeich: хочу принципиально минимаксом. сосредоточился на оценочной, но чет не выходит каменный цветок
magaiti: ERROR "you must be the owner to share this replay"
samrrr: https://www.codingame.com/replay/530939845
samrrr: вот всё непойму как он так круто обыгрывает....
mykeich: samrrr да твой бот за 31 ход проигрывает:) https://www.codingame.com/replay/530940288
mykeich: magaiti да я про https://www.codingame.com/ide/puzzle/othello-1
samrrr: тебя нет в моей лиге
magaiti: я в бронзе уттт, можно клепать мыцытыэс
samrrr: ты его мог и для малой доски делать
magaiti: нафиг
magaiti: и так получилось
magaiti: мегастратегия в вуд лиге - если ход выигрывает, ходишь. иначе если враг выигрывает ходом в какую-то клетку, то ходишь туда. иначе рандом. первый ход 2-2 иначе 0-0
mykeich: samrrr ну на чем остановился?
samrrr: на томже
mykeich: пилишь mcts?
samrrr: написал, но толку мало
mykeich: ты раньше писал mcts?
samrrr: нет
mykeich: шансы малы что не ошибся
Uljahn: тут даже дело не столько в ошибке (без ошибок такое почти нереально запилить), а в том, что если не понимаешь алгоритм, то дебажить задолбаешься
samrrr: пока мемори корраптов нету
mykeich: месяц подебажить принтами и разберёшься:)
samrrr: у меня есть вижуал
mykeich: да нафиг оно надо, принт всегда помогает
samrrr: лимит же
mykeich: samrrr осталось разобраться не прикрутил ли ты велосипед
samrrr: прикрутил конечно, на простом мктс выше 50 не поднятся
mykeich: у тебя есть функция mcts_start и mcts?
samrrr: нет
mykeich: неожиданно:)
mykeich: ну вот примерно так
mykeich: http://chat.codingame.com/pastebin/8e43edd8-1d4a-4afe-9be4-cfb4b07da659
mykeich: сделал боса в othello-1 ура. нашел правильную простую оценочную без лапши ифоф и без придумывания сложных эвристик
mykeich: samrrr а что у тебя?
samrrr: что-то похожее
mykeich: В теле MCTS сложней, там есть простор для оптимизаций и я вывел удобную мне последовательность действий
mykeich: treeExpand у тебя есть что создает все дочерние ноды равное числу возможных ходов?
samrrr: да
samrrr: http://chat.codingame.com/pastebin/554050cc-c802-4c5b-957e-80473daa1c18
samrrr: http://chat.codingame.com/pastebin/51732555-a844-456c-a386-5c1e8a6100ca
mykeich: resize что там?
samrrr: да вродн как всегла в векторе
Uljahn: ресайзить не слишком дорого? можно указатель на свободную ноду хранить, а массив нод выделять в первый ход
samrrr: не, недорого
mykeich: объекто ориентированное программирование подводит в скорости:)
samrrr: http://chat.codingame.com/pastebin/1b7fbe50-6529-4627-962d-dcac023eff29
Uljahn: профилировал?
samrrr: этож вектор простой
mykeich: в спорте каждая мелочь важна:)
samrrr: да, в профайлере нет больших пробелов в ресайзе
Uljahn: а родителей как хранишь?
samrrr: никак, нафиг они мне
Uljahn: лол
mykeich: ты не прав
Uljahn: какой 4-й этап в мктс?
samrrr: 4, эмм что?
Uljahn: запилил он
Uljahn: ахах
mykeich: Uljahn наверное оценочная из минимакса:)
Uljahn: не удивительно, что в топ-50 еле вползает
samrrr: всё как мне сказали, беру ход с топ визитов и всё
Uljahn: лол
samrrr: да не, он в топ 5 входит
samrrr: это сейчас ошибка 1 есть
mykeich: samrrr короче как хочешь но самый быстрый код это связанные списки тут через индекс в заранее созданном массиве
mykeich: и парента надо хранить
Uljahn: можно отдельным массивом
samrrr: а нафмг мне этот парент?
mykeich: потому что тебе надо распространять оценку по всем парентам до рута
Uljahn: +
samrrr: но у меня на это есть трейс
samrrr:
vector<uint32_t> trace;
mykeich: когда mcts проваливается глуюже ты хранишь список пройденных нод?
samrrr: да
samrrr: там всегото 6-8 индексов
Uljahn: ну вот это и есть паренты
samrrr: но я их не храню в дереве
mykeich: да лишняя возня
Uljahn: цепочку нод во время селекшна можно хранить отдельно
Uljahn: но хранить надо, чтобы оценку вернуть
samrrr: ну у меня есть трейс пока доска идёт внутри дерева
mykeich: просто твой код медленный
Uljahn: у топов на втором ходу 70-100к роллаутов
samrrr: 70% времени на роллаут уходит
Uljahn: битборды юзаешь?
samrrr: да
Uljahn: проверки выигрыша доски в таблице?
samrrr: да
Uljahn: 70% - это вроде нормальное соотношение, но можно селекшн ускорить за счёт fast_rand и fast_inv_sqrt, логарифмы закэшировать или ещё что
samrrr: какие логарифмы?
Uljahn: о_О
mykeich: samrrr select у тебя канонический?
samrrr: что за селект?
mykeich: ну как ты проваливаешься по дереву?
Uljahn: 70% - роллаут, а 30% - всё остальное, в т.ч. и селект
samrrr: беру ноду с топ приоритетом
Uljahn: как вычисляетс приоритет?
samrrr: по какойто формуле, с корнем
Uljahn: что под корнем?
samrrr: tmp_turns_pri[i] = node_child.score / (float)node_child.visit + CC * sqrt(node.visit / (float)node_child.visit)
Uljahn: :upside_down:
Uljahn: Automaton2000: adios
Automaton2000: а то я уже готов в золото (ну хотя бы серебро), пролазить
samrrr: так причём тут логарифмы?
mitfity: как поменять аватар на этом сайте?
samrrr: https://www.codingame.com/share-replay/530948122 не ну рили так слить....
Uljahn: mitfity: наведи курсор на аву, вылезет попап с новой авой, в чате попозже обновится
mykeich: samrrr типовая формула разве такая?
mykeich: tmp_turns_pri[i] = node_child.score / (float)node_child.visit + CC * sqrt(log(node.visit) / (float)node_child.visit)
Uljahn: вон же логарифм
samrrr: понятия не имею, я просто подставлял всё подряд под корень, чтоб заработало
mykeich: https://wikimedia.org/api/rest_v1/media/math/render/svg/b607bd848f08876b247148bad27c3c26a1066a0d
samrrr: 42 и 1/42 на зашло
Uljahn: тогда не говори, что мктс запилил
samrrr: это мктс так как есть дерево, приоритеты, роллауты
Uljahn: формально да, но на практике - нет
samrrr: но работает же
mykeich: samrrr сделаешь маленькую ошибку и работать будет криво
Uljahn: вот-вот
Uljahn: велосипед с квадратными колёсами тоже ездит же
Uljahn: логарифм в формулу не зря засунули, почитай про upper confidence bound
mykeich: samrrr делай формулу из вики. только буквально не пиши, log Один раз вычисляется в select функции
mykeich: у меня логариф и корни вычисляются при старте, а дальше из буффера вытаскивается, но оставь эту оптимизацию на будущее.
mykeich: samrrr согласен или думаешь мы тебя обманываем?:)
mykeich: не знаю как с++, но в си есть sqrtf и logf
Uljahn: есть прагма ffast-math или типа того
mykeich: еще rollout надо проверить, там тоже могут быть сюрпризы. по себе знаю:)
Uljahn: mykeich: у тебя проверки на инста вин есть в роллаутах?
Uljahn: как magaiti выше писал
mykeich: Uljahn я не очень понимаю вопроса
mykeich: если я верно понял вопроса, то в ролаут у меня чисто случайные, никаких предпочтений перед выигрышными ходами нет
Uljahn: ну как бы да, проностью лучайные - это обычные роллауты, а роллауты с предпочтениями и эвристиками - это heavy rollouts
Uljahn: *случайные
mykeich: можно замутить конечно, лень немного:)
Uljahn: где-то читал, что формула UCB даёт оптимистичную оценку, т.е. уязвима к ловушкам, если роллауты подрихтовать, должно стать получше
Uljahn: ловушка - это когда у противника есть возможность навязать хотя бы одну гарантированно проигрышную для тебя линию игры среди множества вариантов, статистически её трудно распознать на начальных этапах из-за эффекта горизонта
YurkovAS: вроде на днях карлисо тоже писал, что выбирает всегда выйгрышный миниборд в роллаутах.
и это их быстрее завершает
YurkovAS: и давно томатос тогда про них писал, не помню только что, вроде тоже юзает
Uljahn: смитс и робо тоже вроде писали, у кого-то просто вероятность выбора повышается для такого хода
Uljahn: т.е. если можем завершить миниборду, то делаем ход с вероятностью 50%
YurkovAS: еще есть момент: на этапе экспанда, можно для всех детей запустить роллауты сразу.
это заметно повышает скорость, но играет хуже, примерно на 15% (-7-12 мест)
YurkovAS: экспериментировал с этим и заметил, что с этой фичей скорость получается как у томатоса, но у него играет хорошо
YurkovAS: возможно он как-то правильно юзает эту фичу
YurkovAS: там же заметно статстика по визитам и скорам меняется
Uljahn: а сколько роллаутов сразу запускаешь?
YurkovAS: может надо брать только небольшой срез лучших нод
да и опять же, визуально не заметишь, придется долго бенчмаркать или много сабмитить
YurkovAS: 1 роллаут запускаю при экспанде
YurkovAS: в других мульти тоже проверял эту фичу и везде она играет хуже
но кол-во роллаутов заметно выше, на 20к+ в крестиках
mykeich: сделал так что ролаут выбирает из ходов что ведут к выигрышу на малой доске, у меня там сассив, так что просто сделал копию этого массива и проверил есть ли выигрышные ходы
Uljahn: если выигрыш на малой доске выигрывает партию, то это обязательный ход, мне кажется
mykeich: такую проверку не сделал, это следующий шаг:)
Uljahn: глупо полагать, что противник упустит возможность выиграть, или заблочить тебе выигрыш
Uljahn: рандомный роллаут это не проверяет
mykeich: надо минимакс в ролаут встроить:)
Uljahn: солверы примерно так и работают
Uljahn: что-то типа, когда ветка дерева близка к достроению, дешевле полным перебором заминимаксить и получить гарантированную оценку, чем каждый раз от рута проваливаться
mykeich: глядя на результат понял что это фигня на малых досках выигрывать, часто выигрывать не требуется на малой доске, а я исключил ходы без выигрыша. надо делать только выигрыш на большой доске
YurkovAS: может их еще и несколько бывает и тогда уже надо их в список выписывать и рандомить
YurkovAS: mykeich юзаешь null window (или zero) в минике в ксб?
mykeich: Пока термин не знаком.
YusufK: всем привет
YusufK: я здесь новеньки можете мне помогать пж
mykeich: YusufK привет
mykeich: YurkovAS что то не гуглица:)
YurkovAS: mykeich поиши: set new null window
https://www.chessprogramming.org/NegaScout <https://www.chessprogramming.org/NegaScout>
YurkovAS: одно из улучшений минимаксов
YurkovAS: я сам еще не освоил, дай думаю тебе сообщу и узнаю за одно
mykeich: с наскоку смыла не понял:) можно повторить и проверить
YurkovAS: смысл не расскажу. видел что его еще немного по разному делают, например в pvs
https://www.chessprogramming.org/Principal_Variation_Search
mykeich: попробовал в othello. у меня там как раз обычный negamax. что то провал, может ошибся где:)
mykeich: И в UTTT что то ролауты с фильтром по выигрышным последним ходам плохо себя показало.
YurkovAS: ясно. ну я только хотел помочь чего-нибудь улучшить... бывает
YurkovAS: проверял negascout + null window в wondev woman и тоже не показало улучшения, чем просто альфа-бета
правда там средняя глубина 2-3 хода...
YurkovAS: mykeich в общем чате пишут про оценочную к отелло
YurkovAS: стабильные диски надо юзать
mykeich: ну я так и сделал, вопрос как запилить не грузной алгоритм
mykeich: YurkovAS у тебя позиция выше, наверное что то запилил крутое ты?:)
YurkovAS: mykeich у меня там мктс с оценочной по позициям на доске как тут в табличке
http://play-othello.appspot.com/files/Othello.pdf
samrrr: не ну босс крыса он тупо себе рейт апает, но со мной не бьётся
YurkovAS: + еще в самих мктс нодах небольшие бонусы за кол-во ходов противнику: чем у него их меньше, тем лучше для нас
Uljahn: о, почти в легу закатился, можешь ведь
Uljahn: http://cgstats.magusgeek.com/app/multi-tic-tac-toe/samrrr
Uljahn: тут можно статистику по сабмиту посмотреть
Uljahn: сливаешь боссу, но выезжаешь за счёт победы над игроками
YurkovAS: да, быстро он мктс запилил
samrrr: какихто жалких 30 часов ну ну
YurkovAS: ну хз, я очередно раз подумал: как обидно (раздражает) что большинство людей намного быстрее меня разбираются в алгоритмах или технологиях
YurkovAS: у каждого свои тараканы :)
Uljahn: кто-то лучше пилит, кто-то лучше разбирается :relieved:
samrrr: может потому, что я по 8 часов в день лет 10 занимаюсь программированием?
YurkovAS: я не меньше
samrrr: насчёт меня можешь особо не беспокоится, таких как я мало. в основном я встречал людей которые и с 3 раза не особо понимают
YurkovAS: :)
Uljahn: кодинг - это освоение инструмента, а чтобы грамотно прикладывать инструмент, нужно иметь компетенции в смежных областях
samrrr: да не, нафиг ненужно. в 99.9% игр боты хуже чем в серебре играют, на стелларис вон посмотри
samrrr: алгоритмы тоже нафиг ненужны, еслиб мне не уужно было 20к роллаутов, то я тупо вектор чилдов в ноду запичнул и всё топ работалобы
samrrr: из всех игр, чтьо мне известны только в star ruler есть что-то запредельно сложное
Uljahn: в RAIC участвовал?
Uljahn: думаю, самое то для тебя
samrrr: не, вообще не слышал
samrrr: у меня такое впечатление, что выйгрыш на малой доске ничего не даёт
samrrr: https://www.codingame.com/share-replay/530990476
samrrr: вон 2 доски отжал, а толку нет
Uljahn: эти две доски не образуют выигрышную комбинацию
Uljahn: выигрыш на малой доске даёт фримувы, если на других досках противник может их выиграть ходом в эту доску
Uljahn: фримувы взрывают пространство вариантов, мктс с недостаточным количеством роллаутов начинает тупить
samrrr: https://www.codingame.com/replay/530994316 вот 2 доски отжал, а серавно начал проигрывать уже на середине
Uljahn: опять они не входят в выигрышную комбинацию
Uljahn: тупо отжиманием досок тут не выиграть
Uljahn: если противник не дурак
samrrr: так это не я отжимаю, это он меня туды спихивает
Uljahn: значит, он игру контролирует, а ты - ент
Uljahn: *нет
Uljahn: Automaton2000: в ты - энт
Automaton2000: это при том что я не прав
samrrr: вотименно и я хз чё с этим делать
Uljahn: а ты в начале всегда на сторону ходишь за нолики?
Uljahn: в угол вроде немного лучше ходить
samrrr: https://www.codingame.com/replay/530995251 вот как так то? мой бот уже слился ещё до занимания какой либо доски
Uljahn: у крестиков преимущество же
Uljahn: попробуй ходить в угол принудительно
samrrr: https://www.codingame.com/replay/530995538 что он творит, все углы отдал и победил как так то
Uljahn: углы отдал в обмен на центр и фримув
Uljahn: неплохой размен
samrrr: 51 ход он просто обязан был выйграть, но мой бот просто взял и слился
samrrr: на ровном месте
Uljahn: возможно, где-то баг
Uljahn: удачи с поиском
tomatoes: возможно недостаточно багов :smirk:
magaiti: нужно ошибиться в знаке в нечетном числе мест
magaiti: похоже я порвал бронзу своим деревянным алгоритмом, просто усовершенствовал до доски 9 на 9
magaiti: мктсом и не пахнет пока
YurkovAS: tomatoes <https://www.codingame.com/profile/66b5c3037cc9a0c762f4f9022612ffd44307061> ты тут? подскажи по крестикам, плиз
Uljahn: что-то я не вижу, как там можно было выиграть на 51-м
tomatoes: тута, а какой вопрос
samrrr: нужно было брать клетку, там шанс вина дольше
YurkovAS: tomatoes <https://www.codingame.com/profile/66b5c3037cc9a0c762f4f9022612ffd44307061> после фазы expand, ты запускаешь рандомные rollout игры для всех новых дочерних нод?
по моим экспериментам, что да, но оно же играет заметно хуже
tomatoes: только один
Uljahn: по одному роллауту на каждого чайлда сразу?
magaiti: через 2 минуты буду в серебре
magaiti: я крутой
Uljahn: жжош
samrrr: нет
tomatoes: но у меня рандомная нода не выбирается, сразу уцт (немного измененный) используется
YurkovAS: спасибо!
magaiti: 120 строк кода
samrrr: ты мимо, на количество символов тут всеравно
Uljahn: magaiti крут, это не обсуждается
YurkovAS: tomatoes странно что, у меня такая же скорость достигается именно когда запускать рандомные игры сразу для всех новых нод.
Uljahn: я думаю, по одному роллауту - это мало для сбора статистики
tomatoes: у меня в начале скорость изза того что несколько роллаутов из одной ноды запускаю
Uljahn: вооот
YurkovAS: всегда, или только после экспанда? когда выбрал одну по формуле
tomatoes: когда выбрал
tomatoes: экспанд только на втором визите
Uljahn: блин, я же уже про это читал раньше
Uljahn: где-то в одном из чатов
YurkovAS: спасибо. сохранил и потестирую еще потом
tomatoes: пробовал еще константу побольше в начале, чтоб он не уползал черти куда, а более объективно пытался. но как-то не пошло
samrrr: новая попытка измерить инициативу...
YurkovAS: tomatoes тебя там уже поджимают, еще один новый чел догнал
tomatoes: боюсь трогать, а то затянет снова на неопределенный срок
YurkovAS: это точно
samrrr: пока мне удалось перетасовать топ, и вывесть боулдер на 1 место...
samrrr: паньше там сф заседал
Uljahn: константа решает, конечно
Uljahn: единственное, что в ванильном мктс можно теребонькать
samrrr: простой мктс на 40 месте был
samrrr: ре лаже вальнуть босса не мог
tomatoes: в легенде внизу reLu какой-то с ниеровой пикчей, рекурс снова твинководит чтоль :thinking:
samrrr: о наконец завалил босса
samrrr: по честному без занимания редиректа
Uljahn: tomatoes: это он с нейронками экспериментирует
tomatoes: а. точно вспомнил говорили об этом
samrrr: а нейронку как прикрутить к игре?
tomatoes: насколько знаю самому надо всё полностью сделать, никаких библиотек нет
Uljahn: в офлайне гонять игры и обучать, потом веса загрузить в код, упихнуть только в 100к символов
Uljahn: библиотеки-то для исполнения не нужны особо
Uljahn: вот для обучения - да
samrrr: ну это то понятно, а что на вход нейронке подать?
Uljahn: фичи
samrrr: чаво?
Uljahn: features
Uljahn: можешь попробовать стейт подавать и доступные ходы
Uljahn: но это тупиковый вариант, скорее всего
samrrr: да точно тупик...
Uljahn: можно граф борды подавать ещё, вторичные свойства придумать и т.д.
samrrr: уже лучше звучит
samrrr: во в легу промот выдали
samrrr: чё тут так мало народу?
Uljahn: потому что босс лютый в голде
Uljahn: зато в леге все крутые
samrrr: я всётаки вычислил чего босс такой крутой, он не делает 20к роллаутов, он использует оценку, вместо полного раскручивания цепочки
Uljahn: и какую оценку? повторить сможешь?
samrrr: по крайней мере когда я убрал роллауты в бесконечность и добавил оценку инициативы босс слился
samrrr: да генерик 3 уровня, оценивает насколько хороши дела в каждой миниборде
Uljahn: так как оценивает, по каким параметрам?
samrrr: ну и оценка прогресса по каждой из 8 линий поверх
samrrr: сколько надо ещё наставить, чтобы занять
samrrr: http://chat.codingame.com/pastebin/60d8a8b7-6272-4d66-8d53-45ca693bff96
Uljahn: ну, это звучит логично, но как на практике будет играть? топ-20 леги займёт?
samrrr: нет конечно, иначе в леге только 20 человек былобы
tomatoes: где-то на 120-е место после голды приземляются
samrrr: да, к тому и идёт
Uljahn: в районе кубера)
samrrr: тут главное по честному босса завалить, без редиректов
samrrr: смотри аж в топ 100 зашло
MadKnight: ну ты крут
MadKnight: samrrr
MadKnight: тыж ещё тут?
tutubalin: у меня новый фетиш
tutubalin: http://chat.codingame.com/pastebin/4b8f0287-bcb5-45bb-ba65-fc39ce3b5743
MadKnight: ага, ты
MadKnight: это показывал
MadKnight: но это же ооочень старый фетиш
tutubalin: только это уже совсем другая задачка )
MadKnight: непонел
MadKnight: что другая задачка? в чём прикол?
tutubalin: я раньше показывал решение Rational Number Tree
tutubalin: а теперь решение Find winning strategy
MadKnight: aaaa
MadKnight: чё, а контест на чём будешь пилить?
tutubalin: не знаю пока. наверное опять на сях придётся
MadKnight: да го на шарпы
tutubalin: может быть на TS попробую. он в принципе ничотак, и пошустрее питона
MadKnight: они по скорости почти как плюсы стали
MadKnight: и очень похожи на TS
tutubalin: шарпы я не знаю вообще :(
MadKnight: да TS списывали с шарпов
MadKnight: подгоняя под жс
tutubalin: это всё что я знаю про шарпы :)
MadKnight: а что ещё нужно знать?)
MadKnight: еулер их обожает
MadKnight: marchete и illedan тоже
MadKnight: на шарпах все контесты пилят
MadKnight: вообще отличный язык
MadKnight: затести
tutubalin: попробую
tutubalin: кстати вот интересно
MadKnight: продолжение будет?)
tutubalin: шарпы срисовали с джавы.
JS как бы не срисовали с джавы, но назвали в её часть
tutubalin: а TS срисовали с шарпа по мотивам JS
MadKnight: JS вообще какой-то студент изначально запилил
MadKnight: так TS и шарпы от одного создателя
MadKnight: от одного "автора"
tutubalin: а слышал про CEO мозиллы, которого прогнали элгэбэташники за то что он дал бабла сторонникам традиционных браков?
tutubalin: так вот это тот самый "студент", который JS придумал
MadKnight: а слышал как кола устроила сотрудникам тренинги, где прямым текстом говорили How to stop being so white"
MadKnight: ?
tutubalin: не, про это не слышал
MadKnight: https://cdn.newsapi.com.au/image/v1/597380bfdf845140bed73a3914e665ec?width=1280
MadKnight: https://www.entrepreneur.com/article/366132
MadKnight: могу в лс таких новостей покидать
MadKnight: tutubalin
tutubalin: да я не про то вобще
tutubalin: я про то, что JS придумал не совсем студент
MadKnight: а кто
MadKnight: ты слишком тонко сравнил
MadKnight: и слишком непонятно
MadKnight: tutubalin а чё ты не спишь?
tutubalin: https://en.wikipedia.org/wiki/Brendan_Eich
MadKnight: а ну ок
MadKnight: а, я кажется понял твоё офигенное сравнение
mitfity: как поменять аватар на этом сайте?
