Chat:Ru/2020-10-11

From CG community
Revision as of 11:29, 15 June 2021 by Chat Log (talk | contribs) (Created page with "<img src=/a/2111605585777> amurushkin: а можете рассказать как вы в 2048 определяете валидный ход или нет? как в сим...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

amurushkin: а можете рассказать как вы в 2048 определяете валидный ход или нет? как в симе сравнением 2 массивов?

amurushkin: запилил бимсерч но он почему то у меня и таймит регулярно на сабмите и даже миллион не набирает

amurushkin: или там оценочная похитрее нужна?

YurkovAS: amurushkin похожа на мув, если кого-то сдвигаем, то доступен ход

amurushkin: вобщем как в рефери?

YurkovAS: нее, у меня самопал и думаю быстрее

amurushkin: ну я пока скопировал с рефери. вчера 5 часов баги фиксил чтобы хоть как то заставить бимсерч работать

YurkovAS: в рефери он же много сдвинет. а тет, если начинаем любого двигать -> то доступен ход

YurkovAS: у меня бим серч

amurushkin: у меня какой то косяк с ним наверное. а оценка какая?

YurkovAS: как в реале оценка

YurkovAS: сам можно сказать только сделал, еще много вариантов не затестил

amurushkin: а по сколько ходов сразу выводишь?

YurkovAS: все

YurkovAS: не помню, на первом ходу это от 500 ходов

amurushkin: вобщем насколько далеко зашел так и выводишь?

YurkovAS: да

amurushkin: казалось бы такая простая сима а я столько накосячил )))

amurushkin: пытался найти видео ромки и сделать на векторах как у него было. видео не нашел на векторах делал 5 часов )))

YurkovAS: без ошибок только принцессы пишут :smiley:

wlesavo: amurushkin я флагом определяю валидность, если было слияние хоть одно или было хоть одно смещение флаг ставлю, смещение это по сути запись в клетку где раньше был 0

amurushkin: попробовал выводить по много ходов. на 11 ходу уже невалидный ход. где то в симе еще косяк видать

wlesavo: YurkovAS ограничение на вывод за ход 10к ходов кстати, если больше выведешь будет таймаут

YurkovAS: wlesavo спс

YurkovAS: wlesavo не подскажешь, есть у кого-то с бим серчем больше 10млн результат?

wlesavo: amurushkin а ты с невалидными как поступаешь? если ты их просто игнорируешь при поиске, то они же в решении будут оставаться тоже

YurkovAS: так надо же пофиксить все невалидные

YurkovAS: это из-за ошибок в симе

amurushkin: wlesavo: я невалидные в пул не добавляю

wlesavo: YurkovAS знаю только что у эйлера бим серч, но уверен что бимом можно больше набрать зависит сильно от параметров, учитывая что у меня MC на 17

YurkovAS: мс на 17 всего? пробовал на первом ходу побольше делать, там же времени много дают

wlesavo: 17 миллионов всмысле

YurkovAS: ааа, подумал глубина такая

YurkovAS: а у топов что?

YurkovAS: большая разница с ними

wlesavo: глубина 6 вообще, я просто ищу не до упора, а оцениваю один ход n раз, добавляю его в выход и дальше играю

wlesavo: у илледана и дбдра знаю что вроде как детерминированные боты, плюс у илледана что-то с плавающей глубиной

wlesavo: но так деталей пока никто не раскрывал

YurkovAS: а, вот оно как, интересный подход

YurkovAS: или не понял. ну ладно, так даже интереснее будет поискать чего-нибудь.

wlesavo: кови сказал что он MC не смог до 10М довести даже, так что я уверен что у бимсерча большой потенциал, просто нужно с имплементацией поиграться

amurushkin: капец у меня похоже seed не совпадает в симе. скопировал же код с рефери ))

wlesavo: главное там сделать сид long long

YurkovAS: или int64_t

wlesavo: ато он переполняется

wlesavo: ну да или так

amurushkin: прикиньте я это уже правил вчера. а сейчас смотрю там опять простой инт. зараза. а я тут кручу верчу ))

wlesavo: я вчера перед тем как баг в эвале найти тоже крутил вертел уже все

amurushkin: у меня еще есть какая то фигня в алгоритме. когда норм ходов нет. если я добавляю одно условие то оно работает дальше но с ним иногда останавливается даже когда игра еще не закончилась

amurushkin: набрал 2 ляма но блин 50% таймауты ))

YurkovAS: тайминг на ход поуменьшай

amurushkin: уже 30мс

YurkovAS: и на первый

amurushkin: да и на первом уже уменьшаю

YurkovAS: у меня тоже таймит, и локально перестало работать, из-за ошибки Total game duration too long (>30000ms) тут либо константы редактировать, либо рефери ускорять - у них еще есть общий тайминг на игровую партию

YurkovAS: догнал wlesavo с бим серчем

amurushkin: я блин не могу придумать как эффективно хранить пул решений и сортировать его

YurkovAS: да, там интересно, правда это уже решил в другой мульти

amurushkin: в подлодках у меня вообще каждую итерацию сортировка была

wlesavo: YurkovAS хорош, давай на 56M уже потихонечку

amurushkin: как думаете почему у меня около 4 только?

amurushkin: YurkovAS: как ты у стейта список ходов хранишь?

amurushkin: я пока ничего лучше не придумал чем массив небольшого размера. но тогда длинные не получаются сразу вывести

YurkovAS: amurushkin в массиве на 10к ходов

amurushkin: и оно у тебя внутри ноды и ты вот с этим добром их сортируешь и от них копируешь новые решения?

YurkovAS: да, внутри

YurkovAS: ну ты что сортируешь двигаешь?

YurkovAS: у меня там указатель и кол-во

amurushkin: вектор структур

YurkovAS: вектор указателей на структуры двигать быстрее

amurushkin: массив правда обьявлен как int[N]

YurkovAS: у меня там самопал, без векторов и без динамический выделений памяти. на старте все выделяется и потом реюзается

magaiti: чего пилите?

YurkovAS: https://www.codingame.com/ide/puzzle/2048

magaiti: если структура не сильно больше размеров указателя, ее может оказаться что двигать быстрее

magaiti: а

tutubalin: её ж захардкодить можно

magaiti: валидаторы как будешь хардкодить?

YurkovAS: вроде как упрешься в лимит кода, т.к. в партии больше 1к ходов

tutubalin: валидаторы сперва надо вытащить

magaiti: ну типа зазиповать

YurkovAS: там и без зардкода в топ10 реально залезть

amurushkin: на 10 месте и я пока с плохим результатом

tutubalin: есть два способа добычи валидаторов: 1. с помощью множественных сабмитов получать по 1 биту информации за сабмит с помощью умышленных runtime ошибок

tutubalin: 2. поискать на гитхабе, может быть кто-то уже сделал это ранее

YurkovAS: так валидаторы же все в исходниках лежат, там спец флаг

magaiti: как ты бит получишь, без решения которые способно выдать пасс?

tutubalin: а, да. валидаторы уже лежат на гитхабе вместе с исходниками игры

tutubalin: magaiti я просто запустил дефолтное решение без каких-то изменений, которое всегда делает U. несмотря на illegal move, оно проходит все тесты, просто с маленькими очками

magaiti: аа

magaiti: там зафейлить можно только если упадет

tutubalin: о, я на 34 месте с дефолтным решением ))

magaiti: сурово

wlesavo: tutubalin у вестиклса хардкод, но он кодит по 8 мувов в 1 символ, у меня сейчас гдето 10к мувов, и это еще достаточно мало, у топов раза в 2-3 больше на 30 валидаторов это 1000к символов уже

magaiti: а алгоритмы сжатия не помогают?

wlesavo: ну вот на сколько получилось у вестиклса. можно пытаться дальше заморочиться, но у топ 3 у всех онлайн решение, пока не понятно есть ли смыслхардкодить

YurkovAS: optimization надо переименовать в hardcoding

wlesavo: хотя я думаю что игра решаема

magaiti: 8 мумов в 1 символ это не алгоритм

magaiti: я имею в виду зип итп

magaiti: так то ясно что 4 мува это 2 бита

wlesavo: ну возможно и можно, но тут опять же сколько символов еще скушаешь распаковщиком. если сделаешь конечно думаю многие с интересом бы послушали

magaiti: хз. давайте на нейронке сделаем

wlesavo: не очень задача для нейронки конечно

wlesavo: если бы сид был неизвестный то да

magaiti: ну распаковщик думаю в 1к символов влезет, если гольфить

magaiti: алгоритм надо выбирать чтоб распаковщик был маленький

wlesavo: лол, убрал одно действие и получил буст в 10M

YurkovAS: убери 5 будет еще лучше

amurushkin: всмысле действие убрал? меньше выводить на 1 стал?

wlesavo: YurkovAS amurushkin нет, никогда не жму вниз

amurushkin: неожиданно

amurushkin: у меня так хуже

wlesavo: илледан говорит что у него так 40М набирает

YurkovAS: у меня тоже хуже

YurkovAS: но вот вернуть на 1-5 мувов меньше добавляет баллов

YurkovAS: видимо специфика бим серча, не надо все ходы возвращать

wlesavo: у меня после этого наконец до 65к начал доходить, но это на брутфорсе

YurkovAS: а с МС такое не прокатило?

wlesavo: на MC почти не было разницы но хуже тоже не становилось, где-то на 17М ост

wlesavo: остановилось

wlesavo: может параметры не докрутил еще просто

amurushkin: а я вот не смог подобрать параметры чтобы не таймило и чтобы больше 4М было

amurushkin: видать прийдется переписывать

wlesavo: amurushkin так а от чего таймит?

amurushkin: да я бы еще знал. сабмитю а там далеко не всегда 100%

amurushkin: и ширина луча и порог среза на это сильно влияют

magaiti: поставь отсечку поменьше чтоб таймило гарантированно на ошибке

magaiti: потом как-то локализовать надо

amurushkin: а толку если я не могу посмотреть сабмит

magaiti: в подозрительных местах добавь проверки, в дебаг выводи

magaiti: лучше хз, локально запустить и ловить дебаггером

wlesavo: так не воспроизводится на реплеях?

magaiti: хз тогда

amurushkin: вот у меня сейчас никак не примет решение на 4.6 ляма. все время 98% и постоянно в разных тестах. а так они отрабатывают до конца

wlesavo: может либо пустую строку выводишь либо больше 10к символов?

amurushkin: да не я больше 10 не вывожу. без к ))

amurushkin: на пустую тоже есть проверка

wlesavo: а пустую не можешь случайно вывести?

wlesavo: или символ какой не тот

wlesavo: от этого сразу падает

amurushkin: символы у меня только 4 могут быть

amurushkin: он рандомно падает на разных тестах. прямо как в search race. сабмитишь пока не примет на 100% по несколько раз

wlesavo: реально странно

amurushkin: не хватает смотреть реплеи с валидаторов

magaiti: отсечка решения по таймеру у тебя?

magaiti: рандом используешь?

magaiti: алгоритм ходит по разным путям в разные сабмиты, и где-то там падает

amurushkin: рандома нет. отсечка по таймеру но не всю катушку

magaiti: выход за границы массива, взятие первого элемента в массиве из 0 элементов

YurkovAS: c бим серчем легко перевалить за тайминг, там же сортировка и циклы по больших массивам

magaiti: а че сортируем?

magaiti: может куча быстрее будет?

amurushkin: там нужно выбрать какое то количество лучших и от них дальше вглубь идти

magaiti: куча теоретически быстрее должна быть

amurushkin: можно впринципе PQ попробовать

magaiti: чем полная сортировка

magaiti: ну PQ через кучу реализован

amurushkin: а его можно быстро отрезать с хвоста лишнее?

magaiti: не, там по другому. лучшие элементы в хвост уходят

amurushkin: нужно же подчищать лишние еще

magaiti: вопрос в том ,сколько из скольки отрезать надо

amurushkin: у меня сейчас из 1500-3000 тысяч отрезает до 32

magaiti: https://en.cppreference.com/w/cpp/algorithm/nth_element

magaiti: kexit 'nj z levf.

YurkovAS: не смысла добавлять лишние в массив

magaiti: думаю это

amurushkin: я сейчас у вектора resize делаю

magaiti: либо хранить кучу из 32 элементов

YurkovAS: хранить макс 32 и всегда отсортированными + бин поиск

magaiti: вариант, но куча может быть быстрее, надо тестить

amurushkin: не катит хранить только 32. тебе же надо от каждого по 4 ребенка еще. затрешь часть так

YurkovAS: причем, можно сравнить по быстрому с худшим, если это лучшее решение, тогда через бинпоиск находим место вставки

magaiti: просто сделай кучу

magaiti: она сама найдет

magaiti: на вершине худший элемент

magaiti: если наш лучше - заменяем и ворошим кучу

amurushkin: надо поискать еще раз видео ромки. у него на векторах было прикольно сделано. и походу быстро

magaiti: цг же до сих пор компилит с ключом -g,

magaiti: ?

amurushkin: надо пока отдохнуть и подумать

magaiti: тогда вектора не быстро

YurkovAS: magaiti вариант с кучей быстрее, чем статический отсортированный массив + бинпоиск?

amurushkin: по идее не должен. на вставке тот же бинпоиск только куча еще ресайзится наверное

magaiti: отсортированый массив тебе придется двигать в среднем n/2 элементов

magaiti: за вставку

magaiti: в куче меньше

magaiti: в общем случае надо бенчмаркать

YurkovAS: а как найти тему, я не вкурсе. куча, так и называется?

magaiti: heap

magaiti: в с++ есть make_heap pop_heap push_heap

amurushkin: я вот не знаю деталей как именно куча работает. мне PQ ближе и понятнее

magaiti: и priority_queue

YurkovAS: спасибо

magaiti: я думаю самописная будет быстрее, но придется разобраться

magaiti: как работает

amurushkin: впринципе если делать linked list то вставка будет быстрее наверное

magaiti: а серчить как ты будешь

magaiti: в листе

amurushkin: бинпоиском. будет log2N

magaiti: бинпоиском по листу? шутник

amurushkin: мне по сути в нем серчить не надо. просто брать первый. а вставлять так чтобы он был сортированный

magaiti: а как он будет у тебя отсортированный без поиска?

amurushkin: а походу вставка за N будет

amurushkin: а вообще я не могу найти почему то ни одной реализации бим серча готовой чтобы код посмотреть как другие делают

amurushkin: я вообще не уверен что его правильно закодил

magaiti: хз на википедии посмотри

magaiti: прочитай внимательно, все ли у тебя так как там написано

magaiti: мне в push_heap и pop_heap не нравится, что приходится первй элемент сначала доставать, а потом запихивать новый. нужна еще операция нормализации кучи когда первый элемент изменился

magaiti: в принципе самому можно написать.

magaiti: но если тебе надо хранить прям 3000 элементов, то частичная сортировка подойдет

magaiti: https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0

magaiti: тут описан heapify

magaiti: он лучше чем pop_heap + push_heap, если нам надо заменить первый элемент

amurushkin: ну на википедии смотрел. вроде да так

magaiti: хз, ищи косяки реализации тогда

magaiti: сделай тест

magaiti: генери случайно инпут, вдруг бот упадет где-то

magaiti: в нормальной иде, с дебаггером

magaiti: или зациклится

magaiti: если поле заполнилось, перезапускай сразу. пусть крутится пока не упадет

magaiti: а когда упадет, чтоб у тебя была возможность перезапустить на том же инпуте

magaiti: сохраняй его в лог типа

amurushkin: спасибо за советы

amurushkin: кстати кажется нашел баг. вопрос он только у меня или в рефери тоже

amurushkin: 2 16 4 8 2 4 64 512 2 1024 4 2 2 16 128 4

amurushkin: какой должен быть стейт после хода вверх?

amurushkin: а не я гоню. все правильно ))

magaiti: левый столбец 4 4 0 0

magaiti: остальное не долнжо поменяться

magaiti: если я не звбыл как играть

wlesavo: да все верно

magaiti: amurushkin, ну че там, у твоего бага другое мнение?

amurushkin: у меня по дебагу выходит что если я убираю условие и пытаюсь искать ходы на заполненной доске то алгоритм из рефери падает что ли. таймит на попытке сделать ход

magaiti: а заполненная доска не считается за цонец игры?

amurushkin: бывает что ее еще можно сдвинуть и уберутся

amurushkin: похоже падает когда пытается спавнить на заполненную доску

magaiti: хм, а точно падает рефери а не твой код?

amurushkin: ну код из рефери скопирован но похоже условие на спавн может у них есть. сейчас гляну внимательнее

magaiti: код рефери же известен? на гитхабе лежит? наверное там можно баг найти и сообщить

amurushkin: да не скорее всего я накосячил. иначе бы у всех падало

amurushkin: а раньше я просто полную доску считал заполненной. а ее еще можно пытаться играьб

magaiti: если после хода заполнена, тогда конец

magaiti: или хз, как там двойки добавляются

amurushkin: может повезти. конец когда нет хода ни одного

amurushkin: стало до лимита в 600 ходов доходить

magaiti: я у себя в гоночках косяк в симе нашел

magaiti: внезапно, через 2 года

magaiti: криво оптимизировал

amurushkin: расскажешь какой?

amurushkin: я тоже не так давно обнаружил что у меня коллизии с чеком неправильные

magaiti: ну у Магуса код виснет, там нет проверки одной

magaiti: вот ее неправильно реализовал

magaiti: не висло, но иногда неправильно считало, по идее

magaiti: проверка что поды сближаются

Default avatar.png Lobs: кто по си шарпу????

amurushkin: лучше сразу вопрос задавай

Default avatar.png Lobs: бляяяя

Default avatar.png Lobs: тут джс нету

Default avatar.png Lobs: я тут по пайтону и как тут решать вообще

magaiti: джс это что? JavaScript есть

magaiti: берешь и решаешь

magaiti: начни с простых пазлов

magaiti: onboarding, descent

Default avatar.png Lobs: спс

magaiti: я загрыз игги

magaiti: кто следующий?

amurushkin: о 8 лямов наколядовал

IlyaP: softpro

magaiti: https://www.codingame.com/replay/492442581

magaiti: 179 ход неплохо запульнул

Default avatar.png Mosha: magaiti, привет, а что это за числа, рядом со звёздочками?

Uljahn: в пазлах?

Default avatar.png Mosha: Uljahn не, в гонках на pod-ах

Uljahn: рейтинг в лидерборде, если ты про звёздочку рядом с ником

Uljahn: magaiti: на два раннера перешёл?

magaiti: не, просто блокер ранит, если больше делать нечего

Uljahn: вообще, неплохо выглядит

magaiti: ну я немного улучшил, в топ 10 влез

Default avatar.png Mosha: Понял, спасибо! У меня встал один вопрос, так сказать. Я соверешенно не могу выкупить, почему раздел называется AI а модельку я ему сам пишу? Это норм? Не должны всякие эти параметры сами обучаться?

magaiti: так стоп, а что за звездочки?

magaiti: чет я сам не в курсе

magaiti: куда смотреть

Default avatar.png Mosha: А ещё я никак не могу понять, почему рейтинг решения задачи зависит от того, сколько соревнований на арене было?

Default avatar.png Mosha: Я зашёл посмотреть твой реплей, и там ниже твой ник, звёздочка и число, что-то около 44

magaiti: а ты в каком разделе? bot programming?

magaiti: а ясно

Uljahn: под реплеем у того, кто выиграл заезд, звёздочка рядом с ником, у проигравшего квадрат

magaiti: ясненько

magaiti: рейтинг, да. в реплее я против более слабого

Default avatar.png Mosha: Я в какой-то момент просто нажал на AI на стартовом экране с ачивками, он кинул меня на coders strike back...

Default avatar.png Mosha: Вопрос, как этот рейтинг рассчитывается? Типа, он проводит N соревнований, и выдаёт результат?

magaiti: ну ты программируешь бота, он сражается против других ботов, около 100 дуэлей

magaiti: и по резултьатам получает рейтинг

magaiti: от рейтинга зависит сколько очков ты заработаешь

magaiti: да, N дуэлей, выбирается случайно из ближайших по рейтингук

magaiti: если победил более сильного, получаешь больше, проиграл слабому -теряешь больше

Uljahn: угу, рейтинг по формуле TrueSkill рассчитывается

Uljahn: или даже алгоритму

magaiti: от удачи часто тоже зависит

magaiti: но всегда можно ресабмитнуть, если тебе показалось что неудачно выступил

magaiti: насчет модельки я не понял. симуляцию нужно самому писать?

magaiti: это да

magaiti: но ест ьпримеры по ссылкам в описании задачи

Uljahn: само ничего не обучается, только матчмейкинг автоматический

magaiti: даже с кодом

Default avatar.png Mosha: Понял, спасибо большое! Ага, удача тут тоже часто роль играет... Окей, а такой вопрос, правда, что чем выше лига, тем больше параметров есть для управления. И ещё кое-что. Правда, что для выхода в лигу выше нужно набить определённый рейтинг в своем?

magaiti: да, под AI здесь это понимаетмся просто алгоритм который ты сделаешь

magaiti: нужно победить босса

Default avatar.png Mosha: Понял, не обучается и ладно, Бог с ним

magaiti: то есть по рейтингу его выше быть в конце

Default avatar.png Mosha: То есть, побеждать его в каждой схватке, условно говоря?

magaiti: не, просто после того как 100% дуэлей сделаешь, чтоб твой рейтинг был больше чем у босса

Default avatar.png Mosha: Понял-принял, спасибо большое!

Uljahn: новые правила каждую лигу добавляют в гоночках, окончательные правила в золотой лиге, в легенде только ускорение побольше будет

magaiti: да, чем выше лига, тем больше дают параметров. но самое главное - быстро ездить по чекпоинтам

magaiti: до легенды можно концентрироваться только на езде

magaiti: в легенде уже тактика

Default avatar.png Mosha: Окей, спасибо, товарищи!

Default avatar.png Mosha: А можно несколько стратегический вопрос, я не совсем понимаю, для чего лучше использовать буст, и как обращаться с тем, что корабли теперь сталкиваются... Правильно я понимаю, что буст нужно оставить для прямых длинных участков? И как толкаться?

Default avatar.png Mosha: Или бустом нужно бороться?

Default avatar.png Mosha: Или это уже моя фантазия?)

magaiti: буст для длинных участков. можно первым ходом

magaiti: толкаться это уже тактика, лучше быстро ездить

magaiti: толкаться щитом можно, но сложно научить

magaiti: чтоб грамотно использовать

magaiti: можешь поэкспериментировать

Default avatar.png Mosha: У меня ещё нет щита) Просто я и использовал буст на первом, но он часто пролетает далеко за первый чек-поинт

magaiti: но один буст за игру не спасет, если противник тебя быстрее

Default avatar.png Mosha: Да я что-то весь вечер экспериментирую, но каждое нововведение долго обкатывается... Это да, один буст, скорее, как приятное дополнение)

magaiti: если за первый пролетает, лучше сохранить на длинный участок, или на рывок на последний чекпоинт

magaiti: результат буста в противника сложно предсказать, он же тоже маневрирует

Default avatar.png Mosha: Просто я не очень понимаю, как он отслеживает количество пройденных чекпоинтов. Этой информации же не предоставляется

magaiti: ну координаты чекпоинта меняются

magaiti: сохраняй и сравнивай

Default avatar.png Mosha: Вот да, это и смущает, тупо буст в противника делать, иногда, себе дороже

Default avatar.png Mosha: Да, но количество чек поинтов от карты к карте меняется же

magaiti: ну значит храни все, и сравнивай, на 2-й круг начнут повторяться

magaiti: и тогда уже можно дрифтовать

magaiti: т.к. будешь знать чекпоинт за следующим

Default avatar.png Mosha: Даже дрифтовать?) А как это?

magaiti: ну просто начинать разворачиваться до того как прошел чекпоинт

Default avatar.png Mosha: Господи, строить карту и начинать учитывать следующие чекпоинты, это же гениально! Осталось придумать, как это сделать) Но идея отличная, спасибо!