Sbergeif: поделитесь, пожалуйста, еще раз C/C++ прагмами, потерял куда сохранил
miklla: #pragma GCC optimize("-O3,inline,omit-frame-pointer,unroll-loops")
Sbergeif: спасибо!
mykeich: Правила с серебра не меняются?
Hoggins: не меняются
TheHexter: Удивительное дело. Ворвался в серебро на 1700/2000 место имея просто посадку/рост/сбор в более богатых клетках в порядке, в котором выдаёт input в possibleActions.
TheHexter: Добавил условие: не сажать у соседних с моими деревьями. Получил 170 место в серебре
TheHexter: Добавил условие: не растить мои деревья, если на следующий ход они будут затенены
TheHexter: Упал на 500
TheHexter: Упал на 500 место
Uljahn: почему не растить-то?
TheHexter: Ну, типа, зачем тратить санпойнты на завтра-затенённые деревья, если можно вырастить те, что не будут затенены.
Uljahn: более высокие деревья дают более сильную тень и могут мешать расти сопернику
TheHexter: Всё верно, если завтра дерево будет выше дерева, создающего тень, то его растим.
Uljahn: ход конём захардкодил уже?
Uljahn: мне ещё дало прирост не сажать много семян, достаточно одного, и лучше всего - на место срубленной трёшки
Uljahn: если деревья у тебя в узлах сетки хода коня, то они друг другу не мешают, а потеря места ломает сетку
TheHexter: О блин, то есть можно сажать не по прямой?)
Я как-то это упустил из виду
Uljahn: по прямой - это как раз не очень оптимально
Uljahn: изи голд
TheHexter: У меня только в исключительных ситуациях сажает не по прямой. Посмотрим.
Vitaliy_Kamalin: Ммм, ранк 1 и не перекидывает в следующую лигу, не такое утро я себе представлял
Uljahn: выше боссса? игры все сыгрались из сабмита?
Uljahn: может, на CG сломалось что-то, во франции сегодня праздник, разрабы могли забить
CyberEcho: У меня вот почему-то рейтинг застрял на 10 уровне и XP больше не изменяется :thinking: Похоже багов в платформе много.
Uljahn: в дискорде есть канал для баг-репортов, или на форуме можно подходящую тему поискать
Uljahn: русский чат разрабы почти не читают
wlesavo: а у меня бимсерч так и не запустился вчера, все какие-то баги вылезают
miklla: я всё пытаюсь глубину 2 запустить, вроде накодил, но пока тоже баги :)
CyberEcho: А мне удалось реализовать beam search. Но он хорошо играет только первые 8 дней, а далее идет в разнос :slight_smile:
Hoggins: мой бимсерч добрался до топ 300.
Хз что с ним теперь делать дальше...
miklla: блин, на КГ моя прога выдаёт неправильный ответ, а локально при тех же входных данных та же прога - правильный - приехали
Hoggins: wlesavo внезапно дубликатов всего ~3% если хэш брать только от доски.
Не нашел каких то статей по поводу прям серьезной войны с ними
Hoggins: Игра, конечно, очень не симметричная. Два идентичных бота без рандома на сидах от 1 до 100 играют: 55 побед у красного 45 у синего.
На арене сиды совершенно случайные, или что то исключено?
wlesavo: Hoggins хм, интересно и правда, надеюсь сегодня как-то хотябы заиграет и посмотрю че у меня
Hamibar: Hoggins я бы попробовал оценку улучшить.
Hoggins: Тычу и чем больше тычу, тем яснее в памяти звучит чья та фраза, что крутить цифры гиблое дело :)
Да, думаю над потенциальными фичами для оценки, спасибо
wlesavo: так ты не цифры крути а новые параметры в оценку добавляй
Hamibar: Обычно первая цифры - самые правильные)
735487: miklla: может банальный совет но такое зачастую из за инициализации нулями. у тебя на компе нули а тут мусором массив или еще что то инициализируется
miklla: да, тоже об этом подумал
wlesavo: чето ничего не пойму, у нас дается 100мс в сумме на день и можно их тратить как хочешь или екак?
miklla: не, на каждый ход по 100мс
YurkovAS: в бим серче можно оценивать не только сами состояния, но и действия.
типа: complete=50, grow=40, seed=30, wait=20
+ добавить доп. параметров и заиграет нормально
wlesavo: блин, значит у меня крашится чето
wlesavo: плюсы в иде отлаживать конечно такое себе удовольствие
mabu: А в чём надо отлаживать?
wlesavo: ну я имею ввиду сайтовую иде
mabu: Я отлаживаю в gdb.
YurkovAS: wlesavo выведи в cerr входные данные, подсунь их в cin и запусти локально
miklla: я сериализирую и отлаживаю локально
wlesavo: да я на работе просто)
wlesavo: так урывками чето дотягиваюсь поделать
YurkovAS: http://chat.codingame.com/pastebin/c60cbe6b-f30b-4f8c-b7ee-b1a052aa2487
YurkovAS: эх
wlesavo: прикольно
wlesavo: я обычно просто первый инпут копирую из дебага и все
YurkovAS: т.е. сначала вывожу инпут данные в таком же виде как они приходят, копирую и подставляю там в коде в переменную ту
BorisZ: забавно что все дебажат бимсерч, может все его из одного и того же места брали? )
BorisZ: я взял псевдокод из посмортема агада
BorisZ: одну ошибку я там уже нашел, но видимо есть еще - не работает
mykeich: скинь ссылку пожалуйста:)
BorisZ: https://github.com/Agade09/Agade-Fall2020-Challenge-Postmortem
YurkovAS: похоже он не чистит массив в который новые стейты потом добавляет
BorisZ: хм
BorisZ: да, после свапа надо обнулять текущий вектор то
BorisZ: YurkovAS глаз-алмаз :sunglasses:
BorisZ: теперь крашится совсем в другом месте, дважемся вперед )
BorisZ: *движемся
YurkovAS: может у тебя таймится?
BorisZ: сейчас виснет где-то, уходит в бесконечный цикл скорее всего, сейчас буду искать
mabu: десу
Uljahn: Automaton2000: ок бумер
Automaton2000: я бы так не сказал
wlesavo: BorisZ во, у меня точно также, в какой-то момент падает просто, если найдешь скажи, может одной природы ошибка
Hamibar: В beam search у нас ширина луча неизменна? То есть на каждой глубине отбираем строго интересующее нас количество узлов? или с ростом глубины растет число хороших ходов?
Uljahn: ага, с переменной шириной луча - это чокудай вроде
Uljahn: насколько я понимаю, в бимсёрче на каждой глубине отбираем топ-k уникальных состояний с максимальной оценкой, полученных от всех экшонов из предыдущих топ-k, а с ростом глубины уточняется перспективность первого хода в серии
Hamibar: Ага, понял. Спасибо
wlesavo: ниче не пойму, бот постоянно хочет ждать, уже спустился до MC и все равно
735487: не используй эту команду
735487: или штрафуй
BorisZ: wlesavo у меня была ошибка при конце игры - он не останавливался
BorisZ: надо было выходить если потомков нет, а он дальше фигачил )
wlesavo: блин, только написал и нашел ошибку кажется, в MC по крайней мере, не там счетчик дня увеличивал
CyberEcho: Кто как сравнивает позиции с разным числом деревьев?
Например, из одной позиции в первом случае сделали 3 действия SEED, а во втором 2 GROW. Как сравнить эти позиции, какая лучше?
BorisZ: какой-то вес должен быть у деревьев
BorisZ: у высоких поболье, у низких поменьше, сам пока думаю над оценкой только
BookSaver: Не делайте 3 seed, смысла нет.
BookSaver: Чтобы дерево вырастить, надо 1 SEED и 3 GROW. На 2 Seed надо 6 grow, и у Вас не будет столько солнышек, чтобы все это подрастить за один ход.
ilgiocatore: да, топы сажают всегда только бесплатно
CyberEcho: Ну пусть это будет последовательность SEED GROW SEED GROW SEED в течении 3-х дней. Конкретная последовательность действий не имеет значения. Важно что при переборе образуются позиции с разным числом деревьев. И непонятно как их напрямую сравнивать, а для beam-search это важно.
BorisZ: чем проще оценка - тем шире должен быть луч, и наоборот
BorisZ: это я не в ответ - так, пришла в голову мысль, которая показалась умной )
Uljahn: сравнивать по количеству полученных солнышек можно
Uljahn: с учётом своих теней и теней противника при условии, что он делает wait всегда
BookSaver: "Какая от коровы польза? Корова молоко дает, или там телят, а от дерева какая польза? Оно солнышки дает, или там очки, если его срубить.
Uljahn: при рубке надо ещё нутриенты учитывать и плодородность, сложна
BookSaver: Сима - это просто. Сложно только хорошую генерацию ходов (чтобы не все возможные), и хорошую оценочную функцию :-)
Сам щас симу пилю, надеюсь к открытию легенды допилить :-)
wlesavo: как марчете писал в общаке, надо "просто" хорошую оценочную
aangairbender: оказывается все здесь общаются, а не в телеге
aangairbender: мне кстати очень не нравится мой beam search, но кроме него хз что писать
aangairbender: смотрел игры топ1 dbdr, не заметил ничего особенного от него. Почему он так сильно от остальных тогда отстает? У кого-то есть наблюдения/соображения?
YurkovAS: aangairbender chokudai - в телеграмме есть 2 ссылки с примерами
aangairbender: так разве chokudai это не тот же бимсёрч?
BorisZ: aangairbender в расте есть nth_element или ты просто сортируешь?
aangairbender: я делаю sort + truncate
YurkovAS: есть еще beam stack search
ссылок у меня нет, его рекурс в прошлом контесте успешно использовал (в ПМ-ах читал) и еще один чел. на яве
BorisZ: я пока тоже, самописный чет не заработал
BorisZ: ну не самописный - скопировал из исходников крейта
aangairbender: меня смущает то, что бимсёрч очень похож на жадный алгоритм и получается что очень важно написать хорошую оценочную. Прям слишком важно. Эйлер вообще на 4-5 дней вперед только смотрит и останавливает поиск если посетил 10к состояний. Толщина луча у него 40
BorisZ: внутренний перфекционист негодует (
YurkovAS: BorisZ beam search не заработал? это же бфс, только оставляем топН лучших.
скорее всего из-за оценочной
BorisZ: заработал, просто оценочной пока нет, думаю
YurkovAS: попробуй оценивать не состояния и только действия (у меня так) и в других мульти тоже работает
BorisZ: defaultAI обыгрывает )
wlesavo: у меня МК такой кривой что проигрывает моему питоновскому трехстрочнику
Xyze: у меня также было
Xyze: но я какой-то странной оценкой его подлечил
BorisZ: надо подумать, непонятно как к этому подступиться - действия оценивать,
YurkovAS: BorisZ не состояния *А только действия
aangairbender: YurkovAS оценивать не состояния, а действия?
Xyze: теперь пишу брутфорс чтобы отладить оценку локальнео
wlesavo: уже с десЯток параметров в оценке
vrabosh: много людей в золото попало
aangairbender: то есть оценивать действия исходя из текущего состояния?
aangairbender: пока не представляю как это
YurkovAS: ну например: http://chat.codingame.com/pastebin/8a4a091f-bcc4-47f8-8a75-f6b02e6ad8fc
BorisZ: YurkovAS то есть сид а б и сид ц д - одинаково оценивать?
aangairbender: и хранить в нодах сумму действий по пути?
YurkovAS: если видно что какой-то seed лучше, то и добавляй доп баллы
это примерно описал
aangairbender: BorisZ всегда можно еще условий написать чтоб такие действия по разному оценивались
YurkovAS: в ноде хранишь общий накопительный скор
aangairbender: ну звучит интересно, можно попробовать
YurkovAS: и чем глубже забираешься, тем меньше этот скор будет влиять, т.е. умножаем на коэфф
YurkovAS: state.score += score * 0.9^depth
BorisZ: у меня пока разрыв шаблона, я только про состояние думал
wlesavo: у меня тоже с действиями, но чето как-то все-равно грустно
YurkovAS: я часто так делал и работало, но не топ1 конечно.
в бим-серче
BorisZ: действия оценивать - это конечно быстрее должно быть, уже плюс
YurkovAS: самое главное это:
state.score += score * 0.9^DAY
YurkovAS: не depth, в day
точнее со сменой дня уменьшаем коэфф
aangairbender: мда, я раньше и не думал о таком
aangairbender: хотя все же на этом контесте первый раз beam search пишу...
BorisZ: тут то в чем смысл затухания - мы сравниваем друг с другом ноды одного поколения всегда
BorisZ: у каждой ноды будет тот же коофициент
aangairbender: логично
YurkovAS: умею писать бим серч, но это не самое главное
темболее скоро все будут уметь...
wlesavo: BorisZ смысл в том что если ты сделал полезное действие раньше, то оно принесет больше очков
wlesavo: поколение то одно, но предыстория разная
kda: aangairbender Дак у тебя же вроде MCST, а не Beam ?
BorisZ: да, наверное, гуд потом бед лучше чем бед потом гуд
aangairbender: тоже логично
aangairbender: kda не, у меня beam search с width 30
kda: *MCTS
aangairbender: и оценочной в points + score/3 + еще пара переменных
aangairbender: все вроде просто, но уже 2 дня не могу обыграть ничем
aangairbender: * там sun/3
kda: В общем чате просто увидел - day before this contest started, I writed MCTS for uttt and it went straight to the legend from bronze. No extra tuning/heuristics/teccles
aangairbender: да, то для крестиков ноликов написал (для другой игры)
aangairbender: тут, как я понял, мкст не особо подходит
kda: ааа) не удидел видимо)
kda: вроде же как раз чтобы функцию сильно не придумывать ?
aangairbender: uttt - Ultimate Tic-Tac-Toe, название игры
aangairbender: мктс в базовом виде не подходит для одновременных ходов
kurnevsky: Почему? И что тогда подходит? :)
aangairbender: ну вот я пока знаю только beam search
aangairbender: есть еще smitsimax, но там есть ограничение, чтоб игроки друг другу ходы не могли заблокировать
YurkovAS: в xmas-rush топы успешно юзали smitsimax, там тоже ходы мешали
YurkovAS: можно ПМ-ы к нему почитать, там есть детали
aropan: Думаю здесь может сработать smitsimax. Здесь одно действие только блокирующее, но его можно игнорировать мне кажется - не так часто сажается в одну клетку.
aangairbender: здесь в принципе легко сделать чтоб ходы не блокировались. По сути блокируется только посадка дерева, можно сделать так, что если садишь в уже существующее дерево, то просто твой seed игнорируется, но солнца снимают
aangairbender: имхо вся суть в том, чтоб с соперником почти не конфликта, поэтому хз много ли даст smistimax
aangairbender: важно себя максимально оптимизировать, тогда соперник просто не догонит
YurkovAS: ну либо минимакс попробывать, с противником
YurkovAS: темболее, если есть оценочная на состояниях
aangairbender: имхо minimax-ы и smitsimax-ы плохи тем, что 90% случаев и ты, и соперник будете делать наиболее оптимальный ход даже не учитывая ход оппонента
YurkovAS: в минимаксе же учитывая, как раз
aangairbender: поэтому нет нужды переберать все пары ходов, можно просто дать возможность каждому сыграть свой лучший ход
aangairbender: я понимаю что минимакс это учитывает, но я боюсь что он найдет те же ходы, что и бимсерч, но потратит на это намного больше времени
YurkovAS: а в смитсимаксе можно провника учитывать или забить
aropan: smitsimax же учитывает. Точнее не знаю как там написать, но почему бы не учитывать.
YurkovAS: если писал мктс, то будет не сложно
aropan: То есть когда спускаешь в обоих деревьях как в mcts то считаешь игру как бы для обоих соперников и правильно подсчитываешь солнышки.
aropan: На пересечение по желудям, например, забить. )
aangairbender: наверное я неправильно выразился
aangairbender: в игре в 90% случаев и ты, и соперник будете делать свой наиболее оптимальный ход даже не учитывая ход оппонента, поэтому нужды учитывать ходы оппонента почти нет, поэтому смитсимак с минимакс будут излишни
YurkovAS: в смитсимаксе и в минимаксе 1 ход будет равен одному дню
aangairbender: вот мысль как должна была быть
aangairbender: ну это мне так кажется, а как оно на самом деле я хз
YurkovAS: ну а окажется, что все учитывали ход опонента
YurkovAS: даже в прошлом контесте почитай, некоторые учитывали для бимсерча
YurkovAS: вот что тоже надо проверить
kurnevsky: Как-то по описанию smitsimax больше на mcts похож, чем на минимакс.
YurkovAS: да это мктс, у каждого свое дерево
aangairbender: хотя смиткисмак может быть хорош для контроля карты, затенении соперника, а это вполне возможно 80% победы
YurkovAS: и ход скорее всего должен быть равен одному дню: т.е. мульти экшен может быть, а может быть и только wait
aangairbender: мне нравится как играет ashelkov, садит оптимально некоторое количество деревьев и начинает каждый ход срезать дерево size=3 и выращивать новое size=2 -> size=3
YurkovAS: он и в пакманах тоже в топе был на js-е
aangairbender: у него моменты среза имеют четкий период на таймлайне
aropan: Да, я тоже в прошлом году учитывал ход оппонента в чокудай. Ифал всякие штуки на то, может ли противник заблокировать комбинацию, которую я планирую собирать.
aangairbender: он признался в чате, что без поиска, на эвристиках сделал
aropan: Вроде даже как было то, что я запускал меньший чокудай для соперника, чтобы понять, какой у него план.
YurkovAS: тогда все дружно прикручиваем определение первого хода для противника :)
aangairbender: я думал в бисерче каждый день запускать для сопреника поиск с глубиной 1 чтоб узнать его действия на этот день
aangairbender: это должно быть лучше чем просто wait
aangairbender: но тогда смысл в бимсерче отпадает и уже лучше смитсимакс сделать:sweat_smile:
aangairbender: ладно, пошел я спать, 4 ночи уже, а в 10 работа
Hamibar: YurkovAS интересная идея с оценкой ходов, а не состояния. Как раз сейчас бот так работает, но без какого-либо поиска.
Hamibar: Становится гораздо проще оценку подобрать как мне кажется
YurkovAS: мне тоже так проще
