Kadim: как убрать всплывающие менюшки при наведении мышки на код?
Uljahn: это вообще возможно? тут встроен Monaco editor
tutubalin: ты имеешь в виду autocomplete?
Kadim: когда ошибка в коде то при наведении мышки всплывает менюшка, проверку на ошибки можно выключить?
Uljahn: Automaton2000: можно, но только нельзя
Automaton2000: один и тот же код
BorisZ: Kadim можно забить на встроенный редактор - в настройках есть пункт использовать внешний редактор
BorisZ: надо будет установить расширение и пиши код локально где привык
BorisZ: оно будет синхронизироваться
Uljahn: такая настройка вроде только в хроме
BorisZ: у меня хром, из оперы тоже заводил, за остальные не скажу
Hamibar: При стандартной формуле UCB дерево должно получаться широким правильно? или у меня косяк и оно должно быть достаточно глубоким?
BorisZ: там же константа в формуле которая регулирует соотношение ширина/глубина
Hamibar: ага. Просто на статейке в хабре написано, что при ее увеличении глубина растет, а у меня наоборот при уменьшении растет глубина
Hamibar: вот я и думаю, там опечатка
Hamibar: или у меня баг
tomatoes: при увеличении ширина растет
Hamibar: ага, спасибо. Тогда все ок
tutubalin: не всё так однозначно
Hamibar: вот какой выбрать это действительно неоднозначно.
BorisZ: тут то просто, перебором
Hamibar: нужно похоже что-то типа брутал тестера ставить
BorisZ: на самом деле это не очень принципиально
BorisZ: я пробовал, у меня играло примерно одинаково в диапазоне от 0.4 до 1
BorisZ: не помню точно уже цифр
BorisZ: если больше или меньше то заметно было ухудшение результатов
Hamibar: я тоже пришел к коэфу меньше 1)
BorisZ: количество ролаутов важнее, надо туда копать
Uljahn: может, лучше cg benchmark всё же?
BorisZ: игр мало там получается
Hamibar: мб и лучше)
BorisZ: а против кого играешь вроде примерно пофиг
Uljahn: против реальных противников, а не против потенциально забагованного своего бота
Uljahn: сколько раз такое было - пилишь фичу, а становится хуже, выпиливаешь баг, становится ещё хуже
tomatoes: тоже где-то 0.5-0.7 стояло. потом переделал скор роллаута от -1 до 1 и коэффицент увеличил в 2 раза
т.е. 1-1.4 стал
Uljahn: ну это как раз логично
Uljahn: коэф зависит от значений наград
BorisZ: да, кстати, наверное логично, должна быть зависимость от того как исход взвешен, у всех по раному
Uljahn: в статьях встречал оба случая
Uljahn: т.е. это не принципиально, кому как удобнее, но важно помнить про зависимость
Uljahn: оптимальное значение всё равно перебором искать, а тут типа отправная точка
tutubalin: по идее MCTS - не совсем подходящий случай для UCB
tutubalin: UCB основывается на предположении, что испытания независимые
tutubalin: а тут они ещё как зависимые
BorisZ: почему зависимые то? разверни тезис )
BorisZ: при данном ходе имеем некоторое множество- дерево продолжений
BorisZ: много раз проходим по дереву этому случайно выбирая ветку - роллауты
BorisZ: каждый ролаут независим от остальных ролаутов
BorisZ: в дереве этом
wlesavo: но по сути каждый путь путь начинается из корня и в этом смысле испытания зависимые, это не совсем бандиты
BorisZ: друг от друга то не зависимые
BorisZ: от начальных условий - все одинаково зависимые
wlesavo: по сути роллаут это путь от корня до терминальной ноды, первая часть пути детерминирована, и она зависит от предыдущих испытаний
BorisZ: может tutubalin имел ввиду что это наше чистое псевдо дерево ролаутов постепенно превращается в настоящее дерево с нодами, в котором выбор уже не случаен?
BorisZ: я думал речь идет про лолауты из одной и той же ноды
BorisZ: лолауты лол
wlesavo: а, если из одной и той же то да, можно считать независимыми
wlesavo: но это если ты их пачкой запускаешь
wlesavo: а если по одному то у тебя не будет двух роллаутов из одной ноды же
BorisZ: потому что ноду сразу разворачиваем после первого ролаута?
wlesavo: ну да
wlesavo: хотя никто не мешает модификацию прикрутить чтобы не разворачивать пока там статистика не наберется небольшая
wlesavo: но вероятно будет хуже
tutubalin: допустим, уже построена часть дерева. мы начинаем ролаут из корня. выбираем ребёнка по формуле. потом опять выбираем ребёнка по формуле, потом ещё раз... это уже не совсем рандом
BorisZ: это не ролаут - тут путаница в терминологии
tutubalin: ну плейаут
BorisZ: вроде все называют ролаутом случайное доигрывание из уже построенной ноды
wlesavo: если роллаут именно из ноды считать то его начальное положение все равно зависит от предыдущих испытаний, а значит и результат испытания зависит
tutubalin: ну вот по идее формула должна работать для терминальных нод, где действительно сталкиваемся с рандомом
BorisZ: путь вниз по построенному дереву делается по формуле - он отношения к рандому не имеет - как я понимаю
tutubalin: вооот! а формула основана на предположении, что испытания случайны и независимы
tutubalin: вот полный курс про UCB:
https://banditalgs.com/2016/08/01/table-of-contents/
BorisZ: ролауты из одной ноды не зависимы от других ролаутов из той же ноды
tutubalin: как называется, когда из корня идёшь?
BorisZ: а если они из раных нод то вобще бессмыслено про независимость говорить
tutubalin: представь, что у тебя многорукий бандит, но шансы выигрыша на каждой руке не постоянны, а меняются в зависимости от того, сколько раз ты эту руку уже дёргал
BorisZ: в нашем случае это не так ведь
BorisZ: допустим мы запретили дереву расти
BorisZ: просто проходим сверху вниз, копим статистику
BorisZ: ролауты из одной ноды не влияют на ролауты из других нод
BorisZ: на результаты
BorisZ: они могут повлиять на частоту, с которой мы будет посещать другие ноды
Uljahn: из корня идёт selection до неразвёрнутой ноды, потом идёт playout (rollout)
BorisZ: но этот процесс и так не должен быть случайным
BorisZ: из неслучайности этого процесса - выбора нод, мы извлекаем выгоду - дерево растет не равномерно как было бы при случайном выборе
BorisZ: а в интересные места глубже
tutubalin: это понятно
tutubalin: но вот конкретно вот это корень из логарифма берётся на основе предположения о независимости испытаний
BorisZ: Uljahn спасай
BorisZ: у меня работа
BorisZ: сожги еретика )
Uljahn: почему шансы выигрыша на каждой руке не постоянны?
tutubalin: потому что внутри бандита сидит несколько маленьких бандитов, которые не хотят, чтобы ты выиграл
tutubalin: они точно так же выбирают лучшего из бандитов. а выбирают они на основе статистики. и каждый раз, когда дёргаешь руку, статистика меняется
Uljahn: для каждой ноды есть предельная вероятность выигрыша, которая равна суммарному значению выигрышей в полностью построенном дереве, не?
Uljahn: в полном дереве уже нет вероятностей
tutubalin: в полностью построенном дереве каждая нода или 100% выигрышная или 100% проигрышная
Uljahn: или ничья
tutubalin: ну да, или ничья
Uljahn: или противник может сыграть неоптимально и отдать тебе победу)
tutubalin: тоже может быть
Uljahn: я про все исходы говорю
Uljahn: рандомные роллауты как раз пытаются собирать непредвзятую статистику по всем возможным стратегиям
tomatoes: добавил маленькую эвристику (избегать фримувов для противника и захват минидосок) в правую часть уцб и ворвался на 5 место :sweat_smile:
tutubalin: смотри. есть нода, из неё 5 ходов. 4 хода ведут к моментальному проигрышу, 1 ход ведёт к моментальному выигрышу
tutubalin: с точки зрения рандома шанс 1/5. но если против нас играет не рандом, а игрок, то он выберет выигрышный вариант
Uljahn: tomatoes :fire:
Uljahn: tutubalin: мы не знаем, что выберет противник, но хотим, чтобы его выбор нам навредил как можно меньше, это минимакс
tutubalin: да, но в минимаксе мы выбираем наиболее неприятный ход противника
tutubalin: а для себя выбираем наиболее приятный
tutubalin: вот тут рассказывается, откуда растут ноги у формулы.
https://banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm/
wlesavo: tomatoes хех, я на этих эвристиках как раз играю
Uljahn: вместо UCB можно epsilon-greedy использовать или thompson sampling
Uljahn: ага, как раз в этом цикле статей и читал про это
tutubalin: >> if X1, X2,…,Xn are independent and 1-subgaussian
tutubalin: надо взять какую-нибудь игру, для которой дерево не такое большое (те же крестики-нолики) и посмотреть, как оно там работать будет
Uljahn: я не понимаю суть претензий :(
Uljahn: минимакс строит полное дерево, MCTS строит такое же полное дерево, только иначе
tutubalin: претензия к правой части UCB
Uljahn: по-моему, она связана с regret
tutubalin: она основана на предположении, что испытания независимы и подчиняются подгауссовскому распределению. но это может быть совсем не так
Uljahn: вот inoryy бы объяснил, он спец в статистике, а у меня только интуитивное ощущение понимания)
tutubalin: ну вот откуда в формуле взялись корень и логарифм?
tutubalin: они взялись из функции Гаусса
Uljahn: https://banditalgs.com/2019/03/17/bayesianminimax-duality-for-adversarial-bandits/
tutubalin: там игра попроще
Hamibar: не давать фримув сопернику - это значит не отправлять в пустую доску?
wlesavo: на заполненную наоборот
Hamibar: ааа, я понял
Hamibar: спасибо
Hamibar: я вот думаю, если можно победить на маленькой доске стоит ли делать этот ход. Или лучше монте карло пусть решит.
BorisZ: дерево должно решать
BorisZ: может после этого взятия у тебя форсированный проигрыш
Hamibar: хорошо, спасибо)
BorisZ: я вот подумал как можно дополнять эвристиками дерево
BorisZ: когда ход выбираешь - надо брать не одну с лучшим скором а несколько если скор отличается незначительно
BorisZ: и потом уже выбирать ход если он подходит под какие-то железобетонные эвристики
Hamibar: я тоже подумал. Типа штрафовать за определенные ходы
BorisZ: в пределах какой-то дельты - 1-2 процента это фигня так то
BorisZ: не, не так
BorisZ: когда уже все время исчерпалось на ход, дерево построено
BorisZ: ты просто выбираешь лучшего чайлда рута, с наибольшим скором
Hamibar: я понял, так тоже можно поробовать
BorisZ: а там может 2-3 чайлда у которых скор отличается на волосок
BorisZ: в пределах погрешности короче
BorisZ: и если один из них попадает в эвристику - теклес, закрытие доски, еще что там, то его и брать
BorisZ: если не попадает то как обччно - с лучшим скором
Uljahn: можно уже при создании чайлда ему задавать начальный скор, если соответствует какой-то эвристике, у меня так
BorisZ: не скор, я попутал, по визитам выбираем же
Uljahn: тогда MCTS его будет чаще выбирать и набъёт ему больше визитов, если вариант действительно хороший
Uljahn: *чаще выбирать в начале
BorisZ: Uljahn мне как-то не очень - подталкиваешь как бы к тому ходу который тебе нравится
Uljahn: а подкрепление хода эвристикой - это не подталкивание?
tomatoes: немного можно
BorisZ: а если наоборот - как я описал, тогда оно считает что-то там, а ты в конце выбираешь из нескольких лучших, по дебютам или как там
Uljahn: кстати, а если но относительному количеству проигрышей выбирать?
tomatoes: то же самое по идеи получится
tomatoes: или я не понял
BorisZ: проверить то недолго
Uljahn: (10 wins, 0 draws, 6 loses) -> 10*1+0*0.5+6*0 = 10pts., 16 visits
(4 wins, 12 draws, 0 loses) -> 4*1+12*0.5+0*0 = 10pts., 16 visits
Uljahn: 0 проигрышей лучше, мне кажется
Uljahn: особенно если за нолики
tomatoes: у меня сделано крестикам за ничью -0.5, ноликам 0.5
BorisZ: может за нолики просто за ничью давать чуть больше?
BorisZ: ничего себе разница у тебя)
tomatoes: ну я не сказать что особо думал, так "на глаз" поставил 😅
tomatoes: за проигрыш -1, выигрыш 1
tomatoes: http://chat.codingame.com/pastebin/af12a59f-a1dc-48e3-9045-87fc92bb175f
tomatoes: как-то в итоге будет :thinking:
BorisZ: хм я выбираю ход чисто по визитам, а статистику побед и поражений в одном счетчике храню, то есть даже не знаю сколько там чего
BorisZ: просто за победу 1 з апоражение 0 за ничью половинка
BorisZ: я думал просто за ничью типа не половинку а 0.4 крестикам и 0.6 ноликам
Uljahn: или 0.25 и 0.75 как у tomatoes
Uljahn: кстати, заметили, в каких случаях karliso проигрывает? у него похоже принудительный вин минидоски стоит в лолаутах
tomatoes: тоже всё вместе, pts это то что в счетчике будет
tomatoes: я из самих ролаутов всё вытащил что раньше насовал. только рандом теперь
BorisZ: во, практика - критерий истины )
BorisZ: все принудительные ходы и инставины - толко тормозят все, а добавляют чего-то или не вобще хз
Uljahn: и за крестики он проигрывает только при ходе на сторону, а не в угол
Uljahn: скорее всего, дебютная книга не очень у него для этого варика
Uljahn: BorisZ: в среднем могут давать больше, пока все не закодят контр-стратегии, эксплуатирующие эти уязвимости
Uljahn: раньше у рекурса как раз на сторону было начало за нолики
BorisZ: какие уж тут контрстратегии
BorisZ: задача на оптимизацию по сути
Uljahn: ну, например за нолики выбирать из двух ходов с некоторой вероятностью
Uljahn: тогда будет шанс порекать топа)
BorisZ: сильно сомневаюсь
Uljahn: мне кажется, даже несколько выигрышей ноликами дадут сильный буст к рейтингу
Uljahn: ну, не в смысле совсем порекать, а подняться в рейтинге за счёт побед над ним
BorisZ: если один из вариантов сильно хуже то проиграешь, если одинаковые то не важно
Uljahn: тогда ему придётся перезатачивать свою стратегию
Uljahn: оба варианта примерно одинаковые, один немного лучше, но второй хуже исследован
BorisZ: да вроде никто тут не затачивает ничего, или я не знаю чего-то
Uljahn: ))))))
BorisZ: дак он его исследует на следующем ходу
Uljahn: недавно топы сабмитили без книг дебютов
BorisZ: ну и заранее тоже уже было исследовано если дерево переиспользуем
Uljahn: книги-то в офлайне составляются
BorisZ: книга дебютов не отменяет обычного расчета деревом
Uljahn: у смита месяцами в фоне MCTS статистики собирает
Uljahn: да, но эффект горизонта встаёт
BorisZ: если у человека 100к ролаутов - не победишь его с 10К и любой книгой, она конечна
Uljahn: я такого и не утверждал
BorisZ: книга просто экономит время нескольких ходов, - против другого с 100к это может оказаться критичным, да
Uljahn: или против другой книги
BorisZ: не считаются лишние ветки, не входящие в дебют
BorisZ: если ход будет сделан не по дебюту то все посчитается быстро
Uljahn: до самого конца просчитается?
BorisZ: нет, и не надо до конца
Uljahn: эффект горизонта - когда просчиталось до хода, который кажется хорошим, но если добавить больше времени, то он становится плохим
BorisZ: с дебютом дерево то все равно строится, просто в недебютные ветки не заходится или заходится намного реже
Uljahn: для недебютных веток статистики будут неточными, ч.т.д.
BorisZ: потому что они априори не выгодные для тех кто их делает
Uljahn: конечно не выгодные, в них выше вероятность проиграть, но и выиграть тоже можно
Uljahn: у смита месяцами MCTS в фоне статистики собирает
BorisZ: ладно, мы с тобой спорим как будто оба в топ 10, все оптимизации перепробовали и только дебютной книги не хватает )
BorisZ: как если бы мы сейчас партию ли седоля против альфа го взялись обсуждать
Uljahn: во, кстати... крутая статейка сегодня попалася
https://www.yuzeh.com/data/agz-cost.html
Uljahn: просто абассака
BorisZ: да уж наверное гугл или кто там, дипмайнд отбил эти вложения пного раз уже
tutubalin: Each move during self-play uses about 0.4 seconds of computer thinking time.
tutubalin: за 400 миллисекунд-то конечно можно норм играть
Uljahn: ну это же го, а не крестики
BorisZ: когда в 90х был дипблю против каспарова там тоже жутко дорогая была эта дипблю, ее долго строили и тренировали
BorisZ: а сейчас прога в телефоне телефон выигрывает у гроссов
Uljahn: я к тому, что RL - это развлечение для богатых, на мобильной видюшке только обратный маятник и обучишь, наверное
Uljahn: естественно, deepmind выгодно гонять своё железо для пиара, чтобы потом выгодно продавать мощности
Uljahn: телефоны сейчас слишком мощные :smirk:
Uljahn: Your smartphone is millions of times more powerful than the Apollo 11 guidance computers, Automaton2000
Automaton2000: главное - никогда не прекращать учиться
tutubalin: Automaton2000 там по-тихому не прекращает учиться
Automaton2000: а если у тебя есть
Uljahn: логи-то запоминает, чем не обучение
Uljahn: лол, чел из топ-5 в крестиках говорит, что у него 10к роллаутов
tomatoes: он вроде выводит. на втором 20-30+, потом падает до 10
tomatoes: может реально как-то странно считает :thinking:
Uljahn: так это он с первого хода переиспользует часть дерева, наверное
Uljahn: а, он топ-6, это смитс ресабмитнулся
Hamibar: разве повторное использование дерева даст такой буст?
Uljahn: на первом ходе 1 секунда, там можно дофига насчитать, вариантов начальных ходов не так уж и много
Uljahn: т.е. переиспользовать можно процентов 50 сразу
Uljahn: с учётом симметрии, конечно
Hamibar: а ну с симметрией мб.
Hamibar: Я так посмотрел мне это может добавить 10к роллаутов на 2м ходу.
Hamibar: Но это число быстро упадет
tomatoes: оно в теории помогает, но на практике не заметил разницы
Hamibar: по прикидкам добавит 5% роллаутов. По крайней мере у меня примерно так получается.
gybson_samara: босс, гад такой, рандомно ходит, хз как отлаживать =)
Uljahn: https://www.codingame.com/replay/472263657
эффект горизонта на 36-м ходу, судя по статистикам в месейдже
Uljahn: а через несколько ходов смит уже просчитал партию до конца
gybson_samara: 31 ход непонятный, крестик отправляет синего завершить ряд совершенно ни с чего
gybson_samara: 43 ход крестик отправляет нголик в свободный поиск при наличии других вариантов
tomatoes: в конце часто бывает такое что как ни крутись, но 100% проигрыш
Hamibar: если я правильно понял, что значит слово win в отладке, то на 40м игра была уже закончена
gybson_samara: это не значит, что надо ходить как попало
Hamibar: это значит, что как не ходи проигрыш
gybson_samara: Т.е. на 40 ходу у него пошел другой алгоритм, не как в основной игре?
gybson_samara: Если это не другой алгоритм, а тот же, то он неверно ходит и какая разница на каком ходу?
Hamibar: там нет верного хода.
Uljahn: Смитс же в месейдж пишет WIN, то есть выигрыш при любом ответе соперника, и у соперника оценка в минуса уходит, тоже без вариков значит
tomatoes: алгоритм (мцтс) по сути выдает шанс выигрыша для каждого хода. и вот в конце он начинает выдавать для всех ноль
tomatoes: и берется первый попавшийся
ilt: а как он определяет что WIN?
Hamibar: наверное просто дерево до конца посчиталось
Uljahn: угу
Uljahn: а дроп на 36-м с 0.69 до 0.32 - это как раз эффект горизонта, когда глубина дерева не достаточная, либо эксплорейшон слабый
Uljahn: возможно, что из-за эвристик, которые игнорируют некоторые ходы
Munchkin: Слушайте, а какой синтаксис у команды "BOOST"?
Uljahn: print(x, y, "BOOST")
Munchkin: Спасибо большое!)
Uljahn: просто строковые символы вместо thrust выводи
Uljahn: вот что jacek написал в общаке:
i have 1-ply check for win and moves that can win small board are twice as likely chosen as others, i dont have any pool node or log table or other fancy optimizators, but i reuse tree
Uljahn: и этого для топ-6 достаточно с 10к на втором ходу
Uljahn: либо недоговаривает
Hamibar: я вообще не понимаю как так)
ilt: если дерево до конца просчиталось, то как понять это победа или поражение?
ilt: оценка ноды близка к WIN_SCORE что ли
Hamibar: если оно просчиталось до конца, то каждый роллаут возвращает поражение.
ilt: почему?
Hamibar: ну так у нас теперь больше нет рандома
Hamibar: во всех листах дерева достоверно известно, что это проигрыш
Munchkin: У меня тут еще вопрос по Coders Strike Back: существуют ли еще какие-то режимы мощности двигателя кроме thrust и BOOST? Сорь за такие вопросы, но я новичок))
gybson_samara: SHIELD
gybson_samara: ускорение 0 на три хода
Munchkin: У меня просто Wood
Division 3 to 1
Munchkin: Его же там еще нет
Munchkin: по-моему)
ilt: Hamibar ты же можешь опираться только на оценку ноды или количество визитов
ilt: для двух терминальных детей это будет 1 и 0 как я понимаю
ilt: если оценка
ilt: и количество визитов близко к общему числу роллаутов
ilt: когда большое дерево не понимаю как из этого понятно, что это WIN
ilt: 14 ходов до конца
Hamibar: если оно у тебя уже построено до конца(например ты его переиспользуешь), то у всех дочерних ноду рутов будет 0 побед.
Hamibar: а если ты достроил и продолжаешь ходить, то будет наверное очень большая разница между количеством роллаутов и количесвом побед
ilt: это поражение, а не победа, как это нет побед?
Hamibar: ну если из данного нода мы не можем прийти к победе, то откуда они появятся ?
ilt: МСмитс пишет вин
ilt: значит он понял, что это точно победа
Hamibar: а ну без разницы
ilt: как это без разницы
ilt: я бы себе такое запилил, если бы понял как это определить
Hamibar: так то же самое получается, только у детей рута не будет ни одного поражения
ilt: Hamibar ты меня на 20 мест вверх запушил?
Hamibar: вроде не я. Хотя я много сабмитил, там что мб и я
BorisZ: за 14 концов до конца дерево достроено - вполне реально, в концовке мало мвриантов хода
ilt: почему у детей не будет поражений? в том реплее я тебе накидаю последовательность чтобы он проиграл
BorisZ: каждая нода - терминальная, либо победа либо поражение
BorisZ: ролауты не нужны уже
Uljahn: ilt: среди любых детей будет вариант, который ведёт к победе
ilt: логически я это понимаю, а технически то как?
Uljahn: строишь полное дерево до конца игры, но это должно роллаутов хватать, а у смита их дохрена
BorisZ: невозможно развернуть список чайлдов
Uljahn: т.е. дерево в данном случае будет равноценно минимаксу с глубиной до конца игры
Uljahn: полный перебор
BorisZ: он 100 тыщь раз пробежал по дереву сверу вниз и ни разу не развернул ноду
Uljahn: ?
ilt: у него фримув там
Hamibar: Кстати ведь мы не можем идти в ребенка, если в ноде еще не из всех детей сыграли?
Uljahn: а, значит именно ход, ведущий к фримуву и был победным
ilt: 28 вариантов на выбор
Uljahn: Hamibar: да
Hamibar: я так на всякий случай, а то вдруг)
Uljahn: ilt: скорее всего jacek именно не учёл, что смитс будет делать фримув, поэтому оценка была оптимистичная слишком
Uljahn: а смитс просчитал все варики, и нашёл беспроигрышный
Uljahn: который как раз с фримува начинался
ilt: у него не мкст?
Uljahn: у обоих
Uljahn: только количество роллаутов разное и эвристики
ilt: я думал как для мкст это определить
Hamibar: да у него вообще странно как-то все работает. 10к роллаутов всего и в топе легенды.
Uljahn: ilt: MCTS сам тебе найдёт этот вариант по формуле, он будет в эту ветку чаще всего ходить
Uljahn: но только если будет достаточно роллаутов
wlesavo: может там не рандомные роллауты
wlesavo: по этому всего 10 к и поэтому в топе
ilt: в минике вроде понятия роллаут разве есть?
Uljahn: нет, тут у обоих MCTS
Uljahn: просто дерево будет одинаковое в итоге
ilt: Uljahn запутал
ilt: если MCST то как он WIN определяет?
Uljahn: по отсутствию неразвёрнутых нод, наверное, т.е. раз дерево полное, то можно точно найти лучший вариант
Uljahn: идёшь по формуле до конца дерева, оно приводит тебя в лучшую концовку
Uljahn: *она
YurkovAS: может проще?
bestNode.score / bestNode.visits >= 0.85
ilt: вот и я что-то такое подозреваю
ilt: но может ли быть для 26 вариантов такое соотношение справедливо?
ilt: тем более если роллауты останавливаются
ilt: надо попробовать
Hamibar: мне кажется, что не обязательно определять вин. Если это действительно вин, то дерево туда тебя и приведет.
Hamibar: Только если вывести в сообщение)
ilt: я только для сообщения интересуюсь!
vrabosh: это вы все крестики нолики обсуждаете?
vrabosh: BorisZ, у тебя задача классная, отложил ее на потом.. почитаю про эту систему счисления.. я как понял, раньше компы могли быть такими
Uljahn: чем хороши крестики - их можно обсуждать бесконечно
Hamibar: только сейчас увидел, что в первую калибровочную игру с боссом сыграл
Hamibar: лега так близко и так далеко)
MelnikovIgor: Hamibar) В очередь за мной)
Hamibar: ты главное там босса выигрывай)
MelnikovIgor: Я застрял в топ 2 навечно)
MelnikovIgor: Босса 38% винрейт
Hamibar: это конечно капец, когда 2й.
MelnikovIgor: Я на C# еще упорлся
MelnikovIgor: Принциписально хочу на нем
MelnikovIgor: На плюсах думаю уже в леге был бы
YurkovAS: MelnikovIgor добавь ходы теклеса и пройдешь. посмотри как у него за Х первые ~20 ходов ставит.
MelnikovIgor: Я так и не понял в тот раз что такое теклес
MelnikovIgor: Поясните еще раз плиз
Hamibar: когда ты на пустой доске ходи так, чтобы враг на ней остался
YurkovAS: https://www.codingame.com/share-replay/472301310
смотри внимательно куда он Х-ы ставит и заметишь
Hamibar: 0-0 0-4
YurkovAS: первые 20 ходов, примерно.
Hamibar: 0-8 4-0 4-4 и тд
MelnikovIgor: Хм, спавсибо, проанализирую, отпишусь потом)
YurkovAS: кстати, там он до 11 так ходит, потом мой его обманул и сам стал О в остальные проставлять.
MelnikovIgor: Это в четь чувака того так назвали?)
MelnikovIgor: честь*
YurkovAS: да
YurkovAS: и сделай реюз дерева, там же статистика накопленная остается. оно заметно прибавляет.
MelnikovIgor: Реюз есть
MelnikovIgor: Ессесно
MelnikovIgor: А есть прикидки насколько теклесс хорош? Кому то помогло?)
YurkovAS: +10 мест
Hamibar: кстати интересная стратегия против теклеса. Уже на 6 ходу можно самому начать так ходить
ilt: MelnikovIgor +20 мест в золоте дало
MelnikovIgor: Кто нибудь юзает зеркалирование/поворот борды?
MelnikovIgor: А поиск уже существующей?
Hamibar: что значит поиск уже существующей?
MelnikovIgor: искать тот стейт борды который был уже проанализирован в других ветках
MelnikovIgor: И обьединить
amurushkin: это скорее всего не будет такой же стейт потому что очередность другая и противнику ходить в другой борде
MelnikovIgor: Ну учитывать чей ход надо тоже
MelnikovIgor: Конечно
Uljahn: это типа transposition tables, смитс говорил, что толку от них мало
Uljahn: а ты в легу собрался, смотрю. хороший сабмит, и винрейт против босса
MelnikovIgor: Спс
MelnikovIgor: Теклес прикрутил на скорую руку
Uljahn: если не сразу, то за пару сабмитов можно боссу сдуть рейтинг, если винрейт хороший
MelnikovIgor: Ага)
Uljahn: у тебя теклесы только за нолики работают?
MelnikovIgor: За всех, за Х скорее всего первые ходи из плейбука
MelnikovIgor: Отрублю плейбук следующим сабмитом если не прокатит
YurkovAS: MelnikovIgor за О у тебя не работает. смотри 3-4 ход
https://www.codingame.com/replay/472314366
MelnikovIgor: Плейбук сработал
MelnikovIgor: На 4 хода
MelnikovIgor: Там 3я цифра в выводе
MelnikovIgor: сколько ходов из плейбка
MelnikovIgor: Уберу плейбук следующим сабмитом
YurkovAS: tomatoes-а порекал :smiley:
gybson_samara: а я нашел баг и исправил
gybson_samara: @MelnikovIgor гратс =)
MelnikovIgor: Рано еще)
gybson_samara: ага, вижу =)
gybson_samara: но все-равно близко уже
ilt: amurushkin скажи пожалуйста как у тебя кэш сложных вычислений в uct сделан
ilt: это двумерный массив?
tutubalin: добавил UCB, стало хуже
Uljahn: есть лега! грац
Uljahn: теклесы помогли?
amurushkin: ilt: нет 2 одномерных
Uljahn: tutubalin: у тебя случайно не повышенный приоритет ходов выигрыша миниборд?
ilt: а что в них хранится?
tutubalin: Uljahn кроме текслеса никаких эвристик пока
tutubalin: завтра поколупаю ещё. может быть бага где-то
Uljahn: а фримувы нормально обсчитывает? надо бы 1ply win check запилить себе
tutubalin: а может из-за того, что медленнее стало и сим меньше
Uljahn: ilt: у меня корень логарифма и обратный корень
tutubalin: фримувы немного криво
ilt: у меня нет обратного корня
ilt: но там же два параметра
ilt: как двумя одномерными массивами это толпу чисел закэшировать
MelnikovIgor: ЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ
MelnikovIgor: ЕЕЕЕЕЕЕ
tutubalin: фримув у меня - это два хода одного игрока: выбор доски и потом выбор клетки на ней
MelnikovIgor: Лега
MelnikovIgor: Спасибо ребята
ilt: :v:
Uljahn: :thumbsup:
MelnikovIgor: Теклес помог)
wlesavo: хорош
amurushkin: ilt for (int i = 1; i < PRECOMPUTED_VALUES; ++i) { SQRT_LOG[i] = (float)(EXPLORATION_PARAM * sqrt(log(i))); INV_SQRT[i] = invSqrt(i); }
gybson_samara: ребята с рандомом очень затрудняют мне работу с одинм багом, но я его вижу и отлажу и так
Uljahn: играй против себя, тут половина ботов с рандомом
Uljahn: особенно в верхней части лидерборды
Uljahn: а, у тебя бага... тогда наверное не вариант
ilt: INV_SQRT[i] это нижняя часть?
amurushkin: это 1 делить на корень
Uljahn: 1/корень от числа визитов, наверное
Uljahn: *визитов ноды, а SQRT_LOG для визитов родителя
gybson_samara: Uljahn тут Босс с рандомом, вот в чем печаль и несправедливость
Uljahn: а ты хотел против него книгу дебютов захардкодить?)
gybson_samara: Uljahn нет, я хотел возможность отладки алгоритма
gybson_samara: и свое я получу
Uljahn: у тебя всё ещё эвристики?
gybson_samara: разумеется!
gybson_samara: я еще не все баги нашел
gybson_samara: вот сейчас исправил баг, при котором не делал выигрышный последний ход. как с этим багом в золото залез я не знаю
gybson_samara: на выходных буду делать симу на два-три хода вперед, самому тяжело анализировать
gybson_samara: Так вот, если бы Босс бы стабилен, я мог бы отлаживать на нем, но я вынужден искать противника без рандома и искать баги на нем
gybson_samara: Это совершенно нечестно я считаю
ilt: не добавляет такой кеш скорости
ilt: странно
gybson_samara: короче, я ожидал от кнопки "same condition" именно "same condition"
amurushkin: same condition гарантирует входящие параметры на рефери а не то что противник будет играть также
MelnikovIgor: 103 в леге стал)
MelnikovIgor: о, и 2ой в мире на шарпике
Uljahn: у первого на шарпике вроде бы минимакс
MelnikovIgor: Да как они это делают?)
MelnikovIgor: Минимакс это же определенная глубина просмотра дерева + эвристика?
Uljahn: ну да, оценка нужна хорошая
MelnikovIgor: Там же плейаутов до конца нет?
MelnikovIgor: Там же по глубине режется?
Uljahn: на некоторую глубину только, на которую времени хватит\
Uljahn: называется iterative deepening, поэтапное увеличение глубины
MelnikovIgor: Бимсерч там наверное хорошо заходит
MelnikovIgor: Если эвристика хорошая есть
Uljahn: кстати, про бимсёрч в крестиках не слышал ни разу
gybson_samara: вот вылезу на эвристиках в легу =)
Hamibar: MelnikovIgor ооо, вышел на шарпе в легу. Поздравляю)
MelnikovIgor: Ага, спасибо)
gybson_samara: возможность составить многочлен для решщения задачи и есть задача про PnP в своем роде
Uljahn: кстати, нейронки примерно так и работают - подбирают некую нелинейную апроксимацию оптимальной функции стоимости
Uljahn: т.е. если получится обучить нейронку оценивать ситуацию и прикрутить к минимаксу, то может взлететь, хотя у рекурса не особо получилось, говорят на уровне днища леги
ilt: скорость взлетела, регулярно бью босса
ilt: но вернулись таймауты
ilt: вроде все что не таймаут все выиграно
Uljahn: за счёт чего взлетела? массивы запилил?
ilt: от лямбды одной избавился
ilt: лямбда занимала 30% времени
ilt: как то что я от нее избавился привело к росту скорости в 3,5 раза
ilt: гребанная джава
Uljahn: даже я слышал про то, что лямбды в джаве медленные
ilt: они то медленные то не очень
ilt: я много раз проверял
ilt: видимо все-таки проблема с GC не только в переиспользовании дерева
ilt: сильный рост роллаутов где-то в другом месте вылезает
YurkovAS: эти ходы теклеса можно по разному сделать и результат будет сильно отличаться. него самого похоже они работают только за Х и у томатоса тоже. и не очень форсированно выбираются...
tomatoes: у меня им в начале поиска фейковые роллауты накиданы немного
YurkovAS: а за О нет? у меня лучше играет, когда за Х и О пытается сделать.
сделано через бонус к скору ноды.
tomatoes: который сейчас сабмит только за Х
YurkovAS: tomatoes ты несколько раз сабмитил? и всегда на 5-е заходит?
не пойму, стоит ли мне пытаться найти улучшение. только ухудшать получается :smiley:
tomatoes: где-то 10-15 было, добавил эвристику и залетело
tomatoes: с первого сабмита
YurkovAS: а, понятно, может быть и удачным сабмитом. который потом не так просто воспроизвести...
tomatoes: смитс сабмитил пару раз потом, кое как держалось вроде :sweat_smile:
tomatoes: и вроде он еще карлисо почти скинул
tomatoes: не знаю правда он улучшал что-то или просто пересабмитил
YurkovAS: значит нормально у тебя должно быть.
надо и мне улучшать
tomatoes: спёр у смитса начало за нолики, пока норм вроде
YurkovAS: да, круто идет.
мы с тобой одновременно сабмитнулись.
YurkovAS: еще у топов 1-2 константа в формуле меняется. но это не точно.
tomatoes: в зависмости от количества детей и от прогресса игры пробовал. но непонятно как получше и в какую сторону
YurkovAS: по оценке сейчас проверяю.
локально показало прибавку, а по факту хз.
tomatoes: локально пробую некоторые ситуации, и с одной константой одни выигрывает, а в другой другие
tomatoes: а что конретно влияет вообще непонятно
YurkovAS: деталей не помню, но топы обсуждали, что константу меняют. давно это было
