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, на остальных ещё быстрее
