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

Материал из 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, примерно как: