ilt: на два хода или на два дня?
Uljahn: Automaton2000: на два дня, на два дня вы забудьте про меня
Automaton2000: А сколько у тебя в крестиках осталось?
miklla: ilt дня
Hamibar: Работает даже грубый обсчет(учитывая только текущие деревья) на несколько дней вперед.
ilt: у меня тяжелая оценка получилась
ilt: когда много вариантов таймауты получаются
miklla: у меня оценка 40 мс считается на старте игры, но зато сразу от всех позиций одной глубины :)
miklla: могу от одной, а могу от тысячи, время будет почти одинаковым, необычная ситуация :)
Xyze: чет не прет у меня оценка
Xyze: симу проверил насколько мог, ну вроде всё по ней хорошо
Xyze: как минимум на отбитые оценки реагирует бот сразу
Xyze: а вот что-то нормальное и стабильное вообще никак
mykeich: И какой сейчас приоритетный алгоритм?
Xyze: в плане сам поиск?
mykeich: угу
Xyze: я пока вообще сильно тут не думал, у меня обычный монтекарло
Xyze: я всегда в начале чекаю симу на простой оценке и монтекарло
Xyze: потенциально он наверное не лучше бим серча или что там щас модно
Xyze: генетики сюда вообще не пихнуть
Xyze: а минимакс - времени не хватит
Xyze: но я стопанулся на самом начале ))
Xyze: не могу побить своего бота на 600 месте =(
mykeich: Я только дорвался. В выходные на даче пропадал. Зная себя стал осторожно выбирать алгоритм, чтоб два раза не переписывать код.
Xyze: у меня монте в 50 строк
Xyze: даже переписывать то ничего не придется )
miklla: у меня 1.2к строк, больше половины из них на оценку
miklla: пока что гляжу на 1 день вперёд, но надо глядеть на 2
Xyze: офигеть
Xyze: 600 строк оценки?
miklla: это необычная оценка, но в определённом смысле это оценка
Xyze: а какой поиск?
miklla: сначала гляжу на 1 ход вперёд за противника, рассчитываю его линию поведения против куклы, потом аналогично от себя
Xyze: без противника пробовал или сразу с ним делал?
miklla: пробовал, но давно, тогда с противником было немного лучше, могу, конечно, сейчас эксперимент поставить
Xyze: понял, спс
Xyze: ну буду пытаться что-то сделать
Hamibar: Тут похоже надо будет не симу оптимизировать, а оценку :grinning:
miklla: да, я долго дебагал и оптимизировал "оценку", вообще было запарно
BorisZ: можно вместо оценки текущей позиции доигрывать несколько раз до конца
Hamibar: Рандомно доигрывать?
BorisZ: рандомно или вейтом или по простым правилам или комбинированно )
BorisZ: все ж оценка текущей позиции, не финальной - штука сложная
Hamibar: Мне кажется тут ветвистость слишком большая для рандома. А вот простой оценкой наверное можно.
Hamibar: Но в любом случае ты заменяешь оценку позиции на оценку каких-то отдельных ходов.
wlesavo: ух, тоже ток вернулся, ладно хоть мой три строчки оценки закинуло в серебро
Hamibar: По строчке на лигу)
wlesavo: )) ну я думаю таки попытаюсь ченить на плюсах написать за неделю, еще бы с работой разгребстись
CyberEcho: > можно вместо оценки текущей позиции доигрывать несколько раз до конца
И работает этот подход?
У меня получается абсолютно нестабильный результат.
Uljahn: стабильность зависит от количества доигрышей, по паре десятков ничего не определишь, нужны десятки тысяч хотя бы
BorisZ: мктс же так работает
BorisZ: и для большого числа игр лучше других подходов
Uljahn: угу, мктс, монте карло, ucb1 так работают, разница только в том, строится ли дерево, или только статистики рута учитываются
BorisZ: ну в общем можно полагаться на статистику либо на свою оценку - два разных подхода
Uljahn: или натренить нейронку, чтоб она оценивала
Uljahn: в принципе, это тоже статистика
CyberEcho: То есть, чтобы оценить одну позицию, нужно 1000+ раз сыграть из нее до конца?
BorisZ: в общем да, мы хотим сравнить два хода, делаем первый, доигрываем много раз до конца случайно, записываем результат, повторяем для второго
BorisZ: у лучшего хода будет статистика лучше
BorisZ: но конечно это не всегда работает или не всегда лучше чем другие подходы
TheCrucial: а не лучше ли рассмотреть на глубину k (сколько успеваешь) все ходы, а доиграть из каждого по простой стратегии в этой игре?
BorisZ: да фиг знает, может и лучше, кто ж знает
Uljahn: в общаке вон бимсёрч пиарят
Uljahn: рассматривать топ-k ходов с хорошей оценкой
BorisZ: ну все в оценку опять упирается
Uljahn: а где не упирается? :)
BorisZ: с доигрыванием - не упирается, считаешь очки да и все )
Hamibar: С доигрыванием тоже упирается. Ну по крайней мере если mcts пилить
Uljahn: с доигрыванием трудно определить доверительный интервал оценки, т.е. насчитали чего-то, а в реальности может всё наоборот получиться
Uljahn: эффект горизонта, оптимистичность прогнозов, вот это всё
Uljahn: т.е. против рандомного противника может и ок
Uljahn: в дискорде кто-то написал, что ГА юзает
BorisZ: во кстати надо попробовать, га легко запилить )
BorisZ: хотя тоже оценка нужна
Uljahn: ГА в чём-то подобен bemsearch, тоже популяция ограничена
Uljahn: *beamsearch
mykeich: А какое ограничение на расстояние для seed?
Beard: высота родителя
mykeich: Спасибо.
Uljahn: полконтеста прошло - пора читать правила, Automaton2000
Automaton2000: и как ты это делаешь
mykeich: ну я слепой наверное:) где цена grow для жёлудя?
Uljahn: в разделе Seed action
Sbergeif: http://chat.codingame.com/pastebin/0e1371bb-f8f5-4f4e-9f22-951968e20190
Uljahn: а, grow
mykeich: смотрю в книгу вижу фигу. спасибр
Uljahn: в разделе Grow actions тогда
YurkovAS: почему-то призов нет, только футболки
Uljahn: :scream_cat:
Uljahn: а футболки - уже не приз? тут некоторые только ради футболок участвуют
Beard: тут бы в топ50 попасть, какие футболки :D
YurkovAS: ну странно, недавно за мелкий левый контест давали PS5
YurkovAS: так то понятно что футболку почти нереально выйграть...
Uljahn: видимо, спонсоры были
Uljahn: зато CodingPoints дадут
mykeich: вот будет спонсор контекста мясокомбинат, пришлют почтой мясо
YurkovAS: это да, ради них и делаю - я статюга :)
Uljahn: блин, как вы в сильвер на трёх строчках выходите? :thinking:
Sbergeif: на каком языке 3 строчек достаточно?
Sbergeif: а, ну хотя в ботом сильвера можно, да
Sbergeif: число деревьев, число деревьев роста 3 и все
wlesavo: Uljahn ну у меня не прямо три строчки, три функции для эвала разных действий, каждая на несколько строчек, но там по сути return score
Uljahn: и кубические координаты используются?
Uljahn: так лень в кораблики лезть за ними, проще контест дропнуть :)
BorisZ: не, тут хексы вобще ни при делах
BorisZ: граф готовый, ребра упорядочены по сторонам света
Beard: хексы можно и захардкодить
BorisZ: вначале считаешь все тени и все площади посадки
BorisZ: грубо говоря массив 37х6х3 - тени, 37х3 - посадка
BorisZ: больше ничего не надо
BorisZ: richness можно не хранить - это функция от номера ячейки )
Uljahn: тени - это каждая потенциальная тень для хекса, а посадки x3 - что значит?
BorisZ: для каждой ячейки массив из 3х сетов например - для длин 1 2 3
Uljahn: я уже захардкодил "ход конём" для каждого хекса на расстоянии 2, надо дальше пилить, значит
BorisZ: для 0 будет [range(1,7), range(1,19), range(1,37)]
BookSaver: у меня без теней, на следующих правилах - рубить дерева на самых богатых почвах, если деревьев размера 3 больше четырех, рубить на сколько хватит очков в последние дни.
Растить сначала 2, потом 1, потом 0, преимущество у богатой почвы.
Сажать ходом коня (захардкожены варианты для каждой клетки) преимущественно на богатую почву, если на карте нет семян.
Все.
Uljahn: почти как у меня, спасибо
Sbergeif: мне кажется проще написать оптимизацию посадки исходя из теней (из-за нее ход коня выгоден), чем его хардкодить
Uljahn: проще выучить плюсы и писать симу, угу
Sbergeif: Симу писать сложно )
BookSaver: Я вчера просчитывал все возможные ситуации расположения деревьев на доске, тени, солнышки за 6 ходов.
У меня на 14 деревьев час ушел. И максимальная по солнышкам конфигурация слабо применима в реальной игре.
BorisZ: не, писать то легко, трудно чтоб она без багов была )
Sbergeif: у меня настойчиво сваливается в ситуацию, когда на 20 ходе 7 деревьев, она за ход их всех вырубает и сидит радостно, позволяя сопернику делать что угодно (
BookSaver: А то, что получается буквой Г, получает только половину от максимально возможных солнышек, если считать по числу деревьев.
Uljahn: значит, не надо рубить то, что затенит соперника?
Sbergeif: нужен баланс какой-то. сколько солнышек не получает соперник за 6 ходов, сколько недополучаешь ты из-за самотени
BorisZ: Sbergeif можно симуляцию костылями подпирать - не давать на входе ходы, которые явно неправильные
tomatoes: а в сильвер обычно поменьше же народу пускали? :eyes:
Uljahn: около 40% обычно
Uljahn: просто народу много в этот раз
Uljahn: мой прогноз - в голду 150 сразу возьмут, и 15 в легу
tomatoes: у меня по воспоминаниям что-то вроде 500-100-10 пускали
Uljahn: сложность боссов так подкручивают, чтобы под конец в леге было около сотни
Uljahn: спасибо чатику, закатываюсь в сильвер :tada:
Uljahn: отключил посадку в радиусе 1, оставил только ходом коня
BorisZ: Uljahn :thumbsup:
BorisZ: это только како-го-то хода справедливо, потом то все равно приходится сажать
Uljahn: а там уже соседи пересекаются, и конь одного будет в радиусе 1 другого, наверное
BorisZ: можно наверное каждой ячейке посчитать свой рейтинг посадки - сложить количество теней от своих деревьев, которые туда падают
BorisZ: это нормальное приближение будет
Sbergeif: угу
BorisZ: вражеские уже вроде решили что не считаются, мы -их. они - нас
Sbergeif: @BorisZ а ты врагов считаешь?
BorisZ: только когда доигрываю случайными ходами
BorisZ: это следующий этап)
BorisZ: я все никак не могу поверить, что у меня все правильно считается
BorisZ: без костылей совсем плохо играет
Sbergeif: а у меня на багах все держится ( без багов 150, с багами 250-300. что-то я недопонимаю или заходил совсем непавильно
Sbergeif: наоборот места
BorisZ: да, у меня такая же фигня была в точности
BorisZ: с ошибкой играл лучше чем без нее
Sbergeif: хоть бы понять как ошибка влияет, понятно было бы что с этим делать. а так от нее эффект совсем неочевидный
BorisZ: и до сих пор не могу понять почему (
BorisZ: у меня был перепутан порядок расчета стоимости апгрейда - сначала счетчики деревьев обновлял, потом считал стоимость
BorisZ: в результате иногда солнышки уходили в минус )
BorisZ: мнимые солнышки )
Sbergeif: а у меня ошибка по сути приводит к тому, что число дней без учета солнышке не позволяет дорастить и дорубить его весь
Sbergeif: и почему-то с этой эвристикой сильно лучше. даже в ide.
Sbergeif: тьфу. нельзя сажать, если дней дорастить не хватает - такая ошибка
Sbergeif: все, надо бросать и отдыхать
BorisZ: пока единственный логичный вывод из этой странности - то что все мои расчеты это просто фигня и ни на что не влияют особо
BorisZ: это меня параллизует и не дает двигаться дальше
BorisZ: что за дом можно построить на гнилом фундаменте, скажи Automaton2000?
Automaton2000: еще не факт что правильно
Uljahn: я почему-то думал, что солнышки на другой день не переносятся, и в правилах не нашёл
BorisZ: стопудов переносятся, у меня какая-то из версий под конец 100+ солнца накапливала
Uljahn: да это понятно, по реплеям догадался
Xyze: как вы понаходили свои баги?
Xyze: у меня в первый раз кажется всё наоборот, багов как будто нет, а не играет
Xyze: хз как это всё оценивать
CyberEcho: Аналогично, багов не видно, а скоро из топ-1000 вылечу :grinning:
Xyze: с этой оценкой голову сломать можно
Xyze: по отдельности бот максит всё, что я попрошу
Xyze: а вместе все параметры - и он сразу дичь творит
Sbergeif: а что, с солнышками не удается? я Макс солнышки, очки считаю как 3 солнышка
Xyze: если его вообще не просить сажать деревья, то он просто ждет
Xyze: ну мб парочку посадит
Sbergeif: мне кажется, если максишь солнышки, все должно получаться автомагически
Xyze: а дальше потери не отбиваются
Xyze: это насколько глубоко надо симить чтобы он понял?
BorisZ: асертами обложиться помогает - чтоб вылетал сразу как дичь какая-то происходит
Sbergeif: я до конца дней симлю, но чем дальше, тем жаднее.
BorisZ: солнышки в минус - исклочение, садим на занятую - тоже - сколько фантазия позволит
Xyze: Sbergeif ты битсетовый читак?))
Sbergeif: тип того. хешовый
Xyze: щас так лень опять париться с хешами, особенно после зелий
Xyze: но всё равно получается ты там слегка фильтруешь массив ходов, верно?
Xyze: а то задохнется
Sbergeif: да, я сиды почти не перебираю. и вот это основная слабость
Sbergeif: то есть для них Сима в статическом окружении
Sbergeif: не знаю как засимить посадку
Xyze: чет я щас вообще того, всё
Xyze: чисто по приколу разшешил доигрывать до конца
Xyze: ну думаю - прагмы надо
Xyze: и стал таймаутится
Xyze: это как
Xyze: без них норм, с прагмами вылет
Sbergeif: ошибка может, лезет за границы, за которые дебаг не дает
Xyze: может
Xyze: ну это уже интереснее
Xyze: мне не нравится, памагити =(
bbrvi2008: Какой вы пазл решаете?
Xyze: контест
Xyze: Spring Challenge 2021
Xyze: на главной там баннер должен быть
bbrvi2008: Спасибо)
Xyze: как будто парочка таких нефиговых утечек памяти
Xyze: Sbergeif супер важный вопрос
Xyze: если ты считаешь всё в солнце, и твои очки помножаются на 3 для перевода в солнце
Xyze: что им движет, чтобы реально собирать деревья?
Xyze: как мне кажется - только слишком высокая цена апгрейда дерева
Sbergeif: так мы получаем очки. очков обычно больше за счет nutrients
Xyze: окей, допустим, но почему он тогда не собирает сразу первое дерево?
Sbergeif: когда вырубка дерева не дает очков больше, чем потраченные солнца + солнца, которые мы вероятно сможем заработать (как среднее по Симе)
Sbergeif: ну собирает иногда, если с топом играешь и в блокаду посадили
Xyze: блин, хотел я по простому, и нифига не получилось
Xyze: не люблю сразу думать там много
Xyze: так*
Sbergeif: ну смотри, сначала до фига nutrients, но и по 3 солнышка за ход, пока не в тени зарабатываешь
Sbergeif: ты оцениваешь, что у тебя 7.3 хода в среднем до того, как посадят в тень
Sbergeif: это 22 солнышка заработанных. то есть nutrients + бонус за сруб должно быть больше 22+4
Sbergeif: что-то я очень путано объясняю, да?
Sbergeif: а, все, я понял твой вопрос. да, у меня вычитается солнышки, которые я отнимаю у врага
Sbergeif: поэтому не выгодно быстро рубить
Xyze: ага, понял спс )
Xyze: я просто пытался сделать похожее
Xyze: и он как бы рашил сбор дерева
Xyze: и сидит радуется
Xyze: а получается и оценку ты считаешь каждый день +-?
Sbergeif: не понял вопрос
Xyze: оценка игры
Xyze: в конце игры
Xyze: или 24 раза
Xyze: ну грубо говоря
Sbergeif: вообще каждый раунд пересчитываю
Sbergeif: есть часть, которая не пересчитывается, если все идет по просчитанному плану, есть поверх динамическая штука
Sbergeif: блин, чет сложно
Sbergeif: наверняка я тут где-то тоже лажаю
Sbergeif: каждый раунд топ ходов пересчитываю, чем слабее страта противника, тем дольше считает )
BookSaver: Xyze пытается уточнить, просчитываешь ли ты симу до 24 дня, и считаешь солнышки на 24 день, или только на 1 день вперед просчитываешь
Sbergeif: я до конца просчитываю, да, но сиды хитрым образом
Sbergeif: каждый раунд заново, но не пересчитываю то что посчитал уже
Sbergeif: если совпало, то отлично, если нет, снова считать приходится
Xyze: не, я немного не об этом
Xyze: у сим есть такая фича, что им не сильно важно, когда они максимизируют счет
Xyze: с начала середине или конце
Xyze: если просто считать оценку только в конце, твою последовательность могут сломать по ходу игры
Xyze: для этого делают что-то вроде
score += moveScore *(-0.99)^day
Sbergeif: я пробовал только 6 ходов, это выглядит логично, но не работает
Xyze: без минуса
Xyze: это позволяет боту выбрать те ходы, которые раньше дают результат
Xyze: но ты обязан считать много оценок по ходу
Xyze: по ходу игры* я имею в виду
Xyze: и вот, паришься ли ты по этой теме?)
Uljahn: логично считать на 4 дня, как раз дерево вырастает полностью
Xyze: у меня например бот в текущей версии лучше всего играет на глубине 4
Sbergeif: ну еще вырубка же
Xyze: на глубине 8 он слишком долго растит, сбор дерева он откладывает
Sbergeif: важно считать до очков, а очки все-таки выгоднее с большой глубины забирать
Xyze: блин, сколько идей есть, но проверить все точно не успею
Xyze: даже когда я взял второе место, я дико костылил оценку
Xyze: из-за чего в итоге не смог ничего сильно изменить за последние полтора дня, и не победил первого
Xyze: с оценками у меня всегда траблы
Sbergeif: да, спасибо за вопросы, я критически взглянул на весь этот бред, что написал, есть вдохновение все переделать
Xyze: да не за что =)
BookSaver: Sbergeif, а сишного бота не выкладываешь, легенды ждешь?
Xyze: всегда приятно позалипать в чате вместо того, чтобы что-то пилить )))
Sbergeif: я си вообще забыл, только Хассель умею )
Sbergeif: *хаскель
BookSaver: т.е. у тебя на пайтоне все эти симуляции и переборы до конца игры?
Sbergeif: но можно заново выучить, но пока не упираюсь в скорость. то есть качественно мне особо не даст
Sbergeif: у меня нумпай почти чистый
Sbergeif: матрицы и линалг
Sbergeif: ничего не выделяется, в фиксированном объеме
Sbergeif: так что С ну ускорит раз в 10, но особо это не поможет
Sbergeif: я не знаю как сиды симулировать правильно
Sbergeif: как узнаю, тогда можно будет попробовать
BookSaver: сиды - в смысле посадку деревьев?
Sbergeif: да
Sbergeif: ну вот тут как раз основной кусок кода - как одно с другим стыкуется, над которым я безуспешно третий день колдую
Xyze: а кто-нить считал сколько может быть прям максимум ходов доступно в один момент?
BookSaver: Видел 70 и больше
BookSaver: За среднее можно 30 взять.
BookSaver: В любом случае если не резать - глубоко не просчитаешь
Xyze: блин, надо рискнуть всё таки
Xyze: я верю что даже тупые идеи могут что-то показать
Xyze: надо дать каждому дереву давать право генерировать столько ходов SEED, сколько его высота
Xyze: по 1 SEED на 1 2 3 дистанцию
Sbergeif: ну 1 у меня никогда не сажает. наверное по теням слишком плохо получается
Xyze: получится что то типо 1-3 SEED + 1 grow + 1 collect
Xyze: что-то около 5 ходов на 1 дерево
BookSaver: посадки на дистанцию 1 - как правило плохие.
ilgiocatore: Xyze это же всё равно очень много
Xyze: не люблю отнимать у бота возможность когда не уверен в этом
Sbergeif: круто рубить и сажать в один ход
Sbergeif: в один день
Xyze: ilgiocatore ну я щас воощбе не отрубаю
Xyze: так что лучше хоть как то
Xyze: 4 хода на дерево в среднем при целевом значении количества деревьев 7-8 даст максимум 32 хода
Xyze: это самое начало дня после WAIT
BookSaver: чтобы рубить и сажать в один день постоянно, желательно иметь 20 солнышек в день, это 7-8 трешек незатененных.
Xyze: это ж невозможно )
BookSaver: если врага убрать, 8 трешек на карте без проблем
Xyze: ты пока поднимешь этот лес, нутриент упадет
Xyze: да и времени маловато будет
Xyze: останется только собрать что есть и всё
Xyze: тут баланс важен
BookSaver: [1, 5, 11, 20, 23, 27, 30, 34] - 24 солца в день)))
Xyze: так, ну miklla смог, и мы сможем
Xyze: никуда не денемся
BorisZ: Xyze мне кажется что если резать сиды, то лучше с другой стороны - для каждой свободной ячейки брать по 1 дереву-родителю
Xyze: методом научного тыка?
BorisZ: не знаю )
Sbergeif: о, тут даже C есть. а там тоже правым нужны?
Sbergeif: *прагмы
Xyze: fuf
Xyze: ага
Uljahn: Sbergeif: "нумпай почти чистый" - а можно поподробнее, что за матрицы и линалг?
Uljahn: не смог придумать, как прикрутить нумпай
BorisZ: ну лучше потерять одного из родителей - у него может и другие есть варианты что делать, чем потерять удачную ячейку для посадки
Xyze: опа, вы стригерили Uljahn
Uljahn: угу, я как бы только ради нумпая и участвую на CG, уже думал дропать контест
Sbergeif: ну ты генеришь здоровую матрицу событий на следующий ход, с весами усредняешь, генеришь на следующий и так далее. можно сделать, чтобы без clone'ов заранее выделенным объемом. солнышки считаются перемножением на матрицу с графом, надо объяснять как?
Sbergeif: все что можно предрасчитать предрасчитываешь
Sbergeif: но С наверное и правда лучше все же будет
Uljahn: матрица событий из каких элементов состоит?
Uljahn: чё-т интересное
Uljahn: спасибо за подсказки, буду думать
Sbergeif: ну значение - высота дерева в клетке, раскрываем по дням. жадность - трата всех солнышек, в матрицу собираем несколько топовых вариантов, которые со средним ожиданием действием соперника дают максимальное произведение
Sbergeif: чет сложно объяснить
Sbergeif: проще код показать )
Sbergeif: он точно проще, чем то, что я описываю, сегодня очень косноязычен
Uljahn: щас может не время для деталей, но постмортем бы я почитал, и код посмотрел после контеста
Uljahn: я так понял, там бродкастится перемножение графа с несколькими вариантами
Hamibar: Выдавили питон из топ 10(
CyberEcho: Поменял алгоритм выбора места для сида, сразу с 900+ поднялся до 100 места. Выходит это весьма важная вещь.
Sbergeif: ничего себе!
CodeDiller: я правильно понимаю, что единственное условие для выбора seed это наибольший richness
CodeDiller: или есть еще что-то
ilt: нет не правильно
CyberEcho: Вот у меня было очень простое условие - выбиралась ячейка с наименьшим индексом (что соответствует наибольшему richness).
Изменил алгоритм на простенькую симуляцию - сразу стало гораздо лучше.
CodeDiller: что такое симуляция?
CyberEcho: > что такое симуляция?
Берется текущее (следующее) состояние игры. За нас играет алгоритм, и за противника играет какой-то алгоритм (возможно такой-же). Симулируем игру на несколько раундов вперед (или до конца 23 дня) и смотрим на счет.
Uljahn: в правилах есть ссылка на рефери (движок игры на гитхабе), можно его использовать, чтобы вычислять следующее состояние игры при реализации любого из возможных ходов
Uljahn: но надо уложиться в 100мс
CodeDiller: Типо BFS,
CodeDiller: ?
Asethon: Пол дня убил на посадку корабля на Марсе. Ужс.
aropan: @Asethon согласен, сейчас модно солнышко собирать.
Hoggins: не могу решить. Если ширина луча и глубина поиска никак не влияет на результат - это плохо или хорошо? )))
Beard: всё просто. Если они не должны влиять, то хорошо, а если должны - плохо)
YurkovAS: глубину можно не ограничивать
