Chat:Ru/2022-06-11
YurkovAS: @tomatoes сделал в тетрисе такой же алгоритм как у тебя: стабильно в топ20 заходит немного оценочную поправил через брутал тесты
YurkovAS: думал ускорить: типа vector-ы медленные, а бинарный поиск в итоге гораздо медленнее работает, чем куча :slight_smile:
YurkovAS: код очень простой в итоге получился, по сравнению с костылями мктс-а (буду изучать еще) изи топ20 игра
wlesavo: надо будет попробовать может, а какая у тебя глубина там?
YurkovAS: а там больше 8 ходов невозможно сделать
wlesavo: полная глубина получается и полный перебор?
YurkovAS: весь диапазон проходит в итоге, с этим алгоритмом
YurkovAS: не полный алгоритм, как раз
YurkovAS: не полный перебор
wlesavo: с прунингом или как?
YurkovAS: очередь с приоритетами + дисконт
wlesavo: а понял
YurkovAS: и он тогда выгребает и в глубину тоже
YurkovAS: гениальный алгоритм! спасибо @tomatoes!
YurkovAS: полный перебор на сколько помню успевал только глубину 3-4
wlesavo: а тут очередь как строится по детям получается?
YurkovAS: да
wlesavo: типа dfs c оценкой детей?
wlesavo: или там хитрая общая очередь какая-то
wlesavo: что-то идею не совсем понял таки
YurkovAS: одна куча с состояниями отосортированы по скору борды это все без примененного комбо
YurkovAS: скор борды с дисконтом! без этого не работает
wlesavo: все состояния в кототрые можно попасть?
wlesavo: блин все равно не понимаю что алгоритм делает то
YurkovAS: выгребаем из него, делаем новые состояния те что с комбо - откладываю в общую статистику когда время кончится, пробегаю по статистке и выбираю лучшее комбо тоже с дисконтом
wlesavo: а, так понял
wlesavo: интересно
YurkovAS: алгоритм делает как бфс только у каждой записи есть скор по нему все данные отсортированны
wlesavo: ну то естьраскрывается текущее состояние и обратно в кучу складывается
YurkovAS: т.к. скор с дисконтом, то игода лучшее состояние из глубины 2, а иногда из глубины 5 и он получается постепенно и в глубь и в ширину исследует
wlesavo: да прикольно, в целом понятно почему это может работать
YurkovAS: - текущее выкидывается - раскрываемф
wlesavo: а противник там учитывается как-то?
YurkovAS: - те что с комбо в статистику - те что без, оцениваем и в кучу на дальнейшее исследование
YurkovAS: да, противник тут нужен
YurkovAS: а то ты выберешь ход далекий, а он может тебя раньше сильно задамажить т.е. тогда чуть похуже комбо применить. ну или контр атаку заранее (оно у меня почти не работает, но есть)
YurkovAS: на счет статистики этой - вроде другие так делали с МС изначально так сделал, т.к. он у меня вообще не работал долго костылил с мктс-ом и к этому пришел
YurkovAS: + битборды прикрутить, типа как в great escape-e
YurkovAS: а обнаружение комбо, быстрее работает тот алгоритм fast connected components (в 2-3 раза) против быстрого бфс-а
YurkovAS: проспойлерил - сейчас тебе будет не интересно делать)
wlesavo: ну я пока сомневаюсь, про кучу интересный алгоритм, ради него может попробую, но это уже после контеста
wlesavo: правда в контесте почти не будет времени поучаствовать
wlesavo: надеюсь хоть пару дней смогу
YurkovAS: запульнул чокудай - тоже норм должно быть