Russian AI Cup 2014: стратегия победителя

[Fluttercom]

Мда, я понял, как мне было далеко до финала…

[imwode]

Так как работает отскок от стены, а?
Каждый тик проверяется пересечение центром шайбы границ поля. Если произошло пересечение, то скорость инвертируется с умножением на 0.25. А вот координата — по разному. Если в следующий тик шайба просто вследствие инверса скорости попадает в поле, то все ОК. А вот если нет — там какая-то чудесная магия происходит, корелляцию я так ни с одним параметром и не увидел.
А автор физику восстановил без декомпиляции локалраннера, просто глядя на изменения параметров? мощь.

[cjey]

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

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

График зависимости угла отражения от угла падения и скорости. Видно, что от скорости угол отражения не зависит.


График скорости отражения от угла падения и скорости падения.

Видно :), что скорость отражения линейно зависит от скорости падения, а значит что нужно искать зависимость ускорения от угла падения.

[imwode]

Подождите, я все равно не понял. Изменение скорости — это всегда 1/4 от скорости ДО удара. Там без графиков за минуту это очевидным становится (но инструмент мне освоить надо, спасибо!). А вот изменение координаты на десяток пикселей, если шайба слишком глубоко погружается в стенку — вот тот чертополох мне непонятнен.

[cjey]

Ну у меня получилась нелинейная зависимость коэффициента поглощения от угла. Возможно у меня где-то закрался баг, возможно при углах близких к 45 градусам коэффициент не сильно отличается от 0.25, но при углах около 0 и 90 значение может быть другим. Возможно после бета теста, что-то поменялось. В целом, полет шайбы у меня предсказывался хорошо даже после нескольких соударений со стенками.

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

[imwode]

Неа, не до конца ты разобрался. Там каждый тик идет проверка — где мы? За полем, ок, _просто инвертируем скорость_. Т.е. шайба уже за полем, а мы целый тик только скорость инвертнули. Ок, на след тик она поехала в обратном направлении. Если выехала в ринг обратно — все хорошо, нехай катится. А вот если нет — координата меняется вручную. А как — фиг поймаешь. Есть только ощущение, что как-то строится нормаль к стенке, берутся отношения отрезков радиуса и т.д. В общем — магия!

[DrSmile]

Детальные формулы можно посмотреть в исходниках. Например, отскок от верхней стенки:

constexpr double wallBounce = 0.25;
constexpr double minDepth = 0.01, depthFactor = 0.8;

if((delta = rinkTop + puckRad - pos.y) > 0)
{
    if(spd.y < 0)spd.y *= -wallBounce;
    if(spd.y < delta)pos.y += depthFactor * (delta - minDepth);
}

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

[imwode]

А вот есть ощущение, что весь этот цирк — необходим был? Почему не сделать тупо «оптическое» отражение шайбы от борта? Зачем все эти расчеты непонятные, дающие +-5точек? Уверен, что на поведение шайбы это бы не сказалось _никак_.

[DrSmile]

Ну так я, вроде, и написал в статье, что эти мелочи не важны были. Просто, если у меня уже есть рабочая формула, зачем ее упрощать, рискуя что-то сломать?

[imwode]

И я ничего не понял про главный алгоритм :-( «Параметризуется» — значит интерполяция, т.е. перебор не по набору ускорений [-1, 0, 1]? Что значит абзац про выход под определенным углом и соезинение двух траекторий коцами? :-(

[DrSmile]

Все ускорения фиксированы, рассматривается только минимум и максимум, а для поворота еще и ноль. Оптимизация идет по времени переключения с одного режима на другой.

Траектория первого типа — это, например, 15 тиков полный вперед и влево, а потом просто полный вперед.
Или 10 тиков полный вперед и вправо, потом 30 тиков (поворот на 90°) полный назад и вправо, потом просто полный назад. В первом варианте 15 тиков поворота, во втором 40 — по этому параметру и ведется начальный перебор.

Траектория второго типа — это одна траектория первого типа плюс еще одна, но назад по времени.
Например, 15 тиков полный вперед и влево, потом полный вперед 50 тиков, потом 20 тиков полный вперед и вправо.
Тут параметры — это 15 тиков первого поворота и 65 тиков — начало второго поворота.

[mentatxx]

Отличная работа. А сколько часов (хотя бы примерно), у вас ушло на все работы по конкурсу, если не секрет?

[DrSmile]

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

[GoodGreenTea]

Вот как значит оказывается, кого-то физика отпугивает, а кого-то наоборот привлекает.
Я вот (GreenTea) из-за необходимости реверс инжиниринга физики вообще решил не участвовать… Как-то этот класс задач не особо интересен.

Но за статью все равно спасибо, было интересно почитать.
Если действительно на все это ушло в сумме по времени только несколько дней — то ты мегамонстр! :)

[imwode]

Случайность добавляет сложности точного предсказания (делает его принципиально невозможным), однако это плохой, «читерский» способ. Настоящая «глубокая» физика позволяет строить все более точные модели (ценой вычислительной сложности или более продвинутых алгоритмов), случайность же не дает этой глубины.

ВОт это мощная мысль, до которой я не додумался, предлагая ввести случайную составляющую. Посмотрел еще твои комментарии к другим топикам — жалко ты чаще не пишешь…

[Neufor]

Я разочарован… собрали статистику, выявили физику, построили модель, и где здесь AI?

[GoodGreenTea]

Зависит от того как вы понимаете термин AI. Многие его понимают как нечто что обязательно должно самообучаться, но это не всего так. Если посмотреть статью на вики то там видим такое определение:

Major AI researchers and textbooks define this field as «the study and design of intelligent agents»,where an intelligent agent is a system that perceives its environment and takes actions that maximize its chances of success.

Intelligent agent — хоккеисты.
environement — поле, шайба, правила игры, хоккеисты соперника, физика мира.
actions — действия хоккеистов.
Так что формально это и есть AI.