Chat:Ru/2021-02-25

From CG community
Jump to navigation Jump to search

MadKnight: samrrr а чё за алго юзаешь?

Default avatar.png samrrr: пытаюсь минмакс сделать

tutubalin: красивый код должен быть квадратным


tutubalin: http://chat.codingame.com/pastebin/e04bbd6a-59f3-43e0-ab3e-3a3bdc597440

Uljahn: хочешь быть передовым - пиши квадратно-гнездовым

MadKnight: tutubalin пиши код ASCII артом в таком квадрате используя пробелы

magaiti: не, надо концептуально писать. шахматный алгоритм в виде коня, решатель сапера в виде бомбы итд

magaiti: вычисление числа пи в виде круга

magaiti: причем вычисление проходит через подсчет площади кода

tutubalin: view-source:https://tutubalin.github.io/

Default avatar.png The_Nigel: (╯°□°)╯︵ ┻━┻

Default avatar.png **The_Nigel slaps around a bit with a large fishbot

Default avatar.png The_Nigel: /

Default avatar.png samrrr: наконецто смог завалить свой прошлый код на рандом, даже место в рейтинге поднял, только босса всё ещё не завалил(

Uljahn: и не завалишь с таким слабым ботом

Uljahn: чтобы босса валить, надо до босса дойти, а у тебя по пути винрейт проседает

samrrr: а как его сильнее сделать то?

Uljahn: вычистить баги, оптимизировать роллауты, строить дерево

samrrr: 150к вариантов рассматривается

samrrr: дерево строится

samrrr: роллаутов только нет, одна оценка диспозиции

Uljahn: тогда оценку улучшать

Uljahn: мктс хорош тем, что оценка не нужна в общем случае

Uljahn: недавно смитс что-то про оценку интересное рассказывал, можно найти в логах

samrrr: ну я оцениваю каждую из 8 полос, сколько надо крестиков на завершение линии

Uljahn: очевидно, что этого не достаточно

Uljahn: в топ-100 даже не зашёл

samrrr: ну так а что ещё к этому добавить? никаких предпосылок поражения/победы я не вижу...

Uljahn: добавь мктс :relieved:

samrrr: а минмакс что совсем победить не может?

mykeich: минимакс удобен там где легко придумать оценку

mykeich: например расстояние до цели

Uljahn: минимаксы есть в легенде, насколько я знаю

Uljahn: но там всё сложно

Uljahn: это не ванильные миники, а монстры какие-то

samrrr: https://www.codingame.com/replay/530753950 вот как он умудрился проиграть тут? 2 линии в шаге от победы...

mykeich: 4-8 надо было ходить, чтоб отправить соперника на другой борд, но не факт что поможет

samrrr: минмакс на этом ходу уже проиграл

mykeich: выбор кривой у тебя под конец

mykeich: 4-8 тыб его отправил на 8 борд

samrrr: это непомоглобы

mykeich: почему?

samrrr: он бы серавно обратно отправил

samrrr: он на 36 ходу слился уже

Uljahn: а на какую глубину у тебя минимакс работает?

samrrr: понятия не имею( ололо 3

mykeich: samrrr завязывай с велосипедами, убери хранения дерева и глубина обычно жестко задана на ход

samrrr: могу сделать прерываемый минмакс, но у меня уже есть дерево

mykeich: что значит прерываемый?

mykeich: ты строишь дерево и двигаешься по нему по принципу минимакса?

samrrr: Чтоб если неуспел, то рандомно сходить

samrrr: да сейчас так

mykeich: я думаю бесполезная трата времени. по сравнению с минимаксом глубина будет маленькая, а по сравнению с mcts выбор не оптимальный из-за наличие оценточной

samrrr: а скока минмакс без дерева открывает?

mykeich: не знаю. к гадалке не ходи, но если не тратить время на построения дерева в памяти программы, то быстрее:)

mykeich: ты придумал оценочную такую что глядя на доски понять что идешь к выигрышу?

samrrr: Придумал, но непомогает

samrrr: https://www.codingame.com/share-replay/530759370

samrrr: вот тут прям к успеху, но потом слился

MadKnight: samrrr тыж помнишь что к концу игры миник может осиливать больше глубину?

MadKnight: тыж отсортировал доступные ходы по оценке?

MadKnight: чтобы а/б действовало

samrrr: какое а/б?

MadKnight: альфа бета

samrrr: я в конце жод с лучшим счётом беру

MadKnight: фишка миника

samrrr: нут у меня таких фишек

MadKnight: всмысле

MadKnight: ну так запили

MadKnight: больше глубины осилишь

samrrr: а что это такое?

MadKnight: там суть в том, что если ты уже получил score=x на глубине выше, а твой текущий min() уже ниже того, то ты можешь просто пропустить все след ходы на этой глубине ибо они точно не пройдут через max() предыдущей глубины

mykeich: нет смысла смотреть ходы в поиске лучшего результата если выше уровнем он все равно будет отброшен

MadKnight: ты чё, запилил миник без этого?)

mykeich: он строит дерево и обходит его по принципу мин макс

samrrr: да, просто беру в шириеу дерево раскрываю

Uljahn: после а-б уже можно пилить прерываемый миник в варианте ID (iterative deepening), когда для каждой завершённой глубины ноды сортируются, а потом уже следующая глубина обрабатывается, тогда эффективность а-б отсечения будет очень высокой, можно будет просчитать глубже и в любой момент выдать лучший результат, а не рандомный

Uljahn: без альфа-беты в легу на минике пройти маловероятно

Uljahn: только если за счёт мегакрутой оценки

Uljahn: на уровне нобелевки :)

samrrr: а как вообще это аб делается?

Default avatar.png SOpatrin: А тут можно как-то открыть задание из clash of code?

Uljahn: SOpatrin: найти условие можно тут http://eulerschezahl.herokuapp.com/codingame/puzzles/

Uljahn: или я вопрос не понял

Uljahn: решение нельзя открыть

Uljahn: samrrr: гугли alpha-beta pruning

samrrr: ээх похлду эту штуку к моему дереву не применить(

samrrr: что там по поводу мктс? дерево для него подойдёт?

Uljahn: что ты называешь деревом?

Uljahn: что хранишь в нодах?

samrrr: http://chat.codingame.com/pastebin/5a08a5f3-4736-4f01-b59c-438922708b47

samrrr: turn_choose явно зря храню, но серавно там 16 бит нечем занять

samrrr: на mcts же нужны ссылки на чилдов?

Uljahn: конечно

samrrr: тогда это жопа, у меня таких ссылок нет....

Uljahn: можно хранить ссылку на первого чайлда и их общее количество, и потом инициализировать чайлдов последовательно

Uljahn: ещё нужно хранить количество посещений ноды, а также её скор

samrrr: ээх

Uljahn: ещё нужно хранить ход, чтобы не хранить стейт

samrrr: инитить последовательно это былобы хорошо, если не 24 бита на скор и вхождения

Uljahn: рано начинаешь оптимизировать

samrrr: не, ход ненадо хранить, ноиер чилда и есть номер хода

Uljahn: задолбаешь дебажить, не?

Uljahn: *ешься

samrrr: ну по факту есть выбор между 2 структурами данных

samrrr: да не, дебажить это ненадо, класс доски то уже есть

Uljahn: AoS и SoA?

samrrr: тут полюбому SoA

samrrr: вопрос лишь в том как чилдов хранить

Uljahn: а мне кажется, что AoS

samrrr: не, судя по картинку из википедии SoA всётаки

samrrr: http://chat.codingame.com/pastebin/c59ff89e-ed08-4554-9925-fdd24d4b142c

samrrr: http://chat.codingame.com/pastebin/a9756a4c-d20a-499b-8ee3-31a4f45e7ef2

samrrr: доска всегда знает сколько чилдов у неё, такчто записывать их не имеет смысла

samrrr: первый вариант самый простой, тупо массив нод. но даже неоткрытые непосещённые ноды прийдётся хранить

samrrr: второй сложнее, прийдётся 2 раза пробежаться по хендлам, чтобы дойти до чилда, зато ненадо хранить ниразу не посещённые ноды

Uljahn: обычно выделяют заранее большой массив нод, а потом по ходу построения дерева инициализируют их и обновляют значения

Uljahn: можно даже в офлайне посчитать начало дерева и скопировать его в код в качестве книги дебютов

Uljahn: эх, я ещё 2048 не добил, а тут такая идея для крестиков в офлайне

samrrr: да это неважно, я могу эти вектора хоть заранее зарезервить, веравно ускорение примерно нулевое

samrrr: тут вопрос в том как хранить ноды и чилды

samrrr: я думаю всётаки сделать 2 массива

samrrr: http://chat.codingame.com/pastebin/4144a7b9-7516-41eb-ab91-fd12f11941af

Uljahn: так нода и есть чайлд

Uljahn: зачем их делить-то?

Uljahn: у ноды есть парент и чайлды, но ссылку на парента можно хранить отдельным массивом во время селекшна в мктс

Uljahn: тут как бы топология и стейт в одном флаконе

samrrr: нее это ссылка на чилдов

Uljahn: ну ок :(

samrrr: а делить чтоб памяти меньше жрали

samrrr: изначально нода 1 уровня

samrrr: потом если больше 60к вхождений, то апается, чтоб оверфлов не наступил

samrrr: http://chat.codingame.com/pastebin/5fc88feb-eccf-4811-a936-57b1136ec078

samrrr: Вот так примерно 3 ноды выглядят

Uljahn: и в чём преимущество такого подхода?

samrrr: 1 2 3 5 6 7 8 эти ноды ненужны, но приходится их тоже хранить

samrrr: в простоте и одной операции перехода, вместо двух

samrrr: но памяти хавает....

Uljahn: простота в одном месте означает, что сложность заметается под ковёр и всплывает где-то ещё

samrrr: ну так да, без боарда эта структура бесполезна

samrrr: но у меня же есть боард

Uljahn: т.е. ты придумал простую структуру, а потом начал искать алгоритм, который с ней может эффективно работать? :)

magaiti: дата дривен девелопмент

samrrr: не, боард у меня уже есть

samrrr: и вообщето эту структуру предложил ты

Uljahn: я про массив нод говорил

Uljahn: где чайлды хранятся последовательно

samrrr: вот я так и сделал

samrrr: массив нон

samrrr: массив нод

Uljahn: чайлды - это тоже ноды, все ноды имеют одинаковую структуру

Uljahn: т.е. имеем AoS

samrrr: ага вектор нод

Uljahn: а проблема-то в чём?

magaiti: че за игра?

Uljahn: крестики

samrrr: в том, что нужна формула, для мктс

magaiti: на бесконечном поле, или как?

Uljahn: UTTT

samrrr: https://www.codingame.com/ide/puzzle/tic-tac-toe

Uljahn: формула для мктс имеет несколько вариантов, самый простой - это UCT

samrrr: мне тот, которым можна босса вальнуть

samrrr: а то минмакс неосилил босса

magaiti: эм в дереве обычные 3 на 3

magaiti: а че там выше по лигам?

Uljahn: в бронзе правила обновляются

samrrr: ну так 9 таких досок

magaiti: ии?

Uljahn: samrrr: скинь реплей

samrrr: и там хрен просчитаешь на 5+ ходов

samrrr: https://www.codingame.com/share-replay/530780781

Uljahn: ulitame tic-tac-toe

Uljahn: *ultimate

Uljahn: твой ход определяет сектор, куда будет ходить противник

Uljahn: если сектор уже заполнен/выигран, то свободный ход

samrrr: да пусть хотябы 3 на 3 решит...

Uljahn: shots fired...

magaiti: на 41 ходу форсед ход же

magaiti: в левом крестик дклать

magaiti: что-то у тебя не то

magaiti: аа

magaiti: сектор определяет

samrrr: спс я уже понял, что босса минмаксом не завалить

magaiti: мктсом пробовать?

mykeich: брось, не твое:)

magaiti: смитсимакс

samrrr: нет уж я хочу босса вальнуть

Uljahn: у босса мктс, 20к роллаутов на второй ход примерно

Uljahn: или поменьше

magaiti: это в какой лиге?

Uljahn: голда

samrrr: значит мктс круче минмакса иди минмакс его не осилил

magaiti: а, норм

magaiti: ифами его, ифами

samrrr: зря только его пилил...

Uljahn: пилил бы WW

samrrr: какой вв?

Uljahn: но там туман войны

magaiti: auto& answer = validActions[rand() % validActionCount];

magaiti: всратегия

samrrr: не завалишь, я пробовал

samrrr: так что насчёт формулы мктс?

Uljahn: а что с ней не так?

samrrr: то, что у меня её нет(

Uljahn: у меня тоже последняя осталась

Uljahn: не могу отдать

samrrr: ну ты же босса вальнул?

Uljahn: нет

Uljahn: я на питоне

samrrr: как так то?

Uljahn: формула не поможет вальнуть босса, если роллаутов мало

samrrr: роллаутов хватит

input.txt: я тут тоже наслушался историй про чудодейственный мктс и решил наконец написать

input.txt: фрормула вроде правильная, и в обычные крестики оно нормально играет, а вот во все остальное отказывается

samrrr: а босса вальнул?

Uljahn: чё, так и пишет - invalid game?

input.txt: ну в dots&boxes делает совершенно неадекватные ходы даже в конце игры

input.txt: саботирует свои обязанности

samrrr: пофиг на боксы

input.txt: не, в uttt я не играл

samrrr: босса то вальнул?

samrrr: ну тогда неважно

Uljahn: в конце игры дерево должно строиться полностью, стопудово баг у тебя

Uljahn: при достаточном количестве роллаутов разницы между мктс и миником нет, в пределе дерево раскрывается полностью

Uljahn: просто миник сделать anytime не тривиальная задача, а мктс anytime by design

Uljahn: и оценка не эвристическая, а статистическая

magaiti: доигрывать рандомно?

Uljahn: да, рандомный роллаут

magaiti: звучит несложно

magaiti: проблема роллаутов намутить побольше?

samrrr: это сложно

Uljahn: намного проще, чем придумывать забубённую оценочную

Uljahn: в общем случае - да, чем больше роллаутов, тем точнее статистическая оценка

Uljahn: тем глубже исследуется перспективный вариант

samrrr: а чё по формуле для мктс? есть лишняя?

Uljahn: нет

magaiti: на вики

magaiti: педии

Uljahn: он забанен

samrrr: ничё, я с тором

Uljahn: скоро и тут забанят за такие вопросы

magaiti: Automaton2000, чё по формуле для мктс?

Automaton2000: зобрист уже применён, даже в оптимизированном блочном виде, о котором я узнал неделю назад

magaiti: фига тут

MadKnight: Uljahn ну сложно ему, он же написал

MadKnight: ничего непонятно на википедии

Uljahn: а я что должен сделать? плюнуть в рот жёваной морковкой?

MadKnight: Uljahn не в настроении сегодня, Automaton2000

Automaton2000: но они не прям сильно помогают

samrrr: я уже попытался оттуда минмакс сделать, босса таким не вальнуть

MadKnight: или его за день достали

Uljahn: ссылку на формулу что ли скопировать?

MadKnight: samrrr так ты видел формулу но не понял её ?

Uljahn: я уже писал про UCT и UCB1

Uljahn: там два слагаемых

samrrr: я видел vi/ni и какойто корень

Uljahn: средний винрейт и корень, угу

Uljahn: корень автоматически повышает привлекательность малопосещённых чайлдов

samrrr: только там штук 5 подобных еще

Uljahn: бери на основе UCB1

MadKnight: яж говорю он просто не понял, а ты бомбишь

Uljahn: да он троллит просто, а я троллю в ответ

Uljahn: насколько я понимаю, все формулы различаются характером оценки упущенной выгоды от малоисследованных вариантов, UCB1 - это оптимистичный вариант, вроде бы

Uljahn: ещё встречал epsilon-greedy, thomspon sampling

samrrr: мне это серавно ниочём не говорит, а для неоткрытых нод вообще nan

Uljahn: лол

samrrr: 0/0 же

Uljahn: неоткрытые ноды открываются в первую очередь, их не нужно по формуле выбирать

Uljahn: почитал бы про алгоритм сначала

samrrr: чо, об этом ничего не сказано

Uljahn: During traversal, once a child node is found which is also a leaf node, the MCTS jumps into the expansion step.

Uljahn: неразвёрнутая нода - это как раз лист

samrrr: Как только во время обхода найден дочерний узел, который также является листовым, MCTS переходит к шагу раскрытия.

Uljahn: формула применяется для поиска по дереву как раз такой ноды, раскрытие которой выглядит наиболее перспективным

samrrr: что за дочерний узел, который не листовой?

Uljahn: не листовой - у которого чайлды есть

MadKnight: 1

samrrr: ну вот у меня есть 3 ноды, в одной 1 визит, в 2 других 0

samrrr: они все листовые?

Uljahn: выбирай рандомно из тех, у которых 0

samrrr: а если я возьму просто первую?

Uljahn: ну возьми, кто ж тебя остановит

samrrr: а босса так завалить получится?

Uljahn: вероятность этого высока

Uljahn: есть ещё много мест, где можно накосячить

samrrr: Да, надо бассивы конверсии незабыть проинитить, пожалуй запихну инит в конструктор

Uljahn: ну и битборды во все поля, плюс LUT на проверку победы на минидоске, также некоторые сложности могут возникнуть при генерации валидных ходов при фримуве

Uljahn: стейт в нодах не хранится, а получается путём применения ходов выбранных нод к начальному стейту рута

Uljahn: удачи

samrrr: да мад мне пару лет назад сказал таблы делать

samrrr: у меня теперь есть класс со всякими таблами конверсии

samrrr: Да не, ходы я уже нагенерил

samrrr: http://chat.codingame.com/pastebin/7aad1654-92ae-4add-9508-81429e6d2642

MadKnight: чё за таблы

samrrr: http://chat.codingame.com/pastebin/294f4892-f2c7-4692-a046-a6b9f8137de0

MadKnight: а, ну да

samrrr: слабовато чёт, 12к роллаутов

samrrr: раньше больше было

samrrr: да ну нафиг... добавил ещё мистисеских прагм и стало в 3 раза больше роллаутов

gamesprogramist: привет всем

Egrace: здравствуй

samrrr: https://www.codingame.com/share-replay/530842039 почти мктс...

samrrr: добавил прагм минмаксу, теперь в топ 100 входит

Chibikko: топ-100 в какой лиге?

samrrr: всё в тойже

samrrr: топ неосиливших так сказать...

Chibikko: у меня пол года назад обычный mcts с ~20к итераций болтался в самом топе золота, но босса не проходил. Затем просто добавил фишку teccles и сразу в середину легенды ворвался.

samrrr: какой такклес?

tutubalin: стратегия, названная в честь игрока teccles

Chibikko: Ну тут про него часто вспоминают. Если посмотреть его игры, то можно быстро заметить в чём оптимизация. Это при игре за Х только

tutubalin: суть простая: когда делаешь первый ход в пустую доску, ходишь так, чтобы ход противника был в ту же доску

samrrr: он что топ 1?

tutubalin: нет, но эта штука очень мощная

samrrr: а топ 1 пользуется этой стратой?

tutubalin: возможно и контр-стратой тоже

tutubalin: прелесть в том, что закодировать её очень просто, а результаты при этом хорошие. то есть соотношение трудозатраты/эффект огромное

samrrr: если топ 1 не юзает эту страту, то значит это путь тупиковый

Chibikko: в реплее первой же игры за Х у reCurse (топ-1) видно, что он юзает.

samrrr: ээх босса не завалил мктс

samrrr: ээх место в топе вырастает, но босса мне так не вальнуть

samrrr: время запускать профайлер, заменить дабл на флоат...

tutubalin: samrrr это не тупиковый путь, это просто первое приближение

tutubalin: в дальнейшем нужно делать книгу дебютов, а это как бы начальная её версия

samrrr: это не босс, а монстр какойто 20к роллаутов еле еле при очень сильных оптимизациях

tutubalin: ну вот теклсы запили и завалишь

samrrr: но босс то без них играет

tutubalin: именно поэтому он тебе и проиграет

tutubalin: босс - это далеко не топ1

samrrr: вотименно, а я его по честному завалить не могу...

samrrr: https://www.codingame.com/share-replay/530874759 вот как он на начале обыграл меня?

tomatoes: первые ходы от роллаутов мало толку, поэтому теклзы/книжки затаскивают

samrrr: у меня такое впечатление, что существует скрытый фактор инициативы

samrrr: ибо я часто вижу что почти победа, и сразу 100% луз

tomatoes: думаю "почти победа" это не для этой игры

samrrr: тоже расставление по редиректу помогает X но не помогает O что странно

tutubalin: вообще в легенде у X шанс победы примерно 66%, а у O 33%, причём чем выше в либерборде, тем выше шансов у крестиков

tutubalin: поэтому есть гипотеза, что существует выигрышная стратегия для крестов

Uljahn: у крестиков есть имба - ход (4, 4)

tutubalin: кстати да. для ноликов (4,4) сильно повышает шансы на выигрыш, поэтому крестикам нужно его делать обязательно

tutubalin: к тому же, это тоже теклс

tutubalin: думаю, игра была бы немного честнее, если бы правила запрещали крестикам первым ходом использовать (4,4)