MadKnight: samrrr а чё за алго юзаешь?
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/
The_Nigel: (╯°□°）╯︵ ┻━┻
**The_Nigel slaps around a bit with a large fishbot
The_Nigel: /
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: а как вообще это аб делается?
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)
samrrr: пытаюсь минмакс сделать
