Asethon: Есть кто по Расту тут?
BorisZ: Asethon ты вопрос то напиши, а то тут мало народу между контестами, так можно несколько дней переговариваться
Uljahn: Automaton2000: ктопорасты есть? а если найду?
Automaton2000: теперь надо заглядывать симой либо больше, чем на 1 ход только
Chibikko: Automaton2000, что лучше, mcts или beam search?
Automaton2000: не так уж и много
Uljahn: в mcts не нужна оценочная, но надо строить дерево и подбирать константу
Uljahn: в любом случае, надо профайлить, т.к. всё зависит от задачи и накладных расходов, т.е. соотношения вычисления оценки, рандомного роллаута, построения дерева и т.п.
Uljahn: ну и доступного времени
Uljahn: т.к. при малом числе роллаутов мктс тупо не взлетает
Uljahn: но при большом числе роллаутов мктс стремится в пределе к минимаксу (дерево будет построено полностью), т.е. в мктс компромис между подрезкой и точностью определяется бюджетом времени и константой, а в бимсёрче - шириной луча и оценочной
YurkovAS: в бимсерче сложнее с ходами противника
YurkovAS: нашел баг - нутриенты не уменьшал :)
и как он до 40 места доходил
теперь все костыли заного перепроверять
Chibikko: Uljahn, спасибо за развёрнутый ответ. Но это была проверка автоматона. Он на нейронках сделан? Чей он?
Chibikko: YurkovAS, твой кстати резко выше стал в рейтинге. Это из-за исправления бага?
Uljahn: Automaton2000 на цепях Маркова и биграммах, кажется. есть даже пазл на эту тему https://www.codingame.com/training/hard/code-your-own-automaton2000-step-1
Automaton2000: ты меня с кем-то путаешь
Uljahn: AutomatonNN на LSTM нейронке
YurkovAS: вчера еще апнул его и с багом.
в общем сильно улучшает ограничение на кол-во выкапываний в день и чтобы постепенно можно было выкапывать больше.
YurkovAS: правда и в проигрышах видно, что противники чаще моих правил выкапывают - может то что он его теряет или какие-то другие правила для противников делать.
пока не понял
BorisZ: YurkovAS а у тебя строго 1 раз в день может копать?
YurkovAS: (completeCount < 1) ||
((day >= 18) && (completeCount < 2)) ||
((day >= 21) && (completeCount < 3))
YurkovAS: вот так когда сделал, он поднялся с 70-80 до 35-40
YurkovAS: надо как-то понять почему так лучше, вывести кол-во ветвей в дереве
Uljahn: а если рубить, если дерево в тень уходит на следующие 4 дня? т.к. за это время можно новое вырастить
YurkovAS: это не в рандомном доигрывании, а для ветвей дерева
BorisZ: то есть в детеве есть разные ноды - копание, рост и семена, так выходит?
YurkovAS: да
BorisZ: надо это обдумать )
YurkovAS: и он потом для каждого начнет делать в нее визиты + скоринг от рандомного доигрывания
и потом еще глубже и т.д.
YurkovAS: вот Магуса стал прям стабильно обыгрывать, что радует, но не доходит до него.
сделал по его ПМ-у и потом надобавлял своего, чтобы хоть как-то заиграло.
Uljahn: как же удобно в 2D с гексами работать, и как лень было на контесте дальше кубических координат заглянуть :(
MelnikovIgor: еее лега, мктс пошаговый + совет от магуса на форуме помогли
Uljahn: грац, тоже попробую в легу закатиться
YurkovAS: :thumbsup:
BorisZ: а DUCT - это ведь когда в одной ноде сразу два хода, и мой и соперника, как бы двумерный массив потомков?
BorisZ: или это что-то другое?
BorisZ: и как там тогда стадия selection делается? в UCT формуле там количесво своих побед на своем слое, а тут тогда как выбор делают?
BorisZ: нельзя ли скрестить обычные мктс с дуктом? )
Uljahn: зачем скрестить? это и так мктс, только варинат для одновременных ходов
735487: BorisZ: а в чем проблема выбирать по той же формуле?
Uljahn: each player uses UCB to select their own moves independent of how the opponent's (simultaneously chosen) move on the same turn can affect the outcome
Uljahn: т.е. два дерева, похоже
Uljahn: а если оба хода в одной ноде, то это Simultaneous Move MCTS (SM-MCTS), видимо
Uljahn: а, это одно и то же
Uljahn: ага, в ноде ходы обоих, но выбираются независимо
https://dke.maastrichtuniversity.nl/m.winands/documents/sm-tron-bnaic2013.pdf
YurkovAS: 2 дерева это смитсимакс, у jolindien-а он получается.
YurkovAS: а самая проблема тогда, в дереве у каждого будут абсолютно все ходы, как для пустой борды и потом каждый раз под тек стейт отфильтровываться недоступные
YurkovAS: в этой доке написано что в каждой ноде храним 2хода для себя и противника
YurkovAS: т.е. под тек. стейт заполняем списки ходов и потом делаем их пересечение
YurkovAS: на одном уровне хранятся как ходы себя, так и противника.
Uljahn: ага, в ноде типа матрицы валидных ходов для данного стейта
YurkovAS: матрица это, т.к. в одной много ходов?
YurkovAS: нарисовано как матрица, но я понял что надо сделать кучу нод
Uljahn: угу, все валидные ходы одного против всех ходов другого, ходы выбираются независимо, но каждое сочетание ходов даёт новый стейт
YurkovAS: о. так они же ну будут по идее друг другу мешать? если независимо выбрать?
т.е. выбрали, а потом гаратнированно найдем ноду с этой парой ходов?
YurkovAS: тогда матрица, да, нужна, а не пересечение каждый с каждым.
чтобы backpropagation сработал
YurkovAS: эх, всеравно в голове не умещается.
так будет ли при матрице проблема, что надо всетаки отфильтровывать стейты?
тогда проще уже смитсимакс с 2 деревьями сделать.
YurkovAS: отфильтровывать доступные ходы
TTeaLL: народ, если делали бетмена, бинарный поиск в двумерном массиве, я реализовал обычный поиск и 2 первых теста сделал, но вот сижу и думаю, как можно запоминать перемещения по карте, потому что на больших отрезках бетмен начинает бегать по кругу, а если я для одного направления напишу список для запоминания, то вот что делать с другими чёт не пойму python если что
YurkovAS: тогда надо еще добавлять список "пересечения ходов" и от него создавать ноду с этой матрицей под этот конкретный ход (пару) для уникальности стейтов
TTeaLL: воооооооооот, у меня такая мысль возникла, но чёт я не могу её сформулировать ни как такое сделать
TTeaLL: а есть где глянуть как такое вообще делается?
YurkovAS: TTeaLL это я отвечал на предыдущю переписку про параллельный мктс.
не отвеча, а размышлял :)
mabu: Вы не отвечаете на мой ответ!
TTeaLL: а, простите, но ваш ответ звучал убедительно для моей ситуации, потому что у меня тоже пересекуются ходы и есть матрица)))
YurkovAS: TTeaLL с этим помочь не могу, даже и не представляю как бинарным поиском искать путь
YurkovAS: вот бфс-ом да, делаешь массив посещенных нод и помечаешь их все. так он обойдет все доступное пространство
TTeaLL: ну там типо, есть направление и по спискам в 2-х измерениях надо перемещаться, это Shadows of the Knight
YurkovAS: + еще в одном массиве указываешь в какую ячейку из какой пришли.
так ты потом от финишной цели построишь кратчайший путь
Uljahn: TTeaLL: это какой эпизод бетмена? в первом всё просто должно быть
Uljahn: задаём границы, прыгаем в середину, сдвигаем границы
Uljahn: конечно, надо представлять, как бинарный поиск работает в одном измерении
Uljahn: в начале границы - это границы поля, нам дают начальное положение бетмена и направление на бомбу, мы отбрасываем координаты, где бомба точно быть не может, т.е. задаём новые границы области поиска, находим середину этой области и прыгаем туда
Uljahn: и повторяем
YurkovAS: получается ему надо завести массив и в нем помечать посещенные места
YurkovAS: пролетел вверх, а ему сказали что еще надо выше, значит проделанный отрезок все клетки помечаем как пустые
YurkovAS: упс, сполейрнул немного
Uljahn: тут граница - это прямоугольник с двумя парами координат по осям, если бомба выше, то нижнюю границу двигаем в Y координату бетмена, если ниже, то верхнюю, если бомба правее, то левую границу в X бетмена и т.п.
YurkovAS: точно, понял
YurkovAS: так что там дукт, все понял?
Uljahn: я чё-то писал в ответ про дукт, но свет из-за грозы обрубился :)
YurkovAS: получается в ноде хранятся:
статистика ходов 1 игрока
статистика ходов 2 игрока
список ссылок на след ходы=попарное пересечение ходов обоих
YurkovAS: *на след ноды
TTeaLL: первый эпизод, и я понял как работает поиск бинарный, просто я не совсем понимаю как отбросить, чтобы в случае когда бомба выше или ниже не было диссинхронизации по координатам
YurkovAS: у тебя 4 переменных?
x-min, x-max, y-min, y-max
YurkovAS: сказали что выше, тогда идешь вверх на половину от тек высоты = (y-max - y-min) / 2
YurkovAS: если скажут после этого что выше, тогда y-min = new-height
если ниже, тогда y-max = new-height
YurkovAS: типа такого
YurkovAS: сжимай границы прямоугольника
как я понял
Uljahn: ага
TTeaLL: да это понятно, но я не пойму, у меня 4 цикла, для UR, UL, U (для того чтобы идти вверх, DR, DL, D для того чтобы идти вних и 2 условия для R и L чтобы лево право идти и как учитывать вот это mew_height в другом условии
TTeaLL: 4 условия*
TTeaLL: в одномерном списке забара нет, а вот в двумерном я не пойму вообще как сохранять
TTeaLL: не понимаю, ввёл эти new_height и new_down и всё равно дальше второго теста не работает
YurkovAS: выведи какие тебе данные подают на вход, на локальном компе запусти с этими значениями и в дебагере по шагам пройдись, может ошибка где
TTeaLL: а, я чёт только одну границу ужимал, только сейчас заметил, но это чую не конец
Uljahn: я делал так: если в направлении есть буква U, то двигаем нижнюю, если есть R, то левую, 4 условия всего, если UR, то выполнятся два условия и сдвинется две границы
TTeaLL: у меня 4 условия, но каждый раз я сдвигаю всего одну, ну ладно, ща кое что попробую
Uljahn: if условие_U else if условие_D, if условие_R else if условие_L
Uljahn: типа такого у меня
TTeaLL: ну ща, я сначала попробую сам, а там может ещё спрошу)
Uljahn: хотя и просто на ифах работает, это я перемудрил
Uljahn: у нас же не бывает U и D одновременно
TTeaLL: почему
TTeaLL: вот кусок
TTeaLL: current location (U, UR, R, DR, D, DL, L or UL)
Uljahn: UD не бывает, невалидное направление
TTeaLL: ну слушай, тут типо прям в задании оно прописано
TTeaLL: bomb_dir = "UD"
TTeaLL: что не так?
Uljahn: :upside_down:
Uljahn: U или D или ничего + R или L или ничего
TTeaLL: погоди, вот если так писать то как раз неверно будет, если придёт UD то по отдельности U или D yне считает
Uljahn: U/D двигают вертикальные границы, R/L - горизонтальные
Uljahn: направление UD не имеет смысла, оно не может прийти
Uljahn: UR и UL могут, а UU и UD не могут
TTeaLL: погоди погоди, может ты говоришь и верно, но игра то тебе может переменную написать UD или DR, если ты имеешь ввиду через __contains__ доставать, то чёт он у меня не особо работал, говорил что я не все данные считываю, ты через него делал?
TTeaLL: не, я чёт не так делаю, я сейчас начертил на бумаге ещё и понял, что я просто не могу сохранить результат, так как я не зна куда будет следующий прыжок, корочет как ты написал про то что 2 границы одновременно сдвигать?
Uljahn: никак, просто два условия сработают
Uljahn: в каждом условии своя граница сдвигается
MelnikovIgor: UD , откуда??
MelnikovIgor: Там не было же такого в условиях)
MelnikovIgor: У вас ошибочка
TTeaLL: ну там же есть оно, прямо прописано 8 направлений, но уже ладно, подсказали как от этого избавиться
MelnikovIgor: Ну где там написано
MelnikovIgor: Вот описание
MelnikovIgor: http://chat.codingame.com/pastebin/18756725-e084-4dd4-a134-072fd20e2c12
MelnikovIgor: Покажешь UD?
MelnikovIgor: Как писали выше, читаешь из инпута буквы(1 или 2 шт) и сдвигаешь x и\ИЛИ у
MelnikovIgor: Если по х - надо сдвинуть, выбираешь какую из границ(макс или мин), для у также
TTeaLL: ой да, UD нету, я имел ввиду что тип 8 направлений и есть смешанные
TTeaLL: да, тут я не обратил внимание что написал
MelnikovIgor: И сжимаешь границы до тех пор,пока не останется 1 клетка)
MelnikovIgor: 2я версия игрыпоинтереснее конечно, там уже надо подумать хорошо, я там целую систему триангуляции придумал, хотя решалось тоже прямоугольными отсечениями
TTeaLL: вот, второе я уже посмотрел и понял, что там какие-то преколы надо придумывать)
mraymun: а че поле Certifications не грузит в профиле?
mraymun: уже день 2-й наверное
Uljahn: да ваще офигели, столько бабла им отваливаем, а они не могут починить саму важную фичу сайта, пора коллективную жалобу писать в Спортлото на имя Automaton2000
Automaton2000: полагаю, что cp-3vel как раз на этот угол и отклоняет
Uljahn: жалобу отклоняет?
Uljahn: теперь ещё и чат лагает, пора удалять аккаунт, пусть кусают локти!
MelnikovIgor: Да кто такой этот ваш Automaton2000
Automaton2000: выше в логах обсуждение было, если ещё не смысло
MelnikovIgor: ))
TTeaLL: народ, если делали бетмена, бинарный поиск в двумерном массиве, я реализовал обычный поиск и 2 первых теста сделал, но вот сижу и думаю, как можно запоминать перемещения по карте, потому что на больших отрезках бетмен начинает бегать по кругу, а если я для одного направления напишу список для запоминания, то вот что делать с другими чёт не пойму python если что
