vrabosh: TeeTeD, нажми compete потом bot programming внижу и выбири себе задачку, там поинетресней
vrabosh: https://www.codingame.com/multiplayer/bot-programming - или вот по этой ссылке переходит, и выбирай задачку.. тут интересней.
tutubalin: TeeTeD в Clash of Code есть три типа соревнований:
Fastest Mode - кто быстрее
Shortest Mode - кто короче
Reverse Mode - кто быстрее, но условия задачи не даны и надо догадаться самому по тестам
tutubalin: чтобы дать ссылку на закончившийся CoC, нажми на колокольчик в правом верхнем углу слева от аватарки
tutubalin: там будет что-то вроде "Clash Over! You're ranked 2/6"
Если туда нажать, можно вернуться на итоговую страничку клэша и дать на неё ссылку
gtj: Глаза режет читать твою помощ после нескольких дней унижений и оскорблений! Хоть бы тебя забанили
TeeTeD: Благодарю, не знал, что хоть где то есть такое комьюнити где все так объяснят
wlesavo: TeeTeD многие тут ради комьюнити сидят, заглядывай в #world тоже
YurkovAS: wlesavo 80k с MC
wlesavo: неплохо, я сейчас хочу попробовать фиксировать порядок цветов в рамках одного роллаута
wlesavo: YurkovAS tcnm ghjcnjq cgjcj, ifakbnm vfccbd d gk.cf[&
wlesavo: блин
wlesavo: есть простой способ шафлить массив в плюсах?
amurushkin: random_shuffle?
YurkovAS: про быстрые сдвиги не вкурсе.
wlesavo: хм, вообще один раз за роллаут можно наверное и встроенным рандомом
amurushkin: туда можно передать свой рандом. будет быстрее
wlesavo: не так уж и дорого
amurushkin: я на этой фишке в картах поднял чуток место
YurkovAS: а что ты там делаешь? это для постороения списка след. ходов?
zuko3d: всем привет, что нынче в тренде? раньше, помню, всё время CSB обсуждали
YurkovAS: привет. вот эту последние дни обсуждают
https://www.codingame.com/multiplayer/optimization/samegame
wlesavo: YurkovAS хочу попробовать сделать приоритет на убирание цветов, типа сначала по возможности убирать один, потом второй, итд, фиксировать порядок в начале роллаута
wlesavo: о, +16к сразу
wlesavo: неплохо так добавил
tutubalin: wlesavo посмотри семейство AVX2 команд PSHUFxxx
wlesavo: почти 50% прироста
YurkovAS: не пробовал такое.
wlesavo: tutubalin да это на один раз в роллауте, я думаю не сильно влияет
wlesavo: YurkovAS попробуй, мне прямо сильно дало в MC сейчас, правда у меня и было в два раза меньше чем у тебя
wlesavo: тем более добавить то это очень просто
YurkovAS: wlesavo у тебя рандом без "остатка от деления"?
wlesavo: да, фастранд тоже как в плейграунде
YurkovAS: inline int FastRand(int mod) { g_seed = (214013 * g_seed + 2531011); return (((g_seed >> 16) & 0x7FFF) * mod) >> 15; }
wlesavo: да, такое тоже
YurkovAS: вот этот проверь, во 2-ой части замена остатка от деления
YurkovAS: он быстрее
wlesavo: ну так у меня точ такое
YurkovAS: может у тебя "дискайнт"? у меня без него, скор, как в самой игре. а с дискаунтом было хуже. и сразу же завелось на 55к
YurkovAS: дискаунт*
wlesavo: да не, наверное просто роллаутов меньше, у меня много не оч эффективных мест
wlesavo: и я 50мс не использовал, ща добавил, гляну мож чуть поможет
YurkovAS: даст + 15к
wlesavo: сколько у тебя на 15ом тесте роллаутов на первом ходу?
YurkovAS: а роллаут это что - 1 раз дойти на рандомах до конца партии?
wlesavo: да
wlesavo: использование 50мс почти ничего не дало, +2к где-то, но мож это побочка фиксации цветов
YurkovAS: Standard Testset 15
110676
260
238
wlesavo: норм, у меня в два раза меньше
YurkovAS: что-то на 2 и 3 ходах так мало. у тебя столько же?
wlesavo: да, на 2-3 тоже мало, но это понятно, ходов до конца еще много а времени в 400 раз меньше
YurkovAS: мне 50мс дало +15к
потом подобных образом улучшил (что-то типа SA) и догнал до 85к
wlesavo: ну я вот тоже думаю прикрутить чтото типа SA
YurkovAS: оно же похоже на number shifting, я не понимаю как ты там его юзал. да и не вкурсе, 1 раз проверял в другой игре.
wlesavo: YurkovAS ты знал что этот тест сет стандартизированный и используется для бенчмаркинга алгоритмов на этой игре в разных статьях?
wlesavo: в этом смысле офлайн имеет право на жизнь
YurkovAS: круто
YurkovAS: смитс подтвердил, что у него 120к+ с мктс в онлайне
wlesavo: смитс вчера кидал таблицу мировых рекордов на каждом тесте
wlesavo: у кови тоже 120+ онлайн
wlesavo: но я не знаю на чем
tutubalin: этот рандом так себе. не самый быстрый и уж точно не самый рандомный
tutubalin: xorshift и быстрее и рандомнее
tutubalin: а если xor заменить на add, то почти проходит тест PR
wlesavo: tutubalin а есть ссылочка на реализацию?
YurkovAS: +
YurkovAS: тоже поменял seed и дало ~+5к (по таблице простых чисел)
YurkovAS: wlesavo спасибо!
Фича с убиранием по цветам дала +13к
wlesavo: YurkovAS круто! мне примерно столько же, я доволен что это не просто удача а хорошая эвристика :slight_smile:
YurkovAS: да, круто! :thumbsup:
YurkovAS: экспериментировал с ней и нормально работает только в одной части - МС, а во второй ~SA (попытка улучшить новое лучшее решеник) нет
wlesavo: хм, интересно, спасибо
gtj: цветные графы меня целовали
gtj: цветные графы шептали мне
gtj: везде 1 бфс блин надо понять его хотя уже понял но задачи опять поменялись чтобы научится
gtj: переписывать стал строка блин опять в инт не идет
gtj: ни стой ни атой ничего не работает
gtj: 3 в ряд идеал для бфс прям
gtj: кое как допетрил) std::cout << (int)*it.str().c_str()<< std::endl;
gtj: бфс все ближе)
tutubalin: wlesavo https://en.wikipedia.org/wiki/Xorshift
tutubalin: если в xorshift32 поменять xor на add, работает лучше
gtj: пишут что барабан быстрее вроде
gtj: как раз за счет ссе
gtj: на асемблере чтоль покодить
gtj: напишу графы и бфс на асемблере
gtj: а си++ выведет ответ
wlesavo: tutubalin чет туплю, не пойму как сюда мод прикрутить
Uljahn: так смысл в том, чтобы избавиться от мода, не?
gtj: Ульян смори чутка оптимизировал
gtj: http://chat.codingame.com/pastebin/c22e504a-b6ac-41c6-ab5f-6f3976252066
gtj: я придумал идею как по человечески просто просканировать лабиринт по крайней мере кажется
gtj: и просто писать как двигался курсив по лабиринту и просто сравню потом все пути
gtj: вот хотя это зипилив будет победа
gtj: по крайней мере теперь я понимаю что делать надо а до этого не понимал)
wlesavo: Uljahn я имею ввиду как ограничить диапазон
tutubalin: wlesavo типа такого:
((uint64)random*N) >> 32
wlesavo: а, понял, спс
tutubalin: короче, это тоже самое, что вещественное число умножать на N и брать целую часть
tutubalin: просто у нас число с фиксированной запятой
wlesavo: ну да, я понял теперь уже, логично
gtj: а никто не делал пространственные деревья напралений?
gtj: квадро деревья
gtj: почемуто кажется если уже класс проектировать как сенсор направлений в голову приходит почемуто 4 ноды
gtj: сенсор отработал смысл идти в другую сторону
gtj: хотя ладно буду разбираться походу тема емкая интересная
YurkovAS: выжал 100к из МС+
Uljahn: а что за МС+? опять я всё пропустил
YurkovAS: улучшенный монте карло :smile:
YurkovAS: понять бы, как сделать SA для игр типа samegame или number shifting, где невозможно поменять рандомный ход, т.к. после него остальные ходы могут быть уже совершенно другими.
wlesavo: YurkovAS у меня в NS было так, для каждого тайла записано направление в котором я буду его пытаться двигать. дальше по очереди пытаюсь подвинуть, если не получилось то переставляю в конец очереди, итд пока не останется легитимных ходов.
wlesavo: здесь как вестиклс говорил что делает случайный ход, и дальше продолжает делать ходы из изначального набора до тех пор пока они не станут нелегитимными, когда стали то просто доигрывает партию случайными ходами, периодически проверяя хвост лучшего решения
wlesavo: типа 50/50 случайный или очередной в лучшем решении
wlesavo: я так понял ты хвост отрезаешь и доигрываешь его случайно, фактически это тоже SA просто мутации не такие незначительные и это ближе к MC
wlesavo: кови добрал 130к онлайн, ничего так
gtj: мне чтобы до мс дойти надо запилить сначало бфс я просто помню как нам его обьясняли вернее вспоминать начинаю и он был уже в конце как типо для развития
gtj: а потом как раз плюсы начались)
gtj: кто нибудь сталкивался с таким он показывает на фигурную скобку функции в самом конце с такой ошибкой нет преобразования "unsigned int (void) noexcept" в "unsigned int"
gtj: переписал все в ансайнед все равно это или теперь надо во всем проекте ансайнед делать?
YurkovAS: делаю так: со 2-го хода запускаю МС на N раз, если получается лучше, то оставляю его.
и т.д. к 3-му, потом 4-му ходам.
как-бы пытается улучшить данное решение
YurkovAS: и это все применяется в основом цикле МС, для всех новых лучших решений (пытается их улучшить).
YurkovAS: wlesavo не пойму как делает? 1-ый ход берет случайный, а последующие из решения, как только в решении неправильные ходы, то доигрываем случайными?
YurkovAS: только 1-ый ход рандомит?
gtj: URA
gtj: :stuck_out_tongue::eggplant:
gtj: я вкурил в дзен бфс
gtj: http://chat.codingame.com/pastebin/a853396b-5feb-4f39-bc95-9c9a4bc53398
gtj: надо просто пройтись и не морочится по всем нодам маркируя проход а я парился)
tutubalin: поздравляю!
gtj: надо было всего найти даже не псевдокод а просто подробный как бы ну не алгоритм
gtj: ну а как бы где интерпретация понятна
tutubalin: одно замечание: myNodes.find(temp)->second[i].first повторяется 4 раза.
лучше присвоить в переменную - будет и быстрее, и читабельнее
gtj: это да сделаю щас хочу на самом графе глянуть понять что он выводит
gtj: всмысле путь глянуть с графом
gtj: да это как по тому видео это 100% бфс
gtj: буду дальше теперь курить
tutubalin: ещё пара замечаний:
1. в данный момент твой код выводит процесс поиска. это будет не сам кратчайший путь, а скорее дерево кратчайших путей
2. для поиска кратчайшего пути нужно знать конечную точку. и когда до неё добрались, останавливаться
gtj: угу он как ли работает
gtj: я проверил
gtj: все пути пускает
gtj: кароче как рендер
gtj: ну в очереди кароче вищитирует метит и показывает на екран ноду
gtj: текущую посещаемую им
gtj: блин наконецто
gtj: мне нужен был бфс
wlesavo: YurkovAS не совсем, берется лучшее на данный момент решение, в нем берется случайный ход, например в середине где-то, делается этот случайный ход и дальше пытается делать те же ходы что и в лучшем решении. это будет не всегда возможно, потому что стол другой уже, и когда попадется невалидный ход доигрывается рандомом. там у него еще детали всякие, но основная суть такая
tutubalin: 3. чтобы вывести именно путь, нужно для каждой клетки запоминать, откуда мы в неё пришли
затем начать с конца восстановить путь
gtj: спасибо напрягусь
YurkovAS: wlesavo спасибо, пытаюсь проверить
tutubalin: wlesavo это ж почти генетический алгоритм получается
wlesavo: tutubalin не, поколений и популяции нет, есть только одно решение которое пытаются улучшить, ближе таки к sa
wlesavo: но да, то что кусок решения отрывается похоже на скрещивания
wlesavo: YurkovAS плюс он вроде сначала чистым MC ищет хорошее решение секунду, в офлайне можно себе позволить, и уже потом улучшает
wlesavo: хотя секунду можно и онлайн потратить
wlesavo: если что расскажешь потом что получилось, я уже разве что над офлайн версией поработаю, онлайн врядли буду теребить
wlesavo: ладно, доброй ночи
YurkovAS: да, расскажу, что получится.
доброй ночи
gtj: заморочусь дерево еще напишу
gtj: https://imgur.com/a/7ZwaJOB
gtj: авлку не строит в ее виде потомучто с числами морочится надо генерировать
gtj: а не это висит мод
gtj: а понял это дфс как раз
gtj: кстати инициализацию графа можно писать на асемблере както перекидывать граф в ++ и будет быстрее
gtj: намного в 2 раза
zuko3d: ну-ну, я бы посмотрел твой код на ассемблере, который будет быстрее моего С++
zuko3d: за счёт чего там будет ускорение?
gtj: вызови цену в отладке инициализация с графом дико дорогущая иза ребер
gtj: 60+%
zuko3d: "вызови цену в отладке инициализация" не понял этого выказывания
gtj: там будет ускорение за счет того что эти операция вывода на екран которые не нужны нам и первая инициализация и быстрее и не так много кода занимает
gtj: плюс если не передавать управление а чисто на асме написать еще быстрее будет ток в те дебри я не лез я писал ток на асме и щас на с++
zuko3d: брр.... при чём тут количество кода и вывод на экран?
gtj: а то в вижуале называется
gtj: смотри
gtj: http://chat.codingame.com/pastebin/74716ec9-5596-449b-ae35-bc9ef8d6d2b9
gtj: это для 9 звездочек
zuko3d: ок, пока это не относится к графу никак
gtj: да но можно загнать туда массив до обработки и выгнать оттуда граф чтобы его простроил асм именно прокинул ребра
gtj: потомучто прокинуть ребра дорого щас скажу как отладке называется
zuko3d: как этот код вообще связан с графом? это же просто вывод на экран, причём написанный очень странно
gtj: да
gtj: да пофиг на код я про идею
gtj: блин вчера ток делал окно там посмотреть код свой по стоимости
zuko3d: так а в чём идея-то? :) за счёт чего ускорение будет?
gtj: щас порыщу получше в вижуале тут есть окошко теста кода
gtj: и граффик стоимости
gtj: хз мб за счет стека или каких фич асмовских плюс можно ж 64 битами напрямую прокидывать код
zuko3d: так, а что мешает всем этим опльзоваться, когда ты на С++ пишешь?
gtj: тоесть к регистру обращаться как есть
gtj: время идет на обращение
zuko3d: ну нет же
gtj: на обращение вниз
gtj: ну мб
zuko3d: есть же инлайнинг, не будет никакого вызова лишнего. И переменные все и так на регистрах лежат.
zuko3d: в общем, очень редко можно на асме написать код, который быстрее С++, обычно он будет строго медленнее
zuko3d: и сильно толще и хуже для понимания
gtj: ммм
gtj: кароче вчера нажал на чтото там можно было сделать тест своего кода и посмотреть где напряженка с кодом, какой запрос какое место занял в сводной таблице и прочее, щас не найду
gtj: в вижуале
gtj: в вижуал студио
gtj: профилировщик производительности во
gtj: во мейн крт стартап на первом месте а потом уник птр
gtj: вчера мапа всех уделала
gtj: 60% было
gtj: новый инсерт ваще работает атас)
gtj: ой не инсерт а перечисление)
gtj: 8 % при строке из 33 элементов и внутри видимо простой цикл
gtj: root.insert(4,5,3,2,1,6,7,16,8,19,9,25,10,26,11,27,12,20,13,21,14,22,17,28,23,29,31,30,32,33,24,18,15);
gtj: http://chat.codingame.com/pastebin/e413c359-63ef-4eec-8ad2-859167b9335a
zuko3d: а ты в релизной сборке профилировщик запускаешь? если у тебя unique_ptr а первом месте после мейна - что-то идёт не так
gtj: да нет все норм потомучто тут 33 символа через рекурсию долбятся а он выделяет место поидее не в дебаге
gtj: в дебаге
gtj: класс ваще тут даже чото проверяет в граффике
gtj: чото профилирует тоже
gtj: жаль что дикс12
gtj: https://github.com/richkirl/graphkirk5/blob/master/graphkirk5/graphkirk5.cpp
gtj: а чо нужно было тогда парню lc? тот кому llvm надо было
gtj: встроено в визуалку кароче
gtj: создать проект
gtj: емпти проект
gtj: создаешь елемент
gtj: и если по русски визуалка на солюшене кликаешь зависимости сборки настроить зависимости сборки
gtj: я вот к примеру щас асм кликнул там еще lc есть
gtj: возможность написания самомодифицирующегося кода (то есть возможность приложению создавать или изменять часть своего кода во время выполнения, причем без необходимости программного интерпретатора);
gtj: https://raw.githubusercontent.com/ThomasJaeger/VisualMASM/master/Images/main.png
gtj: :sunglasses:
gtj: http://lurkmore.to/%2B%2Bi_%2B_%2B%2Bi
gtj: напишу бфс на асемблере)
gtj: Глаза режет читать твою помощ после нескольких дней унижений и оскорблений! Хоть бы тебя забанили
