tutubalin: без ссылки на задачу не понятно о чём речь
Uljahn: https://www.codingame.com/training/easy/a-mountain-of-a-mole-hill
vrabosh: оно оказалось оправданым, т.к. люди показали прикольные решения..
tutubalin: так это ж классическая задача на принадлежность точки многоугольнику
Uljahn: мэд куда-то пропал
Uljahn: судя по логам - обиделся, что его с чат-ботом сравнили в очередной раз :(
Uljahn: Automaton2000: не обижайте модов
Automaton2000: дак он его исследует на следующем ходу
Hamibar: надо написать что-то нехорошее и тогда он придет тебя банить
735487: может он расстроился что его в гоночки порекали?
735487: тут все время говорили что если ноды добавлять в отдельный список то быстрее будет чем по паренту возвращаться. что то у меня не так ))
Uljahn: а в нодах убрал парента?
735487: еще нет ))
Hamibar: а зачем вообще парент нужен?
Uljahn: чтобы статистику обновлять при бэкпропе после роллаута
Uljahn: у тебя рекурсия?
Hamibar: не цикл теперь. Не знаю быстрее это или нет. Я просто подумал, что с парентом только через рекурсию можно
Hamibar: но потом понял
735487: почти идеальный сабмит. 1 проигрыш смиту только ))
735487: я тут выяснил что оказывается вместо того чтобы сделать роллаут для всех детей сразу я делал роллауты из родителя но скоры вешал детям и визиты )) без применения хода. во блин. и самое интересное что оно работает еще ))
Hamibar: хех, всегда не понятно почему это вообще работает)
Hamibar: у меня как-то из терминальных нод продолжался поиск
tutubalin: ну он родителя всё равно оценивал
tutubalin: а чо там внизу дерева происходит не такое больше значение имеет
735487: почему в ide я против tomatoes за нолики 90% игр выигрываю а при сабмитах нет?
Hamibar: там раст
Hamibar: в дебаге вроде
Hamibar: посмотри на количество роллаутов у него в иде и на арене
tomatoes: собирались пофиксить это где-то месяц назад
735487: вот же ж засада
tomatoes: но это же кодингейм
735487: а я тут изменения тестирую )))
Hamibar: стал штрафовать за фри мувы. Вроде гораздо лучше пошло
tomatoes: у меня вроде по ощущениям тоже больше всего эти штрафы принесли
Hamibar: щас бы еще его размер отрегулировать)
tutubalin: неожиданная концовка:
https://www.codingame.com/replay/473080504
Hamibar: из серии никогда не сдавайся
Hamibar: прикольно, что этот штраф действительно работает)
Hamibar: я прямо не ожидал такого результата
wlesavo: чуть чуть поменял и баги починил количество роллаутов с 1.5к до 30к выросло
wlesavo: ух ты, сабмит нормально так пошел
wlesavo: сразу в сотку
Hamibar: можно в легу идти с 30к
wlesavo: я не уверен был что правильно считалось, но судя по тому что всех рекаю правильно
wlesavo: ножет где-то накручивается, хз даже
Hamibar: а дерево переиспользуешь?
wlesavo: ну если я правильно понимаю что это значит то да
wlesavo: результат старых нод оставляю
wlesavo: просто корень меняю
Hamibar: ну тогда точно в легу все пути открыты
wlesavo: начал дебажить с ассертами сразу дело пошло
Hamibar: я щас посмотрел, у меня до сих пор 30к где-то. А я думал, что увеличил:upside_down:
wlesavo: ну я в свои 30к чето слабо верю, слишком уж резкий скачек
wlesavo: правдо я от мап в хеше перешел к массивам, так что один ботлнек почистил
wlesavo: но конечно плюсы классная штука
Hamibar: если не стрелять себе по ногам
wlesavo: ну это да, но с указателей я прямо тащусь
wlesavo: опа, босса в иде выйграл
wlesavo: нормально так рекаю его даже
wlesavo: ой, у меня осталась маленькая константа эксплора со старой версии, поменял ваще босса даже на ноликах могу выйграть
wlesavo: ну это заявочка
735487: щас сделаю убер фичу RAND_SEED = rand()
wlesavo: странно откуда такие цифры, у меня рандом даже rand()% пока просто
735487: ну у тебя два варианта либо ты крут либо считаешь неправильно :)))
Hamibar: а может и оба вместе
MelnikovIgor: Или ничего из этого)
wlesavo: ну блин, нормальный вин рейт против босса играя на ноликах, видимо правильно считаю
wlesavo: но я не верю что у меня косяков там не осталось в плейаутах
wlesavo: в районе 20х мест застреваю
wlesavo: опа, ресабмит с другой константой 20/20 первых игр
Hamibar: константа прямо очень важна
wlesavo: ну ладно, скрестим пальцы
735487: а у кого какая константа?
tutubalin: у меня константа 0 )
wlesavo: у меня 0.3 ща, но я время не обнуляю при переиспользовании дерева
735487: это черезчур маленькая ))
Hamibar: сейчас что-то типа такого тестирую (isFreeMove ? 0.1 : 0.4)+(isTeclesMove ? 0.2: 0.0)
735487: что значит время не обнуляю?
Hamibar: до этого 0.4 была
735487: у меня 0,41
wlesavo: ну полное число
wlesavo: наверное и не надо, но была мысль что стоит с ним что-то делать
tomatoes: у меня сейчас там странная попытка сделать в зависимости от количества детей
wlesavo: оо первая игра с боссом
tomatoes: чем больше детей, тем меньше константа
wlesavo: а не не первая уже, лол
Hamibar: да ты его уже вовсю рекаешь
wlesavo: ни одного поражения 0-2 против босса зато есть победа 2-0
MelnikovIgor: tomatoes по идее UCT и так это коственно учитывает в отношении визита родителя к ребенку
wlesavo: чуть чуть не хватило, чето против бюосса последние 30 игр в топ5 ни одной игры не дыло
tomatoes: возможно как оптимизация срабатывает, мол если много детей, то возьми 1-2 получше и сойдёт
wlesavo: у меня реально много дало получается то что стейт начал хранить как число от 0 до 511 и переходы между стейтами += 1<<action, сразу все в массивы село
Uljahn: угу
wlesavo: правда когда вместо массивов сделал мапы такое хеширование вообще не дало прироста
wlesavo: по сравнению с тем чтобы на каждому шаге из массива рассчитывать даже
Uljahn: += и |= должны быть примерно одинаковы по скорости?
wlesavo: может наверное зависеть от длины
Hamibar: я тоже пробовал делать unordered_map где-то раз в 6 медленнее становилось
Uljahn: щас со второго места затолкаешь в легу
MelnikovIgor: нууу
Uljahn: затолкал
MelnikovIgor: Если в вашем языке нет проверки на переполнения...
wlesavo: у меня винрейт против него не очень, так что если затолкаю проще будет)
wlesavo: о затолкал
wlesavo: лол
Uljahn: в данном случае проверка не нужна, мы не ходим в занятую клетку
wlesavo: потом ради прикола свичнусь на питон и проверю место в леге
Uljahn: да, главное - винрейт против босса
Hamibar: я так ресабмитами опустил босса на пункт и пролез
wlesavo: самое удивительное конечно для меня это то что указатель на ребенка+1 = указатель на следующего ребенка
MelnikovIgor: Магия)
wlesavo: вообще
Uljahn: пока за пределы детей не выйдешь
MelnikovIgor: Тоже на плюсы скоро пойду наверное, вот упорюсь на шарпике доконца сначала
wlesavo: ну разумеется, да
Uljahn: в леге боты сильные, чел со второго места в топ 120 не войдёт, похоже
чего уж про питон из середины голды говорить - на уровне 140-го места, скорее всего
wlesavo: прикольно будет если скор отрицательный будет
MelnikovIgor: http://cgstats.magusgeek.com/app/multi-tic-tac-toe/MelnikovIgor
MelnikovIgor: Упарываюсь на шарпике
MelnikovIgor: Пока не упоролся
wlesavo: но сначала надо в легу просочиться, чето ощущение что баг какой-то остался в плейаутах
Uljahn: MelnikovIgor: потенциально в топ-15 можно на шарпах, но там вроде на минимаксе бот
MelnikovIgor: Uljahn прикольно было бы, но я в упор не понимаю как на минимаксе далеко уехали так, там же эвристика хорошая нужна, а если она есть, то почему бы MCTS не заюзать с ней
MelnikovIgor: Видимо там чтото гибридное MCTS+Minimax например
MelnikovIgor: А где ты нашел эту инфу?
Uljahn: потому что в крестиках лёгкие роллауты дают больше профита, наверное
Uljahn: но только когда их очень много
Uljahn: т.е. на медленных языках хорошая эвристика даст больше профита
Uljahn: проблема в том, что её сложно подобрать, а ванильный MCTS на плюсах сам в легу закатывается
wlesavo: 70к сим это очень много?
wlesavo: видимо действительно чето не так считаю, по профилированию рандом был узким местом самым, фаст рандом добавил сразу скакнуло на 70к
tomatoes: у себя или на сайте?
tomatoes: у меня раза в 2 просто отличаются
Uljahn: если на втором ходу, то офигенно
wlesavo: на сайте
wlesavo: на втором да
wlesavo: может правда где-то накручиваю
Uljahn: 25к для леги должно хватать при отсутствии багов
wlesavo: но вроде нет
wlesavo: ну вот ищу баг теперь, может результат где-то не верно определяю
Hamibar: А ты смотришь сколько в корне визитов? или отдельной переменной считаешь?
Uljahn: wlesavo: у тебя фримувы странно работают
wlesavo: Uljahn есть реплей?
wlesavo: Hamibar отдельной переменной при вызове роллаута
wlesavo: и это без учета проходов в терминальную ноду
wlesavo: то есть когда дерево полностью построено 0 роллаутов
Uljahn: https://www.codingame.com/replay/473105236
45-й ход
wlesavo: там на 47 фримув от крестиков только
Uljahn: я про ход 1-4
tomatoes: наверно про то, что можно было забрать без выдачи фримува
wlesavo: а точно, спс
wlesavo: странное поведение
wlesavo: хотя и объяснимое
tomatoes: такое же было, но не помню чем именно решилось
tomatoes: особенности мцтс наверное, мол у противника больше ходов и среднее получается выгоднее. или что-то вроде этого :thinking:
wlesavo: изза того что менее точноая оценка, да, одинаковые состояния же не мерджатся здесь, ну у меня по крайней мере
wlesavo: ща сделаю паниш на фримувы
Hamibar: 70к роллаутов я думаю и так должны в легу выходить)
wlesavo: да похоже где-то косяк раз не хватает
Hamibar: а ты в конце ноду по количеству визитов выбираешь?
wlesavo: и так и так пробовал, по визитам и по победам, но по победам почему то лучше играет, хотя на бумаге по визитам должно лучше быть
Hamibar: я просто по формуле выбирал и не мог понять долго где баг)
wlesavo: а, ну так то да) не, недавно как раз читал и там было небольшое обсуждение что по визитам возможно даже лучше
Hamibar: у меня примерно одинаково
wlesavo: ну примерно, да, я уже что то менял можно еще раз попробовать
Hamibar: вернее я не заметил разницы
Uljahn: я только что читал, что можно выбор регулировать температурой))
Uljahn: http://matthewdeakos.me/2018/07/03/integrating-monte-carlo-tree-search-and-neural-networks/
Uljahn: в самом конце формула
Uljahn: Choosing an Action
Uljahn: подумал, раз у рекурса получилась нейронка на уровне дна леги, может удастся на питоне запилить и порекать голд босса :relieved:
Uljahn: Automaton2000: фантазии уровня кубера
Automaton2000: после форчана таким не удивить
wlesavo: нашел проблему, а вот где возникает не понятно пока
735487: что за проблема?
wlesavo: ассерт на 0 детей стриггерился, почти нашел уже где
tutubalin: а у меня рандом не обновлял сид.
долбанные ассемблерные вставки
wlesavo: а зачем сид обновлять?
tutubalin: в смысле стейт
tutubalin: я так и знал, что у меня где-то какая-то тупая ошибка
wlesavo: го вместе в легу теперь
tutubalin: ща посмотрим чо выйдет
tutubalin: пока что опять там же застрял на 50-60
wlesavo: я нашел косяк свой, хотел в одном месте сэкономить в итоге оно не работало
Uljahn: пофиксил, и играть стало хуже?))
wlesavo: не до конца, ща переделвыаю кусок вообще
tutubalin: пофиксил рандом. вообще ничего не изменилось
tutubalin: мистика какая-то
wlesavo: лол
wlesavo: ну хоть не хуже стало
wlesavo: у меня просто косяк был редкий и не прям критичный, а фикс кривой задевал вообще все
Munchkin: "пофиксил, и играть стало хуже?))" - слезу пустил
Uljahn: ну это же классика
Munchkin: Я теперь буду с дрожащими руками каждый раз, когда на первое место выхожу, в .txt сохраняться)
wlesavo: лучше коммитить с пометкой топ1
tutubalin: я перед каждым сабмитом создаю тэг с датой и временем. когда бои заканчиваются, создаю ещё один тэг с лигой и местом
tutubalin: первый тэг скриптом, второй ручками пока
wlesavo: умно
wlesavo: эх, чутка не хватило, но босса подпушил вниз
wlesavo: 0.5 очков всего
wlesavo: ttt
wlesavo: ееее
wlesavo: изи
tomatoes: :thumbsup:
Uljahn: грац
vrabosh: неужели 23млн вариантов выигрышных в крестиках всеволишь для поля 9х9?
vrabosh: я даж не думал, что так много
735487: 512
735487: а ты для 9 на 9 посчитал
vrabosh: я все варианты просчитал с противником
vrabosh: вот так '112112201'
vrabosh: или гдето ошибся или хз
vrabosh: в тиктактое правила же не такие, что ты типа ходишь по очереди на одном поле.
vrabosh: а нет 3814, там просто дубликаты накидались)
vrabosh: ну это уже радует..
vrabosh: это 23млн вариантов развития игры
vrabosh: на победу
tomatoes: должно быть побольше мне кажется :thinking:
vrabosh: на 9х9, не на весь тиктак.
vrabosh: это наверно 23млн*9 * (классика ходов крестиков)
vrabosh: или 9 лишняя тут?
Hamibar: сколько бы их не было все дерево за разумное время не построить
tomatoes: если грубо посчитать что 8 вариантов хода, то уже на 10 ходу получается 8^10=миллиард примерно
tomatoes: поворотами можно скроить немного
Hamibar: а фри мувами добавить)
wlesavo: но мувы могут к одной доске приводить, а досок 3^81 разных, правда не все доступны, но думаю порядок не изменится
wlesavo: это 10^40 даже если доступна сотая часть...
vrabosh: а кто нить пытался делать крестики с асемблер вставками?
wlesavo: Hamibar а у тебя чисто мктс или есть эвристики какието хитрые?
Hamibar: теклес мувы
wlesavo: ну кроме этого
Hamibar: старт с 4 4
Hamibar: штраф за фри мув
vrabosh: что такое теклес мувы?
Hamibar: когда стоишь на пустой доске ходить так, чтобы враг на ней же остался
tomatoes: 00 88 08 80 и сайды еще
Hamibar: надо наверное познакомиться с профилировщиком и пытаться оптимизировать
wlesavo: у меня просто под 70к роллаутов, но они ни во что не выливаются, интересно это баг где-то или уже можно эвристики крутить
735487: tomatoes: а ты чего такого хитрого добавил что сегодня заметно еще прибавил?
tomatoes: а рандом нормальный выдается?
tomatoes: я попытался не рандомом раскрывать, а по очереди
tomatoes: а очередь эвристикой
735487: wlesavo: с 70к должен в топе быть уже в 20 как минимум
wlesavo: распределение не смотрел
wlesavo: а вот еще вопрос, за поражение вы 0 или -1 даёте?
Hamibar: а ну еще в дереве если мой ход и есть теклес мув - то у нода будет только 1 ребенок
tomatoes: оно там не принципиально, но мне с -1 считать проще
Hamibar: 1 - победа 0 - поражение 0.5 ничья
wlesavo: хм, ща попробую теклсы нормально учесть
tomatoes: я теклесы не сильно форсирую
735487: фишка в том что твоя победа должна давать противнику поражение и наоборот
wlesavo: ну это понятно что есть, просто tomatoes вроде упоминал про отрицательный скор по этому спросил
tomatoes: в уцб для противника просто -score берется и в солвере с +/- бесконечностью проще немного
YurkovAS: солвере?
tomatoes: а найду сейчас
tomatoes: https://dke.maastrichtuniversity.nl/m.winands/documents/uctloa.pdf
YurkovAS: и у тебя солвер?
YurkovAS: спс
tomatoes: но по ощущениям не сильно помогает
735487: я пытался несколько раз делать солвер и так и не смог
tomatoes: сравнивал две версии и гдето 50-55% винрейт плавал
735487: солвер наверное хорош в конце когда уже до конца досчитывает
YurkovAS: да, вот интересно, за счет чего у тебя такое превосходство.
механика какая-то или евристика.
YurkovAS: скоро рекурса порекаешь
735487: я сегодня и вчера чего только не попробовал. если вчера стабильно в топ 10 заходил и даже на 6 был 1 раз то сегодня топ 12 еле еле )
tomatoes: тут скидывали ссылку, сейчас найду
tomatoes: http://matthewdeakos.me/2018/07/03/integrating-monte-carlo-tree-search-and-neural-networks/
tomatoes: у меня похоже на чтото такое, но P() не сеткой, а эвристикой выдается
tomatoes: где-то в диапазоне 0-2 плавает
YurkovAS: tomatoes спасибо!
tomatoes: и там в конце поиска по винрейту, а не по визитам надо будет выбирать. ломаются визиты изза доп множителя
YurkovAS: tomatoes ты же борд в мктс нодах хранишь?
у себя проверял - играет заметно хуже, чем когда без нее.
tomatoes: два списка, один с нодами, один с играми
tomatoes: пытался переделать, но непонятная ошибка была и забил :sweat_smile:
Uljahn: зачем стейт в нодах хранить?
wlesavo: блин, у меня же нет симуляции на первом ходу
wlesavo: наверное это поиочь должно немного :smiley:
tomatoes: сначала показалось что так проще
Uljahn: у jacek'a бот за счёт первого хода выезжает (20к на втором ходу, но дерево переиспользует), плюс простые эвристики
tomatoes: потом стало работает и ладно
YurkovAS: Uljahn может он не так считает? когда экспериментировал с экспандом всех детей - у нас было одинаковое кол-во роллаутов.
Uljahn: у него там 1ply win check
YurkovAS: а что это значит?
Uljahn: смотрит на ход вперёд - можно ли выиграть миниборду
Uljahn: т.е. для хода проверяется, не дашь ли ты противнику такую возможность
Uljahn: "i have 1-ply check for win and moves that can win small board are twice as likely chosen as others"
wlesavo: а это в оценке использовать или в роллаутах?
wlesavo: а, ок, неплохо
wlesavo: можно добавить даже
Uljahn: в роллаутах, наверное
YurkovAS: эту проверку проще сделать наоборот, на -1 ход. при экспанде все уже просчитано.
YurkovAS: при экспанде родителя, можно проверить - закрыл он минидоску
wlesavo: да в роллаутах это имеет смысл, по хорошему роллауты случайные это плохо
tomatoes: у меня наоборот получилось :grinning:
Uljahn: https://cg.spdns.eu/wiki/Chat:World/2020-06-11
"jacek: well i have 1-ply check for win"
Uljahn: там может что-то ещё есть, я не всё себе скопировал в заметки
YurkovAS: а, затуп, забыл про рандомные игры.
YurkovAS: так и что будет, если в процессе закроет минидоски? бонус начислить
Uljahn: хм, наверное, не только минидоски, но и всей борды, т.е. глобальный win
tomatoes: или не наоборот. локально с "умными" роллаутами лучше играет :thinking:
YurkovAS: tomatoes а ты как проверяешь локально? в брутал тестере по мин 300 игр и за обе стороны?
tomatoes: скрипт на питоне
Uljahn: т.е. если ты определённым ходом даёшь фримув сопернику, и соперник может сделать insta-win, то этот ход надо стараться избегать :thinking:
Uljahn: tomatoes: две своих версии сравниваешь?
tomatoes: уже штук 5
tomatoes: но вообще да
Uljahn: а времени столько же выделяешь?
Uljahn: есть подозрение, что от количества сим качество игры будет сильно меняться
tomatoes: тоже 95, но роллаутов локально больше
wlesavo: забавно, но + 500к роллаутов на первом ходу почти ничего не даало
Uljahn: wlesavo: а ты плюсы себе локально поставил?
wlesavo: ну у меня вижуал студия стояла, я на шарпе когда то делал пару веб приложений и недавно на питоне тоже в ней начал писать
tomatoes: https://www.codingame.com/replay/473148142 :cold_sweat:
wlesavo: профайлер в студии классный конечно, ничего не скажешь
wlesavo: tomatoes хорош, на ноликах
wlesavo: мне кажется у меня фундаментальный косяк где-то
Uljahn: может за нолики стоит теклесы отключать?
Uljahn: или вероятность им понизить
tomatoes: у меня просто с кастомным рандомом косяк был и выдавалось раза в 2 больше роллаутов чем обычно
Uljahn: 7-1 на 14-м ходу был довольно неожиданным (в реплее выше)
tomatoes: маленькая эвристика есть чтоб "ломать" потенциальные выигрышные линии
tomatoes: возможно она сработала както
Uljahn: и карлисо потом взял миниборду с последующим фримувом, замечал за ним такое
Uljahn: если на всех минибордах создать угрозу взятия, то у него алгоритм ломается, выдаёт прям совсем хреновые ходы
tomatoes: такое ощущение что со смарт роллаутами за 0 чаще проигрываю
tomatoes: а в целом примерно так же идет
vrabosh: невкурсе как можно спомощью кода очищать в юпитере окно вывода?
vrabosh: ну типа чтоб там симуляцию сделать
vrabosh: нашел
vrabosh: вы все про крестики болтаете, я переодически тоже к ним возращаюсь)
Uljahn: о, ты в сильвере уже
vrabosh: я тогда 2 часов попрогаммил..
vrabosh: посмотрел что да как..
vrabosh: код вообще простой.. хочу по приоритету:
1. Если могу захватить точку
2. Не хочу туда где противник может захватить.
vrabosh: вот этот скрипт мне 4 место в сильвере дало
vrabosh: потом начал писать функцию которая дерево строит.. и понял, что цифры оч большие для питона.. и бросил..
vrabosh: Но мне кажется, что логикой можно взять легенду.. просто долго продумывать это все.
tutubalin: ВАУ
tutubalin: я в легегде
tutubalin: а я уж думал место проклято
tutubalin: что не делал - всё время болтался в районе 40-60
tutubalin: все баги в UTC пофиксил - всё равно только 33 место
tutubalin: а потом поменял константу - и вуаля!
tomatoes: :grin:
tutubalin: но у меня была мечта пройти в легу без UTC
tutubalin: UCT точнее
tomatoes: https://github.com/leela-zero/leela-zero/issues/860 эт в гугле сегодня попалось, тоже про другие варианты много пдф
tomatoes: но сходу не осилил, вникать надо
tutubalin: обошёл босса на 3.2 очка
tutubalin: все мои страдания были не зря )
vrabosh: 13513 in awin - это dict, есть еще быстрее способ проверить, есть это число или нет?
tutubalin: самый быстрый - массив булеанов для всего интервала чисел
vrabosh: да так есть разница aaWin[13513]
vrabosh: это list
vrabosh: быстрее уже нет?
vrabosh: нампи проверю еще на всяк случай
tomatoes: а сколько всего и сколько из них труе?
wlesavo: tutubalin хорош!
wlesavo: у меня тоже массив булеанов, всего 512, тру где то половина
tomatoes: тоже, но 13513 удивило
tomatoes: хотя может и не про крестики вообще разговор
vrabosh: (18913, 3814) - max, len
vrabosh: 3814 вариантов выигрыша
vrabosh: последнее число это допустим вот '221221111'
vrabosh: такоеж может быть на поле?
Hamibar: если у тебя 2 бита на клетку то всего 262144 вариантов
vrabosh: ну да, но мне не нужны те варианты которые не выигрышные
vrabosh: а максимальный выигрышный это 18913
vrabosh: потомучто такой ситуации 1111111111 на поле быть не может
Hamibar: ну может ты как-то по другому представляешь
vrabosh: надо не поленится и доделать свою идею
vrabosh: посмотреть что получется
Hamibar: только сейчас понял, что в крестиках взял самое высокое место из всех мульти) теперь можно и подзабить
Hamibar: самое интересное посмотреть как люди 100к+ роллаутов делают
tomatoes: 0b001001111 и 0b110110000 в таком виде попробуй хранить
tomatoes: тогда список для лукапа получается 512 всего
tutubalin: ну у меня было 100к+, пока без UCT )
Hamibar: но по идее большой массив же не режет скорость?
735487: режет если весь в кеш не влазит я думаю
Hamibar: хм. Тогда можно попробовать
735487: я попробовал прерывать роллауты. тогда и 200к получается. но у меня нет эвристики
Hamibar: блин хотел уже подзабить, а тут еще идеи в голову пришли)
735487: да я уже больше чем полгода с них не слезу никак. и с гоночек тоже. то туда тосюда возвращаюсь ))
vrabosh: tomatoes, и как быстро такое обрабатывать в питоне, я не нашел логику..
tomatoes: на счёт питона даже не знаю 🤔
tomatoes: https://www.codingame.com/playgrounds/48392/bitboard-for-tic-tac-toe-game но вообще идея такая
735487: tomatoes: а у тебя получается роллаутов нет и их заменяет эвристика? что то сложно ту статью понять
tomatoes: есть, там получается что мцтсу просто рекоммендацию даешь, мол эта нода скорее всего получше/похуже и оно старается её больше/меньше проверять
tomatoes: а в остальном всё так же остается
735487: получается к коэффициенту просто оценка добавляется?
tomatoes: ага
735487: а от посещений тоже зависит?
tutubalin: я тут почитал про RAVE
Uljahn: так это можно начальный скор накидывать эвристикой, и если эвристика не угадала, со временем он рассосётся
tutubalin: там в UCT добавляется пара слагаемых
tomatoes: не, в остальном как есть формула
735487: я его так и понял толком. я вообще кучу всего перечитал но это пипец как сложно чет
tutubalin: которые показывает не только успешность клетки в текущем розыгрыше, но и вообще среди всех розыгрышей
tutubalin: для простых крестиков-ноликов этом прям вообще хорошо работает. но похоже и в UTTT тоже должно помочь
tutubalin: грубо говоря, хоть порядок ходов и имеет значение, но есть некоторые ключевые точки, которые в любом случае лучше других
Hamibar: меня простое изменение коэфа если это фри мув подняло с 40 до 20. если там какую-нибудь норм эвристику приделать должно быть намного лучше
wlesavo: tutubalin для этого надо ноду к полному стейту привязывать же вроде? у меня стейт вообще никак не хранится для ноды
wlesavo: сделал ply1 check
wlesavo: но результат чето не заметил
tutubalin: у меня стейт тоже в ноде не хранится.
один сквозной проходит
tutubalin: по идее, тут надо хранить только статистику для клеток, отдельно от нод
wlesavo: ну а ключевая точка это получается не нода а стейт все таки
wlesavo: а, самих клеток прям
tutubalin: ага
wlesavo: по логике ее надо занулять только после хода
wlesavo: иначе получится неконтролируемое что-то
tutubalin: типа: "где-то в другом конце дерева сходили на 8-8 и победили. может стоит и в этой ветке туда сходить?"
wlesavo: это главное очень легко добавить
wlesavo: хм, или дал этот ply1 что-то, вроде сабмит чуть лучше пошел
vrabosh: int('101002200',3) + int('010000000',3) = '111002200'
tutubalin: https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Improvements
vrabosh: может есть у кого идеи, как легко по скорости узнать какие числа имеют нули?
vrabosh: щаз поясню
MelnikovIgor: В байте?
wlesavo: короче предрасчитал для всех комбинаций пустой борд + ходы одного игрока на этом борде победные ходы и чисто в роллаутах сделал в два раза больше детей победных при случайном выборе
vrabosh: в питоне же байтов нет.. они конвертируюстя в обчные
tutubalin: там про RAVE написано. я сперва испугался формулы. а оказалось это всего лишь линейная комбинация винрейта здесь и винрейта глобального
wlesavo: с коэффициентами просто получается?
vrabosh: т.е. есть число 101 и я хочу узнать, что к нему я могу прибавить только 010
wlesavo: а ucb член остается?
vrabosh: как это сделаь дешево?
tutubalin: vrabosh x ^ 0b111
wlesavo: vrabosh a + 1<<1
MelnikovIgor: !101
tutubalin: ! - это логическое не
MelnikovIgor: ну сделай битовое
tutubalin: тут надо или тильду или xor
MelnikovIgor: Да, тильда
MelnikovIgor: ~101
tutubalin: если прямо все биты инвертировать, то тильда
MelnikovIgor: ну можно с маской ~101 & 111
vrabosh: вот число 1010, мне надо из этого получить 0100 и 0001
tutubalin: если какие-то конкретные, то xor
tutubalin: 101 ^ 111
vrabosh: очень дешево
tutubalin: vrabosh на питоне?
vrabosh: да)
vrabosh: относитльно питона
vrabosh: чтоб это было примерно как два сложения
vrabosh: питоновских. ну или три
wlesavo: я такое предрасчитываю и храню с доступом по ключу
vrabosh: блин причем у меня еще троичная система)
tutubalin: а если 101010101?
tutubalin: тебе надо все 5 единичек получить?
vrabosh: 10201, надо чтоб было 01000, 00010
Uljahn: в numpy я делал вектор степеней двойки (либо единичку сдвигать влево), потом делаешь & с инвертированным числом, он бродкастится в нужный вектор, потом только нулевые элементы удалить
wlesavo: я по совету томатоса разделил отдельно борд для каждого игрока и отдельно пустые клетки, очень удобно
Uljahn: троичная система слишком не удобна
vrabosh: tutubalin , да надо все пять, яж по ним дальше хочу идти проверять выиграю иль нет)
wlesavo: ply1 check дал гдето 40 мест
Uljahn: :scream_cat:
wlesavo: ну я был в районе 100
735487: могу на плюсах показать
vrabosh: покажи плз
735487: uint16_t moves = ~(b.fillboard) & 0b111111111; while (moves) { uint16_t bb = __builtin_ffs(moves) - 1; moves = moves & ~(1 << bb);
Uljahn: wlesavo: инставин через ход проверяешь? или только взятие миниборды?
tutubalin: x & -x даёт самый младший бит
wlesavo: Uljahn только взятие борды и только в роллаутах
735487: а роллаутов на сколько меньше стало?
tutubalin: while x:
bit = x & -x
x -= bit
wlesavo: инставин через ход при таком числе роллаутов будет и так виден мне кажется
Uljahn: хм, и правда
wlesavo: amurushkin процентов 5-10 на глазок, не тестил сильно, 2ой ход в раоне 50к осталось
wlesavo: я красиво предрассчитал все
735487: у меня в роллаутах сейчас просто рандом и все. а так прийдется всех детей проходить и выбирать
vrabosh: tutubalin , вау круто, с младшим битом, щаз буду пробовать
wlesavo:
amurushkin у меня сразу выдается адрес и число детей для комбинации борд+игрок, просто победные ходы в этой комбинации в два раза чаще, дальше просто рандом от полного числа детей
vrabosh: всеравно сложно... как быть в таком случае 002112, надо первые нули..
735487: wlesavo: а они у тебя и в дереве тоже дублируются?
tutubalin: откажись от троичной системы. храни игроков отдельно
tutubalin: потом просто делай |
wlesavo: amurushkin в дереве нет, отдельно для дерева оставил
wlesavo: ща попробую в три раза чаще
tomatoes: попробуй 3х3 сначала сделать как по той ссылке
vrabosh: наверно от троичной откажусь.. попробую с двоичной сделать. посмотрю что будет.. как раз сравню
Uljahn: как я провёл лето))
MelnikovIgor: amurushkin подбираюсь к тебе на шарпике
MelnikovIgor: Ппц меня подмывает на плюсы переписать и посмотреть)
vrabosh: tutubalin, как -х работает?
Uljahn: wlesavo: а что происходит в случае, когда 1ply check срабатывает?
wlesavo: Uljahn ну у меня не явная проверка, просто грубьо говоря у стейта есть массив детей, и тех которые могут закрыть борд в нем в два раза больше
wlesavo: всмысле они дважды встречаются
Uljahn: а, как у робо вероятность повышается для ходов, выигрывающих борду
wlesavo: но кстати если в три раза больше то хуже начинает заметно играть, а подтюнить в такой реализации плохо получается
Uljahn: я думал, мы ещё на полхода вперёд смотрим, и не даём противнику ход, где он мог бы закрыть борду
wlesavo: ну это уже автоматом, если это важная борда то отдав такой ход в роллауте противник более вероятно выйграет
Uljahn: vrabosh: -x наверное переводит двоичное число в дополнительный код
wlesavo: надо по тутубалину сделать будет, статистику клеток завести, выглядит просто реально
Uljahn: "где-то в другом конце дерева сходили на 8-8 и победили. может стоит и в этой ветке туда сходить?"
wlesavo: и все таки не покидает меня ощущение что где-то баг есть
vrabosh: -х == -1*x - просто как это в байтах выглядит. надо почитать будет..
Uljahn: Дополнительный_код есть в вики
MelnikovIgor: Ребята, попал в топ 30 на Шарпике
MelnikovIgor: Такой каеф
MelnikovIgor: Когда думаешь уже нечего выжать, появляется что-то)
wlesavo: неплохо, да
wlesavo: а что зараешало?
MelnikovIgor: Микрооптимизации
MelnikovIgor: Возможно баги были
MelnikovIgor: Кручение коэффициентов
tomatoes: или не было)
wlesavo: да все таки похоже есть баг какойто, вероятность победы очень странно ведет себя
MelnikovIgor: Но странно, что по сравнению с вами у меня роллаутов мало, на 2ом ходу 12-15к
MelnikovIgor: Вы как считаете?
wlesavo: я по вызову роллаута, проходы от корня до терминальной ноды не считаю за роллаут даже
735487: у меня количество запусков dorollout
MelnikovIgor: У тебя несколько роллаутов на 1 итерацию MCTS?
wlesavo: я дохожу до ноды и раскрываю всех детей, суммарную статистику отдаю вверх по дереву
tomatoes: я в первые ходы по несколько (2-5) сразу запускаю
735487: 1
MelnikovIgor: tomatoes сколько на 2ом ходу выходит
wlesavo: может поэтому цифры такие большие получаются конечно
MelnikovIgor: Я по 1 разу и у меня 12-15 к на втором ходу
735487: у меня от 50к до 90к
tomatoes: если по 1, то помоему гдето 30-50 было
MelnikovIgor: Понял
MelnikovIgor: Дело не в количестве роллаутов, а в умении ими пользоваться :)
735487: у меня почему то запуск нескольких сразу дает плохое качествы игры
wlesavo: я тут подумал нулевая сумма лучше наверное, потому что накопление по логике не должно происходить
wlesavo: все таки сделаю ща ради интереса, на статистику чтобы приятнее смотреть было
Uljahn: не забудь коэффициент поменять
MelnikovIgor: Ну это же слагаемое, оно для всех чайллдов смещение дает, но надо коеффициент 2го слагаемого под рендж подбирать
Uljahn: накопление только на переполнение может повлиять, не?
wlesavo: хм
MelnikovIgor: Этож сколько раз надо победить чтобы переполнилось?)
Uljahn: если дерево переиспользуешь, например
MelnikovIgor: Нелеально
wlesavo: у меня странная статистика лезет, надо баг искать видимо
MelnikovIgor: Ну всегда можно к 1ому слагаемому применить деление (сбалансировав 2ое)
wlesavo: ни при какой комбинации победить не могу, а числа заоблачные все еще для этого стейта, именно отношение win/visits
wlesavo: короче пойду искать ща
Uljahn: а скор в инте хранишь или float?
wlesavo: float, но я не храню, вызываю, но же от времени зависит
wlesavo: и значение нужно только один раз все равно
Uljahn: я про скор ноды, он же аккумулируется
wlesavo: просто усеорить можно заметно, просто пока не понятно зачем
wlesavo: отдельно храню победы в флоате и посещения в инте просто
vrabosh: не запутаться бы.. нумирация клеток идет у меня с нишнего угла правого, потомучто так быстрее
vrabosh: 1<<mgc - так быстрее чем 1<<(9-mgc)
Uljahn: в питоне, скорее всего, даже не сможешь замерить разницу - тормозить будет в других местах
Uljahn: это типичная преждевременная оптимизация
Uljahn: я поэтому пишу так, чтобы было удобнее дебажить, а когда заработает без багов, можно будет параллельно пилить оптимизированную версию
Hamibar: ощущение, что сейчас контест по крестикам идет)
Hamibar: ощущение, что все только их и пилят
735487: в ручате наверное да )))
Uljahn: tomatoes: спасибо за ссылку на обсуждение leela-zero, прям зачитался
vrabosh: по go бы подобный контест сделать
tomatoes: othello есть какое-то
735487: в отелло стандартный я сам любитель поиграть. возможно смог бы эвристику написать
wlesavo: нашел багу знатную
wlesavo: почти все ничьи неправильно считались
wlesavo: теперь действительно не понятно как я в легу попал
vrabosh: if not ~(int('1000',2)|int('0101',2)) & int('0100',2): print('сюда нельзя')
vrabosh: подскажите можно это быстрее сделать?
vrabosh: просто хочу один раз уже написать, чтоб потом на С было проще переписать когда нить
wlesavo: MelnikovIgor иду тебя рекать))
tomatoes: не знаю на счёт быстрее, но числа можно сразу писать 0b1000
vrabosh: not ~(100|0101) & 0100
vrabosh: это я вам для удобства покзываю
vrabosh: ой точно можно 0b00 писать)
wlesavo: хехе https://www.codingame.com/share-replay/473185619
wlesavo: конечно на крестиках, но все таки, поставлю в рамочку буду детям показывать
Uljahn: ты же вроде недавно только начал в плюсы вкатываться - ещё накрутишь им хвосты
wlesavo: меньше недели, где то дня три четыре на крестики и все
wlesavo: но смитс то легенда крестиков))
Uljahn: ну, ты же не один будешь, всем чатом будем помогать
