Алгоритм команды Днепр

Материал из Synset

Перейти к: навигация, поиск

Содержание

Введение

Для тех, кто не знает: команда Днепр, чемпион первых (Москва, 2001 г.) союзных соревнований по виртуальному футболу роботов, на самом деле называется по имени нашего сайта: “n-th.com” – в смысле n-тая команда (мы всегда были предельно скромны). Однако в Москве, дабы не потеряться среди множества российских команд, по политическим мотивам :), стали фигурировать в турнирной таблице как команда “Днепр”. В этой статье мы будем именоваться изначальным своим названием.

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

Собственно, алгоритм человеческим языком (С++) изложен в самой программе, которая является вполне самодостаточной. Мы, тем не менее, приведем некоторые идеи, которые были положены в основу этого алгоритма:

  • Прогнозирование состояния
  • Техника удара
  • Специализация игроков
  • Тактика поведения

Команда n-th.com надеется, что открытие финалистами своих исходников и описание идей алгоритмов станет в будущем правилом соревнований.

Однако, прежде чем приступать к разбору полетов, необходимо обсудить ключевой момент – технологию тренировок.

Ложь, огромная ложь и статистика

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

Rate = 200 \frac{S_1-S_2}{S_1+S_2}

Смысл ее ясен. Rate выражает на сколько процентов одна команда забивает больше голов, чем вторая относительно среднего счета S = (S1 + S2) / 2. Естественно, если один алгоритм играет несравнимо лучше другого, Rate стремится к максимуму, равному 200%. В этой области происходит определенное насыщение и слабая чувствительность формулы. Поэтому при постепенном улучшении алгоритмов не стоит новый сравнивать с самым слабым.

Понятно, что если команды сыграли со счетом 2:1 то из этого никак не следует, что одна из них играет на 100% лучше другой. Играть надо долго. Насколько долго? Ответ – очень долго :).

Чтобы исследовать этот вопрос экспериментально, запустим несколько раз игру двух одинаковых команд (у нас это, конечно, была n-th.com) и изучим, как ведет себя Rate при росте среднего счета S.

Двенадцать экспериментов выглядят следующим образом:

Видно, что при малом S, Rate испытывает сильное отклонение от нуля (равные по силе команды). Степень этой ошибки будем оценивать по величине стандартного отклонения сигма, полученного по результатам 12-ти экспериментов при данном S. Поведение сигмы как функции среднего счета S приведено ниже:

Первый график – это зависимость (σ,S), второй (\sigma,1/\sqrt{S}). Как и положено, сигма убывает обратно пропорционально корню из S, примерно как:

\sigma = \frac{100}{\sqrt{S}}

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

Даже достаточно быстрый алгоритм (которым является n-th.com :) требует заметного времени игры для счета порядка 1000. Однако при этом сигма примерно 4. Поэтому если модификация алгоритма дает прирост Rate менее 5, то достоверность его фиксирования в получасовом эксперименте становится сомнительна. Если алгоритм совершенствуется очень постепенно, без заметных “эволюционных” скачков повышения качества игры, то очень быстро он насытится и перестанет улучшаться, хотя бы в силу не достоверности каждой новой небольшой идеи.

Очень интересным является вопрос о математической природе зависимости Сигма(S), W(S) при малых S. Но не будем отвлекаться.

Если Вы захотите воспроизвести эти эксперименты с другими командами (сообщите мне обязательно о результатах), то: включите в game.ini запись счета в log файл: LogFile=soccer.log, в файле arg.cfg установите очень большое время игры. Получившийся после игры файл soccer.log пропустите через утилитку и вперед - в Excel. Да, перед каждым новым экспериментом файл soccer.log необходимо очищать (удалять, переименовывать). Заметим также, что, по-видимому, в сервере стоит встряхиватель случайных чисел в виде srand(clock()), а не srand(time(0)), поэтому, часто последовательные запуски могут быть полностью скоррелированы. Чтобы этого не случилось, для корректного воспроизведения этого эксперимента стоит запускать одновременно несколько игр (из различных директорий). Тогда время запуска программы clock() будут скорее всего различны и нескоррелированы. Можно и другими действиями загрузить диск – например, форматированием :).

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

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

Однако хватит. Переходим к алгоритму.

Знание будущего

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

В нулевом приближении найти время столкновения можно следующим образом. Предположим, что r является радиус вектором от игрока к мячу, скорость игрока в этот момент равна u, мяча v :

Если столкновение произойдет через время t, мы можем записать: \mathbf{u}t=\mathbf{r}+\mathbf{v}t. Возводя в квадрат правую и левую часть, получаем квадратное уравнение относительно времени столкновения:

(\mathbf{u}^2-\mathbf{v}^2)t^2-2(\mathbf{r}\mathbf{v})t-\mathbf{r}^2=0

Вектор r и скорость мяча v нам известны. Полагая, что модуль скорости u равен или текущей или, лучше, максимальной скорости игрока, мы можем найти время столкновения и, соответственно, точку, в которой будет находиться в этот момент мяч. Естественно, уравнение может и не иметь решений. Это будет означать, что игрок мяч догнать не может. В этом случае необходимо либо просто гнаться за мячом либо делать это с небольшим упреждением.

t=t_0+c\,\frac{\mathbf{v}^2 t_0^3+\mathbf{r}\mathbf{v}\, t^2_0}
{\mathbf{r}\mathbf{v} + (\mathbf{v}^2-\mathbf{u}^2)t_0}

где t0 является решением квадратного уравнения. Параметр торможения "c" при фиксированном cfg файле стоит подбирать (в алгоритме 2001 он стоит равный 0.001, хотя на самом деле для rolling friction = 0.995 его теоретическое значение равно 0.002).

Следующими очевидными шагами являются: учет конечного размера игрока и мяча, предсказание с учетом отражения мяча от стенок, невозможность движения игрока за полем, факт дискретности времени, аккуратное значения времени потраченного, на реальную (не прямолинейную) траекторию движения игрока и т.п. Ничего такого команда n-th.com не делает :).

Удар по мячу

Эта техническая проблема является краеугольной в версии виртуального футбола ниже v2.0. Так как единственный способ удара по мячу – это удар всем корпусом, мы должны уметь не просто догнать мяч в точке 3, но и подъехать к нему с определенной стороны и толкнуть в направлении k:

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

Игрок команды n-th.com ведет себя, на самом деле, очень простым образом. В точке удара проводится касательная к вектору удара k окружность с радиусом, равным радиусу минимально возможного разворота при максимальной скорости: ( a = Velocity_max / dAngle_max = 25 ). Игрок, как можно быстрее движется по прямой, которая касательна к этой окружности, и достигнув окружности, начинает разворачиваться с максимально возможной угловой скоростью в направлении k (и, тем самым, движется по этой окружности).

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

Если взять дифференциал от уравнения касательной прямой, проходящей через точки 1 и 2:

(xx1)(y2y1) = (yy1)(x2x1)

и от уравнения окружности радиуса a с центром в точке 0:

(xx0)2 + (yy0)2 = a2

и вычислить его в точке касания 2, то получим:


\begin{array}{l}
(y_2-y_1)dx = (x_2-x_1)dy\\
(x_2-x_0)dx = (y_0-y_2)dy
\end{array}

Разделив уравнения, находим:

(x2x0)(x2x1) = (y0y2)(y2y1)

Положив теперь в уравнении окружности (x,y) = (x2,y2), легко находим положение точки 2:


\begin{array}{l}
(x_2-x_0) = \displaystyle\frac{a}{R^2}(aR_x\pm R_y\sqrt{R^2-a^2})\\[2mm]
(y_2-y_0) = \displaystyle\frac{a}{R^2}(aR_y\mp R_x\sqrt{R^2-a^2})
\end{array}

где вектор R = (x1x0,y1y0). Сам же центр окружности 0 лежит на перпендикулярном к k векторе a\cdot(-k_y,k_x), или a\cdot(k_y,-k_x). К вектору (в плоскости) можно провести две касательные окружности, лежащие по обе стороны от него. Не сложно сообразить какая из них используется в зависимости от расположения и скорости игрока по отношению к точке удара и вектору k.

Что необходимо учесть для повышения точности удара? Прежде всего, конечные размеры мяча и игрока – они сравнимы с радиусом окружности разворота a. Затем не мешает вспомнить о физике. Масса мяча всего лишь в шесть раз меньше, чем у робота. Поэтому, если до удара мяч двигался, то он полетит не совсем туда, куда мы его бьем. Мы не будем на этом останавливаться, так как соответствующие формулы можно найти в трудах любимых ученых. Алгоритм их, к сожалению, не использует. Для квазиучета этих аспектов применялся лишь небольшой сдвиг ударной точки, который подбирался последовательными приближениями.

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

Ударная функция называется Kick и наряду с Goto широко используется алгоритмом команды n-th.com.

Специализация игроков

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

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

void Goalkeeper(short Player, double * dAlpha, double * dV, double s)
{
  double x  = GetX(Player), y  = GetY(Player);
  double xb = GetX(0),      yb = GetY(0);
  double x0 = myGateX,      y0 = GateY0;
  if(  (SortTimeBall[0]==Player && TimeToBall[Player]>0)// мы ближе всех
                                                        // или мяч"в штрафной"
     ||((Dist2ToBall[Player]<Sqr(0.15*fW)||LT(xb, fW1))&&LT(xb,fW0))
                                                        // или мяч летит на нас:
     ||(Dist2ToBall[Player]<Sqr(0.5*fW)||LT(xb,fW1))&&LT(xb,fW0)&&LT(GetdX(0),0))    
    )
  {                                                     // то мы отбиваем мяч
     double KickX = LT(x,xb)? (enGateX+x)/2: xb;
     double KickY = ( y<yb )? GetMaxY(): GetMinY();
     Kick(0, xb, yb, KickX, KickY, Player, dAlpha,dV);
  }
  else Goto(x0+s*(xb-x0),y0+s*(yb-y0),Player,dAlpha,dV);//иначе бежим в защиту
}


Мы не будем описывать все переменные (fW = field width, …)– они есть в исходниках. Отмечу только часто используемую функцию:

bool LT(double x, double y){return (DLL1)? x<y: x>y;}

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

Полузащитниками становятся те, кто не может догнать мяч. Они ведут себя аналогично вратарю, только защищают не центр ворот, а его нижнюю и верхнюю половины. К тому же точка привязки к соответствующим прямым у них смещена в сторону мяча s=0.6, а не ворот как у вратаря.

Все части алгоритма ответственные за специализацию, просты и их стоит прочитать на C++ (функции Goalkeeper и CalcState).

Тактика

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

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

Стратегия

О ней мы даже не размышляли :)

Особые благодарности

Алгоритм команды n-th.com выражает особую благодарность Павловскому Владимиру Евгеньевичу, а также формуле вычисления времени до столкновения с мячом - Predict, методу удара Kick и вратарю Goalkeeper. Вклады каждого из них (кроме В.Е. который неоценим :) приведены в таблице:

Вариант алгоритма dll1 Вариант алгоритма dll2 Rate
Kick(без предсказания и сдвига) Goto 60
Kick(без предсказания, сдвиг 2) Kick(без предсказания и сдвига) 40
Kick (с предсказанием, сдвиг 2) Kick(без предсказания, сдвиг 2) 80
Goalkeeper Kick (с предсказанием, сдвиг 2) 60
Start (начальный розыгрыш) Kick (с предсказанием, сдвиг 2) 15
SimpleKick (тактика) Kick (с предсказанием, сдвиг 2) 12

Цифры для Rate взяты из старых манускриптов и могут отличаться от реальных, но они правильно отражают относительный порядок вклада каждой идеи.

Что стоит делать дальше

Прежде всего - получать от жизни удовольствие. Если форма получения этого удовольствия у Вас выразится в совершенствовании алгоритма команды n-th.com, то предлагаю поразмыслить над следующими моментами:

  • Улучшение предсказания. Учет конечности размеров игрока и мяча; отскока от стенки; штанги; учет начальной скорости игрока в начале предсказания; разворот и разгон в направлении мяча, а также время потраченное на разворот перед ударом; положение вражеских игроков и т.д.
  • Улучшение техники удара. Учет конечности размеров игрока и мяча; физика столкновения игрока и мяча (конечные массы объектов); переменная точность удара в зависимости от ситуации, и т.п.
  • Специализация. Можно попытаться подобрать многочисленные параметры привязки к прямой ворота – мяч для защитников; добавить третьего полузащитника; не мешает поэкспериментировать с выделенным нападающим.
  • Тактика. Здесь существует огромное поле для действия, и многие наверняка уже имеют значительно более продвинутый вариант тактического поведения. Главное, не поддаваться демону очевидности и без самообмана жестко тестировать каждую идею на достоверной статистике.
  • Командная игра. В версии сервера 2 это будет основным тактико-стратегическим аспектом игры. Однако и сейчас возможны более энергичные попытки в этом направлении. Собственно командность игры, по-видимому, и должна стать краеугольным камнем научной части движения виртуального футбола. Тактика “куча мала” не эстетична и, следовательно, неэффективна и не научна J.
  • Учет действий противника. Здесь возможны как простейшие приемы (например, не бить туда, где рядом с линей полета мяча окажется вражеский игрок), так и довольно изощренные (прессинг вратаря, анализ цели групповых действий противника и т.д.)
  • Стратегия. Начиная с версии 1.5, появилась возможность узнавать текущий счет, время игры и т.п. Это уже позволяет менять стратегию по ходу игры. Кроме того, стоит четче реализовывать различные линии действий – защита, полузащита, нападение. Эти стратегии должны обладать определенной инерцией и зависеть не только от положения мяча, но и от общего распределения игроков на поле, того, кто контролирует мяч и т.д.
Личные инструменты