Russian AI Cup

Расширенный поиск  
Страницы: [1]

Автор Тема: Ключевые решения вашей стратегии  (Прочитано 3902 раз)

mortido

  • Full Member
  • ***
  • Сообщений: 80
Ключевые решения вашей стратегии
« : Декабря 25, 2016, 06:23:36 pm »

До конца песочницы осталось всего несколько системных игр. Скоро будут результаты, а так же начнут появляться статьи от победителей. Но ведь участников было много, и было много интересных решений/алгоритмов.
Я предлагаю максимально кратко рассказать об основных вещах которые вы реализовали или вещах, которые вы сделали лучше, чем другие (кто-то там у нас самый шустрый в лесу бегает? ;) ). Если кто-то писал на языках, вроде python, то я бы почитал как они обходили проблемы с производительностью.

(тему создал сейчас пока еще читают форум, но если боитесь за беспорядок, то лучше начать делиться после окончания борьбы в песочнице)
Записан

DVS

  • Hero Member
  • *****
  • Сообщений: 682
Re: Ключевые решения вашей стратегии
« Ответ #1 : Декабря 25, 2016, 06:29:34 pm »

До конца песочницы осталось всего несколько системных игр. Скоро будут результаты, а так же начнут появляться статьи от победителей. Но ведь участников было много, и было много интересных решений/алгоритмов.
Я предлагаю максимально кратко рассказать об основных вещах которые вы реализовали или вещах, которые вы сделали лучше, чем другие (кто-то там у нас самый шустрый в лесу бегает? ;) ). Если кто-то писал на языках, вроде python, то я бы почитал как они обходили проблемы с производительностью.

(тему создал сейчас пока еще читают форум, но если боитесь за беспорядок, то лучше начать делиться после окончания борьбы в песочнице)
а что же топик кастер скромничает?
Записан

mortido

  • Full Member
  • ***
  • Сообщений: 80
Re: Ключевые решения вашей стратегии
« Ответ #2 : Декабря 25, 2016, 07:16:26 pm »

а что же топик кастер скромничает?
Кастовал в торопях, дайте мне пару едениц времени и я попробую максимально кратко описать, на мой взгляд, самые интересные вещи или проблемы которые мне удалось решить.
Записан

Stef

  • Full Member
  • ***
  • Сообщений: 96
Re: Ключевые решения вашей стратегии
« Ответ #3 : Декабря 25, 2016, 07:33:10 pm »

А всеже подожду до 00:00 а потом выложу написанный текст по поиску пути...
Записан

DVS

  • Hero Member
  • *****
  • Сообщений: 682
Re: Ключевые решения вашей стратегии
« Ответ #4 : Декабря 25, 2016, 07:57:00 pm »

А всеже подожду до 00:00 а потом выложу написанный текст по поиску пути...
лучше чем стандартный А стар? :)
Записан

Stef

  • Full Member
  • ***
  • Сообщений: 96
Re: Ключевые решения вашей стратегии
« Ответ #5 : Декабря 25, 2016, 08:09:26 pm »

А всеже подожду до 00:00 а потом выложу написанный текст по поиску пути...
лучше чем стандартный А стар? :)
Тебя нету в телеграмме? :)
Я про вот это: https://www.youtube.com/watch?v=VUH_yNDKNXw
Записан

ud1

  • Full Member
  • ***
  • Сообщений: 92
Re: Ключевые решения вашей стратегии
« Ответ #6 : Декабря 25, 2016, 08:53:05 pm »

А всеже подожду до 00:00 а потом выложу написанный текст по поиску пути...

Круто выглядит. А у меня колхоз какой-то тормознутый.
Записан

Stef

  • Full Member
  • ***
  • Сообщений: 96
Re: Ключевые решения вашей стратегии
« Ответ #7 : Декабря 25, 2016, 08:58:55 pm »

А всеже подожду до 00:00 а потом выложу написанный текст по поиску пути...

Круто выглядит. А у меня колхоз какой-то тормознутый.

Я его запилил зачемто вначале... потратил недельку на него, думаю очевидно что толку от него в соревновании на самом деле небыло почти, а вот неделю уже потраченную на это не вернуть.
Просто мне показалась задача поиска пути гораздо интересней чем война магов :)
Записан

DVS

  • Hero Member
  • *****
  • Сообщений: 682
Re: Ключевые решения вашей стратегии
« Ответ #8 : Декабря 25, 2016, 09:00:40 pm »

А всеже подожду до 00:00 а потом выложу написанный текст по поиску пути...
лучше чем стандартный А стар? :)
Тебя нету в телеграмме? :)
Я про вот это: https://www.youtube.com/watch?v=VUH_yNDKNXw
если вместо ли использовать а стар то будет меньше процессорного времени истрачено..  :)
я вот Ли использовал, да A стар времени не зватило, да и зачем если проц времени с избытком для хождения по вейпоинтам :)
Записан

Stef

  • Full Member
  • ***
  • Сообщений: 96
Re: Ключевые решения вашей стратегии
« Ответ #9 : Декабря 25, 2016, 09:08:39 pm »

А всеже подожду до 00:00 а потом выложу написанный текст по поиску пути...
лучше чем стандартный А стар? :)
Тебя нету в телеграмме? :)
Я про вот это: https://www.youtube.com/watch?v=VUH_yNDKNXw
если вместо ли использовать а стар то будет меньше процессорного времени истрачено..  :)
я вот Ли использовал, да A стар времени не зватило, да и зачем если проц времени с избытком для хождения по вейпоинтам :)

Через три часа (может быть слегка пораньше) скину. Я там кратко но написал почему всеже Ли. Там конечно сравнения по времени в тексте нету, но по факту моя реализация Ли работает за O(N*N) где N это размер сетки по одной оси (классическая реализация за O(N*N*N) но у меня и не совсем честный Ли... ктомуже Ли дает возможность найти путь до любой точки потом быстро, а A* надо до каждой точки отдельно просчитывать.
хотя есть впринципе оптимизации A* которые бы дали думаю тоже хороший и быстрый результат.

Если честно там Дейкстра... просто на 2д сетке  ;D или Ли но с весами переходов в соседние клетки  ;D это как посмотреть
« Последнее редактирование: Декабря 25, 2016, 09:12:06 pm от Stef »
Записан

DVS

  • Hero Member
  • *****
  • Сообщений: 682
Re: Ключевые решения вашей стратегии
« Ответ #10 : Декабря 25, 2016, 09:32:41 pm »

А всеже подожду до 00:00 а потом выложу написанный текст по поиску пути...
лучше чем стандартный А стар? :)
Тебя нету в телеграмме? :)
Я про вот это: https://www.youtube.com/watch?v=VUH_yNDKNXw
если вместо ли использовать а стар то будет меньше процессорного времени истрачено..  :)
я вот Ли использовал, да A стар времени не зватило, да и зачем если проц времени с избытком для хождения по вейпоинтам :)

Через три часа (может быть слегка пораньше) скину. Я там кратко но написал почему всеже Ли. Там конечно сравнения по времени в тексте нету, но по факту моя реализация Ли работает за O(N*N) где N это размер сетки по одной оси (классическая реализация за O(N*N*N) но у меня и не совсем честный Ли... ктомуже Ли дает возможность найти путь до любой точки потом быстро, а A* надо до каждой точки отдельно просчитывать.
хотя есть впринципе оптимизации A* которые бы дали думаю тоже хороший и быстрый результат.

Если честно там Дейкстра... просто на 2д сетке  ;D или Ли но с весами переходов в соседние клетки  ;D это как посмотреть

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

но если дерево сносится за один выстрел то штрафа к стоимости во вход в дерево нет. :)

такая реализация сожрала всего лишь половину отведенного процессорного времени.

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

утонул в нюансах игрового мира.

вот в те же три в ряд, было бы здорово, быстро реализовал игровой мир,  и дальше реализовывай свои алгоритмы, готовых же нет..

а тут тебе и Ли и А-стар, и поля влияния(которые хорошо вписываются в Ли и А-стар), и еще всякой стандартной всячины.

вот в гонка в прошлых... было интересно ГА воткнуть в генерацию идеального пути, но времени не хватило довести до идеала этот алгоритм.. :)
Записан

ilt

  • Jr. Member
  • **
  • Сообщений: 26
Re: Ключевые решения вашей стратегии
« Ответ #11 : Декабря 25, 2016, 09:46:25 pm »

Тебя нету в телеграмме? :)
Я про вот это: https://www.youtube.com/watch?v=VUH_yNDKNXw
Эхх... Боль моя... Обломал я об этом волновой алгоритм Ли все свои новичковские зубки перед раундом 1  :)
Записан

Stef

  • Full Member
  • ***
  • Сообщений: 96
Re: Ключевые решения вашей стратегии
« Ответ #12 : Декабря 25, 2016, 09:51:51 pm »

Цитировать
такая реализация сожрала всего лишь половину отведенного процессорного времени.

O_o все что было показано на видео, отъедает дай бог чтобы 1% отведенного времени... у меня больше всего времени сьедают сейчас увороты, и даже это 20-30% времени от отведенного...
Записан

DVS

  • Hero Member
  • *****
  • Сообщений: 682
Re: Ключевые решения вашей стратегии
« Ответ #13 : Декабря 25, 2016, 10:00:19 pm »

Цитировать
такая реализация сожрала всего лишь половину отведенного процессорного времени.

O_o все что было показано на видео, отъедает дай бог чтобы 1% отведенного времени... у меня больше всего времени сьедают сейчас увороты, и даже это 20-30% времени от отведенного...
у меня клетки слишком мелкие, но зато визард может впритык между деревьями просочится, и у его пути минимум пересечений с здоровыми деревьями
Записан

Stef

  • Full Member
  • ***
  • Сообщений: 96
Re: Ключевые решения вашей стратегии
« Ответ #14 : Декабря 25, 2016, 10:11:45 pm »

Напишу мини пост, о немного другой стороне олимпиады - времени:
первая неделя - 26 часов
вторая неделя - 26 часов
третья неделя - 27 часов
четвертая неделя - 34.5 часа
пятая неделя - 38.5 часов
на шестой недели я забил там очень мало - 10 часов
На последней текущей недели - 8 часов

Итого: 170 часов.

На поиск пути я убил: 49 часов.
На поддержание своей архитектуры в более менее норм состоянии (около 70 классов - 140 файлов на С++): 28 часов.
На увороты: 26 часов.

Все остальное: 67 часов - правки багов, подгонки коэффициентов, и другие более скучные вещи (выбор линии, карта опасности, понимание когда атаковать а когда убегать)
Записан

DVS

  • Hero Member
  • *****
  • Сообщений: 682
Re: Ключевые решения вашей стратегии
« Ответ #15 : Декабря 25, 2016, 10:29:16 pm »

Напишу мини пост, о немного другой стороне олимпиады - времени:
первая неделя - 26 часов
вторая неделя - 26 часов
третья неделя - 27 часов
четвертая неделя - 34.5 часа
пятая неделя - 38.5 часов
на шестой недели я забил там очень мало - 10 часов
На последней текущей недели - 8 часов

Итого: 170 часов.

На поиск пути я убил: 49 часов.
На поддержание своей архитектуры в более менее норм состоянии (около 70 классов - 140 файлов на С++): 28 часов.
На увороты: 26 часов.

Все остальное: 67 часов - правки багов, подгонки коэффициентов, и другие более скучные вещи (выбор линии, карта опасности, понимание когда атаковать а когда убегать)

какие планы на участие в следующем году?
Записан

Stef

  • Full Member
  • ***
  • Сообщений: 96
Re: Ключевые решения вашей стратегии
« Ответ #16 : Декабря 25, 2016, 10:40:08 pm »

Напишу мини пост, о немного другой стороне олимпиады - времени:
первая неделя - 26 часов
вторая неделя - 26 часов
третья неделя - 27 часов
четвертая неделя - 34.5 часа
пятая неделя - 38.5 часов
на шестой недели я забил там очень мало - 10 часов
На последней текущей недели - 8 часов

Итого: 170 часов.

На поиск пути я убил: 49 часов.
На поддержание своей архитектуры в более менее норм состоянии (около 70 классов - 140 файлов на С++): 28 часов.
На увороты: 26 часов.

Все остальное: 67 часов - правки багов, подгонки коэффициентов, и другие более скучные вещи (выбор линии, карта опасности, понимание когда атаковать а когда убегать)

какие планы на участие в следующем году?

Ну думаю буду писать на питоне 3 в следующем году (не хочу писать на одном и томже языке, хочу на разных уметь думать), и всеже постараюсь подойти к олимпиаде серьезно, а не по принципу студенческих годов... Эту писал реально от балды, только поиск пути более менее целенаправлено писал, а все остальное просто ночной бездумных хаос мыслей (зря я по факту писал ночью... организм сдался к 6 недели и сказал - все я спать и отдыхать :)

Но там еще зависит от темы, если будет какая-нибудь стратегия с кучей юнитов, то постараюсь даже выиграть (ибо мне это более всего интересно)
Записан

ud1

  • Full Member
  • ***
  • Сообщений: 92
Re: Ключевые решения вашей стратегии
« Ответ #17 : Декабря 25, 2016, 10:59:25 pm »

На питоне? Ok, одним соперником меньше, прекрасно.
Записан

Stef

  • Full Member
  • ***
  • Сообщений: 96
Re: Ключевые решения вашей стратегии
« Ответ #18 : Декабря 25, 2016, 11:14:14 pm »

На питоне? Ok, одним соперником меньше, прекрасно.
;D наивное дитя, я пишу на Swift в жизни, и знаю функциональщину (а именно умение мыслить в её стиле, поможет понимать как писать на питоне быстро), и у меня под боком сидит питонист на работе, который мне рассказывает некоторые приколы питона, и то что если писать грамотно то питон по скорости становиться С (ибо он сам написан на С).

+ ты хоть раз видел от меня стратегию которая отжирала все процессорное время? на C# было 40% на С++ сейчас 30% гдето ;D
Так что я осилю на питоне вписаться во временные рамки :)
Но я себе тут комп прикупил в раза 4 мощнее моего текущего... так что одного главного ограничения у меня не будет - мой комп текущий не тянет даже 10% времени системного с нормальным фпс :)

И да я не оптимизировал ни С++ ни С# вообще у меня там можно найти циклы идущие друг за другом к примеру, ибо я решил что так красивее, или очень много чего я не кэшировал - ибо лень (например объекты вокруг меня, я наверное за тик раз 30 пересчитываю)
Записан

Stef

  • Full Member
  • ***
  • Сообщений: 96
Re: Ключевые решения вашей стратегии
« Ответ #19 : Декабря 25, 2016, 11:37:37 pm »

Ладно Думаю за 25 минут всеравно никто ничего уже не перепишет, да и игр уже не будет:

Поделюсь и я своими алгоритмами. В принципе мне можно только описать один, ибо все остальные на порядок хуже чем у топов, а именно поиском пути и беганьем по лесам.
Условно я разделю алгоритм на две части:
Первая часть алгоритма – обход препятствий, достаточно простой, но позволяет проходить почти идеально если это возможно. Вторая часть использует первую, но решает проблемы с вырубкой деревьев и оцениванием длины пути (первый умел обходить, но не умел оценивать расстояние до точки).

Первая:
По факту, это не поиск пути вообще – это качественный обход препятствий (досихпор работает на ура). Я уже много раз писал о нем в телеграмме – касательные наше все.
Если посмотреть видео: https://www.youtube.com/watch?v=lHjqjRJodog, то можно заметить, что между деревьями очень много фиолетовых линий. Эти линии в алгоритме не присутствуют, но они были созданы для визуализации групп. В самом начале видео и на 40 секунде, где маг уходит в лес, очень хорошо видно, что у нас в «левых» лесах есть две больших группы и между ними маг и проходит на 40 секунде.
Если описать алгоритм построения групп, то:
Имеем множество объектов и множество групп, которое вначале пустое.
Берем объект из множества объектов и проверяем – если он попадает в одну группу {находится близко к одному из объектов группы} то добавляем его туда. Если более чем в одну, то объединяем эти группы, и добавляем в новую группу новый объект.

Далее определяем, куда двигаться в текущем тике. На входе имеем множество групп, мага и точку, куда хотим прийти. Я бы этот алгоритм назвал так – бросание лучей, хотя на самом деле всеже это не лучи, а отрезки – у них есть макс длина.
Вначале бросаем луч в точку, куда хотим прийти. Находим пересечение с той группой (объектом из группы) которое ближе всего к нам. Проходим по всем объектам группы, считаем обе внутренние касательные к каждому объекту группы и находим такие которые будут давать максимальный угол отклонения от текущего луча – их будет две (одна влево другая вправо). Дальше по магической логике (в первом варианте алгоритма функция выбора из двух касательных была сложной, ибо выбирать ту, которая наименьший угол отклонения даст, было очень плохо – когда подходишь близко к краю группы, этот угол зачастую становится максимальным), выбираем одну из двух. Точка касания (с учетом правда радиуса мага) будет нашей новой точкой, куда надо двигаться. После чего снова бросаем луч, но в новую точку, предварительно удалив ту группу с которой мы уже пересекались.
Собственно говоря, все. Первый алгоритм работал на этом, но имел несколько недостатков: Мне не нравилась функция, какую касательную брать из двух; я не мог оценить дистанцию до точки; не рубил деревья.
Второй алгоритм, использовал туже функцию для обхода препятствий, но перед этим он считал приблизительный путь, и удалял из него деревья. Как он работал:
Вначале использовал алгоритм Ли (волновой) и строил от себя волну на всю карту (карта представляется сеткой 125x125). Здания и миньоны считались непроходимыми, а вот деревья, имели просто завышенную цену прохода, в зависимости от ихнего хп, и расстояния от центра {дерево может попадать на несколько клеток одновременно, и былобы не логично все эти клетки помечать одним весом}. Тех кто знаком с алгоритмом Ли возмутятся – этот алгоритм умеет искать путь, но не умеет учитывать цену перехода, и будут правы. По этой причине:
а) Я считал волну на всю карту
б) Он был немного скрещен с Дейкстрой – по факту это можно даже назвать Дейкстрой а не Ли, где граф представлен в виде 2д массива.
Вообще сложно сказать что это – Ли или Дейкстра ибо обход  я использовал из Дейкстры, но с оптимизацией, а хранил данные как для Ли.
Итог – мы имеем карту и можем найти из любой точки оптимальный путь до мага. Так как нам нужно за тик иногда просматривать несколько путей, это еще и имело преимущество по сравнению с a*, которому для каждого пути нужно заново все пересчитывать. А для полной оптимизации, я еще и саму карту обновляю раз в 60 тиков. Если так случалось, что за 60 тиков менялась клетка (что происходило всегда и по несколько раз) использовал быстрое обновление – у предыдущей клетки завышал вес, а у новой занижаю.
Следующий этап – скрестить это с частью один… Тут все просто берем наш путь пересекаем его с окружностью радиусом 300 (не помню уже почему такой был выбран, вначале был 600) - точка пересечения и есть та точка до которой мы будет считать обход препятствий. Такое решение помогло упростить старый алгоритм обхода, так как теперь можно было брать минимальный угол смещения от вектора направления, так как сам вектор был коротким и уже указывал, куда нужно идти.
Последний этап – рубка леса. На вход имеет путь, представленный в виде отрезкой небольшой длины (построен на основании сетки 125x125) и множество деревьев. Задача: найти деревья которые можно быстро срубить, которые нельзя обойти и рядом с которыми проходит путь или через них. Алгоритм простой, но в нем есть баг – иногда рубит лишнее. Когда его писал, уже понял всю бессмысленность написанного, и не стал его догонять до идеала.
Алгоритм: Идем по пути и находим дерево, которое ближе всего к нашему текущему сегменту пути и при этом не далеко от него. Убеждаемся, что это дерево нам на самом деле подходит (его нельзя обойти). Для этого образно делим наше игровое поле на две части – по одну сторону пути и по другую. Если есть такое дерево, которое принадлежит другой стороне пути и между этими двумя деревьями нельзя пройти, значит, текущее дерево надо снести.
Есть проблема - в местах, когда путь проходит близко к середине дерева, и дерево в итоге оказывается не в той половине пути, в которой бы стоило. В итоге просто не решал эту проблему, ибо не фатальная.

Почему все это работает? Когда строится путь, то он строится так, что радиус дерева влияет не линейно на цену. По этому деревья которые легко срубить, оцениваются так как будто их там почти и нет (очень маленькая цена), а большие деревья сравнимы с почти непроходимыми точками. И так как вес дерева затухает со временем, то в большинстве случаев путь проходит между деревьями, но ближе к маленьким. Благодаря этому выбирается под сруб маленькое дерево. И из-за того что обход теперь идет не глобально а локально (радиус 300), и те деревья которые нужно срубить я удаляю при поиске групп {дабы обход препятствий просчитывался без них}, то первая часть алгоритма показывает себя еще в большей красе – ей не нужно обходить препятствия за километры, она их обходит здесь и сейчас.

Пожалуй на этом все. Поиск пути находиться в файлах Algorithms/A_PathFinder. Обход препятствий Algorithms/A_Move. Построение групп в Environment/E_World.
Различная 2д математика в Common/C_Math
Почти финальный вариант движения можно посмотреть на видео:
https://www.youtube.com/watch?v=VUH_yNDKNXw

Но в реальной жизни не все так хорошо – иногда точка куда бежать меняется прям в середине леса, иногда крипы за тобой гонятся и надо выбирать – или лес рубить или крипа бить… и еще много мелких факторов.

Ссылка на код: https://github.com/ivlevAstef/CodeCupAI2016MOBA


Записан

vzverev78

  • Newbie
  • *
  • Сообщений: 4
Re: Ключевые решения вашей стратегии
« Ответ #20 : Декабря 26, 2016, 01:50:34 am »

1-й раунд (по его старым правилам): Mid. Cбор бонусов (причём кривой, первый всегда нижний, даже если на верхнем нет конкурентов, а на нижнем есть. Но в раунде прокатило :) ).
Избегаю башен, когда они готовы выстрелить. Для этого сам веду счётчик cooldown'а башни в моменты, когда её никто из моих союзников не видит.
2-й раунд: прокачивание Fireball'а. Приоритет на башни (потому что позволяет быстрее набрать очки для Fireball'а), вражеских миньонов оставляю своим миньонам или менее продуманным волшебникам. С Fireball'ом вражеские волшебники выносятся быстро и без проблем.
Начинаю по mid'у. До 2000 тика анализирую количество вражеских волшебников на каждом из lane'ов и перебегаю туда, где врагов меньше, либо если врагов одинаково, то где своих меньше, но есть хотя бы один помошник. Это позволяет прокачаться быстрее.
http://russianaicup.ru/game/view/199936
финал: тут я звёзд не хватал, поэтому стратегия, видимо, не самая лучшая.
Двое волшебников идут по верху, качая Fireball. Уничтожая башни стараются использовать также удары посохом (потому что они круто прокачиваются в ветке Fireball'а). Оставшиеся трое защищают mid.
После перерыва добавил стратегию core2duo для определённого списка противников. То есть все пять валят напрямую через лес к первой вражеской башни низа. Стоя в лесу и не привлекая внимания первой волны миньонов уничтожают её. Качают Fireball (Damage от посоха). Вторую башню обступают со всех сторон и бьют посохами. Затем игнорируя новую волну миньонов бегут к базе, обступают её по кругу и бьют до победного конца. Миньонов игнорируют полностью.
http://russianaicup.ru/game/view/201816
К сожалению, на практике, не всегда выходит так удачно.
Ещё я пытался реализовать уворачивание от ракет в бок. Но оно не всегда работает как задумано ;) Идея в том, чтобы стоять к вражескому волшебнику боком, когда он готов выстрелить. И так как в тик выстрела я ещё не вижу ракету, то первый шаг я делаю, когда враг готов стрелять (cooldown=0). В этом случае я могу на максимальной скорости успеть отбежать вбок. Например, http://russianaicup.ru/game/view/201535 тик 865. Свои же выстрелы я немного корректирую в зависимости от того, куда смотрит враг.
Также стреляю с упреждением в движущихся миньонов. Определяю съагренных нейтралов.
« Последнее редактирование: Декабря 26, 2016, 01:53:36 am от vzverev78 »
Записан

Diesel301

  • Newbie
  • *
  • Сообщений: 1
Re: Ключевые решения вашей стратегии
« Ответ #21 : Декабря 26, 2016, 07:46:55 am »

Напишу мини пост, о немного другой стороне олимпиады - времени:
первая неделя - 26 часов
вторая неделя - 26 часов
третья неделя - 27 часов
четвертая неделя - 34.5 часа
пятая неделя - 38.5 часов
на шестой недели я забил там очень мало - 10 часов
На последней текущей недели - 8 часов

Итого: 170 часов.

На поиск пути я убил: 49 часов.
На поддержание своей архитектуры в более менее норм состоянии (около 70 классов - 140 файлов на С++): 28 часов.
На увороты: 26 часов.

Все остальное: 67 часов - правки багов, подгонки коэффициентов, и другие более скучные вещи (выбор линии, карта опасности, понимание когда атаковать а когда убегать)

Я думал я один уйму времени потратил...
Записан

antmsu

  • Newbie
  • *
  • Сообщений: 5
Re: Ключевые решения вашей стратегии
« Ответ #22 : Декабря 26, 2016, 08:05:38 am »

Более полное описание стратегии будет немного позже. А пока вкратце:

1-й раунд. Ходил только в центр из-за того, что бонусы брать удобнее, плюс линия шире. Так как стратегия была реализована через потенциальные поля, то, чтобы избежать зависания между бонусами за 700-800 за тиков до их появления начинала действовать слабая сила притяжения к каждому из них. В зависимости от расположения миньонов, вражеских и союзных визардов, а также вражеской башни и ее кулдауна (напрямую я эти зависимости никак не учитывал) мой визард выбирал одну из сторон для взятия бонуса. И примерно за 300-400 тиков «отключался более слабый бонус». Возле самого бонуса в случае, когда был мой визард и еще один союзный (если врагов было больше, то я все равно шел за бонусом до последнего и часто умирал, так как бонус считался намного более приоритетным, чем все остальное) я использовал небольшую «киллер-фичу»: вставал в точке между бонусом и приближающимся союзным визардом, и когда тот пытался меня обойти, чтобы встать ближе к бонусу перед его появлением, то я по меньшему радиусу сдвигался, чтобы снова оказаться между союзным визардом и бонусом. Если союзников было больше, то уже не получалось применить подобное. Также в первом раунде были реализованы увороты и на тот момент они работали хорошо, так как большинство визардов стреляли ровно в центр и можно было легко отбежать за время полета снаряда в сторону. Бежать начинал также, как и vzverev78, еще в момент выстрела, а не в тот момент, когда видел вражеский magic missile. На самом деле более выгодная точка для стрельбы смещена примерно на 7-8 пикселей от центра, в сторону поворота визарда (из-за разности скорости перемещения в разных направлениях). В последствии, чтобы выбрать лучшую точку, куда стрелять (в пределах одного визарда), я просто перебирал углы, начиная от центра +- пару градусов, как раз для случая, когда в момент выстрела вражеский визард стоит боком. В какой-то момент уворачиваться стали многие в топ-30 песочницы и также я заметил, что многие начиная пробовать уклоняться от magic missile в момент выстрела. Изначально хотел собирать статистику, кто начинает бежать на тик раньше, чтобы увернуться, а кто нет (от этого зависит, стоит ли смещать точку стрельбы на move.speed или нет). Но придумал более просто решение, которое, вероятно и было той фишкой, которая давала такое преимущество в микро: в тот момент, когда я мог выстрелить во вражеского визарда, я не стрелял, а ждал один тик, что позволяло мне в большинстве случаев угадать направление движения в следующий момент и попадать в уклоняющихся визардов с чуть большего расстояния.

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

2-ой раунд. У заклинания Fireball было неоспоримое преимущество с точки зрения нанесения кол-во урона за единицу времени, да и к тому же от него можно увернуться, только если стоять очень далеко. Также, начиная с первого раунда у меня был реализован ближний бой с миньонами, поэтому данная ветка была просто идеальной по сравнению с другими. Соответственно вражеское главное здание получалось уничтожать в среднем чуть быстрее, чем это делали враги. На момент, как я только научился пользоваться этим заклинанием, то из 42 игр в 35 одержал победу (в режиме 10*1+). Конечно, потом эту ветку стали выбирать очень многие и преимущества почти не было. В остальном чуть более аккуратно стал ходить за бонусами, чтобы реже умирать на них, плюс в начале игры выбирал линию, где было меньше всего союзников для максимально быстрого получения опыта. Микро на тот момент было еще не доработано, поэтому выбирать другую ветку развития при численном преимуществе врага на линии я не стал, хотя это бы принесло чуть больше очков в раунде.
Основную часть времени во время второго раунда я потратил на симуляцию всех юнитов на карте, чтобы прогнозировать, стоит ли идти на защищать базу или выгоднее уже донести вражескую, а также для определения в кого выстрелит башня. Симуляция работала быстро и более-менее точно, но недостаточно точно и в итоге я ей воспользовался только для того, что Fireball бросать с упреждением в миньонов для нанесения максимального кол-ва урона. Неточности были из-за того, что не дописал поведение визардов. Да и к тому же баланс оказался таким, что идти защищаться было редко выгодно. Также данную симуляцию можно было бы использовать для прогнозирования, стоит ли идти в массовом бою в наступление или же отступать (на самом деле это неплохо решается с помощью менее ресурсозатратного метода при помощи «Influence map», учитывающих эффективное кол-во жизней, кулдауны выстрелов, ауры, характеристики персонажей, но его я успел реализовать даже к финалу).

Финал. Вплоть до последнего дня не хотелось идти в 5-ом по миду, поэтому пробовал 1-3-1. Против активного раша старался минимизировать время прохода по боковой стороне (тут самой выгодной была ветка ближнего боя), и получалось это сделать примерно за 6 тыс. тиков. Буквально за сутки до финала удалось исправить несколько недочетов, которые присутствовали в стратегии с самого начала: вставать в одну линию в массовой драке, не ходить за бонусами всеми визардами, правильно передвигаться при повышенной скорости, учитывать действие аур скорости на вражеских юнитов, чтобы делать меньше промахов при выстреле и не рубить лишние деревья. Эти исправления позволили хорошо сражаться 5х5. Плюс немного улучшил микро за счет разных коэффициентов. Также заметил одну особенность: чем шире построение, тем лучше в среднем получалось проводить сражения, но скорее всего это из-за того, что не был реализован командные выбор цели и одного вражеского визарда мои 5 боялись точно также, как и 1 боялся (держался на расстоянии примерно enemyCastRange + 20). «Искусственно» я повышал уровень агрессии в зависимости от кол-ва вражеских визардов на линии со мной. Перед второй часть финала у меня никак не получалось одолеть в микро NighTurs, поэтому при соблюдении нескольких условий одним из визардов я уходил на другую линию, в надежде, что он быстрее уничтожит вражеское здание, чем 5 визардов оппонента продавят моих 4-ых по центральной линии. Но в итоге это работало с багом, плюс удача была не на моей стороне, так как перед финалом с теми же самыми версиями против NighTurs счет был 5-0 в мою пользу, а во время финала 1-4 в пользу NighTurs (после финала снова 2-0 в мою пользу). А так как ники я не хардкодил, то еще и на других действовала эта импровизированная тактика 4+1. Из-за чего я проиграл несколько дополнительных матчей, которые скорее всего бы выиграл, если бы шел просто в 5-ом по центру. Но с другой стороны мне очень повезло и во второй части финала тестирующая система успела провести только 5 волн, а не 6, как это было в первой половине финала.

После финала радостного чувства победителя не было, потому что казалось, что стратегия далека от идеала, и отрыв от 2-ого и 3-его места настолько мал, что победа досталась во многом, благодаря везению.

И последняя «киллер-фича»: в годы обучения в университете я очень много играл в доту и был в ней неплох:). Конечно, про киллер-фичу я в этом пункте пошутил, так как навыки игры дали только повышенный интерес в начале соревнования
Записан

ilt

  • Jr. Member
  • **
  • Сообщений: 26
Re: Ключевые решения вашей стратегии
« Ответ #23 : Декабря 26, 2016, 12:27:24 pm »

Напишу мини пост, о немного другой стороне олимпиады - времени:
первая неделя - 26 часов
вторая неделя - 26 часов
третья неделя - 27 часов
четвертая неделя - 34.5 часа
пятая неделя - 38.5 часов
на шестой недели я забил там очень мало - 10 часов
На последней текущей недели - 8 часов

Итого: 170 часов.

На поиск пути я убил: 49 часов.
На поддержание своей архитектуры в более менее норм состоянии (около 70 классов - 140 файлов на С++): 28 часов.
На увороты: 26 часов.

Все остальное: 67 часов - правки багов, подгонки коэффициентов, и другие более скучные вещи (выбор линии, карта опасности, понимание когда атаковать а когда убегать)
А как ты это подсчитал? Софт какой-то?

У меня поменьше, но думаю не очень сильно. Вообще, если исходить из того, что рабочих часов в месяце ~170, то для работающего этот конкурс в таком формате тяжелейшее испытание, грозящее различными проблемами в жизни. :)
Записан

Stef

  • Full Member
  • ***
  • Сообщений: 96
Re: Ключевые решения вашей стратегии
« Ответ #24 : Декабря 26, 2016, 01:07:07 pm »

Напишу мини пост, о немного другой стороне олимпиады - времени:
первая неделя - 26 часов
вторая неделя - 26 часов
третья неделя - 27 часов
четвертая неделя - 34.5 часа
пятая неделя - 38.5 часов
на шестой недели я забил там очень мало - 10 часов
На последней текущей недели - 8 часов

Итого: 170 часов.

На поиск пути я убил: 49 часов.
На поддержание своей архитектуры в более менее норм состоянии (около 70 классов - 140 файлов на С++): 28 часов.
На увороты: 26 часов.

Все остальное: 67 часов - правки багов, подгонки коэффициентов, и другие более скучные вещи (выбор линии, карта опасности, понимание когда атаковать а когда убегать)
А как ты это подсчитал? Софт какой-то?

У меня поменьше, но думаю не очень сильно. Вообще, если исходить из того, что рабочих часов в месяце ~170, то для работающего этот конкурс в таком формате тяжелейшее испытание, грозящее различными проблемами в жизни. :)

Да я в начале олимпиады себе toggl поставил, и всегда в нем отмечался.
Ну по факту получилось гдето +4 часа в день на код, так-как олимпиада длилась полтора месяца, но код писал и на выходных.
Записан

MikeWazowski

  • Newbie
  • *
  • Сообщений: 8
Re: Ключевые решения вашей стратегии
« Ответ #25 : Декабря 26, 2016, 04:39:37 pm »

... для работающего этот конкурс в таком формате тяжелейшее испытание, грозящее различными проблемами в жизни. :)
и для женатого тоже ...  :o
Записан

DistinGa

  • Newbie
  • *
  • Сообщений: 8
Re: Ключевые решения вашей стратегии
« Ответ #26 : Декабря 26, 2016, 04:43:05 pm »

А кто-нибудь пользовался возможностью натравливать нейтралов на врага?
Записан

DVS

  • Hero Member
  • *****
  • Сообщений: 682
Re: Ключевые решения вашей стратегии
« Ответ #27 : Декабря 26, 2016, 04:51:59 pm »

Напишу мини пост, о немного другой стороне олимпиады - времени:
первая неделя - 26 часов
вторая неделя - 26 часов
третья неделя - 27 часов
четвертая неделя - 34.5 часа
пятая неделя - 38.5 часов
на шестой недели я забил там очень мало - 10 часов
На последней текущей недели - 8 часов

Итого: 170 часов.

На поиск пути я убил: 49 часов.
На поддержание своей архитектуры в более менее норм состоянии (около 70 классов - 140 файлов на С++): 28 часов.
На увороты: 26 часов.

Все остальное: 67 часов - правки багов, подгонки коэффициентов, и другие более скучные вещи (выбор линии, карта опасности, понимание когда атаковать а когда убегать)
А как ты это подсчитал? Софт какой-то?

У меня поменьше, но думаю не очень сильно. Вообще, если исходить из того, что рабочих часов в месяце ~170, то для работающего этот конкурс в таком формате тяжелейшее испытание, грозящее различными проблемами в жизни. :)
Ззадание перегружено деталями, на которые уходит много времени.
Вот к примеру игра го, описание это два предложения, но сколько тактик..

Вот к чему нужно стремиться при придумывании задачи, чтоб время по максимуму Шло на АИ
Записан

MikeWazowski

  • Newbie
  • *
  • Сообщений: 8
Re: Ключевые решения вашей стратегии
« Ответ #28 : Декабря 26, 2016, 07:56:08 pm »

Ззадание перегружено деталями, на которые уходит много времени.
Вот к примеру игра го, описание это два предложения, но сколько тактик..

Вот к чему нужно стремиться при придумывании задачи, чтоб время по максимуму Шло на АИ
+1
машинки в этом отношении поинтереснее были, если опустить тему с не ньютоновской механикой, то всего-то было: руль/газ/тормоз/шайбы/шины/канистры ...
против нынешних орков/фетишей/башень и магов с пятью группами разных заклинаний/аур ... просто не успеваешь все это закодировать/отладить "без отрыва от производства" в отведенное на конкурс время ... и судя по тому, что моя недоделанная стратегия попала в финал и при этом еще и на последнее место не попала, я был такой совсем не один ...
Записан

AlexKol

  • Jr. Member
  • **
  • Сообщений: 11
Re: Ключевые решения вашей стратегии
« Ответ #29 : Декабря 26, 2016, 08:53:49 pm »

Ладно Думаю за 25 минут всеравно никто ничего уже не перепишет, да и игр уже не будет:

Поделюсь и я своими алгоритмами. В принципе мне можно только описать один, ибо все остальные на порядок хуже чем у топов, а именно поиском пути и беганьем по лесам.
Условно я разделю алгоритм на две части:
Первая часть алгоритма – обход препятствий, достаточно простой, но позволяет проходить почти идеально если это возможно. Вторая часть использует первую, но решает проблемы с вырубкой деревьев и оцениванием длины пути (первый умел обходить, но не умел оценивать расстояние до точки).

Первая:
По факту, это не поиск пути вообще – это качественный обход препятствий (досихпор работает на ура). Я уже много раз писал о нем в телеграмме – касательные наше все.
Если посмотреть видео: https://www.youtube.com/watch?v=lHjqjRJodog, то можно заметить, что между деревьями очень много фиолетовых линий. Эти линии в алгоритме не присутствуют, но они были созданы для визуализации групп. В самом начале видео и на 40 секунде, где маг уходит в лес, очень хорошо видно, что у нас в «левых» лесах есть две больших группы и между ними маг и проходит на 40 секунде.
Если описать алгоритм построения групп, то:
Имеем множество объектов и множество групп, которое вначале пустое.
Берем объект из множества объектов и проверяем – если он попадает в одну группу {находится близко к одному из объектов группы} то добавляем его туда. Если более чем в одну, то объединяем эти группы, и добавляем в новую группу новый объект.

Далее определяем, куда двигаться в текущем тике. На входе имеем множество групп, мага и точку, куда хотим прийти. Я бы этот алгоритм назвал так – бросание лучей, хотя на самом деле всеже это не лучи, а отрезки – у них есть макс длина.
Вначале бросаем луч в точку, куда хотим прийти. Находим пересечение с той группой (объектом из группы) которое ближе всего к нам. Проходим по всем объектам группы, считаем обе внутренние касательные к каждому объекту группы и находим такие которые будут давать максимальный угол отклонения от текущего луча – их будет две (одна влево другая вправо). Дальше по магической логике (в первом варианте алгоритма функция выбора из двух касательных была сложной, ибо выбирать ту, которая наименьший угол отклонения даст, было очень плохо – когда подходишь близко к краю группы, этот угол зачастую становится максимальным), выбираем одну из двух. Точка касания (с учетом правда радиуса мага) будет нашей новой точкой, куда надо двигаться. После чего снова бросаем луч, но в новую точку, предварительно удалив ту группу с которой мы уже пересекались.
Собственно говоря, все. Первый алгоритм работал на этом, но имел несколько недостатков: Мне не нравилась функция, какую касательную брать из двух; я не мог оценить дистанцию до точки; не рубил деревья.
Второй алгоритм, использовал туже функцию для обхода препятствий, но перед этим он считал приблизительный путь, и удалял из него деревья. Как он работал:
Вначале использовал алгоритм Ли (волновой) и строил от себя волну на всю карту (карта представляется сеткой 125x125). Здания и миньоны считались непроходимыми, а вот деревья, имели просто завышенную цену прохода, в зависимости от ихнего хп, и расстояния от центра {дерево может попадать на несколько клеток одновременно, и былобы не логично все эти клетки помечать одним весом}. Тех кто знаком с алгоритмом Ли возмутятся – этот алгоритм умеет искать путь, но не умеет учитывать цену перехода, и будут правы. По этой причине:
а) Я считал волну на всю карту
б) Он был немного скрещен с Дейкстрой – по факту это можно даже назвать Дейкстрой а не Ли, где граф представлен в виде 2д массива.
Вообще сложно сказать что это – Ли или Дейкстра ибо обход  я использовал из Дейкстры, но с оптимизацией, а хранил данные как для Ли.
Итог – мы имеем карту и можем найти из любой точки оптимальный путь до мага. Так как нам нужно за тик иногда просматривать несколько путей, это еще и имело преимущество по сравнению с a*, которому для каждого пути нужно заново все пересчитывать. А для полной оптимизации, я еще и саму карту обновляю раз в 60 тиков. Если так случалось, что за 60 тиков менялась клетка (что происходило всегда и по несколько раз) использовал быстрое обновление – у предыдущей клетки завышал вес, а у новой занижаю.
Следующий этап – скрестить это с частью один… Тут все просто берем наш путь пересекаем его с окружностью радиусом 300 (не помню уже почему такой был выбран, вначале был 600) - точка пересечения и есть та точка до которой мы будет считать обход препятствий. Такое решение помогло упростить старый алгоритм обхода, так как теперь можно было брать минимальный угол смещения от вектора направления, так как сам вектор был коротким и уже указывал, куда нужно идти.
Последний этап – рубка леса. На вход имеет путь, представленный в виде отрезкой небольшой длины (построен на основании сетки 125x125) и множество деревьев. Задача: найти деревья которые можно быстро срубить, которые нельзя обойти и рядом с которыми проходит путь или через них. Алгоритм простой, но в нем есть баг – иногда рубит лишнее. Когда его писал, уже понял всю бессмысленность написанного, и не стал его догонять до идеала.
Алгоритм: Идем по пути и находим дерево, которое ближе всего к нашему текущему сегменту пути и при этом не далеко от него. Убеждаемся, что это дерево нам на самом деле подходит (его нельзя обойти). Для этого образно делим наше игровое поле на две части – по одну сторону пути и по другую. Если есть такое дерево, которое принадлежит другой стороне пути и между этими двумя деревьями нельзя пройти, значит, текущее дерево надо снести.
Есть проблема - в местах, когда путь проходит близко к середине дерева, и дерево в итоге оказывается не в той половине пути, в которой бы стоило. В итоге просто не решал эту проблему, ибо не фатальная.

Почему все это работает? Когда строится путь, то он строится так, что радиус дерева влияет не линейно на цену. По этому деревья которые легко срубить, оцениваются так как будто их там почти и нет (очень маленькая цена), а большие деревья сравнимы с почти непроходимыми точками. И так как вес дерева затухает со временем, то в большинстве случаев путь проходит между деревьями, но ближе к маленьким. Благодаря этому выбирается под сруб маленькое дерево. И из-за того что обход теперь идет не глобально а локально (радиус 300), и те деревья которые нужно срубить я удаляю при поиске групп {дабы обход препятствий просчитывался без них}, то первая часть алгоритма показывает себя еще в большей красе – ей не нужно обходить препятствия за километры, она их обходит здесь и сейчас.

Пожалуй на этом все. Поиск пути находиться в файлах Algorithms/A_PathFinder. Обход препятствий Algorithms/A_Move. Построение групп в Environment/E_World.
Различная 2д математика в Common/C_Math
Почти финальный вариант движения можно посмотреть на видео:
https://www.youtube.com/watch?v=VUH_yNDKNXw

Но в реальной жизни не все так хорошо – иногда точка куда бежать меняется прям в середине леса, иногда крипы за тобой гонятся и надо выбирать – или лес рубить или крипа бить… и еще много мелких факторов.

Ссылка на код: https://github.com/ivlevAstef/CodeCupAI2016MOBA

Я так же реализовал обход препятствий по касательным. С поиском пути вообще не заморачивался. Иди в ту точку. И обходи все препятствия. По лесу старался не ходить, так как если зажмут в лесу можешь не выбраться.
А так получается. Кидаешь луч в точку назначения, проверяешь кто его пересекает. Если никто, двигаешься прямо. Есть кто то, то 4 касательных. 2 от визарда, 2 от точки назначения. Из точек пересечения опять смотришь есть прямой путь или нет. И по итогу все препятствия обходятся по касательной. А ну и ищем кратчайший найденный путь.
Записан

vestild

  • Newbie
  • *
  • Сообщений: 2
Re: Ключевые решения вашей стратегии
« Ответ #30 : Декабря 26, 2016, 09:07:17 pm »

Думаю из моего будет интересен только поиск пути:
пришлось вспоминать геометрию, а также в упрощении выражений и решении систем уравнений мне помогла maxima :)

базовая идея: строим линию от А до Б.
если она не пересекает препятствия то эта часть пути найдена.
если она пересекает препятствие (добавляем ко всем радиусам радиус волшебника и запас), то берём ищем "связную область": набор препятствий между которыми не может пройти волшебник, выбираем крайне правое и левое препятствие,
для правого берём правую точку касания от А (опять естественно берём радиус препятствия + радиус мага), для левого  левую.
получаем таким образом 2 пути
чтобы пути не дублировались, отбрасывал путь, если новая точка образует острый угол с предыущей
далее рекурсивно для всех путей ищем путь между точками пути

поиск в глубину работал медленно, поэтому сделал "поиск в ширину", и если есть "найденный путь" то отбрасывал все пути у которых путь больше найденного

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

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


Вообще конечно времени ушла уйма, в начале я брал неделю отпуска, за которую заложил основу - поиск пути, базовые примитивы и т.п.
Багов тоже была уйма, кажется из-за бага, который я закинул в середине 2 раунда я и не попал в финал. Ну, а подняться в песочнице у меня уже не хватило сил.
Записан

AntonT

  • Jr. Member
  • **
  • Сообщений: 37
Re: Ключевые решения вашей стратегии
« Ответ #31 : Декабря 26, 2016, 09:42:13 pm »

А у меня вплоть до финала дожил модифицированный квикстарт, и только в финале с 2-1-2 я поменял на 1-3-1 и прикрутил сбор бонусов ;D
Путь искал так: из конечной точки с шагом П/4 делал виртуальные шаги, выбирал ближайшую ко мне валидную точку и "шагал" снова. Вроде прокатило.
Вообще весь конкурс прошёл под эгидой "хватит тратить кучу времени на конкурсы" ))
Записан

tyamgin

  • Full Member
  • ***
  • Сообщений: 142
Re: Ключевые решения вашей стратегии
« Ответ #32 : Декабря 26, 2016, 10:40:40 pm »

Итак, опишу и я немного свою стратегию.

Как и у многих, позиционирование в бою устроено на потенциальных полях (что это так называется я узнал из чатика). Это просто самое простое, что могло прийти в голову.
Сразу, видео как это выглядит: https://www.youtube.com/watch?v=pTVXVW2sYcI  (ускорение 4x)

На каждую точку карты действуют притягивающие (+) и отталкивающие (-) поля. Просто линейные функции, зависящие от расстояния до точки/отрезка. Вот основные из них:
- вражеские визарды
+ вражеские визарды, которых нужно «добить»
- вражеские башни
+ вражеские башни, которые нужно «добить»
+/- вражеские минионы, чтобы отходить когда слишком близко, и чтобы подбегать для ближнего боя
- союзные юниты - на всякий случай, чтобы было пространство для маневров
+ место за вражеский троном
- точки респавна минионов
+ точка, указывающая направление к бонусу. Сделано, чтобы сломя голову не бежать к нему, а учитывать опасные зоны в бою.
- лес (просто отталкивающие треугольники, чтобы лишний раз не заходить в лес)
- стены и углы карты
- места, где могут зажать между стенкой и башней
Н каждом тике выбиралось смещение в ту точку, где больше потенциал. Лучшее, что я придумал для избежания попадания в локальные максимумы – это учитывать не только следующий тик, но и 15 тиков вперед (в выбранном направлении). Чем дальше предсказание, тем оно меньше влияло (экспоненциально угасало).
Для поиска пути использовался алгоритм Дейкстры, код которого переходит из года в год. Вся карта размечена сеткой размера 80*80. Переходить можно в 8 направлениях (смежные по диагоналям и в боковые). Ребра, на которых есть деревья, штрафовались пропорционально здоровью этих деревьев.  Далее, после того как путь построен, он «сглаживается», чтобы убрать последствия разбиения на сетку, и строится список деревьев, которые нужно разрубить.
Здесь же учитывался штраф за переход на другой Lane, заход глубоко в лес, количество врагов по пути, конечная позиция (т.к. желательно стать на линию за своими минионами, а не сбоку за деревьями)

Для первого раунда уже была более-менее готовая версия уворотов от MM. Перебиралось 20 различных направлений отхода, и перебиралось нужно при этом поворачиваться. Как тогда казалось, всё учтено, но позже я ещё раза 2 всё переписывал, и почти каждый день находил различные баги и недочеты. Если летит одновременно несколько снарядов или Fireball, то выбирался отход с минимизацией суммарного урона.

Основной веткой прокачки стал Fireball. По тем-же причинам, что описаны у Antmsu: неплохо работал посохом, и сам Fireball показался самой убийственной ультой. Перебирал c каким углом он будет выпущен, и определял какую дальность лучше ему пролететь. Так же союзникам передавалась инфа о только что выпущенном фаерболе. Теоретически, это можно было сделать по-нормальному, но я сделал через «танцы»: округлял move.Turn до 5 знаков, остальные 3 десятичных знака были в моем распоряжении :)
Второй веткой качал Range, но для финала сделал только RangeBonusPassive1, затем Haste.

Для второго раунда подсмотрел увороты у Antmsu (которые, заранее, перед выстрелом), позиционирование боком у Commandos, киллер-фичу “жало” kirdark'a, и в итоге забрался на второе место.

Для финала до последнего не хотел использовать схему 0-5-0. Начал пробовать со схемой 2-2-1. В начале финальной недели оно даже стабильно выигрывало (всем, кроме Commandos, Antmsu, Recar – с ними 50 на 50), но я понимал, что это не на долго. Т.к. 0-5-0 сходу не зашла, принял решение развивать то что есть.
В итоге в финале играла версия с 1-3-1 с перестроением «по ситуации». Не обошлось без хардкода ников в последние минуты (неактивных участников захардкодил пораньше :)))

Если ещё что вспомню интересного - напишу.

Как обычно, проиграл из-за того, что не уделил должного внимания выжным деталям. Но в следующем году будем сильнее.

P. S.
Код: https://github.com/tyamgin/AiCup/tree/master/CodeWizards
Записан

r2d2_133800

  • Newbie
  • *
  • Сообщений: 1
Re: Ключевые решения вашей стратегии
« Ответ #33 : Декабря 26, 2016, 10:51:48 pm »

У меня много времени ушло на обход препятствий и его отладку.
От алгоритма поиска пути через всю карту я сразу же отказался т.к. часть карты не видна и может обновиться, ситуация меняется слишком стремительно, но и главное перформанс.
В итоге если мой бот видит что есть пересечение с объектами на пути к цели, он из окружения отбирает только те из них у кот расстояние от окружности до меня не больше 220. Далее сортировка по углу от меня и просмотр каждой пары препятствий, левый-правый. Левый объект обходим справа по касательной, правый слева. Если между объектами угол больше 180 градусов считаем что уже пролезли, если меньше то смотрим дистанцию, если она меньше диаметра волшебника, то отбрасываем такие касательные. Также сразу нужно исключить из рассмотрения касательные к объектам, которые полностью скрыты секторами касательных других ближайший препятствий. Такие скрытые объекты влияют только на факт можно ли пролезть между двумя видимыми окружностями. Т.е. если расстояние между ближайшими препятствиями больше диаметра, но за ними есть последовательность, образующая тупик, то такие касательные тоже отбрасываются. Определить, что скрытые объекты образуют коридор, а не тупик можно, исходя из факта что если это коридор, то объекты можно поделить на 2 группы и расстояние от любой точки левой стороны дороги до любой точки правой стороны будет больше диаметра волшебника. Итеративно расширяем левую сторону и если в нее попадает правая видимая точка - это тупик, если нет - коридор. В итоге из всех касательных выбирается та, что образует наименьший угол к цели назначения.
Алгоритм простой и быстрый, мне лично нравилось, как волш забуривается в лес за нейтралами и змейкой обходит деревья. Но есть существенный недостаток - зависание когда он залезает в тупик, идет обратно, затем объект, замыкающий тупик, исчезает из поля видимости (220) и он снова идет в тупик, думая что это коридор. Решение одно и насильственное - ракета и дубинка по дереву стоящему на пути к цели путешествия.

Глобальное перемещение - вейпойнты из примера, + бонусная линия и все залитое в связный граф из 30 точек. Весовой алгоритм поиска пути. Своя линия вес - 1, чужая - 4, бонусная линия - 2. Позже добавил бег к бонусу и от него через лес напрямую. Также смена веток - через лес.

Прицеливание - видел что даже в топ 50 промахиваются по миньонам, стреляя в центр или с упреждением. За 15 тиков полета ракеты миньон проходит максимум 45 пикселей, т.е. всегда меньше чем 50 его диаметр и всегда существует точка пересечения между текущим положением миньона и его будущим положением. Если бросать снаряд в середину, то будет гарантированное попадание, куда бы он ни шел. Еще нужно выставить minCastDistance в центр объекта, а не на границе окружности чтобы исключить попадание по своим полностью.
С вражескими визардами почти тоже самое, оцениваю его бафы скорости и смотрю куда он может убежать за N тиков полета ракеты Назад, Влево и Вправо, конечно с учетом наихудшего случая когда он доворачивается к цели и ускоряется. В итоге если он может уклониться назад - совсем не стреляю, если между стенками левой и правой позиций меньше диаметра снаряда - в этот центр и надо стрелять с 100% попадания. Если же расстояние больше, то стоит рассмотреть, а не подпирает ли кто визарда сзади, слева, справа, если да, то стоит сделать смещение центра от блокирующего объекта и кидать снаряд туда.
Т.к. в момент выстрела визард может сместиться, в том числе и по рэндому, долго не мог решить что лучше, считать что он не подвижен,  или считать что он сделает шаг вперед или назад куда повернут, в общем, чтобы не сливать дамаг, решил добавлять тик к оценке полета снаряда, тем самым на 100% гарантируя попадание по врагу. Оборотная сторона медали - бои с топами кот стреляют с прицельной эвристикой с гораздно большего расстояния, попадают и отходят, в то время как мой мчится за ними чтобы отстреляться, и в итоге отхватывает на полную. Так что Антон сделал правильную киллер фичу)

Еще считаю хорошим вложеним прилипание к вражеской базе. Да его бьют, но по большей части он успевает даже один заколотить ее. Иногда умирает и слава достается союзником, но ничего не поделаешь. Прилипание срабатывает если цель - база, рядом есть 3 любых союзника, и все враги рядом только здания. При этом за базой могут стоят в инвизе вражеские визарды - это уже ничего не меняет, его не остановить. Т.к. он по сути идет к центру базы, то само сабой получилась очень полезная фича - если его пытается догнать появившийся орк, то срабатывает обход препятствий и он ищет путь в центр базы с другой стороны от орка, тем самым убегая от него вокруг базы.

Про дубинку - хоть и расстояние безопасного дамага по орку от 85 до 95, аж целых два тика, тем не менее этот запас может быстро иссякнуть при обходе дерева например или союзника, в итоге орк догоняет и дамажит, в общем подступать надо аккуратно маленьким шажком учитывая и скорость орка.

Смена веток - стыдно, но факт, заимплементил, по сути заглушку перед финалом, и какоето подобие - после, и.. с ужасом закомментил почти полностью. В боях не 5 на 5 это просто самоубийственное падание рейтинга. Такие товарищи как vzverev78 бросают все и идут фармить туда где и так своих куча, а ты бежишь спасать свою базу вместо набора очков, в итоге если выйграли ты 5й а то и 6, 7й, если проиграли 10й. Отсутствие смены веток - если програли ты 6, 7й, если выйграли скоре всего сам взял базу - ты 1, 2, 3й. Вот так. Конечно полностью исключать защиту не стоит, я например оставил ее при возрождении, но в целом - крайне не выгодная штука.

Так и остался не заимплеменченным выбор общей цели и стрельба залпом (когда один из двух снарядов да попадет при стрельбе с дальней дистанции). Причина - помимо тотальной усталости еще и ужасное API через текстовую строку, а также отсутствие фидбека от визарда мастеру. В общем после работы с объектами с кучей полей, это как то ммм.., в общем не захотел связываться, в итоге у меня бегают 5 одиночек, которые сливают обученному спецназу.

Затраченное время - можно считать что по 8 в день. Большая часть на просмотр боев, и визуальный анализ багов.

Вроде все, народ, пишите еще, интересно читать.
Записан

DVS

  • Hero Member
  • *****
  • Сообщений: 682
Re: Ключевые решения вашей стратегии
« Ответ #34 : Декабря 26, 2016, 10:57:32 pm »

Ззадание перегружено деталями, на которые уходит много времени.
Вот к примеру игра го, описание это два предложения, но сколько тактик..

Вот к чему нужно стремиться при придумывании задачи, чтоб время по максимуму Шло на АИ
+1
машинки в этом отношении поинтереснее были, если опустить тему с не ньютоновской механикой, то всего-то было: руль/газ/тормоз/шайбы/шины/канистры ...
против нынешних орков/фетишей/башень и магов с пятью группами разных заклинаний/аур ... просто не успеваешь все это закодировать/отладить "без отрыва от производства" в отведенное на конкурс время ... и судя по тому, что моя недоделанная стратегия попала в финал и при этом еще и на последнее место не попала, я был такой совсем не один ...
эт точно, не один, как минимум три:)

ты + AntonT + я

у меня стратегия до безобразия противна, т.е. проста как пять пальцев.

кстати и отрыв тройки лидеров об этом говорит, они просто быстро могут реализовывать идеи, а у меня например стабильно во всех конкурсах по факту более 50% не реализовано :)
« Последнее редактирование: Декабря 26, 2016, 11:01:12 pm от DVS »
Записан

ud1

  • Full Member
  • ***
  • Сообщений: 92
Re: Ключевые решения вашей стратегии
« Ответ #35 : Декабря 27, 2016, 12:50:34 am »

У меня стратегия получается очень похожа на стратегию Тямгина. Тоже потенциальные поля, с теми же притяжениями/отталкиваниями. И опасность в треугольнике с деревьями. И тоже не использую messages, мне они не нравятся, а вместо этого кодирую текущее состояние визарда в его скорости.
Но декстры нет, и нету ранего уклонения от снаряда, видимо поэтому и слил, думал об этой фиче, но так и не вписал в свою архитектуру.
Обхода препятсвий на самом деле тоже специального нет, из-за этого могу застрять в лесу, если нейтральные миньоны выстроятся в ряд.
А что есть, так это попытка сделать симулятор. Идея проста, описываем мир, пишем перебор вариантов, и этот перебор сам тебе находит оптимальный набор действий, профит. Ведь, от того, в какую сторону ты пойдешь, влево, или вправо, может зависеть весь исход игры! Надо просто, провести несколько симуляций, сначала грубо говоря двигаешься влево, потом запускашь симуляцию на тыщу тиков вперед, смотришь что получилось. Потом вдигаешься несколько тиков право, потом опять симуляция на тыщу ходов вперед, сравниваешь, где получилось лучше, и то направление и выбираешь. Но правда незадача, вот сходишь ты несколько тиков налево, а как симуляцию запускать потом? Надо же опять в этой симуляции куда-то двигаться. Видимо надо это делать рекурсивно. Получается, строим гигантское дерево, например выбираем 20 направлений во все стороны равномерно и пытаемся ходить в каждом их них. Начальная точка - корень дерева, из него 20 веток, например по 10 тиков. Дальше из 20 получившихся точек опять пускаем лучи во все стороны, и у нас уже 20*20 = 400 веток, и т.д. И так до конца игры моделируем все возможные движения твоего визарда, выбираем от корня ту ветку, которая ведет к большим очкам в конце моделирования. Но возникает проблема - посчитать это невозможно, даже имея суперкомпьютер на руках.
И что же в итоге получилось? А получилось, что от корня веток пускаем не 20, а всего 12, и то из них оцениваем наилучшие и ветвим дальше из них только 4. Да и то, что значит ветвим, пускаю 9 направлений и выбираю из них всего 2, и дальше вообще только по одному. Да и моделирую не на тысячи тиков вперед, а всего на 84. Ну и делаю это не каждый тик, а через один. И все равно все тормозит.
Альтернативный подход, строим вокруг начальной точки окружность, берем на ней 20 произвольных точек, и спрашиваем себя, а в какой их этих точек более комфортно в плане наличия опасности и общего стремления к базе противника находиться в данный момент? И моделируем дальше несколько тиков движение к этой точке. Дальше опять строим окружность, и опять выбираем наиболее комфортную точку на ней, и т.д., пока 84 тика не промоделируем. Тем самым получаем траекторию, длиной 84 тика, и таких строим несколько, с разными радиусами окружности, 10 там, 50, или даже 300, с разным число тиков в сегменте. Чем богаче набор, тем лучше. Причем, если посчитали траекторию то появляется возможность перепросчитать ее снова, но вычисляя степерь комфорта не в текущий момент времени, а на несколько тиков в будущем. В конечном итоге выбираем из кучи траекторий наиболее хорошую.
Хорошесть траектории определяется двумя функциями, двумя потенциальными полями. Первая, это getDanger - показывает насколько опасна ситуация для визарда, фактически это сумма всяких хитро вычесленных опасностей от башен, визардов, миньонов, в зависимости от их поворота и кулдаун тиков. И вторая это getPositionScore(), она говорит, насколько мы близки к цели. Она намного меньше первой функции и задает общее направление движения к вражеской базе по заданному лейну, т.е. фактически равна растоянию по лейну от текущего положения до базы, а если ты вышел за пределы лейна вбок, то она пытается тебя вернуть на него.
И хорошесть траектории равна getPositionScore() конечной точки траектории минус сумма getDanger() всех точек траектории (вычисленных конечно в тот момент времени, на то состояние мира, когда мы придем в соответсвующую точку).
В симуляторе я предсказываю в основном положение всех миньонов, немного предсказываю положение чужих визардов, хотя повороты не сделал, и кулдаун тики всех объектов. Даже вроде делал моделирование смерти миньонов, когда они друг друга бьют. И моделирование смерти дерева, когда по нему ударяешь посохом, от этого хождение в лесу улучшается. Идеально надо сделать еще моделирование выстрелов сделать, но это сложнее, так как снаряд еще лететь может некоторое время, и надо держать в памяти это и применять дамаг не сразу, как при ударе посохом, а через некоторое время, когда долетит. В общем симулатор не идеален, надо бы еще деталей в него накидать, может что-то реальное получится.
Вот так все и работает, хотя пришлось эти функции все равно немного перемешать, добавить в них отрицательные слагаемые, хотя изначально этого не хотел.
И пытался перед финалом его усовершенствовать, сделал сброс кулдауна при моделировании выстрела, и стал давать плюс тректории, если в ней был сделал выстрел или удар посохом. Запустил и что я вижу, мои визарды, вместо того, чтоб пойти по лейну вперед, вместо этого побежали в лес, рубить деревья. В принципе что, логично, я же дал бонус им за то, чтоб они стреляли и били посохом, но не уточнил, кого именно бить, деревья или кого-то другого. OK, убрал бонус за рубку деревьев, вроде все прекрасно, визарды нормально так побежали воевать, заливаю на сервер, создаю стратегию с NighTurs и вижу, что они не воюют. Повернулись боком, куда-то в лес смотрят. Открываю в репитере, спрашиваю, что вы творите? Мне визард говорит, вот я траекторию нашел замечательную. Сейчас я 14 тиков в лес буду смотреть, но потом обязательно повернуть лицом к врагу и выстрелю! Ну тогда ввожу затухание бонусов за выстрел, чтоб стрелять сейчас было выгодно, чем стерять потом, ввожу штраф за бездействие, что если кулдайн тиков ноль и не стреляешь, это плохо. Тестировал, тестировал на своем компе новую стратегию со старой, но так вразумительных результатов не получил и забил на это. Но ветка в принципе перспективная, надо будет продолжить исследования.
Записан

mortido

  • Full Member
  • ***
  • Сообщений: 80
Re: Ключевые решения вашей стратегии
« Ответ #36 : Декабря 27, 2016, 01:51:10 am »

Итак. Все началось с 2х фейлов за неделю до старта беты :) Я начал писать свой визуализатор на базе того, что увидел у Ромки в последне видео за прошлый год, а также свой оптимизатор констант. и даже довел это до более менее рабочего состояния, но я не был готов к 20 000 тикам и стольким объектам :) Визуализатор крешил браузер из-за огромных файлов логов. Оптимизатор не отыгрывал достаточное количество матчей и я их забросил.

Основа алгоритма - потенциальные поля: смотрим 32 точки вокруг + под собой, идем в лучшем направлении. Первые 1,5 недели просмотривал разные материалы/научные работы по ботам для RTS, смотрел игры, разобирался в локал раннере (тогда еще лелеял надежду на моделирование миьнов, но лимиты по времени слишко жесткие).

Отступление про ПП и выбор направления: изначально точки брал не на одинаковое расстояние, а на максимальный шаг, но т.к. поварачивал я в том же направлении (а не направлении градиента), то бот очень не охотно ходил по диагонали. В итоге стал всегда ходить в сторону антиградиента, хотя сейчас уже дуаю, что надо было в эту сторону только поворачиваться, а идти в лучшую доступную на макс шаг точку.

Чтобы не попадать в локальный минимум при ходьбе (в бою отключал) добавлял "холмы" своим прошлы позициям, идея взята из видео: https://www.youtube.com/watch?v=22rG3IRuV5U
В принципе всего у меня было 4 вида полей: текущая "цель" (вейпоинт, бонус), "препядствия" - поле росло быстро около них, но почти не росло на расстоянии, "опасность" и "мишень". Последнее поле отключало поле "цель" и представляло из себя хитрую формулу учитывающую положение цели и точки оступления (чтобы не забегать в лес).

Опасность вычислялась для всех юнитов по разному но учитывала мою скорость, их кд, дальность атака, текущие таргеты миньонов, текущие таргеты башен (ведь зная как они выбирают цель можно бегать под ними довольно смело, хотя только уже после финала научился определять, что база врага на КД если я ее не вижу - очень помогло рашить), для магов еще и время поворота на меня.


Т1 - точка отступления, Т2-цель к которой тянется + ее опасность

Как многие для оптимизации мир "обрубал" оставляя только существенные препядствия и объекты.
Ходил по вейпоинтам + дейкстра, но проапгрейдил их до точек, которые имели "влияние" комманд и "владельца". Чтобы захватить точку нужно было удерживать влияние над ней определенное время с определенной силой.



Увороты: самое интересное и проблемное. У меня было 3 версии:
1 - На Потенциальных полях - добавлял отталкивающее поле опасности в каждое будущее положение прожектайла. Основная проблема - если в тебя летит 2 прожектайла, то маг встает по середине и ловит оба :)

2 - моделировал отход в 32 направления + стоть на месте пока не увернусь/подставлюсь/упрусь, брал то где меньше дамага получаю (для ледышек дамаг завышал). Оставшиеся направления подавал в ф-юю хождения по потенциальным полям и жил так радостно до конца второго раунда. Основная проблема - не оценивает еще не выпущенные прожектайлы. + поля опасности от магов учитывали каст ренж, но они не учитывали, что если я очень быстрый то могу подойти ближе и все еще уворачиваться от всего. Эту версию уворотов я потом использовал для оценки стрелять во врага или нет, если он дамаг по нему до добавления "вероятностной" ММ в мир меньше чем после, то я стрелял. Потом стал добавлять туда еще прожектайлы от союзных визардов, готовых выстрелить в ближайшие 5 тиков - это слегка повысило кучность и хитрость стрельбы в группах. Стрелял не  центр, а в точку от которой бежать во всех направлениях одинаковое время:

public static V2d getShootPoint(V2d aimPos, V2d aimAngle, double projectileRadius) {
    return aimAngle.copy().mul((projectileRadius + 35.0d) / 7.0d).add(aimPos);
}

3 версия... примерно тоже самое, что и вторая, только теперь я в коллекцию прожектайлов добавлял те, что могут быть выпущенны магами в ближайшие 50 тиков, для каждого направления они генерировались свои, чтобы маг как бы всегда стрелял в самую неудобную точку. перебиралось примерно так:
- сначала пытался увернуться от всех реальных снарядов в 32(+1) направлениях, при это создавая снаряды "вероятностные" по мере движения
- если снаряд попадал в меня в этом направлении добавлял его дамаг
- если попад в поле вышки и я был та таргетом и кд =0 добавлял еще дамаг от вышки
- если ни один снаряд в меня больше не попадает, то из этого направления я начинал новый перебор опять в 32(+1) направлениях до тех пор пока уже не "вероятностных" снарядов или пока не увернусь от всех них или не столкнусь с препядствием.
А, и дамаг от "вероятностных" снарядов я добавлял с экспотенциальным затуханием по расстоянию которое пролетит снаряд - чтобы со временем маг убегал от слишком приблизишихся магов, а не считал "какая разница, что тут попадут, что на границе в 1 пиксель от безопасной зоны" - ведь раг мог и не выстрелить :)

Это самая сложная и сама костыльная часть проекта, т.к. приходилось ного чего править, допиливать, убирать лишнюю пугливость, проверять когда можно поворачиваться для выстрела, а когда надо 100% уворачиваться (если не мог увернуться от реальных прожектайлов, то я даже не рыпался). Делать костыли на то, что маг может слегка подбежать.



Вот 3 версия позволила убрать поле опасности визарда и приближаться к нему гораздо ближе и все еще уворачиваться от выстрелов (даже тех, что еще не сделали).

Наверное это самая основа алгоритма, разуеется было куча твиков, я падал по времени с 3ми уворотами, было куча ошибок и багов в константах, некоторые баги в константах заставляли меня подниаться буквально моментально мест на 10-20 выше (в топ-100)

Получилось много и субурно, если что-то не понятно или какая-то конкретика нужна - спрашивайте.

P.S. с первого раунда научился добивать своих (даже с бешенныи рейтами на Френдли фаер в первом раунде это можно было сделать чередуя дубинку и ММ), это иногда помогало не "кормить" врагов + давало немного больше опыта в перво раунде, но это не так значимо, как удовольствие от очередного союзника которого увел в лес и забил под сосной...
Записан

vzverev78

  • Newbie
  • *
  • Сообщений: 4
Re: Ключевые решения вашей стратегии
« Ответ #37 : Декабря 27, 2016, 02:23:23 am »

Такие товарищи как vzverev78 бросают все и идут фармить туда где и так своих куча, а ты бежишь спасать свою базу вместо набора очков, в итоге если выйграли ты 5й а то и 6, 7й, если проиграли 10й. Отсутствие смены веток - если програли ты 6, 7й, если выйграли скоре всего сам взял базу - ты 1, 2, 3й. Вот так. Конечно полностью исключать защиту не стоит, я например оставил ее при возрождении, но в целом - крайне не выгодная штука.
У меня тоже заложен возврат к базе на защиту и последующая смена ветки на ту, которую пробили. Но только если я не ушёл за пределы диагонали бонусов. Например, тут после 2800-го тика: http://russianaicup.ru/game/view/200097
Случаи не частые, но мне кажется, что это проигрышная тактика.
Записан

lama

  • Full Member
  • ***
  • Сообщений: 83
Re: Ключевые решения вашей стратегии
« Ответ #38 : Декабря 27, 2016, 02:39:37 pm »

Я "для своих" написал более-менее подробно, но т.к. особых успехов у меня не получилось (на момент прекращения разработки, перед финалом, был где-то в районе 45-го места), не знаю, насколько это кому-либо будет интересно, но если что, прочесть можно тут: http://lama.od.ua/stuff/wiz.html

Сюда же кину только видео:
https://www.youtube.com/watch?v=x3RbgLczAzg
Записан

wntgd

  • Jr. Member
  • **
  • Сообщений: 36
Re: Ключевые решения вашей стратегии
« Ответ #39 : Декабря 27, 2016, 05:05:45 pm »

Присоединюсь и расскажу, как мой квикгай в топ 30 песка пытался держаться.

Первый вариант передвижения был прост как пробка, иди по вейпоинтам и обходи препятствия по касательной с зазором 5 юнитов. А так же в любой ситуации бей деревья палкой)
Потом проапгрейдил до А* на поле со штрафом проходимости, деревья на 1 удар имели мизерный вес, остальные чуть больше. Визардам  и миньонам поставил средний вес, башням и краям карты максимальный. В таком случае если на уголке получившейся карты была цель, проход к которой закрывала скажем башня, А* проходил все поле ища обходной путь и ломая фпс, поэтому непроходимые обекты на краю поля считались проходимыми и обретали вес только при приближении к ним. Ломаную выпрямлял просто, если между точками есть дорога, то удаляем промежуточные. Так же всегда стирались первые 2 точки, обеспечивая костыльную гладкость движения. Обход препятствий по касательным, вроде даже без всяких зазоров. В итоге очень бодро бегал по лесам, срезая только деревья на пути.
Руну контролил создавая фейкового миньона на карте, визард кружился вокруг него до появления руны, а в последний тик фантомный объект убирался и визард брал руну.

Так же написал всякие поля опасности и потенциального опыта для этой же карты передвижения, но не успевал ничего отладить и оставил идею за двойными слешами.

Само передвижение контролилось относительными вейпоинтами: текущее положение лайна, точка отступления, точка нападения. Отдельный класс рассчитывал опасность и решал, отступать или нет. Там рассчитывалась относительная сила союзников и врагов и при превосходстве визард мог зайти за крипов врага и бить стафом. Из-за такой тактики пуша в первом раунде (отдавая максимум своего регенящегося хп танкуя урон) в меня постоянно стреляли тавера, из-за чего я сильно бомбил. Но с постом о приоритете таргетов башен все решилось. Смотрел текущую цель башни и подходил когда все норм. Так же тут была куча ультимативных условий типа: Отступи при получении дамага, никогда не подходи один к таверу, отходи от трона или точки спавна крипов перед их появлением, упарывайся за лоу хп противниками, держи дистанцию для уворота и т.д.

В зависимсти от раунда менялся выбор целей. Сначала в приоритете были визарды, за ними слабые крипы, незаагренные нейтралы, башни, потом все остальное. С появлением уворотов начал игнорировать фул хп визардов и больше приоритета отдавал башням. Фаербол кидался в наиболее приоритетную цель с попыткой задеть основным сплешем еще кого-нибудь.

Позже реализовал простейшие увороты назад: сохраняя тик появления снаряда вычислял его дальность полета и отходил назад, если надо было. Тут добавилось еще одно условие опасности: держаться на макс ренже от визардов врага (при их огневом превосходстве). После этого так же переключил ветку прокачки на ренж, т.к. иначе визард был очень пугливым и не доставал иногда даже до крипов.

Ну и для финала успел сделал пару костылей. В первой части финала шел всеми мид и качали дальность атаки. Каждый визард независимо принимал решения, но ввиду одинаковой ситуации действовали они сообща. Единственное что успел сделать, так это упарывание в ближайшего врага, если есть превосходство в силе. Ну и раш в трон, как только тот получил дамаг (но убийство визардов на респе все равно имело больший приоритет) Во второй части ходил 1-3-1, боковые качали фаербол и заморозку и шли на мид после получения ульты. Винрейт от смены стратегии не изменился, 35%
Записан

Adler

  • Jr. Member
  • **
  • Сообщений: 31
Re: Ключевые решения вашей стратегии
« Ответ #40 : Декабря 27, 2016, 06:03:55 pm »

У меня всё намного проще:
Идём к текущей башне на mid`
Если видим врага за спиной(его проекция на ось атаки ближе к нашей базе чем наша проекция), то идём к нашей базе.
Если какой-то враг/башня может в нас попасть, то идём к нашей базе.
Если в нас летит пуля, то идём к нашей базе.
Если hp меньше 50%, и на основе симуляции оказываться, что после одного нашего шага вперёд враг сможет нас догнать и попасть в нас выстрелом даже если мы будем идти к нашей базе поворачиваясь, то поворачиваемся и идём к нашей базе.
Когда идём используем обычное расталкивание, чтобы обходить препятствия.
Всегда как-бы пытаемся выстрелить в центр каждого врага всеми доступными орудиями.
Затем используя оценочную функцию выбираем самый выгодный выстрел и выполняем его: делаем поворот и стреляем.
Вначале стреляем по магам с максимальной дистанции, но чтобы не стрелять в тех кто уворачивается ведём статистику стрельбы и отслеживаем свои пули, а потом даже не пытаемся стрелять если с этой дистанции ранее попасть не удавалось.
Были ещё всякие мелки костыли типа: забить на угрозу от башни если не видно вражеских магов и hp>90, но это всё мелочи и лень про них писать.

Собственно всё.

Когда появились скиллы, то сразу же добавил код который их учитывал, но играл в Round2 без учёта эффекта от ауры ускорения союзников/врагов.

Скиллы до финала качал по порядку, но игнорируя болт/шар/ускорение/щит, т.к не было реализовано.

Перед финалом добавил:
Учёт эффектов от ауры ускорения.
Изучение разными магами разных умений в финальном режиме вот так: TO_FROST_BOLT, TO_FIREBALL, TO_MISSILE, TO_HASTE, TO_SHIELD.
Использование болта/шара.
Накладывания ускорения/щита на союзников.
Сделал в финальном режиме общую для всех пяти вражеских магов статистику по выстрелам.
Сделал в финальном режиме сбор статистики стрельбы со всех пяти своих магов. Для этого просто вызывал: ((MeWorld&)world).move(ally,world,game,unused);
Начал вести статистику стрельбы в формате: ang, maxspd, dist.
В финальном режиме запретил проворачиваться к нашей базе если hp больше 16.
В финальном режиме сделал костыль который уменьшал радиус опасности от врагов на 64 если если рядом есть здоровый союзник который готов стрелять также как и мы.
Ну и ещё всякие мелочи от которых никакого толку типа: в финале стоять стеной перед своей базой.

Вроде всё.

also: после Round1 разрабатывал версию на основе переборщика траекторий из CodeRacing, но не увидел выгоды от него в финале(т.к в финале ПЯТЬ магов, а не одна машинка) и поэтому прекратил его разработку за день до начала Round2 так ничего толкового и не залив.

Вообще мир слишком грубый:
1) Нет инерции.
2) Нет подготовки к выстрелу.
3) Нет подготовки к появлению миньонов.

И сложный:
1) Импульсный и точно не предсказуемый поток вражеских миньонов. // Да и своих тоже
2) Миньоны с закрытым алгоритмом управления.
3) ДЕСЯТЬ wizard`ов.
4) ДЕСЯТЬ параметров в Move.

Поэтому у меня с планировщиками/переборщиком в этом конкурсе всё плох, но основная причина не использования - закрытый исходный код симулятора игрового мира.

PS: вот код: https://github.com/adler3d/CodeWizards/blob/master/v150.cpp
« Последнее редактирование: Декабря 27, 2016, 06:06:27 pm от Adler »
Записан

DVS

  • Hero Member
  • *****
  • Сообщений: 682
Re: Ключевые решения вашей стратегии
« Ответ #41 : Декабря 27, 2016, 07:07:51 pm »

Закрытый исходный код.. Как много об этом уже написано.
По аналогии с именами игроков, нужно чтобы по этому поводу высказался ктото из топов в духе что не должно быть тем для декомпиляции бокал ранера.

Тогда есть надежда, что в следующем капе будет концепция полностью открытого кода.
Записан

bulletnsk

  • Newbie
  • *
  • Сообщений: 1
Re: Ключевые решения вашей стратегии
« Ответ #42 : Декабря 28, 2016, 10:06:24 pm »

У меня стратегия была на основе смартгая + улучшения:
1) Вейпоинты смещены так, чтобы не пересекаться с тропами миньонов (нападать и отступать удобнее)
2) Уворот: сначала оценивается, летит ли в меня снаряд, или же вражеский маг смотрит на меня, у него заклинание не в КД и рейндж позволяет. В этом случае уворачиваюсь. По возможности отстреливаюсь.
3) Опасность: вражеские маги (в оценочной функции рейнж вражеской атаки, угол поворота, разность ХП, кд заклинаний), вражеские миньоны (если нет моего миньона, расстояние до которого меньше, чем до меня, то опасен) и башни (формула на основе темы из этого форума). В случае опасности отступаем на предыдущий вейпоин и по возможности отстреливаемся.
4) Цель: башни, вражеские маги, миньоны. Все просто: если рейн моей атаки позволяет, атакую. Для магов еще добавлял дельту, чтобы гнаться и добивать.
5) Реализован обход по касательной препятствий
+ костыли вроде отступления перед новой вольной вражеских миньонов (если стою в зоне респавна), прокачки только одной ветки скиллов (первым делом дмг+лёд, затем рейнж атаки).

Больше всего профита дали увороты. К сожалению, на момент 2 этапа, еще не все части были готовы, так же было много багов, вроде неправильного знака или сравнения или коэффициента. Закончил соревнования на 75 месте второго раунда, а затем на момент старта финала был на 13 месте в песочнице из тех, кто не попал в финал :)
Записан

infsega

  • Jr. Member
  • **
  • Сообщений: 36
Re: Ключевые решения вашей стратегии
« Ответ #43 : Января 03, 2017, 01:21:42 pm »

Моя стратежка уложилась в 895 строк, сто из которых - поддержка скилов :)

Ключевые моменты:

 (1) МЯСО ВПЕРЕД!
идти по линии ЗА союзным авангардом (любой юнит или здание). Если авангард расстреляли - пятиться назад вдоль линии.
особенно круто смотрится, когда ты возвращаешься от бонуса к своему авангарду, расстреливая противника с фланга

 (2) ПЬЯНЫЙ СТИЛЬ
непреодолимые препятствия обходятся стрейфом (60 тиков в одну сторону, 60 в другую, упруго отскакивать от препятствий)

 (3) КАНАДСКИЙ ЛЕСОРУБ
рубить всё подряд. если начал рубить дерево - не отвлекаться, рубить до победного

 (4) И ВЕСЬ МИР ПОДОЖДЕТ
не ходить на базу противника, ждать у ближайшего респауна, отвлекая вражеских миньонов на себя

 (5) ХОЛОД ВСЕГДА МНЕ БЫЛ ПО ДУШЕ
основной скил - ледяная стрела. грамотно добивать отморозков я так и не научился - банально не успел.

Вкупе со всякой мелочью - стабильно в топ300 и футбооооолочка :)
Записан

Stef

  • Full Member
  • ***
  • Сообщений: 96
Re: Ключевые решения вашей стратегии
« Ответ #44 : Января 03, 2017, 03:36:18 pm »

Моя стратежка уложилась в 895 строк, сто из которых - поддержка скилов :)

Ключевые моменты:

 (1) МЯСО ВПЕРЕД!
идти по линии ЗА союзным авангардом (любой юнит или здание). Если авангард расстреляли - пятиться назад вдоль линии.
особенно круто смотрится, когда ты возвращаешься от бонуса к своему авангарду, расстреливая противника с фланга

 (2) ПЬЯНЫЙ СТИЛЬ
непреодолимые препятствия обходятся стрейфом (60 тиков в одну сторону, 60 в другую, упруго отскакивать от препятствий)

 (3) КАНАДСКИЙ ЛЕСОРУБ
рубить всё подряд. если начал рубить дерево - не отвлекаться, рубить до победного

 (4) И ВЕСЬ МИР ПОДОЖДЕТ
не ходить на базу противника, ждать у ближайшего респауна, отвлекая вражеских миньонов на себя

 (5) ХОЛОД ВСЕГДА МНЕ БЫЛ ПО ДУШЕ
основной скил - ледяная стрела. грамотно добивать отморозков я так и не научился - банально не успел.

Вкупе со всякой мелочью - стабильно в топ300 и футбооооолочка :)

За одно только описание алгоритма, уже можно давать футболочку :)
Спасибо развеселило :)
Записан

zn-soft

  • Jr. Member
  • **
  • Сообщений: 36
Re: Ключевые решения вашей стратегии
« Ответ #45 : Января 04, 2017, 04:16:14 am »

Моя стратежка уложилась в 895 строк, сто из которых - поддержка скилов :)

Ключевые моменты:

 (1) МЯСО ВПЕРЕД!
идти по линии ЗА союзным авангардом (любой юнит или здание). Если авангард расстреляли - пятиться назад вдоль линии.
особенно круто смотрится, когда ты возвращаешься от бонуса к своему авангарду, расстреливая противника с фланга

 (2) ПЬЯНЫЙ СТИЛЬ
непреодолимые препятствия обходятся стрейфом (60 тиков в одну сторону, 60 в другую, упруго отскакивать от препятствий)

 (3) КАНАДСКИЙ ЛЕСОРУБ
рубить всё подряд. если начал рубить дерево - не отвлекаться, рубить до победного

 (4) И ВЕСЬ МИР ПОДОЖДЕТ
не ходить на базу противника, ждать у ближайшего респауна, отвлекая вражеских миньонов на себя

 (5) ХОЛОД ВСЕГДА МНЕ БЫЛ ПО ДУШЕ
основной скил - ледяная стрела. грамотно добивать отморозков я так и не научился - банально не успел.

Вкупе со всякой мелочью - стабильно в топ300 и футбооооолочка :)


за самую аскетичную, минималистичную страту тоже можно давать призы и оценивать их скил в отдельном конкурсе типа js1k.com
Записан

ALEXks

  • Jr. Member
  • **
  • Сообщений: 19
Re: Ключевые решения вашей стратегии
« Ответ #46 : Января 09, 2017, 12:13:49 pm »

Идею с потенциальными полями я увидел достаточно поздно, а опыта участия в подобных соревнованиях было мало - участвовал только в прошлом году. Поэтому за основу был взят пример из быстрого старта. Очень понравился тот факт, что не было физики, как в прошлом году, а также я когда то играл в доту=). Так как уже очень смутно осталось представление о том, что было до 1 раунда, что до 2 раунда  и финала, опишу просто ключевые моменты.

Концепция: когда я узнал по ПП, то был на подходе либо 1 раунд, либо он уже был пройден. Переделывать алгоритм очень не хотелось, так как я начинал еще с бета тестирования и написано было уже много. Но проводя аналогию, мой подход был чем то похож на ПП. В основе лежал набор состояний, в которые стратегия может перейти в зависимости от условий и текущей ситуации. Такими состояниями могут быть: движение к бонусу, атака, добивание башней, уворот от атаки и т.д. Каждое состояние может влиять на другие состояние - в большинстве случаев перекрывать (отменять) действие состояния. Так как код фактически линейный, то все состояния просто проверяются каждый раз и активируются те, у которых выполнены условия. Например, если мы стоим на лайне и подходит время брать бонус, то в дополнении к времени проверяются разного рода условия - идет ли наступающий фронт, есть ли у нас преимущества, находимся ли мы в пределах зоны, где можно отойти за бонусом, или же надо проносить базу.

Некоторые ошибки: возможно из-за такого объема всяких свойств времени действительно не хватало на детальную реализацию, поэтому почти до последнего момента (где то до второй недели после 1 раунда, можно узнать по коммитам) передвижение было очень топорным - ключевые точки из быстрого старта + возможность отходить назад, но потом это было исправлено. Также я почему то не подумал, что можно наносить урон дальше, чем дистанция каста, причем сильно дальше. Почти до начала 2го раунда многие этот факт не учли и было все окей, но потом - моя страта начала проигрывать и я стал замечать, что можно атаковать с большего расстояния, а также где то на форуме это тоже звучало.

Передвижение: Основной момент - рекурсивная функция, которая позволила просчитывать на глубину в 6 тиков по сетке в 7*6 и порогом 25%. Суть такова: перебираем все шаги на максимальное расстояние вокруг себя по сетке 7 шагов по длинной стороне (вперед-назад) и 6 по короткой (влево-вправо) и оцениваем эту позицию: можно ли на нее встать, и если да - то накладываем разные штрафы и бонуса - как раз то место, где есть использование ПП. Далее по порогу отсеиваем этот набор точек по функции оценки и повторяем рекурсию для оставшихся. Функции оценки линейны, в зависимости от расстояния, а также учитывалась атака противников, кулдаун до начала атаки, радиус деревьев и даже была попытка учесть союзных минионов, чтобы не застрять. Так же передвижения всех остальных юнитов тоже симулируются на 6 тиков, но в том направлении и с теми же скоростями, что были зафиксированы до запуска рекурсивной процедуры. Деревья также давали штраф. Если вокруг не было вражеских юнитов, то просчет упрощался, чтобы сэкономить время.

Некоторые выше писали, что рекурсия - это долгий процесс из-за вложенности и многократного вычисления расстояния. Через профилировщик я увидел, что все время в этой процедуре занимает функция hypot(x, y) и, погуглив в нете, я обнаружил, что эта функция работает намного дольше (примерно в 40 раз), чем простое sqrt(x*x+y*y). В данном случае, где координаты лежат в диапазоне 0..5000, функция hypot вообще не нужна (предлагаю читателю самим поискать, почему функция hypot лучше sqrt). И в итоге, я решил отказаться вообще от извлечения корня, где это возможно и тем самым перевел все на сумму квадратов. Ведь даже расстояние между юнитами можно оценить не вычисляя корень - достаточно только суммы квадратов. Умножения и сложения выполняются быстрее, чем извлечение корня и тем самым стало возможным считать на глубину 6-7 тиков и достаточно подробной сеткой (или деревом), причем на последнем уровне могло быть 3-6 точек.

Единственный минус - я мог оказаться в локальном минимуме между деревьями и частенько застревал. Причина этого явления - слишком близкая допустимая дистанция до самих деревьев, а также - все таки маленькое количество тиков рекурсивной функции. С этим я так и не поборолся, но решил сделать так, чтобы мой маг уничтожал деревья, которые потенциально могут ему помешать в будущем.

В итоге, такое передвижение позволило разъединить поворот, атаку и шагание. С самого начала игры я пробовал делать уворот, но лучше, чем просто отход назад, у меня ничего не вышло, так как если находиться слишком близко к врагу, то увернуться практически не возможно. Также был добавлен прогноз где то на 2-3 тика (регулируемый параметр), который позволял сдвигать центр атаки в ту сторону, куда собирается двигаться вражеский юнит.

Почему не попал в финал: во время второго раунда мне не хватало около 100 очков, чтобы попасть в список финалистов. Но я решил рискнуть и сбросить рейтинг, а также добавить больше агрессии - не так отрегулировал коэффициенты и в том числе от того, что союзные герои ведут себя не так, как хотелось бы, падал в рейтинге. Например, был повышен коэффициент и условия добивания базы. И я наблюдал такую ситуацию, что вместо того, чтобы помочь добить базу, мой союзный волшебник просто отходит назад и в итоге я дохну. Либо происходит плохое распределение по линиям. Либо некоторые стратегии продолжают ходить за бонусами, вместо проноса базы. И так как я не поднялся до того уровня, что хотел, а до финала оставалось 3 дня, я решил забить и не стал больше ничего менять.

После изменения баланса после 1 раунда, я держался в районе ТОП 30-50. Возможно не правильный тюнинг коэффициентов и не такой правильный подход не позволил попасть в финал. Для боев 5*5 я тоже пробовал много тактик, но остановился на 5 по центру, так получалось и лучше и быстрее. Но опять же не хватало более точной оценки соперника. Функции штрафов были слишком грубыми для ТОП20.

Как ни странно, я почему то решил, что огонь - не самый лучший вариант, потому что если не дать прокачать огонь противнику на лайне и быстрее прокачать дальность и скорость атаки, то ты становишься в плюсе. Я пробовал разные тактики, и через скорость + фриз, и через огонь + дальность. Все они есть в коде. Для 5*5 я одного мага качал на дальность + скорость, остальных - на огонь.

В целом, я убил достаточно много времени и игра в этом году была достаточно интересной. Участие в чемпионатах подобного вида мне нравится и я готов продолжить участие в следующем году =)

Ссылка на код: (почему то в этом проекте, и только в этом, решил писать русские комменты. Там прокомменчено достаточно много и я думаю разобраться можно очень легко, писал на С++).
https://bitbucket.org/ALEXks/wizards/overview
Записан
Страницы: [1]