Алгоритм команды Днепр — различия между версиями

Материал из synset
Перейти к: навигация, поиск
(Удар по мячу)
(Удар по мячу)
Строка 124: Строка 124:
 
</center>
 
</center>
 
Положив теперь в уравнении окружности <math>(x,y)= (x_2,y_2)</math>, легко находим  положение точки 2:
 
Положив теперь в уравнении окружности <math>(x,y)= (x_2,y_2)</math>, легко находим  положение точки 2:
 +
 
<center>
 
<center>
 
<math>
 
<math>
Строка 132: Строка 133:
 
</math>
 
</math>
 
</center>
 
</center>
 +
 
где вектор <math>R=(x_1-x_0, y_1-y_0</math>). Сам же центр окружности 0 лежит на перпендикулярном к k  векторе <math>a*(-k_y,k_x)</math>, или <math>a*(k_y,-k_x)</math>. К вектору (в плоскости) можно провести две касательные окружности, лежащие по обе стороны от него. Не сложно сообразить какая из них используется в зависимости от расположения и скорости игрока по отношению к точке удара и вектору k.
 
где вектор <math>R=(x_1-x_0, y_1-y_0</math>). Сам же центр окружности 0 лежит на перпендикулярном к k  векторе <math>a*(-k_y,k_x)</math>, или <math>a*(k_y,-k_x)</math>. К вектору (в плоскости) можно провести две касательные окружности, лежащие по обе стороны от него. Не сложно сообразить какая из них используется в зависимости от расположения и скорости игрока по отношению к точке удара и вектору k.
  

Версия 16:40, 15 января 2010

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Soccer004.gif

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

Soccer006.gif
Soccer008.gif

Первый график – это зависимость , второй . Как и положено, сигма убывает обратно пропорционально корню из 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 :

Soccer011.gif

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

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

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

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

Удар по мячу

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

Soccer018.gif

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

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

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

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

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

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

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

Положив теперь в уравнении окружности , легко находим положение точки 2:

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

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

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

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