Chat:Ru/2020-08-01

From CG community
Jump to navigation Jump to search

735487: YurkovAS привет ты тут. расскажи в чем фишка в Search Race? у меня почему то не всегда валидаторы 100% получают. уже до 40мс время убрал. какой алгоритм там для поиска у тебя?

YurkovAS: amurushkin привет. сима там немного другая (не как в csb, см рефери). тайминг у меня 38мс, но у других вроде как 35мс.

YurkovAS: алгоритм - га

735487: о как неожиданно. а написано вроде лимит 50. неужели так плохо лимит там меряют

735487: надо посмотреть рефери тогда да. почему то подумал что такая же сима

735487: спасибо за подсказку

YurkovAS: странно, ресабмитнул 2 предыдущие версии и обе не набирают 100%

YurkovAS: еще там 3 разных проца, один раз просто ресабмит улучшил не пару мест

YurkovAS: с 35мс набрал 100% и результат немного хуже, чем в таблице.

735487: вот и я пока 100% наберу надо полдня сабмитить

shegeley: Skynet Revolution - Episode 1

кто решил? сначала написал неоптимизированное решение, потом, казалось, нормальное, но все равно фейл по таймингу

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

shegeley: Но все равно фейлится.

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

Default avatar.png jiki: в питоне сеты есть?

amurushkin: конечно

Default avatar.png jiki: Амур помоги плис

Uljahn: это же базовые структуры данных, они во всех языках есть, наверное

amurushkin: с чем помочь?

Default avatar.png jiki: написал функцию перегонки буквы в биты 7 мер

Default avatar.png jiki: в строке нормально все

Default avatar.png jiki: а я хочу из строки через буфер перегнать в число

Default avatar.png jiki: 2147483647

Default avatar.png jiki: не дает это сделать

Default avatar.png jiki: с 1 числом только работает

Default avatar.png jiki: 2 и более такое магическое число подставляет

Uljahn: ты уверен, что в строке на каждый символ один байт выделен?

Default avatar.png jiki: что ты хочешь сказать?

amurushkin: не очень понятно что у тебя на входе

Default avatar.png jiki: строка

Default avatar.png jiki: 1 символ

Default avatar.png jiki: с 1 символом работает с более символами нет

Default avatar.png jiki: http://chat.codingame.com/pastebin/dccc2ed1-ab57-493e-acb2-8f654f079fad

Uljahn: это хороший повод подучить работу со строками

Default avatar.png jiki: ага

Uljahn: не надо в чате спрашивать то, что можно нагуглить за 5 минут

Default avatar.png jiki: а что гуглить?

Default avatar.png jiki: я нен пойму что ты сказать хочешь?

Uljahn: как итерировать по символам строки, наверное. хз чё ты там делаешь

Default avatar.png jiki: Ульян кто вопрос задал ты или я?

amurushkin: да итерация по строке очень странная

Default avatar.png jiki: по какой?

amurushkin: for (auto a : message) не работает так разве?

Default avatar.png jiki: итерацция нормальная

Default avatar.png jiki: если про первый цикл

Default avatar.png jiki: трабла не тут

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

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

amurushkin: из строки в число это по моему atoi и не надо буферов

Default avatar.png jiki: ты у меня спрашиваешь

amurushkin: в крайней случае можно черзе printf

Default avatar.png jiki: атой я гуглил не работает

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

Default avatar.png jiki: стой работает

Default avatar.png jiki: stoi работает только

Default avatar.png jiki: не надо буферов окей

amurushkin: ну вот.

Default avatar.png jiki: он так же отрабатывает

Default avatar.png jiki: а как ты числа переводишь из строки в число

amurushkin: на riscos там у меня atoi не было я черзе printf делал

Default avatar.png jiki: for (auto a : mesage) равнозначна моей записи

Default avatar.png jiki: он в строку то превращает

Default avatar.png jiki: все символы

Default avatar.png jiki: а вот из строки в число только если в исходной строке 1 елемент

Default avatar.png jiki: щас попробую стой атой

Default avatar.png jiki: 1427134923

Default avatar.png jiki: а стой вот что пишет

Default avatar.png jiki: http://chat.codingame.com/pastebin/3c5e1365-411d-490d-bf29-1e9b5d8baab4

Default avatar.png jiki: а значение принтф ты записывал в переменную?

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

Default avatar.png jiki: просто вместо каута буфер

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

Default avatar.png jiki: bitset<7> b(*a);

      stream << b;

Default avatar.png jiki: ты про это?

Default avatar.png jiki: а щас попробую

Default avatar.png jiki: bitset<7> b(*a);

      stream << b.to_string();

Default avatar.png jiki: тот же еффект а если в лонг пилить то 67 выдает

Default avatar.png jiki: http://chat.codingame.com/pastebin/6a71dd01-f364-4a8a-a6a2-6f57a16a80e1

Default avatar.png jiki: 10000111000011-48-48-80-71-49-49-4979-48-48-50 такой вывод

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

Default avatar.png jiki: в стрим?

Default avatar.png jiki: nfrc

Default avatar.png jiki: такс

Default avatar.png jiki: щас я подтвержу что в первом цикле все нормас

Default avatar.png jiki: http://chat.codingame.com/pastebin/a7f834c0-e757-41a8-a7a2-73edd74bf29e

Default avatar.png jiki: валик показывает

Default avatar.png jiki: все как надо

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

YurkovAS: крестики пилишь?

Default avatar.png jiki: нет чак нориса

YurkovAS: :thumbsup:

YurkovAS: крестики тоже интересно - mcts и bitboards, там много простора для оптимизаций

Default avatar.png jiki: я не понимаю мктс вернее понимаю но не понимаю как его реализовать

Default avatar.png jiki: https://www.youtube.com/watch?v=LYs6bfocYxc

Default avatar.png jiki: посмотрел я видео

Default avatar.png jiki: говорит все понятно

Default avatar.png jiki: открываю вики не понятно

YurkovAS: я делал по этим двум ссылкам https://www.baeldung.com/java-monte-carlo-tree-search https://github.com/Oreshnik/MCTS_TTT

Default avatar.png jiki: ну а тебя точно монте карло?

Default avatar.png jiki: как ты рандом проверяешь?

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

tutubalin: да пускай чака сперва сделает

YurkovAS: mcts

YurkovAS: да, доделай чака

Default avatar.png jiki: ну для снимка нужен чоткий рандом

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

tutubalin: юбя

tutubalin: упс

Default avatar.png jiki: да я знаю как задачку сделать

Default avatar.png jiki: cout << stream.str().c_str() << endl;

tutubalin: для проверки рандома есть тесты, например Practically Random

Default avatar.png jiki: а если превращаю ее в числа то тут мусора много

Default avatar.png jiki: я за это время даже в шейдеры вььехал уже

Default avatar.png jiki: а эту бадягу не пойму никак

Default avatar.png jiki: в строке нет мусора

Default avatar.png jiki: щас в строку скопирую хз

Default avatar.png jiki: а стопе

Default avatar.png jiki: ненадо в числа)

Default avatar.png jiki: в числа это уже перебор

Default avatar.png jiki: tutubalin и что прям снимок получаешь как в этом видео про газы говорят?

Default avatar.png jiki: я про мктс

Default avatar.png jiki: например в тех же крестиках

Default avatar.png jiki: я смотрю вики похоже на авл

Default avatar.png jiki: тоесть просто заполняю дерево

Default avatar.png jiki: потом я его я так понимаю фиксирую

Default avatar.png jiki: балансю

Default avatar.png jiki: и что дальше?

Default avatar.png jiki: например 3 на 3

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

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

Default avatar.png jiki: дерево понимаю сбалансить дерево тоже

Default avatar.png jiki: получается корень 0 0

Default avatar.png jiki: или центр

Default avatar.png jiki: как в жл тут пока понимаю

Default avatar.png jiki: конкретики не понимаю кароче

Default avatar.png jiki: потом если допру до мкст рандом градиентами заменю

Default avatar.png jiki: мне интересно

Default avatar.png jiki: я так подозреваю без гч реального надо градиенту брать

Default avatar.png jiki: потомучто софт гч не стабилен

tutubalin: минимакс знаешь?

Default avatar.png jiki: нет пока ниче не знаю но из слов более менее понятно но к конкретике нет

tutubalin: игры типа крестиков, шашок, шахмат и т.д. легко раскладываются в дерево

tutubalin: есть начальное состояние. из него возможные ходы. из них возможные ходы противника

tutubalin: и так далее

tutubalin: есть построить полное дерево, то можно найти беспроигрышную или выигрышную стратегию

tutubalin: для простых крестиков 3х3 это можно сделать на бумаге

Default avatar.png jiki: стой

Default avatar.png jiki: погоди

Default avatar.png jiki: предположим 00 слева сверху

Default avatar.png jiki: ну ок я понял считал размер дерева 1 раунд я прочел состояние

Default avatar.png jiki: заьил число противника куда поставил в дерево

Default avatar.png jiki: аааааа

Default avatar.png jiki: ты хочешь сказать что загоняем x y в дерево

tutubalin: нет

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

tutubalin: я не понимаю твою мысль

Default avatar.png jiki: за нарисую скину скрин секу

Default avatar.png jiki: https://imgur.com/a/35ooYRz

Default avatar.png jiki: 2,2 там внизу

tomatoes: текущее состояние это корень дерева. есть 5 вариантов хода => делаешь из корня 5 ветвей в которых сделаны соответствующие ходы

Default avatar.png jiki: исходя из твоей логики не 5

Default avatar.png jiki: а либо 9 либо 8

Default avatar.png jiki: либо 8 либо 8

Default avatar.png jiki: если я в центре

tutubalin: из корня 9

Default avatar.png jiki: смотрю значение и все поле в дереве

tutubalin: из каждого из детей 8

YurkovAS: jiki примерно так дерево строится https://www.youtube.com/watch?v=QH9h-XSi5nw&feature=youtu.be&t=462

Default avatar.png jiki: отросток в данном случае это корень результат который мы смотрим

Default avatar.png jiki: а почему все поле не проинициализировать?

YurkovAS: да, от корня и в глубину (на много ходов)

Default avatar.png jiki: пока не понимаю

Default avatar.png jiki: тоесть я стилусом вожу

Default avatar.png jiki: моя рука это паренты

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

Default avatar.png jiki: кончик стилуса рут

YurkovAS: но и худшим ходам, дается шанс, но редко

Default avatar.png jiki: а как ты узнаешь куда стилусом направляет твой корень?

tomatoes: https://i.imgur.com/L6uAKBD.png

YurkovAS: https://www.baeldung.com/java-monte-carlo-tree-search прочитай внимательно статью и сделай как тут. в процессе поймешь, как оно примерно работает

Default avatar.png jiki: аааа

Default avatar.png jiki: как папки

Default avatar.png jiki: на каждое решение своя ветка

Default avatar.png jiki: вот щас более менее понял

YurkovAS: в tomatoes-а примере видно, что дерево не все развернуто. в этом и есть главная фича алгоритма.

Default avatar.png jiki: диагоналей нету

Default avatar.png jiki: это нормально?

Default avatar.png jiki: там вроде диагонали тоже считаются за страту

Default avatar.png jiki: кстати если как у томата мктс то нам преподовали такое

Default avatar.png jiki: получается это лес решений

Default avatar.png jiki: надо построить лес решений исходя из текущего значения поля

BorisZ: jiki забудь про MCTS пока до золотой лиги не дойдешь, сосредоточся на ближайшей задаче - выйти из вуда

BorisZ: для этого достаточно просто делать случайные валидные ходы

BorisZ: ну может еще что-то подкрутить

YurkovAS: разве? у меня сначала был миник, с ним так и не вышел из золота. долго ускорял...

YurkovAS: да и с мктс-ом не сразу из золота выйдет.

BorisZ: я говорю - пока не дойдет до золота

YurkovAS: а как с рандомами, просто выбрать любой рандомный ход?

BorisZ: я не уверен что получится так

YurkovAS: ну может быть. только мне кажется он так далеко не уйдет.

BorisZ: может нужно еще какой-нибудь твик добавить

YurkovAS: миник можно. там тоже интересно - оценочную сделать и поускорять все это дело.

BorisZ: да, я тоже миник делал сначала

BorisZ: но надо хоть правила игры увидеть для этого, а они в бронзе

tutubalin: из вуда достаточно рандома

Default avatar.png jiki: нет там р=лорен ловит и сечет

Default avatar.png jiki: уже не достаточно рандома

Default avatar.png jiki: он на втором месте

Default avatar.png jiki: 3 дня сабмит нажимал и три он меня сёк

Default avatar.png jiki: три дня

Default avatar.png jiki: не дает выти

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

Default avatar.png jiki: а пока ты нарандомишь винстрик он 1 место и бос я хз скоко дней рандомить надо)

Default avatar.png jiki: это да видимо есть такое

BorisZ: хотя список валидных ходов на каждый ход приходит прямо в инпуте

BorisZ: сохранил в список и выбрал случайный ну или не совсем случайный

Default avatar.png jiki: ааа

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

Default avatar.png jiki: теперь понял что такое мктс

Default avatar.png jiki: даже могу закодить его

Default avatar.png jiki: еще 1 фичу попробую из стандарта

Default avatar.png jiki: и намучу мктс

BorisZ: ну молодец, я вот до сих пор не понял

Default avatar.png jiki: томатос показал же

Default avatar.png jiki: это называется лес решений

Default avatar.png jiki: дерево просто быстрее других типов работает

Default avatar.png jiki: ты можешь сделать массивы решений

Default avatar.png jiki: и убедиться что дерево быстрее

BorisZ: ну посмотри где томатос в лидерборде

Default avatar.png jiki: где

Default avatar.png jiki: ну а ты сделай градиентой

Default avatar.png jiki: лес решений

Default avatar.png jiki: от рандома надо уходить у нас нет реализации гч это все поделка

Uljahn: :pensive:

BorisZ: угу, заговр рептилоидов

Default avatar.png jiki: настоящий гсч это коробка

BorisZ: подсовывают нам случайные числа второй свежести

BorisZ: билл гейтс всяко руку приложил

Default avatar.png jiki: нет просто гсч по ачх не проходит его надо оптимизировать

Default avatar.png jiki: частота совпадений у софтового гсч велика

Default avatar.png jiki: а должна быть 50%

Default avatar.png jiki: я сейчас про генерацию последовательностей

BorisZ: для чего-то может и не подходит, а для всех реальных задач - вполне

BorisZ: даже наоборот - упрощают его для скорости

Default avatar.png jiki: с дополнительными алгоритмами проверки

Default avatar.png jiki: и фикс рандома

Default avatar.png jiki: я сам так сделал

Default avatar.png jiki: в змейке

Uljahn: "для проверки рандома есть тесты, например Practically Random"

Default avatar.png jiki: нифига он не нормальный

Default avatar.png jiki: ну там эти алгоритмы которые у меня

Default avatar.png jiki: в змейке пресловутой

Default avatar.png jiki: фиксят в игре

Default avatar.png jiki: прям в коде

BorisZ: да наплевать нормальный или нет, сосредоточся на задаче текущей

Default avatar.png jiki: потомучто он заходит за зону допустимых значений даже если указать зону ему

BorisZ: сохранить ходы в список, выбрать случайный элемент

BorisZ: любой свежести

Default avatar.png jiki: я уверен в играх где

Default avatar.png jiki: бокс

Default avatar.png jiki: или точка

Default avatar.png jiki: с шансом

Default avatar.png jiki: 9 7 5 4 2 1 1 (%)

Default avatar.png jiki: это градиенты

Uljahn: в каком смысле?

Default avatar.png jiki: они уже в памяти или хз как там это обратывается

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

Uljahn: что такое градиенты, от чего?

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

Default avatar.png jiki: от евента

BorisZ: качество ГСЧ неважно для 99% задач, для крестиков точно не важно

Default avatar.png jiki: от евента игрока

Default avatar.png jiki: опр типа

Default avatar.png jiki: точка или открыть кейс

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

Default avatar.png jiki: которого быть не может в игре с 9 гигабайтами

Default avatar.png jiki: часть которого это мапы и шейдеры

Default avatar.png jiki: соответственно проще сделать сразу градиенты от ивента и хранить все в одной строке

Default avatar.png jiki: пофиксил все точнулись

Default avatar.png jiki: вернул обратно нет

Uljahn: :confused:

Default avatar.png jiki: градиенту щас посчитаю что это такое

Default avatar.png jiki: производная

Default avatar.png jiki: вектор

Default avatar.png jiki: вполне похоже на правду

Default avatar.png jiki: можно в шейдере его хранить прям

tomatoes: каши захотелось

Default avatar.png jiki: шейдер евентов

Default avatar.png jiki: шейдер компилируется ж

Default avatar.png jiki: там векторы есть

BorisZ: Шейдер Градиентович Евентов

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

Default avatar.png jiki: и там можно по градиентам сразу на лету сделать 100% гсч градиентный

Default avatar.png jiki: нарисовать иными словами

Default avatar.png jiki: нарисовать шансы

Uljahn: хватит бредить, покажи код

Default avatar.png jiki: щас покажу что делать надо чтобы так было

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

Default avatar.png jiki: вот 1 из них

Default avatar.png jiki: на каждый столбец своя вероятность события

Default avatar.png jiki: https://exceltip.ru/wp-content/uploads/2015/01/95-8-%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D0%BA-%D1%81-%D0%BD%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%BC-%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5%D0%BC.png

Default avatar.png jiki: тоесть каждый столбец является текущим если точек 9

Default avatar.png jiki: то будет идти от 1 стоблца и так пока не доточится

Default avatar.png jiki: теперь представь там такой шейдер ты вбиваешь проценты

Default avatar.png jiki: график построился скомпилировался

Default avatar.png jiki: и ты не обойдешь эти проценты

Default avatar.png jiki: будет ровно 1%

Default avatar.png jiki: если указать 1%

YurkovAS: будет ровно 0, в крестиках)

Default avatar.png jiki: Юрков я просто не знаю как это называется

Default avatar.png jiki: но полюбасу такое есть

Default avatar.png jiki: теоретически на сервере это может делать видео обработка

Default avatar.png jiki: графическая станция

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

Default avatar.png jiki: ну вот

Default avatar.png jiki: знач я близок к истине

Default avatar.png jiki: интуиция мать его

Default avatar.png jiki: я это в змейке заметил что раном простой заходит за границы потом Ульян навел на градиенты

Default avatar.png jiki: потом я посмотрел икс джи

Default avatar.png jiki: вник чутка в шейдеры

Default avatar.png jiki: и пазл сошелся

Uljahn: на сколько процентов?

Default avatar.png jiki: ну смотри шейдер компилируется

Default avatar.png jiki: потом если шейдер тени может править

Default avatar.png jiki: туман и прочее

Default avatar.png jiki: запускать в опр координатах вьювера музыку

Default avatar.png jiki: то примерно на 95%

Default avatar.png jiki: тебе же не дадут в клиенте эти %

Default avatar.png jiki: эти % в памяти на сервере что логично

Default avatar.png jiki: это событие

Default avatar.png jiki: евент клиента

Default avatar.png jiki: 0 или 1 если 1 запускает шейдер

YurkovAS: Кто-нибудь разбирается в SA? Есть хороший пример?

Default avatar.png jiki: ладно буду доделывать текущую задачку и погнал в топы в тик так)

tutubalin: jiki ты из вуда вышел?

YurkovAS: https://stackabuse.com/simulated-annealing-optimization-algorithm-in-java/ не пойму, там пример, и температура уменьшается в цикле. а для КГ тоже надо уменьшать, или можно как-то симулировать по ttl

Default avatar.png jiki: фурье

Default avatar.png jiki: вроде помогёт

Default avatar.png jiki: фурье надо превратить не в линию

Default avatar.png jiki: а ступеньки

Default avatar.png jiki: и чонить там попробовать

Default avatar.png jiki: а нет

Default avatar.png jiki: но очень похоже было просто

Default avatar.png jiki: и формула оч похожа

Default avatar.png jiki: я как раз ловил на фурье глобальный максимум

YurkovAS: ловил на спининг или донку?

Default avatar.png jiki: нет сначало писал фурье

Default avatar.png jiki: туда обратно

Default avatar.png jiki: подставлял частоту

Default avatar.png jiki: рисовала бадягу первого графика ток наоборот

Default avatar.png jiki: както так

Default avatar.png jiki: ну можно и минимум так ловить можно максимум смотря какая функция в фурье

Default avatar.png jiki: и сколько точек

YurkovAS: а окуня можно?

Default avatar.png jiki: не знаю но видишь тут граффик какой

Default avatar.png jiki: синусоидальный с искажением

Default avatar.png jiki: волной идет

YurkovAS: ой, ладно, все, выключаюсь. что-то отвлекся на чат и все силы закончились..

tomatoes: wlesavo помоему в number shifting делал SA

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

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

Default avatar.png jiki: время это х

YurkovAS: amurushkin в search race топ-1 юзает sa. вот хотел по быстрому проверить. у меня ГА очень похож.

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

amurushkin: у меня там сейчас смитмакс на 1 игрока ))

amurushkin: надо будет попробовать переписать на SA

amurushkin: у меня готовые код уже есть. могу дать

YurkovAS: amurushkin пример с SA? о давай, не откажусь.

inoryy: Uljahn зачем человека на градиенты навёл

Uljahn: Automaton2000: градиент - сила, рандом - могила

Automaton2000: что у меня нет рандома

Uljahn: Automaton2000: тоже на градиенты подсел?

Automaton2000: https://dpaste.com/6526a2kgk без всяки там сетов и векторов:)

inoryy: ссылочка то битая

Default avatar.png jiki: в любом случае спс я теперь буду юзать мкст

Default avatar.png jiki: мктс

Default avatar.png jiki: так можно и шахматы намутить

Default avatar.png jiki: https://youtu.be/cTtXfF3OLfs

Default avatar.png jiki: мозг окончательно взорван

Default avatar.png jiki: http://chat.codingame.com/pastebin/533ebff7-d337-4e76-b5e8-752409ac38aa

Default avatar.png jiki: я еще и заболел пойду я

Default avatar.png jiki: кароче не дай бог вот так