vrabosh: про что контест будет?
BorisZ: про ведьм
BorisZ: они варят зелье в котлах, если волосы загорелись у ведьмы то камень на лбу становится красным
BorisZ: или наоборот
BorisZ: у нас есть 26 дней чтобы выяснить что причина а что следствие
BorisZ: огонь или красный камень
BorisZ: ну и цвет кожи у ведьм совпадает с зельем
BorisZ: что наводит на мысли что они варят не простое зелье, а создают новых ведьм
BorisZ: но может быть это профдеформация - типа как у шахтеров кожа становится черной
BorisZ: в мультике подсказок никаких нет(
mabu: Как стать ведьмой?
BorisZ: спрошу у тещи
vrabosh: скорей всего какието зелья варить будем
vrabosh: может чтото типа похожее на кухню будет
vrabosh: в видео все примеры были на построение пути.
BorisZ: в смысле на клетках все, без физики
BorisZ: я думаю что с физикой не будет уже оф контестов
BorisZ: судя по тенденции последних контестов, они пытаются сделать более-менее равные условия для компилируемых и скриптовых языков
BorisZ: чтоб не было такого что быстродействие все решает
BorisZ: https://static.codingame.com/servlet/fileservlet?id=51850923132948
BorisZ: картинка в высоком разрешении
amurushkin: BorisZ: красный и синий камни это просто разные игроки
vrabosh: книги - это рецепты, чтото похожее на кухню наверно. А горит у него бошка потомучто он неуспивает и дотокой степени напрягся что загорелся
amurushkin: или наоборот проапгрейдился
BorisZ: да, возможно цвет камня - это игрок, значит будут тольок 1х1 игры можно предположить
BorisZ: а огонь - это баф на ускорение )
BorisZ: все понятно, можно начинать кодить
vrabosh: да скорее всего это буст будет какой нить.
vrabosh: камень возможно светится в темноте.. может им надо будет по темному лабиринту ходить и собирать ингредиенты
amurushkin: не зря вон мэд модуль какой то пилит для поиска :)
fexolm: http://chat.codingame.com/pastebin/e19dfb91-0654-4f29-b0df-d0b8c01defb8
fexolm: оу
fexolm: Всем привет, я решил попробовать порешать https://www.codingame.com/multiplayer/optimization/search-race.
Я пока просто сделал симуляцию и beam search каждый тик, при этом никак не используются результаты с предыдущих тиков и секунда, дающуюся на первый тик. Не подскажете, как правильно хранить результаты предыдущих итераций beam search'a и как их правильно пересчитывать? Я чего-то не нашел об этом информации...
fexolm: И еще, в генетическом алгоритме, я правильно понимаю, что нужно генерировать вектор из N действий, и его оптимизировать пытаться итеративно? Просто по-моему тут возникнет проблема, что чтобы скор для каждого вектора посчитать, придется каждый раз 60 тиков симулировать. Можно это как-то оптимизировать?
fexolm: копипастил свое сообщение из дискорда, почему-то ссылка какая-то вставилась)
amurushkin: fexolm: для генетики симулировать надо не 60 тиков а на какую то глубину. подобрать чтобы давало приемлемый результат. а так в целом да
amurushkin: а вот как дли бим серча прошлые состояния юзать я сам еще не сделал. есть только мысль что брать в пуле искать все состояния которые начинаются на тот же ход который ты делаешь и их оставлять а остальные убирать.
BorisZ: да, 60 тиков - перебор, бессмысленно так далеко заглядывать, обычно до 20 скорее даже ближе к 10, нужно подгонять как лучше будет
fexolm: 60 я случайно написал, просто у меня сейчас beam search столько успевает)
fexolm: ну т.е в генетике по любому придется каждый вектор с нуля симулировать?
BorisZ: с предыдущей итерации можно брать, отрезать 0 шаг и добавлять случайный в конец
fexolm: ну после скрещивания, я так понимаю, все равно все пересчитать придется?
BorisZ: вроде консенсус такой что на непрерывных полях скрещивание не помогает, тормозит только
BorisZ: я пробовал несколько раз - каждый раз выкидвал скрещивание, без него лучше было
fexolm: а чем тогда генетический алгоритм будет от beam search'a отличаться?
BorisZ: только мутации, можно по 1 можно по нескольку сразу генов мутировать случайо
fexolm: я немного нуб, извиняюсь за такие вопросы)
BorisZ: я не уверен что мы бим серч одинаково понимаем
BorisZ: я понимаю так - генерим все возможные исходи из начальной позиции
BorisZ: потом все возможные от них и так далее
BorisZ: при этом откидываем все кроме Н лучших, чтоб влезало
BorisZ: тут все возможные исходы - дофига сколько 37 углов умножить на 200 ускорений
BorisZ: надо как-то дискретизировать все это
fexolm: да, вроде одинаково понимаем
fexolm: только я генерирую только 2 угла и 2 ускорения
BorisZ: радикально как то черезчур
fexolm: возможно
fexolm: ну вот, а в генетике какое отличие от beam search'a будет тогда?
BorisZ: можно больше вариантов сделать углов и ускорений, будут перебираться не все
BorisZ: если брать самый простой вариант генетики - с одной хромосомой то вобще просто в реализации
BorisZ: генерим случайную, меняем случайно, если получилось лучше то старую выкинули новую сохранили и дальше тюним ее
BorisZ: есть название у этого какое-то свое, не помно (
BorisZ: оно быстро к оптимальному значению сойдется так как поле непрерывное, препятствий нету
fexolm: ну вот, меня смущает, что если мы поменяем случайное действие в векторе, то симулировать заново придется с этого момента
BorisZ: ну да, каждая хромосома симулируется от начала до конца
BorisZ: если длина 10, то 10 ходов отыгрываем от текущего до +10, потом оцениваем, потом сравниваем с лучшей
fexolm: ага, понял, просто думал, что это слишком медленно и можно как-то быстрее сделать
fexolm: кстати, все никак не мог ответить
я делал примерно то, что говорил @amurushkin. Но почему-то не зашло, решения хуже получались
fexolm: если на первой секунде построить beam search'eм дерево для всей игры, что возможно на некоторых первых играх, то почему-то тоже медленней получается, чем если каждый раз пересчитывать
fexolm: даже допустим мы построим beam search дерево глубины 120, ширины 120, на первую игру, то просто следовать по этим ходам получалось хуже, чем каждый раз генерить дерево глубины 60 , ширины 60 на каждом ходу и брать из него первый ход
fexolm: непонятно написал, наверное..
fexolm: спасибо, кстати, ребят @BorisZ, @amurushkin )
fexolm: попробую генетику еще написать
magaiti: а что за игра?
amurushkin: fexolm: пересчитывать все равно надо будет. потому что ни один алгоритм так глубоко нормально не просчитает. а первый ход нужно использовать так чтобы просто успеть больше
amurushkin: magaiti: search race
fexolm: а, окей, понял, спасибо)
amurushkin: fexolm: попробуй в свой бимсерч добавить 3 угол равный 0. возможно будет лучше результат
fexolm: сначала так было, оставил 2, стало лучше
fexolm: больше посчитать успевает просто
magaiti: я сделал обратную симу в 2048 кстати
wlesavo: и как успехи?
magaiti: но результаты пока отрицательные
magaiti: в общем протестил для таких условий: 3 хода (вниз не ходим)
magaiti: начальные позиции - 2 верхние строки по змейке
magaiti: нижние - всевозможные перестановки
magaiti: чисел от 256 до 8 4 4
magaiti: причем не все из них имеют решение вперед
magaiti: если четверки не рядом например
magaiti: это тоже учитвал
magaiti: при таких раскладах можно собрать только в 6, 8 , 17 и 28 тестах
magaiti: но так похоже что даже на 58 миллионов не хватает
wlesavo: а 4 хода ничего не дают?
magaiti: не пробовал
magaiti: но по идее не должны
magaiti: ход вниз сломает цепочку сверху
magaiti: пока неясно, куда дальше двигаться
magaiti: попробую все варианты поворотов и отражений доски, с 3-мя ходами
magaiti: если не поможет, значит придется отказаться от змейки, хз
magaiti: что тогда
magaiti: потестирую с ходом вниз с тех же позиций
wlesavo: я пробовал добавлять в оценочную подобие дфс на поздних этапах но тож как-то ничего не дало
magaiti: хмм, не находит решений для 8-го, где-то косяк
magaiti: может я нагнал тут
amurushkin: ну 6 8 17 у меня действительно больше всех набирает
amurushkin: 56929668 пока что лучший мой результат
magaiti: 28 у меня набирает если отзеркалить смейку
magaiti: с верхнего правого считать
amurushkin: тогда возможно некоторые тесты будут лучше если там другая змейка будет и например не низ запрещать а вправо
magaiti: это я тестил все без обратной симы, не дало результатов, только для 28-го помогло
magaiti: с обратной симой не делал пока
amurushkin: наверное есть такие позиции в которых никак не получится собрать
magaiti: ща гляну как 80й тест проскакивает в 131
magaiti: через какие позиции
magaiti: 65536 32768 16384 8192
512 1024 2048 4096
256 128 32 64
4 16 16 2
magaiti: вот с суммой 131078
magaiti: ща надо глубину 1 сделать а не 3
magaiti: 131068: http://chat.codingame.com/pastebin/ea5e8840-d120-4636-9496-5c8fd345e568
magaiti: блин
magaiti: 65536 32768 16384 8192
512 1024 2048 4096
256 128 32 64
16 4 4 4
magaiti: тут очевидно следующий ход - влево или в право, и добавляется 4-ка
magaiti: вправо 4 16 4 8 не сыграет
magaiti: влево 16 8 4 4
magaiti: подходит
magaiti: странно, я вроде тестирую этот вариант
magaiti: а лол
magaiti: вперед не так тестирую
magaiti: ща надо испрвавить
magaiti: исправил, надо перетестить
magaiti: тот же результат
wlesavo: я вот тоже нашел ошибку в скоринге, но исправление тоже не дало ничего
magaiti: ну, можно пытаться без выхода на 131 максимизировать
magaiti: просто по сумме очков, хз
magaiti: но это копейки
magaiti: топ как-то 62 выжал
magaiti: а что если попробовать дфсить обратной симой
magaiti: хмм
magaiti: опа, 24-й тест возможно есть шанс
tutubalin: чо пилите?
tutubalin: а, понял. 2048
amurushkin: я посчитал что чтобы набрать 62 ляма нужно 23 теста на 1.7 и 7 по 3.3
magaiti: 1.7474
magaiti: 3,3 не все смогут, большинство только 2.8
amurushkin: ну да я сильно грубо посчитал. сейчас попробую точнее
amurushkin: ну я чтобы упростить рассчеты. так то просто еще больше надо будет тестов больше 2
amurushkin: 24 + 6 выходит. наверное более реально что то типа 2 теста на 3.3 + 6 по 2,8 и 22 по 1,75
amurushkin: сейчас у меня вообще не похоже чтобы так могло быть
magaiti: я немного увеличил счет, но где-то теряю немколько сотен тысяч
amurushkin: я провел эксперимент. если оценивать змейку только первые 2 строки то результат не меняется
amurushkin: magaiti: что такого хитрого придумал?
magaiti: в 24 тесте использовал обратную симу
magaiti: генерю 50000 позиций назад, а потом смотрю, когда луч пересечется с ними
magaiti: и стыкую
magaiti: , а потом опять запускаю луч, после сборки 131
magaiti: точнее после выхода на исходную позицию обратной симы
magaiti: там где сумма клеток 1310272
magaiti: 131072
magaiti: позицию захардкодил
amurushkin: о блин я пока до этого далек и вряд ли буду делать
magaiti: Юрков как-то и без этого на 2-е место вышел
magaiti: за счет оценочной наверное
amurushkin: я пару раз попробовал на PQ переписать. но то ли я сильно прилип к текущему алгоритму то ли не могу :) не получается у меня. непонятно как очищать задние элементы и куча других проблем
YurkovAS: у меня без хардкодов, но больше и не набирает: ни на локальном компе, ни в проде
amurushkin: так у него вроде и оценочная простая
magaiti: ну смотри, запускаешь брутфорс на глубину 3 например, и пихаешь все в PQ
YurkovAS: в общем убрал у себя накапливание скоров от оценочных с предыдущих этапов
и сразу же стало набирать 58.2
magaiti: потом из PQ достаешь, удаляя дубликаты
magaiti: все отсортировано
YurkovAS: оценочная простая - змейка.
экспериментировал по разному и гуглил - ни чего не улучшается
magaiti: дискаунт какой использовал, сколько строк ?
amurushkin: может ты сильно круто с шириной луча угадал? тоже 3 хода у тебя?
magaiti: 58.2 это как у меня до обратной симы
magaiti: накапливание скоров, хмм
magaiti: надо затестить. я переделал позицию в bitset<80>
YurkovAS: ко мне вопросы?
дискаунт змейки 0.1, проверял и pow(4, X) и т.п
magaiti: 0.1 чет большой
kotobotov: здаров посоны
kotobotov: в че рубаете?
YurkovAS: ширина да там любая от 200 до 400 набирает 58.2
magaiti: или ты имеешь в виду 0.9?
magaiti: 2048 оптимизация
magaiti: а тип фитнеса флоат или дабл?
YurkovAS: magaiti ты у меня спрашиваешь?
magaiti: у тебя
amurushkin: 0.1 дисконт это разница или ты умножаешь на 0.1?
amurushkin: у меня с 0.3 неплохо было
magaiti: тоже интересуюсь
YurkovAS: в змейке сейчас скоры +0.1 от худщего к лучшей позиции
magaiti: у меня внезапно 0.97
amurushkin: а я вот пробовал тоже не умножать а вычитать но по 0.05
YurkovAS: тогда тип флоат
но если сделать скоры pow(4, 0), pow(4, 1) и т.д тогда переполнение и надо double
magaiti: а ясно
amurushkin: вот еще не пойму если дисконт это арифметическая прогрессия с разницей 0.1 то после 10 клетки она уже в минус идет
magaiti: не, там геометрическая
YurkovAS: amurushkin прибавляю
и змейка только одна.
начинается от левого верхнего, идет вниз и получается останавливается на правом верхнем
magaiti: а, у меня идет слева направо по веру
magaiti: верху
magaiti: но я экспериментировал с вращениями доски
amurushkin: ага у меня тоже слева направо. тогда получается что и ходы у него другие
YurkovAS: вот результаты тестов
https://pastebin.com/52fA4eJ6
amurushkin: о у тебя еще и 5 много набирает
magaiti: надо расковырять его
YurkovAS: змейка - просто такую картинку первую нашел.
проверял другие - лучше не становилось
amurushkin: а хуже?
YurkovAS: вроде бы было хуже, но тогда у меня нестабильные результаты были.
надо еще раз проверить
amurushkin: а у тебя дисконт с левого угла на увеличение или на уменьшение идет?
YurkovAS: на увеличение на 0.1. т.е. в левом верхнем 0.1
amurushkin: вот тут похоже и отличие
amurushkin: у нас наоборот
magaiti: я так и не понял
magaiti: что значит увеличение на 0.1
YurkovAS: sigmas[0][0] = 0.1f;
sigmas[1][0] = 0.2f;
sigmas[2][0] = 0.3f;
sigmas[3][0] = 0.4f;
amurushkin: он первую ячейку умножает на 0.1 а все следующие на 0.1 больше
amurushkin: выходит что последняя 1.6
amurushkin: или 1.5
YurkovAS: 0 = y
1 = x
YurkovAS: да, последняя 1.6
magaiti: ок спасибо
amurushkin: а запрещенные ходы есть? или все 4?
magaiti: ну так утебя тогда в левом нижнем собирается большая клетка?
magaiti: в правом нижнем
YurkovAS: в правом верхнем
magaiti: а, да
amurushkin: у меня с таким дисконтом вообще не работает :)
magaiti: так запрещенный ход влево с такой змейкой
amurushkin: о 2.6 поймал на 5
amurushkin: там лимит у меня теперь )))
YurkovAS: а может там надо разные змейки подставлять? в каждом тесте своя рулит
wlesavo: не, разные змейки большого буста не дают у меня
amurushkin: у меня если не ошибаюсь когда то 28 тест 2 ляма набирал
magaiti: 28й да
magaiti: может
wlesavo: тесты которые смогли
wlesavo: http://chat.codingame.com/pastebin/a55298d8-20d8-481e-8126-981f294197a2
magaiti: неа
wlesavo: https://pastebin.com/s4jankQA
wlesavo: ну не у меня а вообще, у меня ток 5 6 8 24
YurkovAS: поменял змейку для 28 теста и стало 59.3 :smile:
amurushkin: у меня 5 тест больше набирает если все ходы разрешены
magaiti: я тестирую пока 3 хода, с 4-мя видел решение для 5-го, но там уже 512 на неправильном месте
magaiti: то есть среди позиций где 8 старших клеток змейкой по порядку, решений нет
magaiti: там еще бывают позиции где для сборки 131к нужно 4 хода
amurushkin: http://chat.codingame.com/pastebin/d2a04ebc-4e20-4ddb-af37-fc3eebd5ddd8
_Lion_: привет
_Lion_: :wave::wave:
_Lion_: что обсуждаем
_Lion_: :thinking:
wlesavo: 2048
_Lion_: что
_Lion_: ли не мне
_Lion_: или не мне
amurushkin: тебе. пазл такой есть 2048
_Lion_: ясно
_Lion_: :joy::joy:
wlesavo: интересно на многих тестах разные змейки дают в точности одинаковые результаты
amurushkin: а спираль пробовал кто нибудь?
wlesavo: я пробовал но там чет совсем грустно
magaiti: а она вообще играбельна?
magaiti: угол пробовали?
amurushkin: ну спираль так то тоже последовательность
wlesavo: пробовал еще последний участок делать по другому типа сначала горизонтальная змейка потом последние два ряда вертикальная
wlesavo: хуже не стало но и сильно лучше нет
amurushkin: угол я пробовал вручную играть. со временем наступает тупик и позиция портится
magaiti: ну вроде последние 2 ряда любые могут быть
wlesavo: amurushkin там важно чтобы были мувы которые сохраняют часть стола, в спирали их меньше
amurushkin: у меня некоторые тесты вообще дают одинаковые результаты если в оценке только 2 ряда
wlesavo: то есть не только последовательность в зимейке хороша
amurushkin: а на некоторы тестах у меня влияет разная длина выводимой последовательности. причем на одни то что улучшает ухудшает на других
wlesavo: много локальных дедендов авидимо, где-то можно случайно в него залететь
amurushkin: в иде набирает 58. осталось сабмитнуть на такой же результат или лучше
YurkovAS: остальные змейки проверил - не нашел улучшений в тестах
amurushkin: иногда улучшаю скор мелкими шагами приближаюсь к magaiti )))
magaiti: у меня щас разломан код
magaiti: не доигрывает до конца
magaiti: так я еще какую-то мелочь смог бы набрать
magaiti: типа если 3 хода кончились, то все. а так можно было бы еще продолжать. но по идее там несколько сотен за тест, не больше
magaiti: дыбдр какой-то монстрила, много где в топе
wlesavo: да, я удивляюсь с него,даже в одной игре тяжело в топе держаться, а у него в половине игр
magaiti: о, чуток улучшил
