Chat:Ru/2022-06-11

From CG community
Jump to navigation Jump to search

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: запульнул чокудай - тоже норм должно быть