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: проверка что поды сближаются
Lobs: кто по си шарпу????
amurushkin: лучше сразу вопрос задавай
Lobs: бляяяя
Lobs: тут джс нету
Lobs: я тут по пайтону и как тут решать вообще
magaiti: джс это что? JavaScript есть
magaiti: берешь и решаешь
magaiti: начни с простых пазлов
magaiti: onboarding, descent
Lobs: спс
magaiti: я загрыз игги
magaiti: кто следующий?
amurushkin: о 8 лямов наколядовал
IlyaP: softpro
magaiti: https://www.codingame.com/replay/492442581
magaiti: 179 ход неплохо запульнул
Mosha: magaiti, привет, а что это за числа, рядом со звёздочками?
Uljahn: в пазлах?
Mosha: Uljahn не, в гонках на pod-ах
Uljahn: рейтинг в лидерборде, если ты про звёздочку рядом с ником
Uljahn: magaiti: на два раннера перешёл?
magaiti: не, просто блокер ранит, если больше делать нечего
Uljahn: вообще, неплохо выглядит
magaiti: ну я немного улучшил, в топ 10 влез
Mosha: Понял, спасибо! У меня встал один вопрос, так сказать. Я соверешенно не могу выкупить, почему раздел называется AI а модельку я ему сам пишу? Это норм? Не должны всякие эти параметры сами обучаться?
magaiti: так стоп, а что за звездочки?
magaiti: чет я сам не в курсе
magaiti: куда смотреть
Mosha: А ещё я никак не могу понять, почему рейтинг решения задачи зависит от того, сколько соревнований на арене было?
Mosha: Я зашёл посмотреть твой реплей, и там ниже твой ник, звёздочка и число, что-то около 44
magaiti: а ты в каком разделе? bot programming?
magaiti: а ясно
Uljahn: под реплеем у того, кто выиграл заезд, звёздочка рядом с ником, у проигравшего квадрат
magaiti: ясненько
magaiti: рейтинг, да. в реплее я против более слабого
Mosha: Я в какой-то момент просто нажал на AI на стартовом экране с ачивками, он кинул меня на coders strike back...
Mosha: Вопрос, как этот рейтинг рассчитывается? Типа, он проводит N соревнований, и выдаёт результат?
magaiti: ну ты программируешь бота, он сражается против других ботов, около 100 дуэлей
magaiti: и по резултьатам получает рейтинг
magaiti: от рейтинга зависит сколько очков ты заработаешь
magaiti: да, N дуэлей, выбирается случайно из ближайших по рейтингук
magaiti: если победил более сильного, получаешь больше, проиграл слабому -теряешь больше
Uljahn: угу, рейтинг по формуле TrueSkill рассчитывается
Uljahn: или даже алгоритму
magaiti: от удачи часто тоже зависит
magaiti: но всегда можно ресабмитнуть, если тебе показалось что неудачно выступил
magaiti: насчет модельки я не понял. симуляцию нужно самому писать?
magaiti: это да
magaiti: но ест ьпримеры по ссылкам в описании задачи
Uljahn: само ничего не обучается, только матчмейкинг автоматический
magaiti: даже с кодом
Mosha: Понял, спасибо большое! Ага, удача тут тоже часто роль играет... Окей, а такой вопрос, правда, что чем выше лига, тем больше параметров есть для управления. И ещё кое-что. Правда, что для выхода в лигу выше нужно набить определённый рейтинг в своем?
magaiti: да, под AI здесь это понимаетмся просто алгоритм который ты сделаешь
magaiti: нужно победить босса
Mosha: Понял, не обучается и ладно, Бог с ним
magaiti: то есть по рейтингу его выше быть в конце
Mosha: То есть, побеждать его в каждой схватке, условно говоря?
magaiti: не, просто после того как 100% дуэлей сделаешь, чтоб твой рейтинг был больше чем у босса
Mosha: Понял-принял, спасибо большое!
Uljahn: новые правила каждую лигу добавляют в гоночках, окончательные правила в золотой лиге, в легенде только ускорение побольше будет
magaiti: да, чем выше лига, тем больше дают параметров. но самое главное - быстро ездить по чекпоинтам
magaiti: до легенды можно концентрироваться только на езде
magaiti: в легенде уже тактика
Mosha: Окей, спасибо, товарищи!
Mosha: А можно несколько стратегический вопрос, я не совсем понимаю, для чего лучше использовать буст, и как обращаться с тем, что корабли теперь сталкиваются... Правильно я понимаю, что буст нужно оставить для прямых длинных участков? И как толкаться?
Mosha: Или бустом нужно бороться?
Mosha: Или это уже моя фантазия?)
magaiti: буст для длинных участков. можно первым ходом
magaiti: толкаться это уже тактика, лучше быстро ездить
magaiti: толкаться щитом можно, но сложно научить
magaiti: чтоб грамотно использовать
magaiti: можешь поэкспериментировать
Mosha: У меня ещё нет щита) Просто я и использовал буст на первом, но он часто пролетает далеко за первый чек-поинт
magaiti: но один буст за игру не спасет, если противник тебя быстрее
Mosha: Да я что-то весь вечер экспериментирую, но каждое нововведение долго обкатывается... Это да, один буст, скорее, как приятное дополнение)
magaiti: если за первый пролетает, лучше сохранить на длинный участок, или на рывок на последний чекпоинт
magaiti: результат буста в противника сложно предсказать, он же тоже маневрирует
Mosha: Просто я не очень понимаю, как он отслеживает количество пройденных чекпоинтов. Этой информации же не предоставляется
magaiti: ну координаты чекпоинта меняются
magaiti: сохраняй и сравнивай
Mosha: Вот да, это и смущает, тупо буст в противника делать, иногда, себе дороже
Mosha: Да, но количество чек поинтов от карты к карте меняется же
magaiti: ну значит храни все, и сравнивай, на 2-й круг начнут повторяться
magaiti: и тогда уже можно дрифтовать
magaiti: т.к. будешь знать чекпоинт за следующим
Mosha: Даже дрифтовать?) А как это?
magaiti: ну просто начинать разворачиваться до того как прошел чекпоинт
Mosha: Господи, строить карту и начинать учитывать следующие чекпоинты, это же гениально! Осталось придумать, как это сделать) Но идея отличная, спасибо!
Lobs: кто по си шарпу????
