gsomix: А логи чата куда-нибудь пишутся?
vrabosh: gsomix да, я видел сайт гдето
vrabosh: там с марта логи были на каждый день
BorisZ: https://cg.spdns.eu/wiki/Special:PrefixIndex?prefix=Ru%2F&namespace=3000
BorisZ: все ходы записаны
BorisZ: все что вы скажете может быть использовано против вас
gsomix: Спасибо!
tutubalin: ConstantBolzmann а где там визуализация?
vrabosh: я так и не вьехал как с помощью га решать задачки, где на вход даешь разные данные и полчаешь быстро результат.
vrabosh: допустим как задачку решить, есть число N и надо сказать, сколько в нем единиц если перевести в двоичную систему?
vrabosh: я как понял ГА либо я выдумываю свой алгоритм жизни его, либо это просто подбор лучшего коэфициента для рабочего алгоритма.
vrabosh: типа у меня уже есть рабочий бот, но для него надо подобрать 10 констант которые дадут лучше результат, и простым перебором это делать триллион игр, а через ГА болемение можно пдобрать за 10000 игр.
vrabosh: Правельно я понял эту тему?
gybson_samara: Неплохой туториал по разрезанию полигона https://web.archive.org/web/20200122185639/https://geidav.wordpress.com/2015/03/21/splitting-an-arbitrary-polygon-by-a-line/
gsomix: Хороший блог, жалко, что давно не обновлялся.
gybson_samara: за четыре года полигоны не сильно изменились =)
735487: ГА ищет лучшую последовательность действий как бы
735487: ну или набор чего то
vrabosh: amurushkin немогу понять как в кодезомби это использовать?
vrabosh: я ему даю координаты зомби,свои людей.. вот га обучился допустим, то что он должен сделать чтобы потом мне выдать куда идти, на каждый ход?
gybson_samara: ГА это альтернатива полному перебору
vrabosh: как данные хранить гена? и потмо как с ним работать?
vrabosh: перемножать, сумировать или что?
vrabosh: это как с нейронами работать?
gybson_samara: вчера же кидали туториал
vrabosh: я простотрел быстро. как я понял. он просто нашел луший результат на 1 слово..
vrabosh: если я ему дам другое слово он заного начнет работать?
gybson_samara: нашел перебором
vrabosh: а понял, просто другой перебор.. а я то думал как нейронка.. обучил.. даю координаты и результат за наносекунду)
vrabosh: но в ютубе есть га как чел играет в змейку. но там он свою конструкцию придумывает..
BorisZ: vrabosh в основе всех поисковых алгоритмов, не только ГА - симуляция реального мира, поверх нее работают они
gybson_samara: симуляция позволяет оценивать результат
BorisZ: например для зомби: все хуманы стоят на месте, это просто
vrabosh: поясните на пальцах
vrabosh: на коде
vrabosh: какой массив создавать?
BorisZ: все зомби перемещаются - либо к ближайшему хуману либо к ашу если он ближе - ты это можешь вычислить легко
vrabosh: вычислил, дальше что делать?
BorisZ: дальше - переменная, ход аша, она может быть любой, это входной параметр для симы, в данном случае единственный
BorisZ: для любого хода аша твоя сима должна пресказать состояние мира
BorisZ: следующий шаг - берем не один ход аша, а несколько
tutubalin: vrabosh геном - это последовательность шагов до конца игры. выбираешь из популяции те, которые не проиграли и набрали макс очков
vrabosh: asha(x,y) == mir(arr_zom_chel)
BorisZ: например 10 ходов каких-то, теперь берем эти 10 последовательных ходов и считаем как будет выглядеть мир через 10 шагов
vrabosh: mir - это делаю я,
asha - га
vrabosh: что внутри asha должно быть7
vrabosh: что он делаешь? перемножает коофициенты или что?
BorisZ: посчитали эти 10 ходов, посчитали оценку для мира, тут это просто количество набитых очков
vrabosh: как запрограммить?
vrabosh: я поинмаю теорию что как работает..
vrabosh: как это перевести на конструкцию математики?
735487: vrabosh: смотри рандомишь например 10 действий. это будет у тебя последовательность для 10 ходов. выполняешь их и оцениваешь. потом мутируешь последовательность, оцениваешь и если она лучше то сохраняешь. потом когда время кончилось выводишь первый элемент. а хвост можешь использовать на следующий ход добавив еще элемент в конец
vrabosh: что мутировать?
735487: последовательность
735487: самая простая мутация заменить 1 рандомный элемент
vrabosh: это что? xy ашера или что?
735487: последовательность из набора действий которые ты можешь выполнять
735487: для зомби это например пара координат куда он идет
vrabosh: xyash, xyzom1, xyzom2, xychel
что я с этим делаю?
vrabosh: перемножаю? суммирую с чемто?
735487: а что это вообще такое у тебя?
vrabosh: координаты
vrabosh: вот я стою на 0.0, а мне надо идти на 10.10 как я ашеру говорю, что мне надо туда идти?
vrabosh: какие данные я перемножаю, сумирую ищи что делаю, чтобы получилось 10.10?
gybson_samara: vrabosh вот исчерпывающе про ГА на питоне и притом это марслендер https://www.youtube.com/watch?v=qtN-I7s4RQE&t=1140s
vrabosh: при условии что ГА уже идеально обучен..
tutubalin: при условии, что ГА идеально обучен, у тебя есть готовый путь как идти из 0,0 в 10,10
tutubalin: ГА не обучается, это не нейронка. ГА - это способ находить решения с помощью случайных мутаций и естественного отбора
vrabosh: gybson_samara они теорию поверхостную расказывают.. а ккак это смодерировать я хз.
735487: ГА это алгоритм случайного поиска
vrabosh: понятно. я думал это типа как нейронка
vrabosh: но что тогда то, что чел сделал со змейкой на ютубе?
tutubalin: берёшь 1000 случайных решений. оцениваешь их, насколько они близки к нужному ответу. выбираешь лучших и мутируешь их - заменяешь один рандомный элемент на другой, например.
повторяешь оценку, отбор, мутации, пока не кончиться время
vrabosh: типа я у себя на компе пошаманил, а потом сюда вставил результат, и он мне ходы за милисикунды ищет
tutubalin: почитай статью старенькую из ТМ.
http://zhurnalko.net/=nauka-i-tehnika/tehnika-molodezhi/1993-05--num6
gybson_samara: vrabosh на видео полное решение задачи
BorisZ: vrabosh вот каркас для обсчета вселенной, я удалил все лишнее
BorisZ: http://chat.codingame.com/pastebin/fb71fea1-e05d-4194-ba60-b93857f15a7b
vrabosh: пошел читать смотреть, может дайдет до меня.. пока я не представляю что даже программить надо
vrabosh: через нейронку хоть както представляю
BorisZ: для начала не надо заморачиваться с ГА - просто подаешь на вход случайные гены (точки, куда должен идти аш), считаешь полученный скор, лучшую из найденных последовательностей запоминаешь, отдаешь рефери первый ген
vrabosh: ну это я должен буду в игре делать?
vrabosh: а точек же там тысячи куда сходить можно
BorisZ: да, ГА это не нейронка, он не обучается, это просто улучшение случайного поиска
vrabosh: но я видел га которые обучаются
vrabosh: у которых есть сенсоры и в них насроены коэфициенты
tutubalin: vrabosh пожалуйста, хватит флудить
vrabosh: я думал есть чтото общее для всех задачь)
vrabosh: а тут оказыается надо самому эти сенсоры думать и как их обучать
BorisZ: можно сказать что он обучается, но на ходу, вопрос терминологии
vrabosh: ладно понял, пошел расти.. а то реально нубские темы не интересно людям слушать)
vrabosh: рано мне еще обсуждать эту тему здесь
tutubalin: vrabosh информации дали более чем достаточно. вместо того, чтобы 10 раз подряд писать "я всё равно ничего не понимаю" стоит попытаться прочитать внимательно и понять
gybson_samara: vrabosh вот, кстати, таку книгу видел? https://e-maxx.ru/bookz/files/cormen.pdf
vrabosh: нет
gybson_samara: хорошая, сбереги в закладки
vrabosh: еще подскажите, чтоб у меня картина сложилась.
vrabosh: есть чел, и 2 зомби идут с разных краев, как вы ищите лучший вариант, чтобы убить сразу двух?
tutubalin: я смотрю, есть ли шанс спасти человека. если шансов нет, то забиваю на него
gsomix: gybson_samara, просто жалко, когда хорошие блоги становятся неактивными.
BorisZ: vrabosh оно само найдет лучший вариант, с максимальным скором - это и будет какая-то последовательность ходов аша чтоб сразу обоих убить
vrabosh: BorisZ если допустим без ГА, как бы это искать? я каждую точку перебираю на каждый ход?
vrabosh: как я раньше делал, трон, я брал в рекунсии каждый ход проверял.. и где я больше всего ходил тот и выбирал.. т.е. иду налвео, потом с лева на 4 направления и отудова еще на 4 итд.. в итогде рекурсия возращает самый длиный путь.
vrabosh: тут также получается?
BorisZ: не каждую точку, это невозможно, просто случайные точки даешь
vrabosh: а через ГА я бы мог просто почти также делать, только сократить во сколько то раз рекурсию?
gybson_samara: так ... тут чо scipy можно?
vrabosh: да, и пандас
BorisZ: поскольку поле тут непрерывное, то к цели пприведут разные последовательности ходов
BorisZ: например из точки 0 надо попасть в точку 150, максимальная твоя скорость 100
vrabosh: например я пускаю первую рекурсию которая дойдет доконца.. это будет ЛПЛЛНР - лево проаво низ итд
BorisZ: можно сходить в 100 потом в 150, можно в 70 потом в 150 и так далее
vrabosh: и таких разных я пускаю штук 50
vrabosh: потом из них выбираю лучших, скрешиваю.. и получаю других.. их опять пускаю?
vrabosh: и так пока время не закончится?
vrabosh: и потомвыбираю лушего?
vrabosh: это про ГА?
BorisZ: поэтому случайный поиск найдет хоть какую-то успешную последовательность ходов
vrabosh: посути это просто оптимизация поиска.. я думал ГА это другое
vrabosh: но чтоб оптимизировать поиск, лучше предварительно всетаки придумать алгоритм играющий.. чтобы поиск еще лучш был
BorisZ: если на трон это переделать, то ты тогда генеришь кучу случайных цепочек ЛП и так далее, потом проверяешь каждую и запоминаешь лучшую
vrabosh: допустим не рандомно тупо кидать координаты.. а допустим 1 ген это то что я сейчас хожу, где я точно выигрываю пускай и с небольшим результатом.. второй ген кооординаты примерно +- 20 возле этой токи.. итд
vrabosh: не ген, особь точнее
BorisZ: если кратко то так будет хуже
vrabosh: пчему?
vrabosh: или делать рандомно, если результат лучше моего не нашелся играть моим
BorisZ: грубо говоря ты найдешь лучший ход длиной 2 шага- на максимальное убийство, а есть ходы длиной 10 шагов, где одним выстрелом сразу толпу положишь
vrabosh: ну или 1 ген мой, а остальные рандомно.
vrabosh: мне чтото не верится что это сработает на питоне с 100мс
vrabosh: слишком большое поле и ходов много
tutubalin: это и не сработает на питоне с 100мс
BorisZ: ну пробуй конечно, комбинируй
BorisZ: моя ставка что 100% рандом будет лучше на непрерывном поле
gsomix: vrabosh, мне кажется, надо пробовать. Меньше слов, больше дела. :)
BorisZ: я думаю что хватит питона чтобы как-то все тесты пройти, но хорошего результата не будет конечно
BorisZ: переписать потом будет проще если есть на питоне рабочаа версия
vrabosh: впринципе понял.. я просто думал в другом направлении .
vrabosh: gsomix лучше лишний полчаса поболатю.. чтоб потмо не переделывать..
gsomix: gybson_samara, а мы, получается, с тобой земляки. :thinking:
gybson_samara: gsomix ну хорошо =)
gsomix: vrabosh, просто через руки и код обычно быстрее доходит.
gsomix: Чем на словах. :)
vrabosh: уже иду делать) мне надо было точно убедиться и инфы куча получить, спасибо вам за то что накидали
gsomix: А я пойду симуляцию для гоночек писать.
inoryy: хватит питон мучать не по назначению
gybson_samara: внезапно =)
tutubalin: в хроме наконец-то появились collapsable tab groups
gybson_samara: вот ыбы в питоне сделали спецсимвол для массивов нампи, как для словарей сделали {}
gybson_samara: пишешь <1,2,3> и массив нампи =)
gybson_samara: отбой, нашел алиасы. Идеальный способ сделать так, чтобы тебя ненавидели
A = np.array
gybson_samara: кто-нибудь пробовал такое в кодегольфе?
vrabosh: лучше тогда уже отдельный тип сделать матрица - это встроиный нампи, где матрица оптимизированная и работает раз в 10 быстрее списков, но только допустим с числами.
vrabosh: т.е. типа матрица это хранит в себе обьекты, она выделяет кусок памяти и работает с этим куском памяти..
tutubalin: gybson_samara
from numpy import array as A
gybson_samara: tutubalin спасибо
я, кстати, склонился к ARR =)
gybson_samara: у нампи шикарная часть по линейке есть, как оказалось
gybson_samara: http://chat.codingame.com/pastebin/b94bd095-c3ed-4d87-b3cd-c1d7b51a0ba4
gybson_samara: Как решейпнуть в массив [ [x1,y1] ... [xn,yn] ]?
735487: gybson_samara: в код гольфе частенько делаю I=input
gsomix: Жалко, что на CG нет языка Julia.
gsomix: По ощущениям было бы как python с numba.
gsomix: Да и numba было бы неплохо добавить. :) Я давний пользователь MATLAB, и там активно используются приседания с матричными операциями для получения адекватной производительности в симуляциях. Это часто ведет к ухудшению читаемости кода. То же самое, наверное, касается и numpy.
gybson_samara: Кстати, про Бэтмен-2. Допустим у нас есть пластина (пространство даже может быть), которая нагревается одним источником и надо найти его координаты. Тогда последовательно измеряя температуру мы можем бинарным поиском найти точку нагрева. Так задача становится не игрой, а практикой.
gsomix: gybson_samara, только измерение температуры обычно дает численное значение. Можно просто по градиенту пройтись. :)
ConstantBolzmann: нет ты правильно делаешь гибсон
ConstantBolzmann: ты кидаешь камни
ConstantBolzmann: тоесть процесс твоего решения можно представить как будто ты кидаешь камни на плоскость там н на н и типо проверяешь рванет нет
ConstantBolzmann: ну как в сталкере)
ConstantBolzmann: типо подсветит если значит рядом с областью забыл как называется, артефакт вроде
ConstantBolzmann: интересно а если прикрутить бетмена 2 на сталкера найдет артефакт
ConstantBolzmann: он должен этот алгоритм находить зону и обойти ее
tutubalin: ConstantBolzmann комариная плешь называется
gybson_samara: я уже не кидаю камни
gybson_samara: я режу полигон
gybson_samara: делю область поиска пополам, как и надо
ConstantBolzmann: аааа
gybson_samara: все функции дописал, пока вместе не собрал
gybson_samara: т.е. изначально прямоугольник делится пополам, потом трапеция, каждый раз находится средняя точка и так до достижения результата
ConstantBolzmann: ну а камень кидать тоже гуд
ConstantBolzmann: посути глаз тоже
gybson_samara: да
ConstantBolzmann: кстати есть еще игры где надо находить пары как в вове щас есть локалки у черепашек
ConstantBolzmann: типо на память
ConstantBolzmann: пару находишь они сгорают
ConstantBolzmann: чисто под монтекарло
ConstantBolzmann: а как ты хранишь решение с отсевом в массиве или дереве?
ConstantBolzmann: вершины
gybson_samara: полигон? просто список линий
ConstantBolzmann: ммм понял
gybson_samara: массив с началом и концом линии
gybson_samara: немного излишне, но удобнее
BorisZ: gybson_samara а зачем трапеции то почему не делить пополам сначала по икс потом по игрек
BorisZ: одни прямоугольники будут, с ними проще, не запутаешься
