Russian AI Cup

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

Автор Тема: Интересные решения  (Прочитано 936 раз)

sat2707

  • Newbie
  • *
  • Сообщений: 2
Интересные решения
« : Декабря 25, 2017, 01:55:43 pm »

Друзья, прежде всего -- огромное спасибо за участие! Мы гордимся теми, кто не спасовал перед задачей этого года, которая у нас получилась слегка "с особенностями" ;)
Ну и как вы знаете, мы очень радуемся, если кто-то описывает своё решение и опыт участия куда-нибудь например на хабр, так что не стесняйтесь писать. В начале следующего года, кстати, выберем лучшую статью и подарим автору что-нибудь небольшое, но милое!
Если же вам кажется, что на статью у вас не набирается, смело кидайте решение/мысли/код например сюда. Я, так же как и в прошлом году, буду писать на хабр отчет, куда с удовольствием вставлю дайджест лучших стратегий и отсюда в том числе.
Записан

PlayerDark

  • Jr. Member
  • **
  • Сообщений: 12
Re: Интересные решения
« Ответ #1 : Декабря 25, 2017, 06:48:38 pm »

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

sat2707

  • Newbie
  • *
  • Сообщений: 2
Re: Интересные решения
« Ответ #2 : Декабря 26, 2017, 03:12:09 pm »

так давай же! :)
Записан

mixei4

  • Jr. Member
  • **
  • Сообщений: 36
Re: Интересные решения
« Ответ #3 : Декабря 26, 2017, 10:45:00 pm »

Я очень долго не хотел отказываться от бутерброда. В том смысле, что сначала я строю бутерброд, а потом разбиваю его на несколько частей в зависимости от количества зданий.
Но от полного бутерброда пришлось отказаться по понятным причинам. Я очень боялся отпускать БРЭМы в свободное плавание и мне было лень как-то отдельно следить за разными группами юнитов, поэтому решил всё-таки оставить бутерброд из них и БМП, если они удобно расположены изначально и их можно быстро объединить.
Далее вся моя стратегия свелась к тому, чтобы собрать ещё один бутерброд из самолетов и вертолётов и постараться побыстрее уничтожить вражеские вертолёты. С топ игроками это получалось не очень хорошо, потому что они прятали вертолеты за БМП, ну и истребители тоже мешали. :)
Наземные же юниты просто идут к ближайшему строению для захвата, иногда убегая от врагов, если их слишком много.
По большому счёту это всё. Хотя я в этом не уверен, потому что разобраться в моём коде очень сложно мне самому.
https://bitbucket.org/mixei4/aicup2017
Записан

evgeny.vyalyy

  • Newbie
  • *
  • Сообщений: 1
Re: Интересные решения
« Ответ #4 : Декабря 30, 2017, 05:49:49 pm »

Я играл в пятнашки с помощью графов.
Рассматривал клетки, в которых могут появляться группы, то есть сетку 3х3. Положение каждой группы задается числом v = 3*row + col, где row,col - номер строки и столбца (начиная с 0).
Далее для трех наземных групп.
Определил состояние формации как тройку чисел - положения групп v1,v2,v3. Числа отсортированы по возрастанию. Получилось C93 = 84 состояния. Это вершины графа.
Дальше строил списки смежности. Для каждого состояния рассматривал каждую из трех позиций, сдвигал ее на +1,-1 по строкам и столбцам (4-смежность обычная), исключая сдвиги, которые пересекаются с остальными двумя точками текущего состояния. Двигал по одной точке за раз, поэтому в результате для некоторых состояний получилось псевдооптимальное решение. Новое положение точки вместе со старыми точками образуют смежное состояние, в него проводим ребро.
Потом просто запускал поиск в ширину на полученном графе, если встречал состояние, в котором все точки выстроены в линию (вертикальную или горизонтальную), останавливал поиск. Это тоже приводит к неоптимальности в некоторых случаях (когда одна группа в углу, а остальные рядом), потому что такая структура смежности не учитывает распараллеливание движений.
Затем по полученному маршруту на графе получал последовательность движений для конкретных групп (так как одно ребро - движение только одной группы, это сделать просто).
Потом еще смотрел, и если можно выполнял последовательные действия одновременно (конечное положение текущего действия не пересекается с начальным или конечным положением следующего).

Вот, собственно, и все. Больше в стратегии ничего интересного нет :)
Записан

ud1

  • Full Member
  • ***
  • Сообщений: 98
Re: Интересные решения
« Ответ #5 : Января 01, 2018, 01:47:37 pm »

Итак, расскажу кратко, как работает моя стратегия. Она очень проста и работает исключительно на потенциальных полях.
Есть класс Group который задает группу юнитов. В простейшем случае, в режиме без зданий, группа задается просто типом юнита, всего 5 групп.
В более сложном задается идентификатором группы, или для групп состоящих из одного самолета - идентификатором юнита.
Действия совершаются для групп по кругу - группы пересортируются по времени совершения последнего действия и дальше идет работа с группой у которой время наименьшее.
Для определения куда двигаться, из центра группы испускаются равномерно 20 направлений с одинаковым радиусом зависящим от типа юнитов в группе, т.е. фактически 20 точек на окружности.
Для направления определяется, не приведет ли оно к столкновению с другими дружественными юнитами, и если нет, то для точки вычисляется потенциал.
Выбирается точка, с наибольшим потенциалом, и дается команда move к этой точке.
Для определения столкновений используются только текущие скорости юнитов и максимальная скорость для типа юнитов группы. В простом случае у группы есть BBox, и проверяется,
что при движении BBox не пересечется с другим юнитом не из группы. Если для всех 20 направлений получается пересечение, то выполяется более точная проверка, в которой участвует не BBox группы, а индивидуальные юниты.
Так что остается самая важная часть - это то как вычисляется потенциал точки.
Поле разбивается на ячейки 32*32, для каждой ячейки считается число и суммарное здоровье по типам юнитов.
Дальше производится операция, при которой для каждой вычисленной ячейки приплюсовывается значения из 8ми соседних ячеек. Тем самым каждая ячейка результирующей матрицы фактически содержит суммарное число и здоровье вражеской группы юнитов которая задевает эту ячейку (если конечно эта группа компактна, соизмерима с размером ячейки).
Дальше для каждой ячейки вычисляется опасность для текущей моей группы. Для этого вычисляется суммарное здоровье юнитов запсисанное в ячейке, суммарный максимальный урон, который может быть нанесен моей группе (определяется по типам юнитов и их количеству).
И вычисляется коэффициент опасности ячейки:

double alpha = 0.3;
double alphaM1 = 1.0 - alpha;
double pts = (myGroupHealth * alphaM1 + dCell.totalEnemyHealth * alpha) / (dCell.totalEnemyHealth*0.01 + dCell.totalEnemyDamage)
   - (dCell.totalEnemyHealth * alphaM1 + myGroupHealth * alpha) / (myGroupHealth * 0.01 + myDamage);

Есть интересный коэффициент - alpha. Два крайних случая, alpha = 0 и alpha = 1. В одном случае не будут учитываться количества юнитов в воюющих группах, а только их тип, т.е. группа из 100 вертолетов будет боятся одного самолета.
В другом случае будет учитываться лишь полный урон на единицу техники противоположной комманды, при этом вертолеты могут напасть на меньшую группу самолетов, но монут иметь бОльшие потери. Я использую нечто среднее этих двух случаев.
Для вычисления потенциала в точке, суммируются значения pts для каждой ячейки деленные на квадрат расстояний от цетра ячейки до точки (на самом деле это для положительных pts, для отрицательных же коэффициет убывания другой, чтоб не было дальнодействия).

Это основная часть, но есть пара усовершенствований.
Первое это улучшенный расчет потенциала, чтобы не прижимали к углам карты. Для этого, зная координаты целевой точки, координаты ячейки, максимальную скорость моей группы, усредненую максимальную скорость вражеских юнитов ячейки, чисто геометрически считается число тиков, которой нужно для врага, чтоб догнать мою группу.
В чисто поле это число равно расстоянию между целевой точкой и центром ячейки, деленная на разность скоростей врага и моей группы. В случае краев и углов карты это число тиков получается меньше.
Значение pts соотвествеенно учитывает это число через коэффициент (625 - t) / 625.0. Число тиков рассматривается в диапазоне от 0 до 625.

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

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

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

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

И есть обычное через SCALE уклонение от ядерки. Для этого приберегается 2 действия, елси кулдаун ядерки у врага меньше 100 тиков, чтоб незамедлительно запустить уклонение.
Число действий не учитывает наличие конмандных центров, и строго равно 12 командам в 60 тиков. Попытки более равномерно распределить команды по тикам положительного эффекта не дали и я не стал это делать.
Для вычисления числа доступный тиков используется очень простой метод:

int Simulator::getAvailableActions(int actionsPer60Ticks) const
{
   size_t actions = std::distance(actionTicks.lower_bound(tick - 59), actionTicks.end());
   return actionsPer60Ticks - (int) actions;
}

Исходный код:
https://github.com/ud1/ud1_RAIC2017_CodeWars
« Последнее редактирование: Января 01, 2018, 01:49:56 pm от ud1 »
Записан
Страницы: [1]