vrabosh: подскажите по этому пазлу "Plague, Jr"
vrabosh: прохожусь про дереву, и показываю на какую глубину прошелся.. но походу не это имеется введу
vrabosh: g = {0: [1, 2], 1: [3, 4], 2: [5, 6], 3: [7, 8], 4: [9, 10], 5: [11, 12]}
vrabosh: вот такой список строю.. начинаю с нуля.. он идет в 1,2 - это 1 проход, потом в 3,4,5,6 - это второй проход итд..
vrabosh: на этом списке сработало, это второй тест, а дальше не хочет. тесты проходить.
vrabosh: может логику не прально понял..
tomatoes: с каждой вершины надо пробовать начинать и найти где "быстрее" всё обходится :thinking:
vrabosh: а как насчет вершин которые некуда не видут?
vrabosh: у меня в одном примере за 3 прохода проходит, а результат должен быть 13
vrabosh: я первую вершину беру.. и виать она всеоволишь вглубину 3 ведет.. а там наверно были больше
vrabosh: вообщем понял походу.. надо брать вершину которая максимально больше пройдет и за меньшее время
tomatoes: не должно быть каких-то оторванных. где-то ошибка
tomatoes: "such that a unique path from a pad to another always exists"
vrabosh: 2
0 1
1 2
vrabosh: вот у них первый пример.. 1,2 - двойка уже некуда неведет
tomatoes: ведет к 1
vrabosh: пчему?
tomatoes: 0-1-2
vrabosh: а понял.
vrabosh: ошибку вернула на один тест RecursionError: maximum recursion depth exceeded
vrabosh: получается задачу без рекурсии делать?
vrabosh: там результат 500
vrabosh: такое решение красивое получилось.. и тут на таком лажануть
vrabosh: if res>190: print(500)
else: print(res)
vrabosh: читирнул)
vrabosh: ну его нафиг переделывать
tomatoes: переделать рекурсию в цикл вполне полезное упражнение :relieved:
vrabosh: там чел через scipy.sparse.csgraph решил задачу.. вообще полезная штука эту библиотеку смотрю изучить.
vrabosh: потом контесты будут проще решаться
vrabosh: нельзя эту ошибку убрать с переполнением стека рекурсии?
tomatoes: есть там вроде что-то, но не помню
tomatoes: https://docs.python.org/3/library/sys.html#sys.setrecursionlimit
vrabosh: спасибо, сработало.. теперь у меня красивый код получился
ilt: Ура! Поднялся на 200 мест в крестиках
ilt: Есть корреляция между количеством роллаутов и местом
ilt: 11 вылетов и все когда я хожу вторым
ilt: вылет на первом ходе
ilt: еще загадка, что во многих играх где я проиграл в первой половине игры есть сильная просадка количества роллаутов
ilt: на один ход иногда на два хода
tutubalin: vrabosh на питоне можно изменять максимальную глубину рекурсии
vrabosh: кто чем занимается по жизни?)
Uljahn: о, я тоже Plague на scipy зарешал
Uljahn: по-моему, это почти один-в-один Teads
Uljahn: только Teads контест закончился год назад, и его убрали
BorisZ: надо найти диаметр графа а потом ответ будет средняя вершина в диаметре
BorisZ: поленились они тесткейс сделать действительно большой, чтоб перебором не решалось
Uljahn: ответ будет половина диаметра, наверное
Uljahn: я сделал решения для наихудшего случая сразу, 1к нод
Uljahn: О - оптимизация, Automaton2000
Automaton2000: automaton2000: а что если кто-то сгенерит случайный токен и получит валидный чужой токен?
Uljahn: пазл недели внезапно прикольный
Uljahn: ой
Uljahn: новый пазл назначили, а нотификейшна не было что-то
wlesavo: скинь название
Uljahn: https://www.codingame.com/training/medium/forest-fire
wlesavo: спс
tutubalin: мне про камень-ножницы-бумага-ящерица-спок понравился
tutubalin: читаю тут про UCB1.
интересно, что в тексте упоминается очень много русских фамилий
tutubalin: Колмогоров, Чебышев, Марков
wlesavo: ну тут каждый человек фигура
Uljahn: похоже, что всех русских собрали, что были)
Uljahn: Марков ещё как-то к UCB отношение имеет, а вот другие два?
wlesavo: вики В 1930-е годы Колмогоров заложил также основы теории марковских случайных процессов с непрерывным временем
tutubalin: ну там всё на теории вероятности основано. А в ней есть неравенство Чебышева, теория Колмогорова
wlesavo: колмогоров оказывается доказал закон больших чисел, я не знал даже
tutubalin: а ещё Колмогоров — практически отец кодгольфа
wlesavo: кодгольмогороф
wlesavo: у меня чебышев отложился в голове по правилу для интегралов, оказывается там целая теория ортогональных многочленов
Uljahn: хм, о Колмогорове знал по другим теориям, а крутой чел был, оказывается, много где приложил руку
Uljahn: про Чебышева - про его многочлен, его расстояние и его ударение в фамилии))
Uljahn: о, правило пяти сигм
wlesavo: правило пяти сим - пять сим слишком мало :slight_smile:
wlesavo: но самый запоминающийся мем из теории вероятности это конечно как пирсон бросал монетку 24000 раз, потому что после 12к сим отклонение слишком большое было
Uljahn: задача Бюффона о бросании иглы тоже норм
wlesavo: только рф, неплохо было бы eulera на них натрафить https://alfabattle.ru/
tutubalin: Интеграция с API Альфа-банка
tutubalin: очень увлекательно
Uljahn: скоринг-то и на питоне можно бы было, клятый кровавый энтерпрайз
Uljahn: "Чтобы 5 часов кодинга прошли легко, в день чемпионата тебе домой доставят кофе-брейк." :yum:
Uljahn: эйлера не получится, "В чемпионате могут участвовать граждане РФ старше 21 года. Необходимо уверенно владеть заявленным технологическим стеком, а также иметь опыт разработки от 1 года."
Uljahn: ой, "только рф" не заметил
wlesavo: хм, ради хавки можно и решить тестовое задание на джаве :slight_smile:
wlesavo: бля ахахаха
wlesavo: начаал проходить, первый вопрос, укажите ваш опыт на джаве:
нет опыта
извините, на вас задачи не рассчитаны
Uljahn: надо попробовать тоже, указать опыт 200 лет
wlesavo: скажут вы слишком стары, у нас молодой коллектив
BorisZ: для них интересен в первую очередь найм - может оказаться дешевле и качественнее чем через агенства
BorisZ: поэтому надо идеальный образ создавать - года 3 надо писать
BorisZ: ну и на остальные вопросы соответственно держать в голове кого они хотят видеть
BorisZ: кроваво-красный энтерпрайз
BorisZ: читаешь вроде как реклама какие крутые задачи и хочется убежать сразу )
wlesavo: ну вообще да, могли бы что поинтереснее придумать, ато как-то прямолинейно, звучит как мы вам дадим задачку из беклога
YurkovAS: Каждому участнику чемпионата
МЕРЧ ALFA BATTLE LIMITED EDITION
Толстовку подарят чтоли?
Uljahn: кроваво-красную)
wlesavo: либо стикер))
Uljahn: ещё б весло дарили
BorisZ: чувак на фотке с толстовкой не может стоять уже, замученный какой-то - прям готовый демотиватор
BorisZ: хочешь ночами напролет дебажить распределенные транзакции - приходи к нам в банк
wlesavo: :smiley:
Hamibar: Скажите а в монте карло, когда мы доходим до конечного узла(в котором уже известен победитель), то должны ли добавлять его в статистику? или мы просто не должны больше в него заходить?
Hamibar: *в mcst)
wlesavo: если ты проигравший то ты автоматически в него не пойдешь, а если ты победитель, то будешь ходить пока ucb не сработает
Uljahn: в статистику только роллауты добавляются вроде
Uljahn: т.е. их результаты
wlesavo: ну если у тебя неисследованных узлов не осталось то как бы уже и роллауты не нужны, а если ты в конечный узел зашел,Ю то роллаут это детерминирорваная симуляция
Uljahn: а мне кажется, это всё ещё фаза selection
Uljahn: если нода терминальная, то оценка у неё точная, а не статистическая
Hamibar: вот и я тоже в сомнениях)
Uljahn: хм, счётчик общего количества проходов будет увеличиваться, всё равно, наверное
Uljahn: с визитами не понятно
Hamibar: можно просто не заходить туда.
wlesavo: это на оценку повлияет по логике, но я бы подождал умного кого-нибудь, ато я диванный эксперт пока)
Uljahn: ну, относительный скор у терминальной ноды не будет меняться же, т.к. число визитов будет увеличиваться пропорционально скору
Uljahn: т.е. просто роллаут будет возвращать результат на первой же итерации
Uljahn: и можно не заморачиваться в итоге
Uljahn: http://chat.codingame.com/pastebin/f05971b9-0357-4e6d-8ac4-5bdfd5f351ed
Uljahn: т.е. для терминальный сразу результат получаем и бэкпропагейтим
Hamibar: просто непонятно как это на всю ветку повлияет. Но наверное пока так и сделаю.
Uljahn: повлияет через эксплорейшн составляющую
Uljahn: полное число проходов алгоритма увеличивается, интересность малопосещённых нод увеличивается
Uljahn: хм, в UCT там визиты родителя? а то я про UCB1 похоже думаю
Hamibar: оно и без посещения конечного нода увеличится. По хорошему надо и так и так протестировать
MelnikovIgor: Uljahn UCT и есть UCB1
MelnikovIgor: обычно
Uljahn: ну, они почти идентичны, я как раз про различия
Uljahn: для UCB1 число проходов алгоритма - это как для UCT число посещений родительской ноды
Uljahn: т.к. в UCB1 всего одна родительская
vrabosh: из за того, что незнаю как математика устроена решаю задачу какимто кривым способом
vrabosh:
Dead men's shot - вот пазл, у меня идея такая, я нахожу площать, а потом вторую площать уже если провести вектор последний и первый к точки выстрела.. и ессли площать меньше получается то попал
vrabosh: но походу она проще должна решаться
vrabosh: в википедии нашел как вычисляется площадь гауса функцию уже слелал..
735487: если еще актуально. в терминальные ноды тоже заходить надо. и статистику вести
Hamibar: конечно актуально спасибо.
wlesavo: vrabosh я бы задал направление обхода по контуру и смотрел справа или слева выстрел лежит
vrabosh: ппц как я черех одно место задачу решил
wlesavo: ну тоесть можно угол между векторами смотреть просто, положительный или отрицательный
vrabosh: да с углами у меня вообще сложняк..
vrabosh: через площадь я сдела.. но с перебором, если углов будет 1000 то скрипт не вытащит
vrabosh: точек т.е.
wlesavo: так углы быстрее же намного, тебе нужен просто знак векторного произведения
wlesavo: http://chat.codingame.com/pastebin/add6b65a-a939-4468-9cac-5d54f414f26e
tutubalin: Uljahn UCT основан на UCB1.
UCB1 более общий алгоритм, но константа корень из двух.
UCT - адаптация для поиска в дереве, но с плавающей константой
vrabosh: wlesavo, да мне просто в голову эти решения не приходят, т.к. я вообще даже элементарную геометрию не знаю.. мои знания по математики это 5 класс
vrabosh: поэтому когда мне такие задачи попадаются, я свою математику придумываю)
735487: тогда может тебе нужно 100 уроков математики? :)
735487: я правда сам не смотрел эти лекции у Савватеева. но сам дядька прикольный. нравятся его интервью
735487: прикольно обьясняет правда у него наверное черезчур умная математика будет
vrabosh: я чтото начинал смотреть.. он как начял про группы чисел расказывать с первых уроков и я понял, что запутаюсь..
vrabosh: я препода нашел, который обычно как в школе рассказывает.. вот его буду слушать.. только сначала задачки хочется порешать, хотябы уровень изи
vrabosh: я думаю, если контест будет где нужна математика, вот перед этим контестом как раз поучиться...
vrabosh: за какое время примерно понятно, что будет в контесте?
wlesavo: боюсь что непосредственно после начала
wlesavo: математика никогда не лишняя, хотя бы общее представление иметь полезно об уже решенных задачах чтобы колесо не изобретать
735487: как откроют так и понятно :)
Uljahn: если внезапно утечки не случится
vrabosh: покартинке примерно понятно же иль нет?)
735487: не всегда
735487: посмотри картинку ice and fire
vrabosh: ну да)
BorisZ: курсы по математике сомнительная затея - убивается время на какую-то хрень которая 99% не пригодится
BorisZ: а если еще и бросишь на полдороге, то самооценка упадет
BorisZ: знаем, плавали )
BorisZ: идея вот есть про скалярное произведение векторов - странички в википедии достаточно чтоб смысл понять
BorisZ: если первй вектор слева то произведение положительное, если наоборот то отрицательное
BorisZ: ну или наоборот, я то не читал )
BorisZ: если многоугольник выпуклый то точка внутри - значит все произведения должны быть положительные
BorisZ: вектор стороны умножить на вектор из угла в точку искомую
BorisZ: а может отрицательные, зависит от того по часовой идем или против
BorisZ: короче я тот еще математик
BorisZ: у wlesavo видимо это и делает код
Uljahn: ну, линейная алгебра - не самый сложный и не самый объёмный раздел математики, мне кажется. по крайней мере, судя по тому, что в вузике нам давали
Uljahn: вот модульную арифметику не давали нам, а она в криптографии широко применяется
Uljahn: но по мануалам можно раскурить неспеша, если в дебри не лезть
wlesavo: Uljahn для таких применений достаточно примитивной математики, а вообще на линейной алгебре весь квантмех и там очень много тонкостей всяких
735487: в каждом разделе наверное есть такие дебри куда лезут еденицы
wlesavo: BorisZ да, только векторное произведение надо
Uljahn: wlesavo: ну, я же не про тензорную методологию
wlesavo: ну и да, нуэжный знак будет зависеть от направления обхода
BorisZ: ну вот блин и тут ошибся )
wlesavo: так линал без тензоров не линал вообще :slight_smile:
wlesavo: BorisZ я на самом деле сначала тоже скалярное сдлеал))
Uljahn: мне кажется, есть некоторое оптимальное количество знаний, когда можешь уже получать от них профит, но при этому не перегружаться теорией
wlesavo: ну хорошая база часто может помочь, скорее даже не тем что ты точно что то знаешь, а тем что представляешь возможности и проще найти нужное
BorisZ: у меня в универе семинары по линейной алгебре вела жутко красивая тетка, видимо аспирантка, я ее вот очень хорошо помню, а все остальное видимо пролетело как-то )
wlesavo: курсы согласен что вещь сомнительная
Uljahn: матрицы помножить, обратить, найти ранг, дискриминант, собственные числа - мне кажется достаточно
inoryy: я спецом статистику на бакалавре брал, у нас и функ анализ и теория чисел и абстракная алгебра были; диффуры которыми обычно запугивают относительная лафа была
inoryy: так вот почти ничего не применяю в итоге )) хотя фундаментом хорошим служит
Uljahn: я не против фундамента, просто пока ты учишь что-то одно, в это время ты не учишь что-то другое
wlesavo: диффуры по сравнению с урматами конечно изи, ими точно пугать можно)
Uljahn: мне ещё тфкп понравилась
wlesavo: ну тут вопрос приоритетов, да
inoryy: в ML реально дальше многомерного матана не надо знать даже если в теорию хочется лезть
wlesavo: о, тфкп самая красивая наука помоему из математики
BorisZ: не раз встречал точку зрения что сами знания которые дают в школе и ли вузе вторичны
BorisZ: в школе главное научить человека жить в обществе, в вузе - систематической работе
BorisZ: ну и так инфа по верхам что какие-то прикольные штуки вообще есть
wlesavo: ну если ты по дороге заимеешь неплохой фундамент тоже не повредит
BorisZ: ну да, это я и называю - знать что такая-то штука есть, если надо будет - сам углубишься
wlesavo: ну вот да, знание о существовании прикольных штук
wlesavo: тоже это имею ввиду)
inoryy: ну как сказать какой-нить функ анализ я бы сам точно не освоил ))
BorisZ: inoryy ты видимо особый случай, заканчивал недавно и в сознательном возрасте
BorisZ: знал за чем идешь короче
BorisZ: большинство то не так
wlesavo: функан интересная штука конечно, я только по верхам разбирался, по книге колмогорова как раз)
inoryy: я как раз к тому что универ все-таки не только для систематической работе и тд
BorisZ: для не ийтишных специальностей еще круг знакомств важен который получаешь, для айтишников не так критично
BorisZ: процент релокаций совсем другой
735487: у меня в универе по высшей математике на 1 курсе лафа была. мы это в школе еще проходили. я в математическом классе учился
735487: а на 2 курсе поменялся препод. плюс я подзабил. и еле сдал :)
Uljahn: наконец-то нотис пришёл про пазл недели :confused:
YurkovAS: Automaton2000: сима есть - ума не надо? :slight_smile:
Automaton2000: бля тогда у меня и у кубера
inoryy: Automaton2000 ого
Automaton2000: это еще одна не очевидная штука. Заметил только когда меня стали враги ловко на них ловить
ilt: Automaton2000 как улучшить крестики?
Automaton2000: ты даже не дойдёшь до +-0.001 точности
Hamibar: хех. Так написал mcts, что оно у меня работает так же как многорукий бандит)
Uljahn: ну, по идее так и должно работать, только как дерево из бандитов
Uljahn: или ты про скор в лидерборде?
Hamibar: ну так дерево то покруче) ага, позиция примерно таже. чуть чуть лучше
Uljahn: вон ilt как поднялся, что-то пофиксил видимо
Hamibar: да точно где то баг сидит)
Uljahn: на плюсах в крестиках easy mode
Uljahn: если всё чётенько закодишь
Hamibar: в этом всегда основная проблема.
ilt: Uljahn нашел несколько багов да
Uljahn: молодец
tutubalin: сделал пазл недели через нампи (на самом деле практически import from stackoverflow)
Uljahn: запостил в решения? потом гляну
tutubalin: ага
ilt: самая прикольная бага была с количеством роллаутов
ilt: их насчитывалась раньше в два раза больше, чем реально было
ilt: кеш квадратных корней и логарифмов не помогает
ilt: лямбда выражение медленнее начинает работать
ilt: теклесы тоже только ухудшают ситуацию
Uljahn: из-за лишних проверок?
Uljahn: хм, это если их в роллауты хардкодить...
735487: от лямбд вообще надо избавляться. они же медленные
735487: а теклесы это один if в начале хода
Uljahn: так ещё и 100мс можно потратить на вычисление следующего хода и дерево потом переиспользовать
ilt: amurushkin не всегда они медленные, но в целом буду пробовать их переделать
ilt: теклесы почему прибавки силы не дают
ilt: может роллаутов не хватает, чтобы это почуствовалось
Uljahn: вроде, СМитс говорил, что за крестики они особенно хорошо согласуются с его мета-MCTS
ilt: Uljahn переиспользование дерева это моя печаль
ilt: таймауты из-за этого начинаются
735487: дают хорошо прибавку. проверено.
ilt: amurushkin в моем случае не дают
ilt: -10% с теклесами в бруталтестере
ilt: в чем тут может быть проблема не понимаю
735487: а ты их как применяешь?
735487: их надо проверять только на пустой доске фактически.
ilt: если есть возможность сделать такой ход, то он делается
ilt: вместо хода из дерева
ilt: одна лямбда 1 мкс
ilt: 30% времени этап 1
Uljahn: а в брутале против кого гоняешь?
ilt: против себя же но без теклесов
ilt: кстати да один иф
ilt: if ((a.row % 3 == opponentRow % 3) && (a.col % 3 == opponentCol % 3)) {
Uljahn: возможно, или сим не хватает (возникает эффект горизонта), либо не все баги выловил
ilt: склоняюсь к тому что сим не хватает
Uljahn: против своего бота не показатель, лучше сабмитить
ilt: я сабмитил прошлую стабильную версию
ilt: она хуже была
ilt: если добавлю еще 2-3к роллаутов попробую
tutubalin: ilt то, что ты сделал - это не teccles
Hamibar: что это вообще за слово teccles. От чего образовано?
tutubalin: от ника
Hamibar: ааа, я думал термин какой-то, сокращение или типа того
ilt: tutubalin нет они у меня не работают
tutubalin: это как цепь Маркова, только ход теклеса )
ilt: или я не понял что надо сделать
tutubalin: ilt вот этот один иф, он что вообще проверяет?
ilt: что ход будет в одну и туже минидоску
tutubalin: условие должно быть: если доска пуста, выбрать на ней клетку с тем же индексом, что и доска
ilt: давай на примере
ilt: 4-4 5-5 8-8
ilt: какой ход нужно подставить?
tutubalin: ну вот 4-4 и 8-8 - это текслес
tutubalin: а после 8-8 теклес уже не получится сыграть
ilt: вот жеж, переделаю
tutubalin: условие: доска, в которую тебя отправили, пуста
tutubalin: если выполняется: делаешь ход на минидоске в ту же сторону, где находится сама доска
tutubalin: если не выполняется: считаешь всё как обычно
tutubalin: теклес это: 0-0, 4-0, 8-0, 0-4, 4-4, 4-8, 8-0, 8-4, 8-8 и только в пустую доску
Hamibar: это просто магия какая-то. Как говорится все гениальное просто
tutubalin: это начало беспроигрышной стратегии
Uljahn: inoryy говорил, что эту эвристику давно юзают, но известность она получила благодаря обсуждениям MSmits, потому что надо было её как-то называть, а тут как раз реплей teccles попался, на него и стали ссылаться
Uljahn: локальный мем короче, как smitsimax
inoryy: её точно юзали уже в февраля когда я подключился
inoryy: когда в легу пролез было где-то 15 человек, и у всех уже была эта фича
inoryy: теклес на тот момент даже не зарегился по идее ))
gybson_samara: есть ей математическое обоснование?
tomatoes: позже в игре когда собираешься захватить минидоску, то как бы не хочешь чтобы у противника фримув был
gybson_samara: фримув на ход вперед считается
gybson_samara: как я вижу теклес просто ведет соперника таким путем, чтобы он максимально мешал, потому мне и непонятна фишка
735487: это тот случай когда надо поверить что так лучше :)
735487: доказать наверное можно если запустить MCTS на час из позиции и посмотерть что он выберет
gybson_samara: у меня если противник попадает в выгодную клетку (центр, угол) то просто минус больше к ходу цифра
tomatoes: тут именно ходов через 20+ выгода будет, не на следующий
gybson_samara: сомнительно, через 20 ходов в клетках по 3-4 хода
tomatoes: ситуация например что хочешь захватить минидоску и два варианта закрытия, один посылает соперника в определенную, а второй дает ему фримув.
и тот который посылает на определенную выгоднее обычно
и вот эти теклсы снижают вероятность что у противника будет фримув
tutubalin: представь, что твой ход в верхнюю левую доску. и ты можешь закрыть эту доску ходом в верхний левый угол
tutubalin: делая это, ты даёшь фримув
tutubalin: а если бы ты сходил туда в начале игры, то такой ситуации бы не возникло
tutubalin: щас подумал... а не в пустую доску тоже должно быть выгодно...
Hamibar: amurushkin на час не нужно думаю. По крайней мере 1й ход считает 4 4 если секунд на 10 поставить.
Uljahn: у MSmits мета-MCTS больше месяца считает в фоне на одном ядре, говорит что за крестики у теклесов самый высокий винрейт
tomatoes: серьезный подход :thinking:
Uljahn: так он и книгу дебютов на охрененную глубину сделал за счёт этого
Uljahn: хотя всего 8кБ занимает
Uljahn: ну, там самые топовые ходы видимо, с учётом симметрии
735487: а я даже не придумал как ее хранить )) и как вообще эту мету делать
Uljahn: так же как и переиспользование дерева
Uljahn: только не все возможные ходы брать, а с топовыми статистиками
Uljahn: мне кажется, тут ещё проблема в выборе наилучшего хода, т.к. где много побед и поражений может быть хуже, где мало побед и поражений, но много ничьих
Uljahn: *чем где
735487: типа того что от игре к игре дерево не очищать?
Hamibar: попробовал запихнуть теклес мувы в симу - стало хуже, чем при полностью рандомной.
Uljahn: в симу не надо как раз
Uljahn: amurushkin: типа того
Hamibar: я понял :grinning:
Uljahn: только наверное надо скор и визиты отнормировать
Hamibar: но хотя не понятно почему.
Uljahn: потому что статистика сбивается, ты думаешь, что противник пойдёт так, а он идёт по-другому
Uljahn: при рандому все действия равновероятны
Uljahn: *рандоме
735487: насчет фри мув там есть еще фишки
Uljahn: Hamibar: на плюсах с хорошей симой даже и без дерева должно тащить, мне кажется
Uljahn: с хорошей == с быстрой, на битбордах
735487: многие делают 2 рандома. сначала доску потом ход. мсмит говорит что так плохо и сначала берет весь список и его рандомит. но у меня так сильно проседает скорость и я оставил 2 рандома
Uljahn: подумал тут, что фримувы выгодно давать противнику в начале партии, чтобы сбивать оптимальную игру, а в конце лучше избегать
735487: в начале партии их давать проблематично
Uljahn: ну, в мидгейме
Hamibar: ну у меня около 20к ролаутов получается. Но я думаю в дереве ошибка или в симе.
Uljahn: без дерева должно тащить, симу можно отдебажить
Hamibar: кстати 2 рандома тоже. Не представляю как сделать быстро с одним
Uljahn: а, вроде неплохо у тебя сабмит пошёл
735487: ну мсмит тоже говорит что у него медленнее из за этого но типа качественнее получается. но у него и при этом больше роллаутов в разы
tomatoes: добавил в саму симуляцию теклсы. локально со старой получше вроде, сабмит примерно так же как и старая :thinking:
Hamibar: да как обычно пошел. Уже залезал туда.
Hamibar: я пока в топы легенды не рвусь) наверное можно в разы ускорить, но у меня лапки.
tomatoes: у меня хорошо ускорилось когда стал делать по 10+ роллаутов вместо 1
tomatoes: то есть упиралось в пляски с мцтс деревом
tomatoes: и место гдето с 30 на 20 прыгнул
Uljahn: я думал, на плюсах и с лапками можно за счёт прагм всех рекать)
Hamibar: для этого нужно понимать что с этими прагмами делать)
Hamibar: кстати странно, ведь получается, что ты размер дерева в 10 раз уменьшаешь.
Hamibar: Разве не должно хуже работать
Uljahn: в смысле уменьшаешь? это просто сбор более детальной статистики
Uljahn: меньше времени в формуле проводишь, больше в роллаутах
Uljahn: в статьях по MCTS такое встречал
tomatoes: ресурс ели выборка/оценка, а потом все равно большая часть выбрасывалась
Hamibar: но роллаутов ведь не стало в 10 раз больше. По любому размер меньше станет.
Hamibar: Но мб точнее.
Hamibar: и в кучу нодов просто не будешь заходить
tomatoes: не в 10 раз, но побольше
tomatoes: раза в 2 наверное :thinking:
Uljahn: хорошая начальная статистика позволяет дольше не посещать бесперспективные ноды
inoryy: Uljahn я вроде не кривой но между перваой реализацией и последней был прирост в 20х в скорости, в С++ очень легко самого себя порекать
735487: tomatoes: у меня хорошо ускорилось когда стал делать по 10+ роллаутов вместо 1, а у меня роллауты росли а качество игры падало
Uljahn: это как
tomatoes: сейчас сделано что ближе к концу игры уменьшается размер батча
tomatoes: доигралось. теклсы в симе в общем дали примерно 5 мест :thinking:
Uljahn: в топе леги у многих они наверное есть, поэтому хорошо экономит
Uljahn: а если сделать теклес с вероятностью 50%? :thinking:
ilt: и в симу их тоже запихнуть!?
Uljahn: угу
ilt: я пока их только в конечный вывод добавил
ilt: есть небольшой прирост
tomatoes: в симу не хочется очень еще один рандом добавлять, но попробовать можно наверное как нибудь
Uljahn: робостак что-то такое делал уже, вроде...
tutubalin: у меня фримув - это два отдельных хода
tutubalin: из-за этого проблемка правда
Uljahn: или там был рандомный выбор между ходами, которые блокируют, и ходами, которые выигрывают...
tutubalin: может выбрать ту доску, куда чаще ходили, а ход, в который чаще ходили на другой доске
gybson_samara: зачем рандомный? можно же посмотреть выигрышь на доске ведет к выигрушу глобальному или нет
735487: ход который ведет к глобальному выигрышу находится и без проверок
tomatoes: а эту проверку кстати убрал у себя. то ли ошибка где-то, то ли оно какото принципиальный баг вызывает
tomatoes: роллауты не падают сильно, но играет с ней хуже
tutubalin: я делал оптимизацию: когда первый раз заходил в нод, который даёт фримув, считал, что это сразу победа
tutubalin: при следующих заходах уже считал нормально
tutubalin: когда добавил, разницы не почувствовал
tutubalin: когда убрал, стало лучше
735487: это черезчур оптимистично :)
tomatoes: солвер еще добавил, но он как-то вообще погоды не сделал
735487: у меня тоже не вышло
tomatoes: наверное в конце игры когда роллаутов и так тонна оно и само справляется со всем этим
tutubalin: да, но в конце игры уже поздно )
ты уже в проигрышной ветке
Hamibar: ооо. Я в иде первый раз боса победил :scream:
Hamibar: подождите, а в конце нод как выбирать надо? у которого рейт по ucb наибольший?
MelnikovIgor: что такое теклес?
Hamibar: если ты на пустой доске, то делать ход, что бы на ней остаться. Типа 0 0, 0 4, 0 8
735487: Hamibar: выбирать у кого визитов больше
Hamibar: визитов или побед?
Hamibar: сейчас сделал побед +100 мест)
tomatoes: одна и та же нода должна получаться если сильно не экспериментировать с уцб формулой
Hamibar: а я пол дня в дереве ошибки искал
735487: визитов но по идее это одно и тоже должно быть
Hamibar: шас попробую.
Hiker: А почему текущий контест вроде как на кодингейме? а вроде как кидает для региастрации на левый сайт?
Hiker: В ЧЕМ ВЕЛИКИЙ СМЫСЛ?
Hamibar: tomatoes похоже не совсем одно и то же
Hiker: ой сори капс
Hamibar: ты наверное про неофициальный
Hiker: да
735487: Hamibar: в идеале выходит одно и тоже если все нормально с оценками за победу,ничью и формула нормальная
Hamibar: наверное потому что неофициальный)
Hamibar: я обычную формулу использую. wins/visits + sqrt(2 * log(total) / visits)
Hamibar: и видимо получается совсем разное, раз такие результаты
735487: забыл коэффициент
735487: и что то у тебя формула неправильная
tutubalin: видишь двойку?
tutubalin: это официальный коэффициент - корень из двойки
735487: разве количество побед надо считать?
Hamibar: так вроде стандарт
735487: а ничьи у тебя не учитывает что ли?
Hamibar: нет.
735487: почему?
Hamibar: Ну сейчас наверное можно поэкспериментировать)
Hamibar: в статье такая формула была вот ее и использую :grinning:
tutubalin: формула состоит из двух слагаемых. первое - это оценка вероятности победы на основе наблюдений.
735487: имхо нельзя ничьи не учитывать
tutubalin: но так как это случайная величина, она может отличаться от реальной вероятности
tutubalin: второе слагаемое - это насколько реальная вероятность может отличаться от оценочной
tutubalin: при этом ты выбираешь некоторое эпсилон, на сколько оценка может отличается от реальности
tutubalin: и от этого эпсилон зависит константа
735487: и вот от этой константы в крестиках очень большой разрыв в результатах может быть
Hamibar: звучит так что можно эту оценку прямо целиком брать
Hamibar: но видимо с корнем из 2 она не очень точная.
Hamibar: хотя мб у меня просто какой-то баг в ее подсчете.
tutubalin: эта формула основана на допущении, что отклонение статистического матожидания от реального является подчиняется гауссовскому распределению
tutubalin: а для крестиков возможно, что это вовсе не так. там может быть пуассоновское, например
tutubalin: и тогда вообще всю формулу менять надо
MelnikovIgor: А почему теклес должен как то помочь?
MelnikovIgor: Какая корреляция?
tutubalin: MelnikovIgor потому что если ты ходишь в эту клетку в конце, ты даёшь противнику фримув, а если в начале, то не даёшь
Hamibar: значит нужно точно поэкспериментировать)
tutubalin: в отличие от обычных крестиков-ноликов, в UTTT важно не только куда ты сходил, но и когда ты это сделал
MelnikovIgor: А есть инфа что теклесс реально помогает? Тем более в МКТС? Все будут жаться без фримувов
ilt: tutubalin у тебя сколько времени сейчас уходит на фазу Selection?
tutubalin: я добавил теклес ВМЕСТО MCTS и с 52 места в голде поднялся на 38
MelnikovIgor: вместо?
не понимаю
tutubalin: четыре-пять строчек, а результат лучше, чем от массы предыдущих куда более сложных улучшений
tomatoes: если надолго мцтс оставить молотить, то она будет теклесы и выдавать
tutubalin: MelnikovIgor если можно сходить теклс (т.е. текущая борда пустая, это первый ход в неё), то так и ходить. если не пустая, то запускается MCTS
tutubalin: ilt я формулу пока не использую, у меня своё ноу-хау (которое, как оказалось, работает хреново), поэтому selection занимает где-то 2%
tutubalin: сейчас, после того, как изучил теорию и понял, что формула взята не с потолка, а имеет математическое обоснование, хочу наконец запилить её. но как это повлияет на производительность пока не знаю
ilt: ты что говорил про быструю сортировку
ilt: можешь ткнуть где это посмотреть
tutubalin: проблема моего алгоритма в том, что он слишком много внимания уделяет exploration: плохие ходы всё равно перепроверяются, только чтобы убедиться, что они плохие
tutubalin: ilt у меня сейчас используется priority queue.
поэтому сортировка как таковая мне не нужна
tutubalin: вместо неё используется куча, которая всегда выдаёт вариант с самым большим весом. при этом остальные варианты не совсем упорядочены
YurkovAS: проверил у себя идею делать больше роллаутов (2, 5, 10) - только замедляется в итоге примерно на 30%.
и играет хуже, если после каждого делать backpropagation
YurkovAS: похоже надо из всех этих прогонов выбирать лучший результат.
tomatoes: может быть само дерево у меня не особо оптимально и поэтому вытаскивает за счёт этого :thinking:
tutubalin: не лучший, а средний
YurkovAS: сделал так: 2 прогона с выбором лучшего результата. если после первого победил владелец ноды, то 2-ой не запускаю
tutubalin: точнее, в ролбеке говоришь: было 10 игр, из них 6 побед, одна ничья
YurkovAS: http://chat.codingame.com/pastebin/c8283ce0-67d5-4184-b608-c37470a461d7
tomatoes: если по одному, то 67к роллаутов на 2 ходу. если пачкой из 10, то 110к. так что возможно весь прирост только от этого
YurkovAS: у тебя рандом медленный
YurkovAS: а, не, дерево значит меленное :slight_smile:
YurkovAS: в мктс-е многое можно оптимизировать, как формулу, так и сами ноды.
tomatoes: воткнуто там местами чтоб ноду раскрывало только на втором визите. случайные сначала шафлятся, потом по порядку дергаются
tomatoes: но видать все равно не хватает :sweat_smile:
YurkovAS: у меня так же - раскрываем ноду только на 2-ом визите
tutubalin: кстати, а у кого какой размер дерева получается?
tutubalin: у меня примерно 100-150к нодов, если раскрываю после второго посещения и 400к, если раскрываю всегда
tutubalin: *после второго
Hamibar: у меня сколько сим столько и нодов.
Uljahn: не понял, а что на первом визите нераскрытой ноды тогда происходит?
Hamibar: добавляется рандомная
tutubalin: просто симуляция, без дорогого создания детей
Uljahn: простой рандомный роллаут?
tutubalin: ага
tutubalin: мы может быть в этот нод и не вернёмся никогда. зачем тогда ему детки?
Uljahn: почему не вернёмся?
Uljahn: зачем мы в неё пошли тогда?
Uljahn: все другие варианты были хуже, значит
Hamibar: а зачем вообще раскрывать? Пришли в ноду видим что детей не хватает добавили рандомного.
Uljahn: в дерево по одному добавлять детей?
Uljahn: наверное, нелокальность данных получится, промахи кэша или типа того
Hamibar: ну да. Мы же все равно дальше этого нода не пойдем пока из каждого ребенка не сыграем.
Hamibar: ааа ну такой аргумент я не рассматривал)
Uljahn: чтобы выбрать рандомного, надо создать список доступных, а при добавлении следующего делать выбор из оставшихся?
tomatoes: трекинг кого добавили, а кого еще нет какой-то сложный получается :thinking:
Uljahn: угу
Hamibar: что так, что по другому нужно знать из кого сыграли, а из кого нет.
Hamibar: или при раскрытии нода сразу из всех детей сыграть можно?
Uljahn: так из одного рандомного потомка и играют
Uljahn: кстати, почему операция создания детей трудоёмкая?
Uljahn: если фримув не брать, конечно
tutubalin: или создавать объекты для каждого потомка, или просто посмотреть доступные ходы и выбрать случайный
tutubalin: разница есть
Uljahn: объекты же уже созданы и лежат в пуле, надо только индексы ходов им прописать и начальные статы
Uljahn: не?
Hamibar: а разве это не сложней сначала всех детей создать, а потом из них выбирать рандомный с 0 игр.
Uljahn: я не знаю)
tutubalin: а зачем им что-то прописывать, если можно сразу дальше рандомить?
Uljahn: прописать сразу, чтобы потом дальше проще было дерево строить
Uljahn: надо смотреть статистики по посещениям нод на разной глубине дерева, видимо
Uljahn: и профилировать
tutubalin: ну вот я как раз и ограничивал на глубину 6-7
tutubalin: но это не очень хорошо работает, потому что плохие ветки могут закончится раньше, а хорошие могут пойти глубже
tutubalin: но вообще в классике MCTS за один роллаут создаётся один нод
tutubalin: из него потом происходит быстрая бездревесная симуляция
tutubalin: и вот есть два подхода: полностью инициализировать нод сразу, когда создали, или только когда второй раз в него пришли
Uljahn: а если после 10-го посещения?
tutubalin: тогда дерево будет медленнее расти и это будет больше монте карло, меньше три сёрч
tutubalin: но возможно это лучше, чем сразу 10 симуляций пускать
Uljahn: такое ощущение, что от алгоритма требуется разное поведение на разных стадиях игры, да ещё и при фримувах
Uljahn: в смысле, разным будет оптимальное поведение
Uljahn: в пазле недели что-то вроде np.convolve юзаешь?
Uljahn: не могу сообразить даже :(
tomatoes: раскрытие на второй визит это просто оптимизация. на сам мцтс никак не влияет
tutubalin: Uljahn думал насчёт convolve, но на stackoverflow нашёл в 10 раз более шизанутое решение )
Uljahn: чисто с numpy? без scipy?
tutubalin: ага
tutubalin: np.lib.stride_tricks
Uljahn: у, круто
Uljahn: я же на них делал скользящее окно в ООС
Uljahn: Optimal Square Covering нашёл
Uljahn: или даже 2D packing problem
YurkovAS: локаьно вариант с 2 рандомными партиями за раз показал хорошие результаты, на проде не зашло.
эх, опять теперь "искать лучший сабмит"
tutubalin: я просто загуглил "numpy how to sum rectangular range"
tomatoes: cg-enchancer юзерскрипт есть, там можно пометки к сабмитам делать
tomatoes: он правда корявый очень и лагает, пришлось почти всё кроме заметок отключить
YurkovAS: надо поставить.
в крестиках разброс, последний раз был 5-12 место. матчей против каждого же по шт 10-20 (мало), поэтому результаты так скачут.
да и в других играх так же делаю - сабмичу до самого лучшего результата.
735487: теперь я на 5 месте :))))
YurkovAS: вот где сабмит года
csb top 7
http://cgstats.magusgeek.com/app/multi-coders-strike-back/YurkovAS
Uljahn: ништяк, pb порекал немного
YurkovAS: нейронок ни кто не рекает. топ5 - 1 раз только.
заметил, что на глубине 8 - иногда 1-3 раза может выйграть нейронок за сабмит.
Uljahn: а реплеи есть?
Uljahn: а, нашёл уже
YurkovAS: с пб4 есть реплеи, а вот агаде и фенира нету, хотя точно были.
Uljahn: ничоси, у тебя тоже блокер спиной блочит
735487: 10-0 против мэда ))
YurkovAS: ну там удачный сабмит, так то он на 9 месте был.
Uljahn: мед рект
YurkovAS: да, меда и микеича спустил ниже нааба.
735487: у тебя там миник или мcts?
YurkovAS: смитсимакс
735487: за счет оценки так вырулил?
YurkovAS: была ошибка в симуляции.
YurkovAS: amurushkin если я тебе расскажу детали, то ты меня порекаешь.
думаю она есть у большинства.
735487: о как.
735487: а сам как нашел?
YurkovAS: играл в новую опти search race и заметил, что точность симуляции сильно влияет на результат
735487: ты думаешь у меня недостаточно точная симуляция?
YurkovAS: после нее залез в ксб экспериментировать.
735487: типа мэд в стартеры подложил специально :)
Uljahn: )))
Uljahn: закладочка, чтоб не порекали
Uljahn: в принципе, это правильно, нефиг бездумно копировать
735487: надо будет завтра проверить )
