Chat:Ru/2021-02-20

From CG community
Revision as of 11:35, 15 June 2021 by Chat Log (talk | contribs) (Created page with "<img src=/a/4034881109815> magaiti: о, кто-то сокобан решил. признавайтесь, почему не на плюсах <img src=/a/2111605585777> 7354...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

magaiti: о, кто-то сокобан решил. признавайтесь, почему не на плюсах

735487: походу подлодки всех научили детектить противника в тумане :) и в пакманах подобное юзали. и в WW вон тоже подходит

YurkovAS: magaiti я решил, теперь работает меньше 1сек на любом тесте. спасибо за подсказку!

input.txt: скиньте реплей 2-1

input.txt: не пойму почему полный перебор пропускает решение, если я ничего не отсекаю

input.txt: а только складываю в сет посещенные состояния

input.txt: *2-4

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

YurkovAS: 2-1 https://www.codingame.com/replay/529811600

YurkovAS: input.txt 2-4 https://www.codingame.com/share-replay/529811645

input.txt: спс

YurkovAS: может ошибка в фукциях для сетов: сравнения или hashCode+equals

YurkovAS: смотря какой юзаешь

input.txt: вряд ли, я оба сета пробовал

YurkovAS: а функции эти реализовал сам? может дефолтные не так работают с твоим классом.

input.txt: да, дефолтные никак не работают же

input.txt: остается генерация возможных ходов. но там негде ошибиться

magaiti: YurkovAS, на каком языке решил сокобан?

magaiti: я в С++ только свои решения вижу :(

YurkovAS: magaiti на с++, да я не публиковал.

magaiti: input.txt я бы на твоем месте перепроверил как сет состояний работает, может баг в функции сравнения состояний

input.txt: возможно

input.txt: из начала до 65 хода с реплея не доходит

magaiti: YurkovAS ах ты редиска

input.txt: а с 63 доходит

miklla: ладно, ща попробую ваш сокобан решить, когда решал на телефоне такие головоломки :)

miklla: когда-то*

YurkovAS: miklla у тебя в wondev woman же минимакс? ты используешь zobrist + TT?

miklla: у меня там альфа-бета + навороты + ТТ

YurkovAS: у тебя случайно не ссылки на хорошую доку по ТТ? вообще ни чего не понимаю про это и про зобрист

YurkovAS: на русском :)

miklla: причём там 2 хеш-таблицы, одна на позиции, другая на оценки, это было неожиданно :)

YurkovAS: оно же там даст ускорение?

miklla: ага

miklla: ну про зобриста легко быстро сказать

YurkovAS: ох, а как его там прикрутить - хз

miklla: позиция - это массив высот всех клеток и 4 точки

YurkovAS: может вместо него просто состояние все как ключ юзать

miklla: пусть площадь S

YurkovAS: а скоры и позиции юнитов?

miklla: делаешь массив S х (4 или 5) на высоты и заполняешь rand()

YurkovAS: и этот зобрист потом юзать как ключ в хеш-мапе? которую называют ТТ

miklla: если пока отбросить 4 точки, то первая цель, чтобы хеш позиции был xor всех zob[][] по каждой клетке нужной высоты

miklla: тогда когда меняется высота одной клетке, то xor-ишь с предыдущей высотой и новой, сразу получаешь новый hash из старого всего за 2 действия

miklla: хотя S там немаленькое, но от него эта сложность не зависит

YurkovAS: ну там же надо еще юзера передвинуть - т.е. его отнять?

YurkovAS: и скор же еще отнять и прибавить - когда увеличится

YurkovAS: мне кажется и без зобриста тоже будет профит

miklla: да, hash использовать в TT, только надо его взять по модулю размера хеш-таблицы

YurkovAS: только я не понимаю это ТТ

miklla: остаётся 4 точки

miklla: там пможно по-разному

YurkovAS: можешь про ТТ рассказать?

miklla: например если всего <256 координат, то можно в 4 байта запихать эти координаты - это будет из хеш, затем его xor-нуть с хешем поля

miklla: но можно и в старой моде сделать zob[][] 4хS, напихать туда рандомных чисел, и действовать аналогично

YurkovAS: координат там 7х7х5

miklla: х5? по-моему там высота фишки соответствует высоте клетки

miklla: так что 7х7

YurkovAS: в каждой ячейке по 5 значений - 5-я пустота

YurkovAS: можешь про ТТ рассказать? зобрист я примерно понимаю

YurkovAS: в общем, про ТТ эти

Uljahn: а альфа-бету уже понял?

YurkovAS: нет

Uljahn: может тогда рано про ТТ

miklla: в каждой позиции лишь одно значение, оно уже задано поле, никаких х5

miklla: да, лучше сначала альфу-бету без ТТ

YurkovAS: т.е. ты отсечения без подсматривания сможешь написать?

YurkovAS: альфа беты

miklla: да

YurkovAS: т.к. понимаешь

YurkovAS: ох. я там долго же буду тупить...

miklla: ТТ лишь нужно, когда в дереве позиций одна позиция достигается несколькими способами

YurkovAS: и для iterative deeping?

YurkovAS: ускоряет же вроде

miklla: и ничего ужасного не произойдёт, если без ТТ у тебя образуются копии этой позиции, просто больше вычислений будет, но альфа-бета без ТТ уже куда круче миника

YurkovAS: ну так по примеру то сделал просто не понимаю как оно работает

Uljahn: https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning - я по этой статье разбирался, там вроде иллюстрации довольно понятные

YurkovAS: а хочется дальше и не понятно...

miklla: iterative deeping полезно в альфа-бете тем, что ходы уже заранее упорядочить

miklla: можно

YurkovAS: но у меня то не упорядочены сейчас

YurkovAS: только по своей оценочной

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

miklla: касательно WW я помню, что там огромную роль играет детект противника

YurkovAS: как я понял, когда вызывается eval - надо заносить его результат в ТТ

miklla: прям колоссальную

YurkovAS: детектор есть

miklla: хороший детект добавляет минимум 6 баллов рейта

YurkovAS: я в топ35

miklla: и его не очень просто написать

YurkovAS: но охото улучшиться, особенно в алгоритмах этих

YurkovAS: ладно, будут тупить над отсечениями альфа-беты

YurkovAS: спасибо!

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

YurkovAS: в ПМ-ах пишут про эти зобристы, ТТ и прочее а сам не понимаю...

miklla: твоя цель: понять эти самые альфа-беты, зобристы, ТТ, ....

Uljahn: это свистелки, основа - a-b с ID (чтобы anytime было)

miklla: решение:

YurkovAS: надо тогда еще и детектор поизучать - может можно улучшить

miklla: понимать по одному шагу в том порядке, в каком мы тебе говорим: альфа-бета, оптимизации альфа-беты, ТТ + зобрист, ...

miklla: а не всё сразу

Uljahn: согласен

YurkovAS: понял, так и сделаю спасибо!

miklla: лично у меня детект чуть больше 100 строчек занимает

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

miklla: если что, у меня там 2129 строчек :)

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

YurkovAS: да и когда у противника нет ходов, то мой берет любой ход, т.к. там возвращается одинаковый скор

YurkovAS: надо бимсерч чтоли добавлять туда но это редкость, в основном меня первого убивают

miklla: я не знаю, что это, но эта часть кода в WW мне нравится :)

miklla: const bool access_change_from[4][5] = {{false, false, true, false, false}, {false, false, false, true, false}, http://chat.codingame.com/pastebin/d84df449-c35e-43d7-9c1f-ba2deb005101

miklla: а, 8х8 - это куда можно пихнуть :)

YurkovAS: ну можно заменить на битовые маски

miklla: я не пойму, в сокобане он пишет timeout на любую ошибку? ну не может быть, что 10 сек прошло

735487: да это в плюсах во многих пазлах так

miklla: печалька

miklla: ну бин-поиском по коду нашёл нужное место :)

miklla: блин, жёсткий бектрекинг в этом сокобане

YurkovAS: классная задачка, очень понравилась. особенно, что в процессе получалось находить улучшения, жаль что не все.

miklla: мда, 2 часа дебагал бектрекинг, наконец всё исправил, сразу решились все кейсы без единой оптимизации

YurkovAS: что за бэктрегинг?

YurkovAS: список ходов?

YurkovAS: в каждом состоянии

miklla: да, по найденному решению во внутренних структурах восстановить собственно какие ходы надо делать

miklla: я даже не использовал то, что в угол задвигать коробки не стоит

YurkovAS: ого, не проверял без этой фичи

YurkovAS: не будешь публиковать? магаити опубликовал свое - наверное у тебя так же сделан бектрекинг? через мапу

miklla: всего 200 строчек, неплохо

miklla: у меня 425

miklla: у меня сильно навороченней решение

YurkovAS: я прямо в состоянии вектор засунул

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

miklla: ну хеш-таблица у меня есть

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

miklla: ща замерю время на 30ом кейсе

YurkovAS: 3-4 и 3-5 вроде самые медленные

miklla: у меня больше всего позиций сгенерировалось в 3-10, ну все эти 3 посмотрю

YurkovAS: 260-310мс у меня в 3-10 3 раза запускал

YurkovAS: у тебя бфс ?

miklla: 233-297 на 3-10

miklla: без оптимизации с углами

miklla: ща углы сделаю

miklla: у меня полный перебор

miklla: ну он похож на бфс, но хз

YurkovAS: ну не бимсерч

miklla: нет функции оценки, полный перебор же

YurkovAS: 5.5-6.5 сек с углама

YurkovAS: гораздо медленнее

YurkovAS: что же ты там такое запрогал...

miklla: я сразу компоненты связности целиком обрабатываю

YurkovAS: ох, типа как в D&B

miklla: ну я тут проще, чем там сделал

YurkovAS: было бы интересно посмотреть и понять. а если тут пойму, то смогу для D&B применить?

miklla: не вижу связи

miklla: тут другое

YurkovAS: miklla хочешь в конкурсе поучатсвовать? что-то типа раика, вчера начался, хотя и называется highloadcup, но там и знания ИИ нужны

YurkovAS: там денежные призы и топ50 футболок

YurkovAS: https://cups.mail.ru/ru/contests/goldrush

miklla: 15-19 мс с оптимизацией с углами

miklla: я могу ещё ускорить

YurkovAS: ого, очень круто!

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

YurkovAS: ты определяешь мертвые зоны?

miklla: ну в углы коробки не пихать

YurkovAS: да копоненты связанности

YurkovAS: по простому, "как для детей" :)

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

miklla: мёртвые зоны*

YurkovAS: компоненты связанности = мертвые зоны?

miklla: нет

miklla: остановился в сокобане на самом большом рантайме 9-14 мс на тесте 3-5, на остальных ещё быстрее