Chat:Ru/2020-06-16

From CG community
Jump to navigation Jump to search

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: ну, ты же не один будешь, всем чатом будем помогать