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

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

Введение

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

Для тех, кто не знает не только команду 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, мы можем записать: . Возводя в квадрат правую и левую часть, получаем квадратное уравнение относительно времени столкновения: