Chat:Ru/2020-08-16

From CG community
Jump to navigation Jump to search

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" Если туда нажать, можно вернуться на итоговую страничку клэша и дать на неё ссылку

Default avatar.png 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: хм, интересно, спасибо

Default avatar.png gtj: цветные графы меня целовали

Default avatar.png gtj: цветные графы шептали мне

Default avatar.png gtj: везде 1 бфс блин надо понять его хотя уже понял но задачи опять поменялись чтобы научится

Default avatar.png gtj: переписывать стал строка блин опять в инт не идет

Default avatar.png gtj: ни стой ни атой ничего не работает

Default avatar.png gtj: 3 в ряд идеал для бфс прям

Default avatar.png gtj: кое как допетрил) std::cout << (int)*it.str().c_str()<< std::endl;

Default avatar.png gtj: бфс все ближе)

tutubalin: wlesavo https://en.wikipedia.org/wiki/Xorshift

tutubalin: если в xorshift32 поменять xor на add, работает лучше

Default avatar.png gtj: пишут что барабан быстрее вроде

Default avatar.png gtj: как раз за счет ссе

Default avatar.png gtj: на асемблере чтоль покодить

Default avatar.png gtj: напишу графы и бфс на асемблере

Default avatar.png gtj: а си++ выведет ответ

wlesavo: tutubalin чет туплю, не пойму как сюда мод прикрутить

Uljahn: так смысл в том, чтобы избавиться от мода, не?

Default avatar.png gtj: Ульян смори чутка оптимизировал

Default avatar.png gtj: http://chat.codingame.com/pastebin/c22e504a-b6ac-41c6-ab5f-6f3976252066

Default avatar.png gtj: я придумал идею как по человечески просто просканировать лабиринт по крайней мере кажется

Default avatar.png gtj: и просто писать как двигался курсив по лабиринту и просто сравню потом все пути

Default avatar.png gtj: вот хотя это зипилив будет победа

Default avatar.png gtj: по крайней мере теперь я понимаю что делать надо а до этого не понимал)

wlesavo: Uljahn я имею ввиду как ограничить диапазон

tutubalin: wlesavo типа такого: ((uint64)random*N) >> 32

wlesavo: а, понял, спс

tutubalin: короче, это тоже самое, что вещественное число умножать на N и брать целую часть

tutubalin: просто у нас число с фиксированной запятой

wlesavo: ну да, я понял теперь уже, логично

Default avatar.png gtj: а никто не делал пространственные деревья напралений?

Default avatar.png gtj: квадро деревья

Default avatar.png gtj: почемуто кажется если уже класс проектировать как сенсор направлений в голову приходит почемуто 4 ноды

Default avatar.png gtj: сенсор отработал смысл идти в другую сторону

Default avatar.png gtj: хотя ладно буду разбираться походу тема емкая интересная

YurkovAS: выжал 100к из МС+

Uljahn: а что за МС+? опять я всё пропустил

YurkovAS: улучшенный монте карло :smile:

YurkovAS: понять бы, как сделать SA для игр типа samegame или number shifting, где невозможно поменять рандомный ход, т.к. после него остальные ходы могут быть уже совершенно другими.

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

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

wlesavo: типа 50/50 случайный или очередной в лучшем решении

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

wlesavo: кови добрал 130к онлайн, ничего так

Default avatar.png gtj: мне чтобы до мс дойти надо запилить сначало бфс я просто помню как нам его обьясняли вернее вспоминать начинаю и он был уже в конце как типо для развития

Default avatar.png gtj: а потом как раз плюсы начались)

Default avatar.png gtj: кто нибудь сталкивался с таким он показывает на фигурную скобку функции в самом конце с такой ошибкой нет преобразования "unsigned int (void) noexcept" в "unsigned int"

Default avatar.png gtj: переписал все в ансайнед все равно это или теперь надо во всем проекте ансайнед делать?

YurkovAS: делаю так: со 2-го хода запускаю МС на N раз, если получается лучше, то оставляю его. и т.д. к 3-му, потом 4-му ходам. как-бы пытается улучшить данное решение

YurkovAS: и это все применяется в основом цикле МС, для всех новых лучших решений (пытается их улучшить).

YurkovAS: wlesavo не пойму как делает? 1-ый ход берет случайный, а последующие из решения, как только в решении неправильные ходы, то доигрываем случайными?

YurkovAS: только 1-ый ход рандомит?

Default avatar.png gtj: URA

Default avatar.png gtj: :stuck_out_tongue::eggplant:

Default avatar.png gtj: я вкурил в дзен бфс

Default avatar.png gtj: http://chat.codingame.com/pastebin/a853396b-5feb-4f39-bc95-9c9a4bc53398

Default avatar.png gtj: надо просто пройтись и не морочится по всем нодам маркируя проход а я парился)

tutubalin: поздравляю!

Default avatar.png gtj: надо было всего найти даже не псевдокод а просто подробный как бы ну не алгоритм

Default avatar.png gtj: ну а как бы где интерпретация понятна

tutubalin: одно замечание: myNodes.find(temp)->second[i].first повторяется 4 раза. лучше присвоить в переменную - будет и быстрее, и читабельнее

Default avatar.png gtj: это да сделаю щас хочу на самом графе глянуть понять что он выводит

Default avatar.png gtj: всмысле путь глянуть с графом

Default avatar.png gtj: да это как по тому видео это 100% бфс

Default avatar.png gtj: буду дальше теперь курить

tutubalin: ещё пара замечаний: 1. в данный момент твой код выводит процесс поиска. это будет не сам кратчайший путь, а скорее дерево кратчайших путей 2. для поиска кратчайшего пути нужно знать конечную точку. и когда до неё добрались, останавливаться


Default avatar.png gtj: угу он как ли работает

Default avatar.png gtj: я проверил

Default avatar.png gtj: все пути пускает

Default avatar.png gtj: кароче как рендер

Default avatar.png gtj: ну в очереди кароче вищитирует метит и показывает на екран ноду

Default avatar.png gtj: текущую посещаемую им

Default avatar.png gtj: блин наконецто

Default avatar.png gtj: мне нужен был бфс

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

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

Default avatar.png gtj: спасибо напрягусь

YurkovAS: wlesavo спасибо, пытаюсь проверить

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

wlesavo: tutubalin не, поколений и популяции нет, есть только одно решение которое пытаются улучшить, ближе таки к sa

wlesavo: но да, то что кусок решения отрывается похоже на скрещивания

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

wlesavo: хотя секунду можно и онлайн потратить

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

wlesavo: ладно, доброй ночи

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

Default avatar.png gtj: заморочусь дерево еще напишу

Default avatar.png gtj: https://imgur.com/a/7ZwaJOB

Default avatar.png gtj: авлку не строит в ее виде потомучто с числами морочится надо генерировать

Default avatar.png gtj: а не это висит мод

Default avatar.png gtj: а понял это дфс как раз

Default avatar.png gtj: кстати инициализацию графа можно писать на асемблере както перекидывать граф в ++ и будет быстрее

Default avatar.png gtj: намного в 2 раза

zuko3d: ну-ну, я бы посмотрел твой код на ассемблере, который будет быстрее моего С++

zuko3d: за счёт чего там будет ускорение?

Default avatar.png gtj: вызови цену в отладке инициализация с графом дико дорогущая иза ребер

Default avatar.png gtj: 60+%

zuko3d: "вызови цену в отладке инициализация" не понял этого выказывания

Default avatar.png gtj: там будет ускорение за счет того что эти операция вывода на екран которые не нужны нам и первая инициализация и быстрее и не так много кода занимает

Default avatar.png gtj: плюс если не передавать управление а чисто на асме написать еще быстрее будет ток в те дебри я не лез я писал ток на асме и щас на с++

zuko3d: брр.... при чём тут количество кода и вывод на экран?

Default avatar.png gtj: а то в вижуале называется

Default avatar.png gtj: смотри

Default avatar.png gtj: http://chat.codingame.com/pastebin/74716ec9-5596-449b-ae35-bc9ef8d6d2b9

Default avatar.png gtj: это для 9 звездочек

zuko3d: ок, пока это не относится к графу никак

Default avatar.png gtj: да но можно загнать туда массив до обработки и выгнать оттуда граф чтобы его простроил асм именно прокинул ребра

Default avatar.png gtj: потомучто прокинуть ребра дорого щас скажу как отладке называется

zuko3d: как этот код вообще связан с графом? это же просто вывод на экран, причём написанный очень странно

Default avatar.png gtj: да

Default avatar.png gtj: да пофиг на код я про идею

Default avatar.png gtj: блин вчера ток делал окно там посмотреть код свой по стоимости

zuko3d: так а в чём идея-то? :) за счёт чего ускорение будет?

Default avatar.png gtj: щас порыщу получше в вижуале тут есть окошко теста кода

Default avatar.png gtj: и граффик стоимости

Default avatar.png gtj: хз мб за счет стека или каких фич асмовских плюс можно ж 64 битами напрямую прокидывать код

zuko3d: так, а что мешает всем этим опльзоваться, когда ты на С++ пишешь?

Default avatar.png gtj: тоесть к регистру обращаться как есть

Default avatar.png gtj: время идет на обращение

zuko3d: ну нет же

Default avatar.png gtj: на обращение вниз

Default avatar.png gtj: ну мб

zuko3d: есть же инлайнинг, не будет никакого вызова лишнего. И переменные все и так на регистрах лежат.

zuko3d: в общем, очень редко можно на асме написать код, который быстрее С++, обычно он будет строго медленнее

zuko3d: и сильно толще и хуже для понимания

Default avatar.png gtj: ммм

Default avatar.png gtj: кароче вчера нажал на чтото там можно было сделать тест своего кода и посмотреть где напряженка с кодом, какой запрос какое место занял в сводной таблице и прочее, щас не найду

Default avatar.png gtj: в вижуале

Default avatar.png gtj: в вижуал студио

Default avatar.png gtj: профилировщик производительности во

Default avatar.png gtj: во мейн крт стартап на первом месте а потом уник птр

Default avatar.png gtj: вчера мапа всех уделала

Default avatar.png gtj: 60% было

Default avatar.png gtj: новый инсерт ваще работает атас)

Default avatar.png gtj: ой не инсерт а перечисление)

Default avatar.png gtj: 8 % при строке из 33 элементов и внутри видимо простой цикл

Default avatar.png 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);

Default avatar.png gtj: http://chat.codingame.com/pastebin/e413c359-63ef-4eec-8ad2-859167b9335a

zuko3d: а ты в релизной сборке профилировщик запускаешь? если у тебя unique_ptr а первом месте после мейна - что-то идёт не так

Default avatar.png gtj: да нет все норм потомучто тут 33 символа через рекурсию долбятся а он выделяет место поидее не в дебаге

Default avatar.png gtj: в дебаге

Default avatar.png gtj: класс ваще тут даже чото проверяет в граффике

Default avatar.png gtj: чото профилирует тоже

Default avatar.png gtj: жаль что дикс12

Default avatar.png gtj: https://github.com/richkirl/graphkirk5/blob/master/graphkirk5/graphkirk5.cpp

Default avatar.png gtj: а чо нужно было тогда парню lc? тот кому llvm надо было

Default avatar.png gtj: встроено в визуалку кароче

Default avatar.png gtj: создать проект

Default avatar.png gtj: емпти проект

Default avatar.png gtj: создаешь елемент

Default avatar.png gtj: и если по русски визуалка на солюшене кликаешь зависимости сборки настроить зависимости сборки

Default avatar.png gtj: я вот к примеру щас асм кликнул там еще lc есть

Default avatar.png gtj: возможность написания самомодифицирующегося кода (то есть возможность приложению создавать или изменять часть своего кода во время выполнения, причем без необходимости программного интерпретатора);

Default avatar.png gtj: https://raw.githubusercontent.com/ThomasJaeger/VisualMASM/master/Images/main.png

Default avatar.png gtj: :sunglasses:

Default avatar.png gtj: http://lurkmore.to/%2B%2Bi_%2B_%2B%2Bi

Default avatar.png gtj: напишу бфс на асемблере)