Chat:Ru/2022-01-18

From CG community
Jump to navigation Jump to search

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: ага, но мне пмы не особо помогают)