Chat:Ru/2020-10-17

From CG community
Jump to navigation Jump to search

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: о, чуток улучшил