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