Chat:Ru/2020-08-01
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: я вроде через сеты решал, выбирал из множества линков вокруг выходных нод
jiki: в питоне сеты есть?
amurushkin: конечно
jiki: Амур помоги плис
Uljahn: это же базовые структуры данных, они во всех языках есть, наверное
amurushkin: с чем помочь?
jiki: написал функцию перегонки буквы в биты 7 мер
jiki: в строке нормально все
jiki: а я хочу из строки через буфер перегнать в число
jiki: 2147483647
jiki: не дает это сделать
jiki: с 1 числом только работает
jiki: 2 и более такое магическое число подставляет
Uljahn: ты уверен, что в строке на каждый символ один байт выделен?
jiki: что ты хочешь сказать?
amurushkin: не очень понятно что у тебя на входе
jiki: строка
jiki: 1 символ
jiki: с 1 символом работает с более символами нет
jiki: http://chat.codingame.com/pastebin/dccc2ed1-ab57-493e-acb2-8f654f079fad
Uljahn: это хороший повод подучить работу со строками
jiki: ага
Uljahn: не надо в чате спрашивать то, что можно нагуглить за 5 минут
jiki: а что гуглить?
jiki: я нен пойму что ты сказать хочешь?
Uljahn: как итерировать по символам строки, наверное. хз чё ты там делаешь
jiki: Ульян кто вопрос задал ты или я?
amurushkin: да итерация по строке очень странная
jiki: по какой?
amurushkin: for (auto a : message) не работает так разве?
jiki: итерацция нормальная
jiki: если про первый цикл
jiki: трабла не тут
Uljahn: вот я и спрашиваю, что если там несколько байтов на символ, он по байтам будет итерировать?
jiki: трабла перегнать число из буфера строкове в число
amurushkin: из строки в число это по моему atoi и не надо буферов
jiki: ты у меня спрашиваешь
amurushkin: в крайней случае можно черзе printf
jiki: атой я гуглил не работает
Uljahn: для кого вывод в дебаг придуман? печатай всё и разбирайся
jiki: стой работает
jiki: stoi работает только
jiki: не надо буферов окей
amurushkin: ну вот.
jiki: он так же отрабатывает
jiki: а как ты числа переводишь из строки в число
amurushkin: на riscos там у меня atoi не было я черзе printf делал
jiki: for (auto a : mesage) равнозначна моей записи
jiki: он в строку то превращает
jiki: все символы
jiki: а вот из строки в число только если в исходной строке 1 елемент
jiki: щас попробую стой атой
jiki: 1427134923
jiki: а стой вот что пишет
jiki: http://chat.codingame.com/pastebin/3c5e1365-411d-490d-bf29-1e9b5d8baab4
jiki: а значение принтф ты записывал в переменную?
jiki: каут у меня вот показывает после первогого цикла строку чисел
jiki: просто вместо каута буфер
amurushkin: у тебя в строке бинарная запись. с чего ты взял оно влазит в тип чисел?
jiki: bitset<7> b(*a);
stream << b;
jiki: ты про это?
jiki: а щас попробую
jiki: bitset<7> b(*a);
stream << b.to_string();
jiki: тот же еффект а если в лонг пилить то 67 выдает
jiki: http://chat.codingame.com/pastebin/6a71dd01-f364-4a8a-a6a2-6f57a16a80e1
jiki: 10000111000011-48-48-80-71-49-49-4979-48-48-50 такой вывод
amurushkin: тебя не смущает что ты в поток запихал немеряно нулей и едениц а потом пытаешься из него делать число?
jiki: в стрим?
jiki: nfrc
jiki: такс
jiki: щас я подтвержу что в первом цикле все нормас
jiki: http://chat.codingame.com/pastebin/a7f834c0-e757-41a8-a7a2-73edd74bf29e
jiki: валик показывает
jiki: все как надо
jiki: но это строку не понять как перегнать в том же виде в числа
YurkovAS: крестики пилишь?
jiki: нет чак нориса
YurkovAS: :thumbsup:
YurkovAS: крестики тоже интересно - mcts и bitboards, там много простора для оптимизаций
jiki: я не понимаю мктс вернее понимаю но не понимаю как его реализовать
jiki: https://www.youtube.com/watch?v=LYs6bfocYxc
jiki: посмотрел я видео
jiki: говорит все понятно
jiki: открываю вики не понятно
YurkovAS: я делал по этим двум ссылкам
https://www.baeldung.com/java-monte-carlo-tree-search
https://github.com/Oreshnik/MCTS_TTT
jiki: ну а тебя точно монте карло?
jiki: как ты рандом проверяешь?
YurkovAS: и потом еще долго оптимизировал, что тоже очень понравилось.
теперь mcts только копирую, редко что-то получается улучшить
tutubalin: да пускай чака сперва сделает
YurkovAS: mcts
YurkovAS: да, доделай чака
jiki: ну для снимка нужен чоткий рандом
YurkovAS: главное доделывать - научишься новому.
потом слде задачку - алгоритм
tutubalin: юбя
tutubalin: упс
jiki: да я знаю как задачку сделать
jiki: cout << stream.str().c_str() << endl;
tutubalin: для проверки рандома есть тесты, например Practically Random
jiki: а если превращаю ее в числа то тут мусора много
jiki: я за это время даже в шейдеры вььехал уже
jiki: а эту бадягу не пойму никак
jiki: в строке нет мусора
jiki: щас в строку скопирую хз
jiki: а стопе
jiki: ненадо в числа)
jiki: в числа это уже перебор
jiki: tutubalin и что прям снимок получаешь как в этом видео про газы говорят?
jiki: я про мктс
jiki: например в тех же крестиках
jiki: я смотрю вики похоже на авл
jiki: тоесть просто заполняю дерево
jiki: потом я его я так понимаю фиксирую
jiki: балансю
jiki: и что дальше?
jiki: например 3 на 3
jiki: тоесть каждый раунд я записываю в дерево чтото и фиксю его своим решением или как?
jiki: непойму конкретики после рисунков вики
jiki: дерево понимаю сбалансить дерево тоже
jiki: получается корень 0 0
jiki: или центр
jiki: как в жл тут пока понимаю
jiki: конкретики не понимаю кароче
jiki: потом если допру до мкст рандом градиентами заменю
jiki: мне интересно
jiki: я так подозреваю без гч реального надо градиенту брать
jiki: потомучто софт гч не стабилен
tutubalin: минимакс знаешь?
jiki: нет пока ниче не знаю но из слов более менее понятно но к конкретике нет
tutubalin: игры типа крестиков, шашок, шахмат и т.д. легко раскладываются в дерево
tutubalin: есть начальное состояние. из него возможные ходы. из них возможные ходы противника
tutubalin: и так далее
tutubalin: есть построить полное дерево, то можно найти беспроигрышную или выигрышную стратегию
tutubalin: для простых крестиков 3х3 это можно сделать на бумаге
jiki: стой
jiki: погоди
jiki: предположим 00 слева сверху
jiki: ну ок я понял считал размер дерева 1 раунд я прочел состояние
jiki: заьил число противника куда поставил в дерево
jiki: аааааа
jiki: ты хочешь сказать что загоняем x y в дерево
tutubalin: нет
jiki: каждый раунд икс игрик обновляем в том числе и своими полями так чтоль?
tutubalin: я не понимаю твою мысль
jiki: за нарисую скину скрин секу
jiki: https://imgur.com/a/35ooYRz
jiki: 2,2 там внизу
tomatoes: текущее состояние это корень дерева. есть 5 вариантов хода => делаешь из корня 5 ветвей в которых сделаны соответствующие ходы
jiki: исходя из твоей логики не 5
jiki: а либо 9 либо 8
jiki: либо 8 либо 8
jiki: если я в центре
tutubalin: из корня 9
jiki: смотрю значение и все поле в дереве
tutubalin: из каждого из детей 8
YurkovAS: jiki примерно так дерево строится
https://www.youtube.com/watch?v=QH9h-XSi5nw&feature=youtu.be&t=462
jiki: отросток в данном случае это корень результат который мы смотрим
jiki: а почему все поле не проинициализировать?
YurkovAS: да, от корня и в глубину (на много ходов)
jiki: пока не понимаю
jiki: тоесть я стилусом вожу
jiki: моя рука это паренты
YurkovAS: все дерево нереально построить. поэтому строиться понемногу, от лучшего
jiki: кончик стилуса рут
YurkovAS: но и худшим ходам, дается шанс, но редко
jiki: а как ты узнаешь куда стилусом направляет твой корень?
tomatoes: https://i.imgur.com/L6uAKBD.png
YurkovAS: https://www.baeldung.com/java-monte-carlo-tree-search
прочитай внимательно статью и сделай как тут.
в процессе поймешь, как оно примерно работает
jiki: аааа
jiki: как папки
jiki: на каждое решение своя ветка
jiki: вот щас более менее понял
YurkovAS: в tomatoes-а примере видно, что дерево не все развернуто.
в этом и есть главная фича алгоритма.
jiki: диагоналей нету
jiki: это нормально?
jiki: там вроде диагонали тоже считаются за страту
jiki: кстати если как у томата мктс то нам преподовали такое
jiki: получается это лес решений
jiki: надо построить лес решений исходя из текущего значения поля
BorisZ: jiki забудь про MCTS пока до золотой лиги не дойдешь, сосредоточся на ближайшей задаче - выйти из вуда
BorisZ: для этого достаточно просто делать случайные валидные ходы
BorisZ: ну может еще что-то подкрутить
YurkovAS: разве?
у меня сначала был миник, с ним так и не вышел из золота.
долго ускорял...
YurkovAS: да и с мктс-ом не сразу из золота выйдет.
BorisZ: я говорю - пока не дойдет до золота
YurkovAS: а как с рандомами, просто выбрать любой рандомный ход?
BorisZ: я не уверен что получится так
YurkovAS: ну может быть. только мне кажется он так далеко не уйдет.
BorisZ: может нужно еще какой-нибудь твик добавить
YurkovAS: миник можно. там тоже интересно - оценочную сделать и поускорять все это дело.
BorisZ: да, я тоже миник делал сначала
BorisZ: но надо хоть правила игры увидеть для этого, а они в бронзе
tutubalin: из вуда достаточно рандома
jiki: нет там р=лорен ловит и сечет
jiki: уже не достаточно рандома
jiki: он на втором месте
jiki: 3 дня сабмит нажимал и три он меня сёк
jiki: три дня
jiki: не дает выти
BorisZ: у тебя по ка что даже валидные ходы бот не может сделать - пытается на занятое поле сходить
jiki: а пока ты нарандомишь винстрик он 1 место и бос я хз скоко дней рандомить надо)
jiki: это да видимо есть такое
BorisZ: хотя список валидных ходов на каждый ход приходит прямо в инпуте
BorisZ: сохранил в список и выбрал случайный ну или не совсем случайный
jiki: ааа
jiki: вам огромное спасибо вы мне помогли я все ближе к градиентам
jiki: теперь понял что такое мктс
jiki: даже могу закодить его
jiki: еще 1 фичу попробую из стандарта
jiki: и намучу мктс
BorisZ: ну молодец, я вот до сих пор не понял
jiki: томатос показал же
jiki: это называется лес решений
jiki: дерево просто быстрее других типов работает
jiki: ты можешь сделать массивы решений
jiki: и убедиться что дерево быстрее
BorisZ: ну посмотри где томатос в лидерборде
jiki: где
jiki: ну а ты сделай градиентой
jiki: лес решений
jiki: от рандома надо уходить у нас нет реализации гч это все поделка
Uljahn: :pensive:
BorisZ: угу, заговр рептилоидов
jiki: настоящий гсч это коробка
BorisZ: подсовывают нам случайные числа второй свежести
BorisZ: билл гейтс всяко руку приложил
jiki: нет просто гсч по ачх не проходит его надо оптимизировать
jiki: частота совпадений у софтового гсч велика
jiki: а должна быть 50%
jiki: я сейчас про генерацию последовательностей
BorisZ: для чего-то может и не подходит, а для всех реальных задач - вполне
BorisZ: даже наоборот - упрощают его для скорости
jiki: с дополнительными алгоритмами проверки
jiki: и фикс рандома
jiki: я сам так сделал
jiki: в змейке
Uljahn: "для проверки рандома есть тесты, например Practically Random"
jiki: нифига он не нормальный
jiki: ну там эти алгоритмы которые у меня
jiki: в змейке пресловутой
jiki: фиксят в игре
jiki: прям в коде
BorisZ: да наплевать нормальный или нет, сосредоточся на задаче текущей
jiki: потомучто он заходит за зону допустимых значений даже если указать зону ему
BorisZ: сохранить ходы в список, выбрать случайный элемент
BorisZ: любой свежести
jiki: я уверен в играх где
jiki: бокс
jiki: или точка
jiki: с шансом
jiki: 9 7 5 4 2 1 1 (%)
jiki: это градиенты
Uljahn: в каком смысле?
jiki: они уже в памяти или хз как там это обратывается
jiki: тоесть сервак прогрузился градиенты уже посчитаны
Uljahn: что такое градиенты, от чего?
jiki: в смысле ты никогда не зайдешь за зону допустимой погрешности даже
jiki: от евента
BorisZ: качество ГСЧ неважно для 99% задач, для крестиков точно не важно
jiki: от евента игрока
jiki: опр типа
jiki: точка или открыть кейс
jiki: потомучсто процент неудач явно указывает на отработку качественного гсч
jiki: которого быть не может в игре с 9 гигабайтами
jiki: часть которого это мапы и шейдеры
jiki: соответственно проще сделать сразу градиенты от ивента и хранить все в одной строке
jiki: пофиксил все точнулись
jiki: вернул обратно нет
Uljahn: :confused:
jiki: градиенту щас посчитаю что это такое
jiki: производная
jiki: вектор
jiki: вполне похоже на правду
jiki: можно в шейдере его хранить прям
tomatoes: каши захотелось
jiki: шейдер евентов
jiki: шейдер компилируется ж
jiki: там векторы есть
BorisZ: Шейдер Градиентович Евентов
jiki: те самые которые в градиенте получаются
jiki: и там можно по градиентам сразу на лету сделать 100% гсч градиентный
jiki: нарисовать иными словами
jiki: нарисовать шансы
Uljahn: хватит бредить, покажи код
jiki: щас покажу что делать надо чтобы так было
jiki: представим что у нас есть несколько евентов
jiki: вот 1 из них
jiki: на каждый столбец своя вероятность события
jiki: тоесть каждый столбец является текущим если точек 9
jiki: то будет идти от 1 стоблца и так пока не доточится
jiki: теперь представь там такой шейдер ты вбиваешь проценты
jiki: график построился скомпилировался
jiki: и ты не обойдешь эти проценты
jiki: будет ровно 1%
jiki: если указать 1%
YurkovAS: будет ровно 0, в крестиках)
jiki: Юрков я просто не знаю как это называется
jiki: но полюбасу такое есть
jiki: теоретически на сервере это может делать видео обработка
jiki: графическая станция
YurkovAS: я знаю как это называется, но тебе не скажу.
крестики пройди 1 лигу, тогда скажу
jiki: ну вот
jiki: знач я близок к истине
jiki: интуиция мать его
jiki: я это в змейке заметил что раном простой заходит за границы потом Ульян навел на градиенты
jiki: потом я посмотрел икс джи
jiki: вник чутка в шейдеры
jiki: и пазл сошелся
Uljahn: на сколько процентов?
jiki: ну смотри шейдер компилируется
jiki: потом если шейдер тени может править
jiki: туман и прочее
jiki: запускать в опр координатах вьювера музыку
jiki: то примерно на 95%
jiki: тебе же не дадут в клиенте эти %
jiki: эти % в памяти на сервере что логично
jiki: это событие
jiki: евент клиента
jiki: 0 или 1 если 1 запускает шейдер
YurkovAS: Кто-нибудь разбирается в SA?
Есть хороший пример?
jiki: ладно буду доделывать текущую задачку и погнал в топы в тик так)
tutubalin: jiki ты из вуда вышел?
YurkovAS: https://stackabuse.com/simulated-annealing-optimization-algorithm-in-java/
не пойму, там пример, и температура уменьшается в цикле.
а для КГ тоже надо уменьшать, или можно как-то симулировать по ttl
jiki: фурье
jiki: вроде помогёт
jiki: фурье надо превратить не в линию
jiki: а ступеньки
jiki: и чонить там попробовать
jiki: а нет
jiki: но очень похоже было просто
jiki: и формула оч похожа
jiki: я как раз ловил на фурье глобальный максимум
YurkovAS: ловил на спининг или донку?
jiki: нет сначало писал фурье
jiki: туда обратно
jiki: подставлял частоту
jiki: рисовала бадягу первого графика ток наоборот
jiki: както так
jiki: ну можно и минимум так ловить можно максимум смотря какая функция в фурье
jiki: и сколько точек
YurkovAS: а окуня можно?
jiki: не знаю но видишь тут граффик какой
jiki: синусоидальный с искажением
jiki: волной идет
YurkovAS: ой, ладно, все, выключаюсь.
что-то отвлекся на чат и все силы закончились..
tomatoes: wlesavo помоему в number shifting делал SA
YurkovAS: щас что-нибудь попытаюсь сделать как там в примере, для начала.
amurushkin: YurkovAS: насчет SA. я когда делал я подбирал коэф для затухания. но некоторые вроде на время цепляют но у меня не получилось нормально
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: ссылочка то битая
jiki: в любом случае спс я теперь буду юзать мкст
jiki: мктс
jiki: так можно и шахматы намутить
jiki: https://youtu.be/cTtXfF3OLfs
jiki: мозг окончательно взорван
jiki: http://chat.codingame.com/pastebin/533ebff7-d337-4e76-b5e8-752409ac38aa
jiki: я еще и заболел пойду я
jiki: кароче не дай бог вот так
