tutubalin: подбором константы пытаются исправить непригодную формулу
amurushkin: закинули меня на 12 место пока я спал мерзавцы :)
ilt: пока ты спал... :grinning:
ilt: free memory падает в 0, но не всегда
ilt: total memory всего 64 Мб
ilt: локально у меня 120 выделяется
vrabosh: а комп 1 дается для 2 игроков когда идет проверка?
vrabosh: если да, можно попробовать пере print забить память, а когда input , освободить ее.. может тем самым у противника не будет хватать норм памяти? И как нить асинхроно процессор загружать, и когда свои просчеты делать, отключать функцию которая грузит процессор..
vrabosh: такое пробовали?
vrabosh: я думаю и другие способы есть замедлить комп.. Типа в линуксе процесс какой нить запустить которые хорошо тормазит и расчитать чтоб он работал 50мс.. типа поиск файла. Если есть возможность запустить фоном, и чтоб питон не ждал результата а ищел дальше работать.
BorisZ: там не физический комп то
BorisZ: не знаю деталей, но скорее всего супервайзер который выделяет виртуалки на серверах
vrabosh: понятно, что виртуалка..
vrabosh: там 1 виртуалка играет против 2 виртуалки?
vrabosh: или 1 игра запускается на 1 виртуалке?
vrabosh: для обоих
BorisZ: а ботами рулит рефери - он запускает каждого бота в своем процессе
BorisZ: не знаю (
BorisZ: когда рефери получает вывод от процесса бота или время выходит - он его суспендит
BorisZ: каждому процессу бота - по одному ядру и по сколько то там памяти
vrabosh: с читами с ОС, вродь как не честная штука, но тоже прикольная, развивает понимания как устроена ОС и другие направления.. Думаю этому стилю игры тоже право надо жить)
BorisZ: на чужой процесс ты не сможешь повлиять, только на свой
vrabosh: если 1 виртуалка, то можно.. както весь комп загрузить
BorisZ: попробуй конечно, но мне кажется что только свой процесс сможешь нагрузить отдельным потоком
BorisZ: ну и свое ядро
vrabosh: наверно.. скорей всего для каждого виртуалку делают
vrabosh: вообще разбираться в ОС тоже классная тема
amurushkin: у меня результат игры очень сильно зависит от сида рандома. до сих пор вопрос какой лучше ))
BorisZ: ну и если получится то наградой будет бан скорее всего, это тоже стоит учитывать
BorisZ: 42
BorisZ: это все знают, ты чего )
vrabosh: тут я бы не банил, т.к. это тоже относится к it сфере.. и оно полезно знать.
amurushkin: было же недавно что один чел смог зомби процессов наделать и все встало ))
vrabosh: ну или если это банальные вещи которые уже не исправить, но оно мешает всем, то да..
BorisZ: vrabosh любое приемущество только на некоторое время, потом идея распространяется, все начинают это использовать
BorisZ: то есть результатом не бана будет то что весь топ будет забит ботами которые только блокируют работу друг друга
BorisZ: против другого блокера - 50/50 против не блокера - победа
Hamibar: хех, разница между 10к роллаутов и 25к и больше 15-20 мест. наверное так не должно быть) пойду баг искать
Hamibar: В любом случае это грязная игра и должен последовать бан
tomatoes: вроде пытались некоторые считать что-то во время хода соперника, но безуспешно
BorisZ: Hamibar там от проца еще зависит количество, ты побольше реплеев посмотри, может там не в 2 раза а меньше улучшение то
Hamibar: нее, среднее где-то 25, бывает конечно меньше, но и больше тоже. В иде тоже на разных процах запускается?
amurushkin: о награрока скинул и томатоса на 4 запулил )))
amurushkin: Hamibar: в иде да тоже на разных
amurushkin: блин приятно когда рекурса и награрока обыгрывешь несколько раз подряд )))
ilt: локально перестал падать
ilt: а в иде появилось Warning: your code did not read all available input before printing an instruction, your outputs will not be synchronized with the game's turns and unexpected behaviour may occur.
ilt: что это такое?
amurushkin: ну говорит что ты вывод делаешь еще до того как считаешь все инпуты. я такого не видел еще
tomatoes: считывай весь инпут даже если не используешь
ilt: http://chat.codingame.com/pastebin/28edffe7-a415-4e26-b3a3-ea2bffa306b8
Hamibar: спасибо. Следующая цель карлисо порекать)
ilt: он считывается насколько я понимаю
Hamibar: Какие классные ошибки в джаве) на плюсах бы написало таймаут и все
amurushkin: может сначала цель попроще сделать? :)
amurushkin: на плюсах раньше тоже были подробные ошибки. а потом как то в один момент все пропало и теперь по любому поводу таймаут
Hamibar: Я про тебя говорил)
tomatoes: карлисо за крестики крайне редко проигрывает
tomatoes: 1 игру из 200 наверное
ilt: может мне свободную память смотреть и подрезать лимит в зависимости от ее количества?
tutubalin: DeepMind's AlphaZero replaces the simulation step with an evaluation based on a neural network.
amurushkin: tutubalin: ну да у них как я понял заходит в дерево на глубину и оценочную юзают в виде сетки. в csb у топов так же примерно
ilt: amurushkin а как у тебя сделано переиспользование дерева?
amurushkin: просто беру root переставляю
ilt: ты чистишь память у неактуальных нодов?
amurushkin: ничего не чистю
ilt: а у меня похоже приходит GC
ilt: Хотя я не понимаю почему
amurushkin: веду счетчик просто который нод будет следующим из глобального набора. и если он подходит к концу то начинает брать с начала
Hamibar: интересно, почему карлисо не проигрывает.
amurushkin: у него вроде роллаутов около 200к
amurushkin: по крайней мере у смита больше 120к если я не путаю
Hamibar: и это весь секрет?
amurushkin: свои секреты они не рассказывают
amurushkin: мне смит сказал если он расскажет свои фишки то его все порекают ))
amurushkin: но он все равно довольно много подсказывает. по csb мне кучу всего подсказал
amurushkin: некоторые его советы я даже не реализовал. не смог сделать хорошо :)
Hamibar: ну да) он и чатике писал писал вчера много о крестиках своих
amurushkin: блин как назло меня вчера в чате не было ))) а во сколько не помнишь? хотелось бы почитать
Hamibar: ох, на самом деле не помню. Мб где-то после 4-6 вечера. Он по моему о своей книге дебютов говорил
Hamibar: все что я запомнил, это то что у него состояние игры очень компактное
amurushkin: вот я не могу пока придумать как книгу хранить. может когда нибудь попробую сделать все таки
tomatoes: он говорил что у него еще рандомно не выбираются. сразу по формуле
tomatoes: а время не помню
ilt: заработало переиспользование дерева но таймауты не ушли
ilt: бага была в переиспользовании ссылку на родителя не занулял
vrabosh: все так крестики нолики обсуждают, что тоже захотелось.. но как я понял на питоне туда нет смысла идти?
ilt: давай к нам
amurushkin: ну да парент надо убрать у ноды куда переставляешь рута
amurushkin: vrabosh: на питоне вроде до голды можно
ilt: до середины голды 100%
amurushkin: ilt: самое интересное знаешь что. в CSB у меня не получается сделать переиспользование дерева. только с нуля строить. и не смог за все время найти причину почему таймит
ilt: :)
vrabosh: я просто думал за них взяться когда придет время С изучать.
Hamibar: хех, нашел баг и сразу в 10ку вошел)
ilt: таскаю код между ветками, оказывается вернул багу с подсчетом роллаутом
ilt: лямдба таки медленнее, но все логично
ilt: стало чуть лучше, но не критично
vrabosh: как я понял, вы тут все кто общается в легенде в крестиках?
Hamibar: не все.
Hamibar: из голды тоже много
amurushkin: я бы на твоем месте все лямбды убрал
ilt: из голы даже больше
ilt: amurushkin уже, у меня их две всего было
Uljahn: amurushkin: логи через некоторое время выкладываются на https://cg.spdns.eu/wiki/Special:PrefixIndex?prefix=World&namespace=3000
Uljahn: с задержкой в пару дней
amurushkin: вобщем примерно завтра можно будет искать вчерашние логи :)
Uljahn: вроде, там ничего нового он не рассказывал, только немного про свою книгу дебютов и то, что миниборды у него в троичной стистеме
Uljahn: а глобальная миниборда в двоичной
Uljahn: *глобальная борда
Uljahn: а книга дебютов в третьей системе, которая учитывает симметрию
amurushkin: что то так лениво книгой заниматься что пипец
Uljahn: он сказал что книга хороша против других книг
Uljahn: tomatoes вон тоже заметил, что карлисо за крестики изредка проигрывает, и скорее всего когда нолики ходят не в угол вторым ходом, а на сторону
Uljahn: потому что не по книге
amurushkin: впринципе это можно быстро попробовать что получится. поменять 2 ход
Uljahn: если все будут на сторону ходить, как раньше рекурс делал, то он просто книгу подкорректирует
Uljahn: видел у одного бота в топе голды начало не в 4-4, интересненько
amurushkin: не все не надо. я один буду )))
tomatoes: я пробовал через 2-2 и 6-6 контрить теклзы, но даже локально особо разницы не было
tomatoes: впринципе можно через сайды такое же попробовать
Uljahn: я про 4-4, 5-4
Uljahn: т.е. первый ход ноликов, второй ход игры
Uljahn: или хз как тут правильно считать
YurkovAS: у меня нет хардкода - вроде бы так хуже играло.
Uljahn: скорее всего, так будет хуже против всех, кроме карлисо))
YurkovAS: может константы надо поуменьшать... бонусы и штрафы
amurushkin: ща посмотрим. сабмитнул вбок ходить ))
Uljahn: :fire:
YurkovAS: не должно же быть хуже из-за хардкода первого хода? он всегда туда же ходит.
amurushkin: ход может быть один лучше чем другой по идее
Uljahn: один немного лучше, но другой может вести к интересным ситуациям, где ломаются эвристики
Uljahn: Hamibar тоже почти в легу пролез
Uljahn: amurushkin: какое у тебя место было перед сабмитом?
Hamibar: совсем немного не хватило)
Uljahn: ну, винрейт против босса вроде положительный, так что можно ресабмитить
amurushkin: на 8 была сегодня после сабмита та версия что сейчас но с другим ходом для ноликов. ничего не поменялось особо. только против карлисо стало чаще 1-1
Uljahn: значит, этот ход не сильно хуже, как минимум
amurushkin: пойдем другим путем. будем ходить крестиками не в центр ))
amurushkin: ооо начало не ахти
ilt: проверил три варианта с переиспользованием и без лямбд, только с переиспользованием дерева, только без лямбд
ilt: все с кучей таймаутов
ilt: ~25% игр
ilt: самая стабильная версия без переиспользования и с лямбдами
tomatoes: а само дерево в виде пула какого нибудь или обычное?
tomatoes: с ходами меня пока больше всего смущает что карлисо и смитс всё таки сами ходят в 3-3 :sweat_smile:
tomatoes: особенно смитс у которого я так понимаю куча посчитанного
Uljahn: у них книжки на глубину 12-40
tomatoes: то есть план выдать что нибудь не из книги?
Uljahn: типа того
Uljahn: гипотетически, это будет давать маленький бонус против тех, у кого книги
YurkovAS: может тогда лучше захардкодить глубину 2-3?
аналогично первому ходу: чтобы его выбрал и погнал дальше считать дерево
Uljahn: насколько я понимаю, в этом и заключается суть книги дебютов - начальные ходы выбираются по хардкоду, а время тратится на построение дерева за пределами книги, потом переиспользование дерева
YurkovAS: локально запустить на пару минут. потом вывести дерево на глубину 3.
и вставить это как начальное дерево.
Uljahn: угу, только смитс месяцами гоняет, уточняет скоры
Uljahn: плюс у него хитрая система представления дерева, что и симметрию учитывает, и другие фичи имеет, как например равноценные конечные стейты
Uljahn: OOX
XX.
OOX
Uljahn: у него равноценно
Uljahn: OXX
XX.
OOX
Uljahn: т.к. исход одинаковый
Uljahn: это для миниборд
YurkovAS: без книги у него на каком месте будет?
YurkovAS: миарем выключил книгу, так висит в ~15. а с книгой стабильно был 4-5.
может и не стоит сильно упарываться, как смитс.
достаточно только порекать томатоса :grin:
Uljahn: да, что-то вроде того у них и получилось, +10 мест в топе леги
Uljahn: за счёт книг
Uljahn: только логи не могу найти
YurkovAS: Automaton2000 ты то хоть не книжный червь? :smiley:
Automaton2000: без багов бы давно в голде был, наверное :)
amurushkin: Uljahn: тогда получается что у него в книге наверное не порядок ходов а стейт и лучший ход в нем
amurushkin: ну если книга дает 10 мест то я вообще первым должен быть с ней ))))
Uljahn: https://cg.spdns.eu/wiki/Chat:World/2020-05-18
Uljahn: вот тут про ресабмит без книг было
Uljahn: поиск по слову bookless
YurkovAS: спасибо!
Uljahn: наверное, самое важное обсуждение по крестикам, когда сразу три топа собрались)
amurushkin: MSmits: karliso, one time i noticed your games vs re curse went almost 20 deep with no change MSmits: that was also a book i assume? karliso: well... he plays a forced line....
amurushkin: интересно что там за форсированный вариант у них
YurkovAS: so you select a node, expand it, it gets 9 children and it counts as 9 visits because you do 9 playouts to end?
Roughly so
ответил "примерно так". в общем, он как-то по другому делает.
YurkovAS: и это дает ускорение, не только ему.
amurushkin: типа они с каждой ноды сразу играют?
amurushkin: я пробовал ноду которую только что раскрыл делать роллаут несколько раз а не 1. дало прирост роллаутов но качество игры упало
Hamibar: меня напрягает слово примерно
Hamibar: ох хорошо сабмит пошел
YurkovAS: да, получается они рандомно играют для каждого нового ребенка. как обычно.
но это прибавляет скорости, т.к. к этой родительской ноде не надо больше столько же раз добираться по формуле.
и с другой стороны статистика вся есть.
YurkovAS: даркхорс64 еще это использует. он в последние месяцы апнулся.
YurkovAS: смитс пишет, что он такой подход и в других играх юзает.
надо проверять и разбираться.
amurushkin: тогда понятно что и рандомный выбор не нужен потому что уже все посещены по разу сразу
Uljahn: угу
Uljahn: Hamibar :joy_cat:
amurushkin: нашел способ как прерывать роллаут. стало меньше роллаутов ))
Uljahn: ох ты
Uljahn: вот и закатился
Hamibar: 0.11 до босса как я закатился?
Hamibar: я 2й финишировал)
Uljahn: хз, я в шоке
Uljahn: у тебя иконка с местом цвет сменила
Hamibar: видимо это из-за того, что 2 последние босу проиграл
Hamibar: и оповещение тоже
Uljahn: поздравляем
Hamibar: наверное сначала я просчитался, меня перебросило, а потом босс посчитался
Hamibar: спасибо.
Hamibar: оказалось, что константа важна.
ilt: какая иконка цвет сменила?
Hamibar: с примерно 7-8го места поднялся просто изменив ее.
ilt: я думал ты в легу прошел
Hamibar: с местом. Открой лидерборду увидишь
Hamibar: Прошел
Uljahn: ilt: где ранг показывает, она оранжевая у него теперь
Uljahn: через минуту заберут в легу
Hamibar: Вовремя кстати прошел, не надо ждать)
Uljahn: а в крестиках разве долго ждать?
Uljahn: 20 минут всего
Hamibar: хз. А ну тогда ладно
Uljahn: это в гоночках по 6 часов
Hamibar: я думал несколько часов
ilt: у меня только сейчас обновилась
ilt: Поздравляю :thumbsup:
ilt: надо теперь мне таймауты подебить
Hamibar: фух. Не такая она и простая оказалась)
Hamibar: Самый больщой прирост дал фикс багов)
Hamibar: Теперь надо собраться и переписать все нормально)
YurkovAS: не надо переписывать :grin:
YurkovAS: конкуренты
vrabosh: напомните как проверку времени делать в питоне, чтото типа там %%
Uljahn: это в ноутбуках
Uljahn: на CG я юзаю timeit
vrabosh: мне как раз в ноуте надо
vrabosh: я кстати только в ноуте и программлю)
vrabosh: на vscode ставится.. вообще такая штука быстрая, перебирать идеи быстро.
vrabosh: на С прикольно ты сам видешь примерно сколько твой код ресурсов жрет.. интуитивно..
vrabosh: а на питоне, надо проверять каждый способ.. там не понятно, как он выполняется
Uljahn: https://ipython.org/ipython-doc/3/interactive/magics.html#magic-time
Uljahn: ты про это?
Uljahn: на питоне всё спрятано под капот
Uljahn: поэтому он с одной стороны простой, а с другой - сложный)
vrabosh: да, спасиб...
Hamibar: YurkovAS никто же не говорит, что я нормально перепишу :grinning:
Hamibar: После этих крестиков у меня ощущение, что я старушка на спорткаре. Можно разогнаться на 300, а я 40 еду
YurkovAS: сделал этим способом - после expand, каждого ребенка проиграть отдельно на рандомах.
получилось 10к роллаутов на 2-ом ходу.
Hamibar: а почему уменьшается то?
YurkovAS: или, надо считать теперь по другому. щас проверю.
там еще добавляется лишнее копирование "борды". ее надо восстанавливать для каждого ребенка.
Uljahn: с фримувами наверное совсем всё плохо
vrabosh: через нампи долго оказывается делать, есть тут линия для выигрыша или нет
vrabosh: http://chat.codingame.com/pastebin/adb74b69-e3f8-472e-9c5b-178f5a624c3f
vrabosh: вот код, на моем компе 24.2 µs ± 237 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Hamibar: ооо, оптимистично поставил карлисо в иде и выиграл) правда за крестики
YurkovAS: томатоса ставь - всегда будешь выигрывать.
YurkovAS: там раст будет в дебаг режиме работать
Hamibar: неа
Hamibar: все работает
Hamibar: ааа, я думал таймаут будет)
Hamibar: а так да гораздо меньше сим
Uljahn: vrabosh: очень неэффективный код
Uljahn: и представление борды неудачное
vrabosh: покажите эффективный
Uljahn: миниборду можно хранить в двух int16 для О и Х
Uljahn: все проверки на битовых операциях
vrabosh: я как понял нампи медлен когда логика на питоне и к нему часто обращаться.. он хорош когда всякие операции внутри делает.. типа перемножения матрицы
Uljahn: именно так
tomatoes: https://www.codingame.com/playgrounds/48392/bitboard-for-tic-tac-toe-game
Uljahn: хороший плейграунд
Uljahn: я примерно так и делал, только все кондишоны на первом ходу просчитал для всех 512 возможных состояний миниборд, потом можно за одно обращение к массиву получить результат
Hamibar: мне кажется лучше сразу хранить int32. Но тут уж кому как удобнее
Uljahn: у меня int32, но думаю на два по 16 переписывать, не удобно
Hamibar: кстати получается нам нужны 3 int16
Hamibar: а не не надо
Uljahn: смитс в троичной системе запихал всё один int16
Hamibar: ага я читал вчера. И совсем не понял как это можно сделать
Hamibar: надо погуглить
Uljahn: можно, но только для миниборд, для глобальной ничьи надо учитывать
Hamibar: ну это понятно ведь там 4 состояния
Hamibar: кстати наверное 2 по 16 действительно удобнее. Единственное нужно чекать кто ходит сейчас.
Uljahn: vrabosh: насколько я понимаю, у питона есть свои родные типы данных, а с numpy-данными напрямую он работать не может, поэтому при каждом обращении из питона к нумпи происходит преобразование типа данных с сопутствующими проверками и прочим оверхедом, поэтому желательно всю логику реализовывать на функциях из numpy
Uljahn: иначе вместо ускорения можно получить замедление)
Uljahn: другое дело, если бы была Numba, там вроде всё это пофикшено
vrabosh: http://chat.codingame.com/pastebin/a9a582ff-f567-4803-b4ec-a91442e57802
vrabosh: чтото типа такого надо делать?
vrabosh: кстати может я проверку не эфективно вообще по логике делаю? может есть более короткий способ? и быстрый
Uljahn: потом ещё от размерностей матриц зависит, т.е. для операций над матрицами 9х9 значительного профита от векторизации не заметишь, а вот когда матрицы 1000х1000, то разница будет в десятки раз
Uljahn: vrabosh: да, уже полдела сделано
vrabosh: я еще даж тикток не открыл)
vrabosh: мне страшно его открывать. щаз открою и на неделю можно зависнуть
Uljahn: теперь сделай цикл от 0 до 512, проверь каждое значение и результат занеси в массив на 512 элементов, потом по индексу сможешь получить результат
Uljahn: индексом будет твой стейт, который хочешь проверить
tomatoes: на неделю это очень оптимистичный прогноз
Uljahn: +
Uljahn: но на тиктоке я большему научился, чем на всех прошлых контестах вместе взятых)
Uljahn: в плане оптимизаций
ilt: если у меня массив предварительно созданных нод то по логике ведь объекты в нем живут пока идет игра
ilt: в нем ничего не добавляется и не удаляется
ilt: просто мы двигаем root и обновляем в объектах реквизиты
ilt: хоть убей не понимаю почему GC срабатывает
Hamibar: его же по идее можно отключить?
ilt: как?
ilt: если его отключить то свободная память просто закончится
Hamibar: я не уверен, но мб можно.
amurushkin: а ты как его двигаешь?
amurushkin: по идее не должен gc срабатывать
Uljahn: может, нужны ссылки в нодах на другие ноды или инициализация начальными значениями?
amurushkin: вот я подозреваю что gc срабаывает потому что он null ссылкам ставит
amurushkin: ilt: покажи что ли куски кода как ты это делаешь
amurushkin: если у тебя массив N и parent_ind сначала был 0 то потом просто делаем parent_ind = 100; N[parent_ind]->parent=-1
amurushkin: вот и все переиспользование дерева
Hamibar: Хотел еще на будущее спросить. Вот если мы заранее создаем массив нодов, то что будет если этот массив кончится?
amurushkin: я проверяю если max_node_index подходит к концу то счетчик начинается сначала
YurkovAS: сделай массив на 15млн нод и не будет проблем и проверок
ilt: http://chat.codingame.com/pastebin/7b83aa7b-392a-4070-b24e-cec680848cbd
Hamibar: а откуда знаешь, что ноды в начале этого массива нам уже не нужны?
amurushkin: практика показывает ))
ilt: YurkovAS это очень долго
amurushkin: просто их много же
ilt: суть не в том сколько там элементов
ilt: при переиспользовании дерева появляются таймауты
ilt: у меня root это Node
Uljahn: в IDE тоже? или только на сабмитах?
amurushkin: ты не ссылки на ноды делай а индексы их храни. тогда и gc не будет приходить
Uljahn: в джаве нет простых массивов многомерных?
amurushkin: конечно если ты обьекты в null скидываешь то gc будет их подчищать
ilt: я их не скидываю в null
amurushkin: ну а как ты парент скидываешь у нового рута?
ilt: root = child;
root.setParent(null);
amurushkin: нода сама какую структуру имеет? у тебя root вроде копию должен хранить обьекта еще и делать ее постоянно будет. лучше индексами оперировать
amurushkin: вот а говорит null не ставит )))
ilt: объект в nodesHeap лежит
amurushkin: вобщем я бы на твоем месте делал чтобы parent это был индекс из массива
Uljahn: всё дерево до этого child повисает в воздухе и GC его собирает?
amurushkin: Uljahn: скорее всего да если у него перелинковка через parent идет ссылками
Hamibar: так объекты же все равно в массиве остаются
ilt: думаю нет потому что nodesHeap это массив
amurushkin: а у него копии же
amurushkin: root = child; вот тут же копирование происходит.
Hamibar: аааа, в джаве не по ссылкам
amurushkin: root = nodesHeap[0]; и даже тут по идее копирование тоже
ilt: это не копирование вроде а присваивание ссылки
ilt: сейчас проверю
amurushkin: тут это бы выяснить не помешало потому что по дефолту в джаве везде копирования
ilt: там один и тот же объет
amurushkin: root = child;
root.setParent(null); после такого кода у child тоже parent меняется?
Uljahn: т.е. нужен массив ссылок на объекты, а внутри объектов уже прописывать не прямые ссылки, а индексы в этом массиве?
amurushkin: Uljahn: да у меня так в csb сделано. firstchild и parent это индексы массива
ilt: amurushkin Да меняется
ilt: а в массиве как лежал объект так и лежит
Hamibar: Uljahn А зачем массив ссылок? почему нельзя просто по индексу обращаться?
ilt: массива ссылок нет
ilt: есть массив нод объектов
Uljahn: в IDE наблюдаются таймауты при переиспользовании дерева или только при сабмитах?
ilt: root можно хранить индексом да
ilt: в IDE таймаутов меньше, чем в абмитах
Uljahn: я понимаю, надо хранить два параметра: рут и следующую пустую ноду
ilt: локально меньше, чем в ИДЕ
Uljahn: в смысле, индексы
ilt: пустая да это индекс
Uljahn: и что меняется, если индекс рута изменить?
amurushkin: у тебя парент может копии обьектов держит?
ilt: вряд ли на индекс переделаю, хотя не думаю что от этого что-то измениться
Uljahn: по идее, в руте надо указать, что у него нет парента, чтобы бэкпроп корректно заканчивался, но можно пойти другим путём - сохранять индексы нод, через которые идёт селекшн
Hamibar: я вообще не храню парента в ноде
Uljahn: если отдельно хранить список селекшна, то да, парент уже не нужен
Hamibar: я рекурсивно спускаюсь, наверное с точки зрения производительности не оч, зато удобно)
Uljahn: в ноде будет индекс первого чайлда и их количество, если чайлды инициализировать все скопом
Uljahn: про рекурсию не думал, интересный вариант
Uljahn: дебажить сложнее, наверное
Hamibar: ну это ведь рекурсия)
Hamibar: Но по сути она очень простая
ilt: у меня дети это private List<Node> childArray;
Uljahn: :scream_cat:
Uljahn: я конечно не спец в джаве, но что скажет amurushkin?
ilt: по сути это лист ссылок
ilt: там объектов нет
YurkovAS: каждый childArray будет проверяться сборщиком мусора. т.к память под него выделена на куче.
YurkovAS: сделай как писали выше
int parentId;
int firstChildId;
YurkovAS: еще лучше без parentId - так работает быстрее
ilt: в backPropogation как ты без парентИД обойдешься?
tutubalin: amurushkin у меня с индексами медленнее работает. потому что их надо умножениями потом пересчитывать, а поинтер сразу говорит, где брать
Uljahn: ilt: отдельный список индексов, через которые идёт селекшн
Uljahn: потом по нему возвращаешься
Uljahn: либо вон рекурсию предлагают
tutubalin: рекурсия медленнее
Hamibar: tutubalin зачем пересчитывать?
tutubalin: Hamibar чтобы получить значение из ячейки памяти, в любом случае нужен адрес ячейки
tutubalin: если это поинтер - то вот он готовый адрес
tutubalin: а если элемент массива, то это <адрес начала массива> + <индекс>*<размер элемента>
amurushkin: tutubalin: ну у меня тоже ссылками. индексами у меня в CSB сделано. это я же для джавы предлагаю
tutubalin: у меня когда дерево фиксированное было, там всё было хорошо так расфасовано
YurkovAS: Uljahn спасибо за ссылку с обсуждением крестиков!
Другой способ заметно увеличивает кол-во роллаутов.
В итоге играет хуже, но может надо поменять константы.
И проверить в других играх.
amurushkin: ilt: у меня дети это private List<Node> childArray; а детей вообще в идеале хранить как first и count и в том же массиве их держать
Hamibar: Можно же сделать массив указателей
Hamibar: и не надо ничего пересчитывать
tutubalin: индекс 0 - это рут
индексы с 1 по 10 - это глубина 1
индексы с 11 по 91 - это глубина 2 и так далее
tutubalin: по последовательности ходов можно было найти индекс
amurushkin: YurkovAS: вот у меня была та же фигня роллаутов больше играет хуже. тут наверное дело в том что дерево исследуется меньше
tutubalin: индекс родителя = (индекс-1)/9
tutubalin: индекс ребёнка = индекс + 1 + ход
tutubalin: всё красиво
tutubalin: а потом сделал на поинтерах и стало процентов на 10-20 быстрее
Uljahn: так может это из-за нелокальности
Uljahn: тут надо профайлер уже расчехлять
tutubalin: благодаря фиксированной глубине всё дерево влезало в L2
YurkovAS: amurushkin у меня и с хардкодом первого хода заметно хуже.
поизучаю потом.
если у томатоса так же сделано, то значит надо юзать. у него сильный бот.
ilt: пойду переделывать, этот лист действительно чистится и заполняется заново
tutubalin: ну и чаще всего проходишь по верхним нодам, а они как раз все очень рядом лежат
tutubalin: так что в L1 скорее всего
YurkovAS: ilt и проверь, что в ноде нет Float, Double, Long, замени все на примитивные типы.
tutubalin: но у меня проц не умеет кэш профайлить
Uljahn: т.е. 10-20% тратилось на операции вычисления адреса из индекса?
tutubalin: а фиг знает. может быть и правда с кэшем связано
tutubalin: но мне VTune сказал, что моя микроархитектура ему не нравится и миссы в кэш мне не покажет
Uljahn: что за проц?
tutubalin: Core4Quad 6600
tutubalin: с 2008 года служит верой и правдой
inoryy: вот это старик
Uljahn: рарный старец
inoryy: ниче скоро все равно будет с дц компа работать
TTeaLL: не подскажете, что это значит
TTeaLL: your code did not read all available input before printing an instruction, your outputs will not be synchronized with the game's turns and unexpected behaviour may occur.
TTeaLL: это ошибка или что?
amurushkin: очевидно же. код делает вывод до того как считает все входные данные
TTeaLL: а, блин, секунду назад всё было ок, а теперь это
Uljahn: в дискорде пишут, что какие-то изменения проводятся на платформе
Uljahn: "We've added a warning for input/output desynchronization when not all lines of input are read in gameloop puzzles (except for code golf I think)"
Uljahn: не исключено, что у них баги, такое не редкость
tutubalin: если только в gameloop puzzles то фиг с ними
tutubalin: а если везде такое запилят, то нафиг-нафиг
ilt: я утром такое в крестиках словил
BorisZ: tutubalin с такими индексами куча дырок остается когда доски частично заполнены, а фримув вобще как-то надо обрабатывать отдельно
BorisZ: чайлдов то не 9
Uljahn: у него фиксированная глубина, где фримувов ещё нет
Uljahn: наверное
BorisZ: когда-то появляются неизбежно
amurushkin: Uljahn: когда то у него они все равно должны появиться
Uljahn: в роллаутах появятся
amurushkin: да и в дереве появится во второй половине игр
Uljahn: аааа
Uljahn: блин, вот я тупанул)
BorisZ: кто-то объяснял что дети должны подряд идти в памяти чтобы в кеш проца влазило
BorisZ: если я все правильно понял
amurushkin: BorisZ: ну оно само по себе так получается обычно
amurushkin: впринципе можно как у tutubalin только с запасом по 100 например выравнивать. но хз что из этого получится
BorisZ: почему вобще память до сих пор у всех компов одномерная
BorisZ: почему не пробуют двумерную или трехмерную адресацию или древовидную
BorisZ: ну ладно двумерная и трехмерная это арифметикой можно сделать - сегмент + смещение
BorisZ: может и не дало бы ничего
BorisZ: а вот древовидную прикольно если бы придумали
BorisZ: не программная эмуляция а аппаратно чтоб
BorisZ: нахрена оно надо конечно. это тоже верный вопрос )
Uljahn: на ПЛМ наверное можно запилить
BorisZ: ПЛМ - это что?
Uljahn: программируемые логические матрицы
vrabosh: BorisZ, я хз как там апаратно устроено, но когда 2 карточки воткнуто, это посути массив [2],[4Gb]
vrabosh: а хотя у них там шина наверно одна..
BorisZ: я в архитектуре железа плохо разбираюсь, я имел ввиду с точки зрения логической, как там все оно внутри не важно
BorisZ: память для программы - это длинная цепочка ячеек, одно измерение
BorisZ: если бы эти ячейки не в линию были бы вытянуты, а деревом
BorisZ: можно было бы на такой архитектуре команды выполнять и адресоваться к другим ячекам или вобще неудобно
BorisZ: если дерево бинарное то адресоваться вроде можно, 0 - налево, 1 направо
Uljahn: на ПЛМ/ПЛИС (FPGA) можно декодер сделать, чтобы адресоваться к нужным ячекам в зависимости от топологии, но тогда кэши по бороде пойдут
Uljahn: декодер правда будет аппаратный и быстрый
Uljahn: линейная память удобна как раз с точки зрения иерархических кэшей
BorisZ: угу я прочитал статью в википедии про ПЛИС, выходит еще 1970 году что-то подобное и придумали и сделали
BorisZ: но раз об этом не особо слышно то видимо не взлетело оно (
tutubalin: BorisZ фримув - это два хода: выбор доски, выбор клетки
Uljahn: ну как не взлетело, многие наработки применяют в TPU/NPU
Uljahn: ASIC тоже FPGA
tutubalin: дырок много, да
Uljahn: я просто что-то слишком древнее вспомнил, чему нас в вузике учили))
Uljahn: ну и графы вычислений сейчас в моде, а у них древовидная структура, кмк
Uljahn: соответственно, в железо закладывают возможность адаптироваться под графы
Uljahn: https://cloud.google.com/blog/products/ai-machine-learning/what-makes-tpus-fine-tuned-for-deep-learning
Uljahn: вычитал тут про Systolic array vs Von Neumann architecture
Uljahn: т.е. просто хранить данные древовидно - тупиковый путь, лучше древовидно организовать вычислительные ядра или типа того
BorisZ: ладно, насчет данных в дереве понятно, наверное подумали умные люди, может и попробовали
BorisZ: а что значит ядра древовидно?
BorisZ: сейчас они как? - вроде вобще никак не организованы
BorisZ: у каждого свой конвеер команд, а ось уже отвешивает кому захочет
BorisZ: да, линейная память и конвеер команд - это вроде и есть архитектура фон неймана
Uljahn: граф вычислений и связывает ядра в нужном порядке, если я не ошибаюсь
Uljahn: это не процессорные ядра же, а в TPU/NPU
Uljahn: т.е. результат одного ядра попадает на вход следующего, результат в памяти хранить не надо вообще
BorisZ: по простому там очень много очень маленьких ядер )
Uljahn: угу, как мы недавно пытались до toctou донести)
BorisZ: так много что память не особо нужна, они данные друг другу кидают
Uljahn: в GPU вроде тоже такое используеся для реорганизации вычислений
BorisZ: трудно понять концепцию блин, кто-то этим же всем должен рулить
tutubalin: а не проще сразу аналоговый девайс делать?
tutubalin: сперва нейронку научили, параметры все посмотрели, потом собрали из резисторов.
BorisZ: то что про ПЛИС ульян говорил - это примерно оно и есть
BorisZ: A programmable logic device (PLD) is an electronic component used to build reconfigurable digital circuits.
BorisZ: то есть еще на шаг дальше - можно переделать конфигурацию
BorisZ: если я все правильно понял )
vrabosh: я только понял правила крестиков, прикольно придумали..
ilt: а памяти в с++ тоже выделяется 64880640 bytes?
YurkovAS: у всех ЯП одинакого памяти. в с++ можно объявить большой массив структур, столько памяти там и будет. а в яве и т.п. языках там будут указатели, а сами данные расскиданы по куче в памяти. даже само обращение уже медленне, т.к. сначала читаем из массива адрес и потом по этому адресу читаем данные.
YurkovAS: а если учесть особенности процессора, что он читает из памяти всегда пачкой по 64 байта и подкешивает. то выгоднее как раз пример из с++, т.к. больше полезных данные кешируется.
ilt: кто говорил про 768 МБ
YurkovAS: https://www.codingame.com/faq
ilt: у меня просто в локале total memory растет вначале на 100 МБ
YurkovAS: деталей не знаю - это в яве под хип, или это суммарно под виртуалку.
ilt: а тут как влитое стоит на одном месте
YurkovAS: у тебя таймауты? может там ошибка? пробывал например с 90мс или с 50мс.
amurushkin: когда меня задолбали проседания на джаве я пошел учить плюсы
YurkovAS: там и учить много не надо. можно писать по простому, в стиле си с классами - чего достаточно для cg
amurushkin: во во. циклы и массивы все что надо ))
YurkovAS: vector-ы не юзаю, даже new ни одного нет
YurkovAS: да. по простому делать и будет норм.
YurkovAS: в яве есть off heap решения. ByteBuffer или типа такого. сам не пользовался. смысл в том, что эти объекты будут лежать в другой памяти, не куче, и сборщик мусора их не будет проверять.
ilt: YurkovAS Пробовал уменьшать лимит до 10 мс. Таймаутов становится меньше, но они совсем не исчезают
ilt: без переиспользования дерева таймаутов почти нет
amurushkin: так может у тебя не GC а баг?
YurkovAS: ilt может всетаки ошибка? попробуй в дебаг вывести состояние игры и потом локально его же запустить.
ilt: пробовал не могу воспроизвести
ilt: может и баг конечно
ilt: в локале не вылетает с такого же состояния
YurkovAS: тогда не знаю, на яве не писал ботов. в плюсах была ошибка и искал бы именно так.
ilt: завтра уберу childArray посмотрим что будет
ilt: до того момента как начинает повторно идти по массиву нод не вылетает
ilt: иногда проходит по массиву больше одного раза
ilt: больше двух раз
ilt: чаще валится во втором проходе
ilt: раньше таймаут был на первом втором третьем ходу
ilt: хоть как-то его можно было воспроизвести
ilt: сейчас 20-30
YurkovAS: может массив нод маленький и заканчивается?
а когда локально воспроизводил, то с начала начинал. или комп домашний медленнее и не добралось до конца массива.
ilt: это точно нет, я специально это отслеживал
ilt: 700 000 у меня там константа
ilt: 1 000 000 ставил
YurkovAS: о, так мало)
ilt: разницы не было
ilt: да мало
ilt: но цель заехать в легу на джаве )
YurkovAS: да, помню как сам сначала делал. постепенно ускорилось и упростилось.
amurushkin: 1000000 мало наверное
Uljahn: лега в крестиках - удобный предлог углубить свои познания в джаве
TTeaLL: не подскажете, что это значит
