aangairbender: блин, интересные у вас разговоры, может тоже great escape пописать что-ли
aangairbender: тем временем зашел в бронзу в csb
aangairbender: с трудом)
Uljahn: :scream_cat:
aangairbender: да там писало что я топ1, но не выше босса в деревянной лиге, при том что 20/22 боев выиграл
aangairbender: 3 раза сабмитил, тот же результат, в итоге сдался, а через несколько часов написало что я прошел в бронзу
YurkovAS: csb :) там в обсуждениях игры есть ссылка на отличную статью Магуса
YurkovAS: и ссылки на стартеры есть, сделанные по его статье
YurkovAS: просто копируешь стартер, подправляешь оценочную и уже топ100 :)
aangairbender: та уже great escape начал)
aangairbender: там кстати поле так и останется 9х9 константное?
aangairbender: а то я топ 1 в дереве, босса не обошел)
YurkovAS: ясно, просто у меня много впечатлений осталось от этой игры, долго в нее экспериментировал
YurkovAS: да, всегда будет 9х9
aangairbender: окей, спасибо
wlesavo: YurkovAS а ты случайно топ8 позиций для стен не один раз выбираешь и потом просто в в поиске их проверяешь? у меня просто для каждого состояния выбираются лучшие, и что-то не могу представить как это быстро сделать, получается самая затратная часть
YurkovAS: не понял, для родительского состояния заполняю список всех возможных ходов с оценкой, потом его сортирую и оставляю топ8
wlesavo: ну то есть для каждого состояния
wlesavo: у меня этот кусок как-то грустно работает
YurkovAS: подсказка: ну не совсем для каждого
wlesavo: ну понятно, я тоже некоторые позиции быстро отбрасываю
YurkovAS: не не, тут на уровне алгоритма это сделано
YurkovAS: архитектуры
YurkovAS: всмысле когда iterative deeping depth = 2, то для depth = 1 это уже не делается. аналогично и для depth=3
wlesavo: ну вот да, я понимаю что можно это сильно оптимизировать, у меня сейчас worst case будет даелать порядка 200~300 bfs на каждое состояние
YurkovAS: так уже точно понятно :)
wlesavo: аа, это да, такое давно хочу реализовать, видимо надо
wlesavo: но проблема в том что у меня итераций углубления не так уж и много (
wlesavo: YurkovAS а, блин, переиспользование делалось в две строчки :smiley:
YurkovAS: если ты сделал как я думаю, то principal variation теперь легко сделать
YurkovAS: principal variation - лучший ход
YurkovAS: по aplha-beta
wlesavo: ну да кстати, тоже по сути 2-3 строчки, сортировка детей
YurkovAS: сортировка детей это не pv, т.к. какой-то из детей 2+ может быть лучшим на этой глубине
оценка то не всегда идеальная
и тогда след iterative deeping может не проверять лишних детей, а сначала проверить лучшего
Uljahn: осталось понять, что такое лучший ход по alpha-beta и по какому критерию сортируются дети
aangairbender: советую почитать статьи на эти темы на chessprogrammingwiki
aangairbender: https://www.chessprogramming.org/Principal_Variation
Uljahn: я думал, что сортировка детей просто улучшает эффективность альфа-бета отсечений
aangairbender: и другие статьи там тоже очень крутые
Uljahn: угу, известный ресурс
Uljahn: ещё я думал, что если мы детей сортировали на предыдущей глубине, то первый ребёнок будет PV, его мы пробуем первым
YurkovAS: давай проще: на каждой глубине строим список допустимых ходов, оцениваем их и оставляем топ10
YurkovAS: теперь разберем случай: depth=1, depthMax=5
YurkovAS: pv на depth=1 ведь не будет самым первым ходом, для depthMax=5
YurkovAS: когда мы перейдем на depthMax=6, то на depth=1 лучше сначала проверять pv ход
YurkovAS: т.е. это ход найденный минимаксом
Uljahn: для случая "оставляем топ10" - наверное да
Uljahn: это уже какой-то бимсёрч
YurkovAS: просто на каждой глубине надо запоминать какой в данной ситуации ход из топ10 лучший: по отсечению или просто max(alpha)
YurkovAS: бимсерч для 1 игрока, а тут 2 игрока
YurkovAS: ну минимакс классический, только с отсечениями
Uljahn: по идее, мы должны рассматривать всех детей на данной глубине, не отброшенных по альфа-бете
YurkovAS: ну ты можешь не оставлять топ10 ходов, а перебирать все, только вот на сколько глубоко дойдешь
и может оказаться, что лучше проверять только 10ходов у каждого
YurkovAS: это все зависит от игры
YurkovAS: как в ксб же не проверяют абсолютно все ходы
YurkovAS: для 360градусов и 0-200 скоростей
YurkovAS: *36градусов
Uljahn: это немного другое - дискретизация пространства действий, а топ10 - это грубый прунинг, который ломает альфа-бету
Uljahn: вся прелесть альфа-беты в том, что она строит дерево гарантированно не хуже обычного минимакса с полным перебором, это теоретически обосновано, чего про эвристику топ10 сказать нельзя
Uljahn: понятно, что хочется большей глубины, для чего нужен более агрессивный прунинг
Uljahn: но тогда гарантии теряются
YurkovAS: вот в ww как раз у меня нет прунинга такого, хотя у топ1 был в контесте. да и у других ребят тоже есть, т.к. видна очень большая разница моей глубины и их
Uljahn: тут же ещё оценка сильно влияет, иногда хорошая оценка важнее +1 глубины
wlesavo: Uljahn ну тут два стула, теоретическими гарантиями приходится жертвовать, тут вопрос не +1 глубины а +3-4, и это уже существенно
Uljahn: угу, компромисс между "брать все по альфа-бете и получить точное решение" и "брать топ1 и получить +100 глубины"
Uljahn: +1 я относительно оценки приводил
wlesavo: ну да. просто топ10 например лучше чем просто эвристики, например брать стены в начале и в конце минимального пути итп, более гибко получается
YurkovAS: похоже и бимсерч всетаки да 2х игроков будет работать
YurkovAS: каждый максимизирует себя, ну оставлять только больше состояний и сохранить наш ход
wlesavo: ну учитывая что в топе вообще жадные поиски с очень специфичными оценочными, бимсерч будет работать, но нужно очень постараться
YurkovAS: всмысле и противник там тоже будет: сначала мы, потом он, потом мы и т.д.
каждый максимизирует себя
YurkovAS: правда скорее всего быстро вымоются разные первые ходы и он будет жаднее минимакса
YurkovAS: надо будет проверить на досуге, с противником
wlesavo: вообще бимсерч с противником крайне неочевидная штука
aangairbender: из бронзы в серебро 2 часа ждать чтоб перевели, жесть
Uljahn: из голды в легу 6 часов
aangairbender: и зачем такие правила....
Uljahn: наверное, чтобы масс-промоушенов не было, когда бот из дерева летит в голду на -3Vel, проталкивая по пути сотни ботов
aangairbender: ой то не 2 часа ждать, то в 2 часа перекинет (30 минут ждать), тогда норм
aangairbender: немного правда смущает что мне не написало типа "promotion to silver league in ..."
aangairbender: я просто в таблице выше босса и всё
aangairbender: вот в csb так же было
Uljahn: главное, чтобы цвет аватарки сменился
aangairbender: это как?
aangairbender: пока что бронзового цвета, если ты о квадратике возле аватарки
Uljahn: судя по цвету, ты в бронзе
Uljahn: ага
aangairbender: ладно, через 10 минут узнаем перекинет или нет
Uljahn: когда выше босса закидывает, то цвет меняется на цвет следующей лиги, вроде
Uljahn: не помню, как в гоночках
aangairbender: а есть лимит на кол-во сабмитов?
Uljahn: ещё всплывающее окно должно появиться с экспой
Uljahn: 25 сабмитов за 5 часов или около того
Uljahn: один сабмит в 12 минут
Uljahn: в среднем
aangairbender: я вот думаю еще раз сабмитнуть посмотреть может что-то изменится
TheCrucial: Uljahn как то проводили какой то контест в 2ух версиях. 1 - спринт - на 3 часа закодить. и там со своими призами. и далее эта же игра но уже на пару недель. не знаешь, будет и такое повторяться?
Uljahn: спринт + марафон, как в LoCaM? не знаю
Uljahn: вообще админы сейчас решают, куда двигаться, полная неопределённость с контестами
Uljahn: хотят попробовать мелкие еженедельные ивенты, через несколько недель
aangairbender: а формат весеннего неизвестен пока?
TheCrucial: а откуда народ натягали? раньше, когда только контесты работали мне кажется гораздо меньше людей было. сейчас в клеши очень много играет
aangairbender: сабмитнул в итоге
aangairbender: стало норм
Uljahn: TheCrucial: так переориентировались на нубов, потому и клэши стали популярнее, чем мульти
Uljahn: большинство старожилов свалило, сложив модераторские полномочия
Uljahn: год или два назад тут опрос проводили, и там был вопрос: "Что для вас важнее всего в контестах", и можно было дать только один вариант
Uljahn: результаты были такие: "only 1.64% of the respondants said « Compete against other coders » but 33% reply « Improve my skills by practicing » and 17% « Just have fun while coding »"
Uljahn: 1.64%, Карл!
Uljahn: с тех пор бот контесты задвигают на задний план
Uljahn: и пытаются сделать платформу более дружелюбной для новичков
Uljahn: типа нужен приток людей, на качество пофиг
Uljahn: Coding Escape из той же серии, ну и сретификации на уровне клэшей
Uljahn: *сертификации
Uljahn: хорошо, хоть мульти не прикрыли ещё, а то бы тоже пришлось сваливать
Uljahn: хмм, на самом деле вопрос был «What do you expect from CodinGame?», память подвела
wlesavo: с горем пополам добрался куда-то в районе 40х мест, но чето не получается качественно улучшить, много идей перепробовал уже
TheCrucial: ну все кроме 1% не могут себе поставить цель выиграть контест. просто нереально с дедами соравноваться
wlesavo: TheCrucial а ты к YurkovAS в профиль зайди, он с дедами оч неплохо соревнуется)
YurkovAS: по их же ПМ-ам :)
wlesavo: ага, но мне пмы не особо помогают)
