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

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

Введение

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

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

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

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

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

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

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

Для того, чтобы в процессе совершенствования алгоритма оставлять благоприобретенные признаки и безжалостно избавляться от красивых, но неработающих идей, необходима четкая методика отбора. Для сравнения относительного качества игры двух команд при счете Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_1:S_2} используется следующая формула

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle Rate = 200 \frac{S_1-S_2}{S_1+S_2}}

Смысл ее ясен. Rate выражает на сколько процентов одна команда забивает больше голов, чем вторая относительно среднего счета Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S=(S_1+S_2)/2} . Естественно, если один алгоритм играет несравнимо лучше другого, Rate стремится к максимуму, равному 200%. В этой области происходит определенное насыщение и слабая чувствительность формулы. Поэтому при постепенном улучшении алгоритмов не стоит новый сравнивать с самым слабым.

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

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

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

Soccer004.gif

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

Soccer006.gif Soccer008.gif