Chat:Ru/2020-06-12

From CG community
Revision as of 11:23, 15 June 2021 by Chat Log (talk | contribs) (Created page with "<img src=/a/25714480415254> tutubalin: подбором константы пытаются исправить непригодную формулу <img src=/a/2111605585777...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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: ниче скоро все равно будет с дц компа работать

Default avatar.png TTeaLL: не подскажете, что это значит

Default avatar.png 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.

Default avatar.png TTeaLL: это ошибка или что?

amurushkin: очевидно же. код делает вывод до того как считает все входные данные

Default avatar.png 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: лега в крестиках - удобный предлог углубить свои познания в джаве