Компьютерное моделирование футбола и разработка электронных стратегий игры
, ,
*****@***ru, *****@***ru, *****@***ru
Санкт-Петербургский Государственный Университет
(Университетский пр., д. 28, тел/факс:4284210)
Введение
Группа ведущих мировых ученых, проработав несколько лет, составила список приоритетных задач кибернетики (теории управления) на ближайшие 50 лет (доклад Ричарда Мюррея в на конференции в Вашингтоне, 26-27 апреля 2002 года [1])
Среди них
1. Создание команды роботов-футболистов
2. Управление через Интернет
3. Асинхронная теория управления
4. Динамически реконфигурируемое интеллектуальное управление
5. Перепрограммировать систему управления бактерией
Перед исследователями была поставлена следующая задача:
«By 2050, develop a team of fully autonomous humanoid robots that can win against the human world champion team in soccer» (К 2050 году разработать команду полностью автономных роботов, которая сможет обыграть чемпионов мира среди людей)
Большинство программ виртуального футбола разрабатываются для развития теории искусственного интеллекта, робототехники и смежных с ними областей. Это поле – хороший полигон для развития старых идей и разработки новых. Причины, по которым был выбран футбол:
1) динамичность происходящего,
2) сложность организации командного взаимодействия,
3) популярность во всем мире.
В настоящее время проводится несколько чемпионатов по виртуальному футболу. Каждый из них базируется на своей физической модели. Также варьируются правила, количество игроков в команде и интерфейсы. Наибольшую известность в мире получил RoboCup (www. robocup. org), в России же существует своя лига виртуального футбола (www. *****/programs/robosoccer).
Наша группа ведет разработку команд именно для этих двух чемпионатов. Все чемпионаты производят симуляцию футбола по тактам. В один такт каждый игрок получает информацию и может послать на сервер свое действие. Длина такта варьируется в зависимости от чемпионата, но обычно это достаточно маленькая величина, что является еще одной проблемой для разработчиков.
Российская лига
Лига основана в 2000-м году, и в 2001-м году прошел первый товарищеский турнир. На данный момент прошло более 10 турниров, и 25 сентября начнется турнир «Крымская осень» в городе Кацивели в рамках Пятой Международной конференции «Искусственный интеллект-2004», в котором мы планируем выставить команду «SPbGU». Основные особенности:
1) простая физическая модель (все объекты – упругие шарики),
2) отсутствие правил: аута, углового, штрафного и т. п.,
3) отсутствие помех в модели.
При разработке стратегии игры возникают три проблемы: управление «ногами» и «головой» игрока, а также командное взаимодействие. К первой относятся такие действия, как «добежать в данную точку», «ударить по мячу» и т. п. Сложная задача, относящаяся, ко второй проблеме – предсказание перемещения объектов по полю. К командной стратегии относятся такие задачи, как распределение игроков по позициям, занимаемым ими на поле, взаимодействие игроков.
К сожалению, в этой версии практически невозможно реализовать грамотный розыгрыш мяча. Приходится отбивать мяч в зону, где находится партнер. Кроме того, игра временами, напоминает регби, а не футбол, так как футболисты могут толкать друг друга. Разумеется, это далеко от реальности, однако скоро планируется новый вариант сервера, и игра станет реалистичнее. С другой стороны, такая физическая модель наиболее приближена к модели «роботов-тележек», которые просто толкают мяч своим корпусом. В следующем году планируется организация в России лиги игры среди таких роботов.
RoboCup – Simulation league
В большей степени настоящий футбол напоминает проект RoboCup, а вернее одна из его лиг - Simulation league. Он был основан в 95–м году и зарегистрирован в Швейцарии. Основные особенности:
1) реалистичная физика и модель игрока,
2) наличие почти всех правил футбола,
3) наличие помех,
4) усложненное взаимодействие игроков,
5) локальная визуальная информация,
6) более строгие ограничения по времени такта.
Вся информация приходит игроку с помехами и в системе координат с центром в самом игроке. Помехи зависят от расстояния и могут быть достаточно значительными (на расстоянии 100 метров они могут достигать 10-ти). Так как информацию о положение объектов на поле удобнее хранить в глобальных координатах, нам необходимо локализовать местоположение игрока на поле. Для этого используются метки с известными координатами, называемые флагами. По положению игрока относительно них мы и определяем свое глобальное местоположение. Для этого мы используем методы фильтрации случайных процессов.
Рассмотрим процесс определения нашего местоположения. Для этого мы используются всевозможные пары видимых флагов. Для каждой пары, зная расстояния до флагов и направление на них, мы можем определить свое местоположение, но оно будет не точным, так как присутствуют помехи. Пусть мы получили на шаге с номером n некоторую точку. Теперь на шаге с номером n+1, когда мы получаем новое значение, мы должны учитывать его с некоторым коэффициентом. Какой же он?
Пусть мы имеем два флага. Зная значения расстояний до них, мы можем понять верхнюю и нижнюю границу множества значений, из которого эти расстояния могут быть получены при наведение шумов. Таким образом мы получаем два кольца с центрами в рассматриваемых флагах. Пусть s_i – площадь их пересечения на i – м шаге. Пусть K = s_i/(s_i + s_(i+1)). Тогда можно записать, что y(i+1) = y(i) + (x(i+1) – y(i)), где y(i) – наше положение после i– го шага, а x(i+1) – то, что мы получили при i+1-м измерение. Итого мы последовательно приближаемся к нашему итоговому значению. Точность такой фильтрации это в среднем 0.08 метра, но она достаточно ресурсоемка, так что иногда целесообразно использовать более простые методы.
Так как возможна нормальная игра в пас и точные удары в конкретном направлении и с конкретной силой, то для управления игроком мы планируем реализовать нейросеть. Это будет трехуровневая каскадная нейросеть с примерно 200 входами и 20 выходами. Для взаимодействия с сервером используется протокол UDP, так что игрок должен иметь «нижний уровень», который отвечает за общение с сервером, разбор приходящих пакетов, взаимодействие между потоками управления. Наш низший уровень написан на чистом C, по проведенным тестам он обгоняет по скорости реакции чемпионов мира 2003 года в 3 раза. Второй уровень клиента отвечает за физическое управление игроком и преобразование координат.
Все данные хранятся в разделенной памяти, к которой имеют доступ все потоки программы.
Планы и перспективы
В настоящее время основная трудность состоит в том, что игрок за короткое время должен обрабатывать большой объем информации. Методы, которые используются сейчас не являются эффективными. Поэтому мы собираемся реализовать свой новый способ решения данной проблемы, основывающийся на рандомизированых алгоритмах [2].
В сентябре мы собираемся послать свою команду на чемпионат России, а в следующем году, может быть, принять участие в играх реальных «роботов».
Список литературы:
1. www. cds. caltech. edu/~murray/cdspanel
2. , , «Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах», М.:Наука, 2003
