wlesavo: ееее, полностью восстановил поведение приведений, 100% точность предсказаний на всех тестах
Uljahn: :scream_cat:
YurkovAS: :yes:в нее не просто начать. думал ABCDE для движения UDLR(W), но не похоже. надо еще раз попытаться, на листочке карту порисовать...
Uljahn: да вроде для движения, просто порядок немного другой
Uljahn: насколько помню
YurkovAS: Uljahn <https://www.codingame.com/profile/2e4448c30d32bb44ca3ba3fa28756763885094> как твой 2048, больше не улучшается? до топ1 питона всего 1млн
Uljahn: пилю ещё
Uljahn: решил пойти по пути оффлайна
Uljahn: щас LUT профилирую, 65к комбинаций за полсекунды генерится
wlesavo: YurkovAS да там нюансов очень много
YurkovAS: могу подсказать хорошую фичу, возможно у тебя ее нет
Uljahn: у меня только антифичи и антипаттерны)
YurkovAS: глянул, нет LUT-ов, просто бим серч стандартный над двумя массивами
YurkovAS: в ней 2 фичи: одна оценка змейкой и есть еще одна нестандартная, которую хотел сообщить (ну для меня уж точно), которые заметно улучшают скор
Uljahn: а что за два массива?
YurkovAS: 2 массива для хранения состояний: текущие и новые. 2шт массивов достаточно, меняешь их местами, чтобы память лишняя не выделялась.
ну у меня так. через хип и аналогичные деревья не делал еще, а с массивами просто
Uljahn: ясно
Uljahn: а какой порядок размера массивов, чтобы выделение памяти играло роль?
YurkovAS: ну если каждые состояния хранить в новом массиве, то будет точно заметна просадна на выделение памяти.
а если переиспользуешь 2шт, то предвыделяешь заранее и лишних аллокаций не будет.
тут еще смотря как делать: некоторые в массив все новые состояния добавляют, потом сортируют и оставляют топ-N
Uljahn: в массиве состояния в страктах хранятся?
wlesavo: блин YurkovAS заинтриговал
YurkovAS: тоже смотря как делать, большой стракт будет долго сортироваться
Uljahn: wlesavo предлагал хэшировать скором
Uljahn: я запилил себе такое, сортирует быстро
YurkovAS: у меня в массиве хранится только topN и указатели - для быстрой пересортировки
wlesavo: не, это не моя идея была а магити вроде, но у меня тоже так, нейман и амуршкин сказали у них такой хеш плохо работает и много коллизий
Uljahn: в плюсах есть std::nth_element, можно без полной сортировки голову отбирать
YurkovAS: у меня сейчас тоже хеш только от скора double
wlesavo: блин теперь придется наверное нормальный поиск прикручивать какой-то к пакману, а то че зря чтоли делал идеальный предсказатель
Uljahn: а скор научился предсказывать?
MaksymSkorchenko: ууууу, перешел в пакмане в серебро.... а тут жопа, в хвосте )))
Uljahn: и ещё вопрос по 2048 - как хранить хистори)
wlesavo: Uljahn цель не ставил, но подозреваю что могу предсказать, там просто надо так и так зачищать уровень
Uljahn: в стейтах хранить жирно, надо как-то отдельно в дереве что ли
YurkovAS: Uljahn хистори - это же ходы? прямо в стейтах храню в видет массива байтов.
изначально всю память предвыделяю и потом больше нет новых аллокаций.
новый стейт делается во временной переменной, оценивается и если он лучший, тогда копируем из него в массив лучших
YurkovAS: навелосипедил как всегда
Uljahn: а, сразу навыделять памяти под максимальное число ходов?
Uljahn: но копировать же много придётся ближе к концу
YurkovAS: да, сразу под все выделяем: стейты, история ходов, временный стейт
Uljahn: фронт работ понятен, через пару месяцев отпишусь ))
YurkovAS: да там наверное и без этих велосипедов будет норм, просто так интереснее
Uljahn: угу, я пишу по 4 варианта каждой фичи и профилирую, мне так интереснее
YurkovAS: Uljahn после бимпоиска у тебя еще что-то есть?
Uljahn: нет
YurkovAS: понял, значит нет этой фичи
Uljahn: бимпоиск-то две строчки у меня
Uljahn: код-франкенштейн - ООП+ФП+numpy
Uljahn: даже в офлайне тормозит)
YurkovAS: давай добавим фичу одну?
Uljahn: я думал на глубину 1 потомков анализировать
Uljahn: и ещё графы прикрутить как в статье на хабре
Uljahn: но это в следующей жизни
Uljahn: YurkovAS: рассказывай, что за фича, wlesavo вон тоже вроде заинтриговался
YurkovAS: после бим поиска возвращать на 5-10 ходов меньше, всегда
wlesavo: а ну это понятно, у меня без этого впринципе не работало
Uljahn: это как?
Uljahn: чем это отличается от поиска с шириной луча - 5?
Uljahn: или я в этапах поиска не секу
Uljahn: ааааа
wlesavo: имеется ввиду что не весь найденый луч используется
Uljahn: историю возвращать меньше
Uljahn: магаити про бэктрекинг что-то упоминал, это что0то похожее
Uljahn: проблема в том, что в онлайне у меня питон находит 4-5 ходов ))
YurkovAS: и это число поподбирай, даже 1 заметно прибавляет
YurkovAS: всего 5 ходов) у меня порядка 100, на первом 1к+
Uljahn: вот я и думаю LUT впилить, должно стать пошустрее
Uljahn: ещё в офлайне с numba хочу попробовать профильнуть, да статью на форум накатать
YurkovAS: от ширины луча еще зависит, не думаю что у тебя там 500+
Uljahn: 50-
YurkovAS: да, заметная разница в скорости.
Uljahn: ну, код у меня сыроват, скорее пруф ов концепт, слепленный на коленке за выходные, зато ускорять интересно, мотивирует
Uljahn: ого, реально стало лучше с укороченной историей
YurkovAS: :yes:
wlesavo: top4 :scream:
Uljahn: поиск прикрутил?
wlesavo: не, костыль просто
YurkovAS: из пиджина смайлик не сработал, тут не показывается картинка
YurkovAS: так у него же был поиск МС, на бимсерч если только его поменять. по ПМ-ам к пакману он лучше
Uljahn: в 2048 постоянно таймят 1-2 валидатора, пока лимиты не зарежешь почти в нулину :(
735487: это у всех так. надо сабмитить до тех пор пока не повезет
Uljahn: хм, надо попробовать лимиты привязать к модели процессора, есть подозрение, что подсовывают глючные инстансы на 3ГГц с 16Мб кэша
YurkovAS: юзаю тайминги 750мс (1-ый ход) и 35мс (2+ ход)
YurkovAS: первый можно увеличить, а вот 2-ой тайминг уже редко с 40мс срабатывает
735487: и это не есть хорошо. я думаю что виноват сборщик мусора в рефери
YurkovAS: и в search race похожие тайминги
YurkovAS: и ксб часто таймит
735487: вот если в контесте будет тоже самое будет попадос
wlesavo: ого, у меня с 99мс работает
wlesavo: правда у меня и скор сильно ниже
735487: это в какой игре?
735487: время точно правильно замеряешь?
wlesavo: в 2048, да правильно, но у меня маленькая ширина и глубина достатончно
wlesavo: и в последнюю милисекунду я исключительно печатаю
wlesavo: ой, 99 я перепутал наверно, там же 49
wlesavo: в смысле одна милисекунда остается, чет с пакманом перепутал
735487: а ну тогда реально
