?

Log in

Как я был тренером футбольной команды - Не кинокритик. Не палеонтолог.

сент. 17, 2008

07:43 am - Как я был тренером футбольной команды

Previous Entry Поделиться Next Entry

...которая состояла из несуществующих роботов.

На старших курсах университета и еще пару лет после этого мы с g_e_n_i_e вместе играли в "виртуальный футбол роботов". Это соревнование программистов, цель которого - создать алгоритм игры в футбол для команды, состоящей из пяти роботов-пылесосов (последнее слово - шутка, но и правда очень похожи). Команды сражаются друг с другом на соревнованиях, которые регулярно проходят уже лет восемь. Эти соревнования довольно популярны прежде всего в околонаучных кругах (больше сорока команд, и из них, насколько понимаю, всего пара "любительских"). И потому, что проект "рекламировался" прежде всего в этих кругах, и потому, что создание такой команды является удобной обучающей задачей (в частности, неисчерпаемым источником курсовых работ).

Для дальнейшего изложения важно то, что соревнования полностью симулируются, то есть скорость, с которой проходит игра, ограничена практически только быстродействием компьютера и тем, насколько быстро "думают" команды. Также следует упомянуть, что в случае, если команды примерно равны по силе, для достижения статистически значимого результата приходилось играть до суммарного счета примерно в 1000 забитых голов - в противном случае вывод "кто забил больше голов, тот и лучше играет" оказывается просто недостоверным (кто знает матстатистику, тому что-то скажут слова "три сигма", остальным придется поверить мне на слово). В оправдание настоящего, человеческого футбола предположу, что "примерно равные" (в этом смысле) команды в нем встречаются крайне редко: дело в том, что роботы-футболисты только думают по-разному, а физические возможности всех команд одинаковы. Во всяком случае, хотелось бы надеяться, что дело именно в этом. Иначе, с учетом типичного счета 1:0, обычный футбол имеет не намного больше смысла, чем рулетка.

Примерно год наша команда была "вечно второй", несмотря на то, что мы занимались ей всерьез, и применяли довольно "тяжелые" средства (даже machine learning там тоже был). Отступление: именно тогда я в первый раз понял, что не так важно, с помощью чего вы обучаетесь (SVM, neural networks, генетические алгоритмы, boosting, черт лысый). Гораздо важнее то, как именно вы свели исходную задачу к стандартным задачам machine learning (аппроксимация, максимизация, ранжирование). Ну, наверное, это не универсальное правило, но в задачах "активного AI" оно верно на сто процентов. Наши футбольные алгоритмы весьма глубоко размышляли над ситуацией на поле, распознавали и пытались использовать стандартные паттерны, использовали перебор, в процессе что-то аппроксимировали многочленами от нескольких переменных, решали нелинейные уравнения и тд и тп. Тем не менее, мы стабильно проигрывали команде "Днепр" (второе название - "n-th com"), которая ко всему еще и играла фантастически быстро - если запустить ее играть саму с собой, то на тогдашних компьютерах она доходила до счета 500:500 минут за пять-десять (для сравнения, нашей для этого требовалось часа четыре).

Затем Степанов, автор "Днепра", открыл свои исходники, и мы были жестоко унижены: весь алгоритм занимал строк 500, выглядел тривиальным, и практически в каждом своем блоке был устроен на порядки проще (и, на первый взгляд, хуже) соответствующего нашего. Пора было признать, что мы жили неправильно. Но почему? Сейчас мне это очевидно, но тогда стало открытием: да вот именно потому, что оценить качество любого изменения в "Днепре" можно за 5 минут, а в нашей команде - только за четыре часа. Любое итеративное улучшение происходит в десятки раз быстрее. Именно это и было главным его преимуществом.

В моем пересказе этот вывод кажется почти очевидным; но не появись "Днепр", мы не поняли бы, насколько скорость итераций в AI важна. Я не знаю, осознавал ли это сам Степанов, но когда мы это поняли, мы почти сразу выиграли следующие несколько чемпионатов.

Кроме идеи быстрых итераций наша команда использовала и "тяжелую артиллерию", в качестве которой выступил поиск на графах состояний. И эта тяжелая артиллерия оказалась потрясающе полезной (в отличие от). Поэтому у нас было две версии - быстрая, для тренировок, и финальная, использующая на поиск по графам ровно столько процессорного времени, сколько ей дадут. Вы часто пишете программы, debug которых работает во много раз быстрее release'а?

Оказалось, что скорость итераций можно и еще повысить, если измерять собственные оценки качества для отдельных важных блоков. В качестве примера возьмем блок оценки ситуации, используемый в переборе вариантов действий. По ситуации на поле он выдает число "насколько такая ситуация для нас хороша" В принципе, изменения в нем можно тестировать стандартным способом: поменяли, заставили сыграть с референсной командой, сравнили результаты. Существует ли оценка качества этого блока, которую можно измерить гораздо быстрее? Да, существует. Это то, насколько хорошо он предсказывает свои собственные оценки в будущем. Представьте: блок А последовательно выдает "очень хорошо, очень хорошо, очень хорошо, ПЛОХО". Блок Б для тех же ситуаций выдает "хорошо, хорошо, посредственно, посредственно". Довольно очевидно, какой из них лучше. Чтобы правильно формализовать это наблюдение, надо также придумать, почему не окажется "наилучшим" блок, который все время выдает одинаковые оценки. Для обхода этой проблемы я сделал константой то, какое число выдается в ситуации "гол вот-вот будет забит, и это уже не изменить" (+С, если гол забиваем мы, и -С, если нам).

В процессе я также много чего понял о поиске на графах, что удачно совпало с задачей, которой я в то время занимался в "Нивале". Через несколько лет я даже написал диссертацию по мотивам всего этого. Но это уже другая история.

Tags: , ,

Comments:

[User Picture]
From:freetiger
Date:Сентябрь 17, 2008 05:33 am
(Link)
спасибо за утреннее доброе чтиво

Если пишется что-то интересное, экспериментальное (идеологически) - debug часто работает во много раз быстрее release'а. В жизненной алгоритмике - тоже интересное, правильное наблюдение. Надо снижать )
Тяжелая артиллерия дает следующую ступеньку, когда она нужна. Часто ошибка проектирования в недооценке затрат при применении артилерии (многие вещи могут выступать в этой роли в разных ситуациях); впрочем, я, конечно, о серебрянной пуле.
Формализация - отдельная тема, по хорошему именно этому учат на втором (иногда первом) курсе хороших вузов.
P.S. интересен вопрос - какое было поле действий робота?
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Сентябрь 17, 2008 06:44 am
(Link)
Что вы называете "полем действия"?
(Ответить) (Parent) (Thread)
[User Picture]
From:freetiger
Date:Сентябрь 17, 2008 07:41 am
(Link)
вводные данные на игру
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Сентябрь 17, 2008 07:46 am
(Link)
Игра с полной информацией.
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Сентябрь 17, 2008 07:55 am
(Link)
Напишу развернуто, а то, может, я неправильно понял вопрос. Игроку известно все, кроме алгоритма соперника; в том числе и физ. модель. Т.е. это такие шахматы, но полуходов в партии не ~50, а ~миллион, и "вариантов выбора" на каждом полуходе не ~20, а почти бесконечно много.
(Ответить) (Parent) (Thread)
[User Picture]
From:mikser
Date:Сентябрь 17, 2008 06:05 am
(Link)
Интересно!
(Ответить) (Thread)
[User Picture]
From:rruben
Date:Сентябрь 17, 2008 06:40 am
(Link)
Мне вот тоже стало интересно, насколько определены были правила самой игры? То есть это был некий динамический бильярд с заданной скоростью участников, трением поля, радиусом игроков и мяча и т.п, так чтоли?
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Сентябрь 17, 2008 06:43 am
(Link)
По сути, да.
Правила очень простые, например, понятия "грубой игры" в них нет.
(Ответить) (Parent) (Thread)
[User Picture]
From:baramin
Date:Сентябрь 17, 2008 07:18 am
(Link)
В таких играх часто определяющим является "горизонт событий" модели. Кто, хоть и грубо, смог просчитать дальше по времени - тот и победил.
(Ответить) (Thread)
[User Picture]
From:scmorr
Date:Сентябрь 17, 2008 07:20 am
(Link)
Я тоже как-то до КД-ЛАБа баловался программингом АИ футбольной команды. На джаве. Теперь вижу - как же далеко мне было до профессионалов :).

Спасибо за повествование.
(Ответить) (Thread)
[User Picture]
From:ddima
Date:Сентябрь 17, 2008 07:21 am
(Link)
Спасибо за отличное чтиво.
А мне вот очень интересно стало - монструозный AI в SS появился уже после экспы с изучением исходников "Днепра"? Вопрос без подвоха, просто действительно стало интересно.
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Сентябрь 17, 2008 07:25 am
(Link)
В S^2 аи писал не я.
А вот pathfinding писал я, наверное, ты его имеешь в виду; основную монструозность, конечно, я развел до того.
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Сентябрь 17, 2008 07:31 am
(Link)
Хотя AI там тоже был хорош :)
В "Дозоре" мы его почти полностью переписали.
(Ответить) (Parent) (Thread)
[User Picture]
From:freedom_of_sea
Date:Сентябрь 17, 2008 07:56 am

keep it simple, stupid

(Link)
уверен, что дело не в быстроте итераций а в изяществе логики.

Я читал про аналогичный случай - соревновались программы в "последовательный парадокс заключенного"

Победила программа, повторяющая предыдущий ход соперника.
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Сентябрь 17, 2008 08:01 am

Re: keep it simple, stupid

(Link)
Он описывал, как это работает. Имхо никакого особенного изящества в этом не было - все очень прямолинейно и с кучей хаков.

Я согласен, что простота в большинстве случаев важна, но конкретно в AI можно писать большие и сложные системы, которые выигрывают у простых и "изящных" (другое дело, что это весьма непросто; высокая скорость итерации в этом случае обязательна, но не только она).
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Сентябрь 17, 2008 08:03 am

Re: keep it simple, stupid

(Link)
Ну и насчет iterated prisoner's dilemma - там все-таки сама задача очень простая. В футболе физмодель была "максимально реалистичной", т.е. задача весьма нетривиальна.
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]
From:plakhov
Date:Сентябрь 17, 2008 08:52 am
(Link)
Да.
http://keldysh.ru/pages/robosoccer/teams.htm (таблицу, правда, в последние годы почему-то не обновляли)
Наша старая команда - VST, новая - AVST.
"Днепр" там тоже есть.

VST у "Днепра" не выигрывала ни разу, AVST выигрывает постоянно, за исключением двух раз (на турнире никто, конечно, до 1000 голов не играет, так что это статистический выброс :))
(Ответить) (Parent) (Thread)
[User Picture]
From:wormball
Date:Декабрь 10, 2008 02:29 am
(Link)
Надеюсь, не помешаю.

Однако не могу не сказать, что оба упомянутых раза были делом рук не в последнюю очередь вашего покорного слуги. (команды QuickIron и Аврал)

Логика по своей тупизне не уступала Днепру - всё покоилось на известной формуле столкновения двух тел плюс кое-каких эвристических соображениях. А дальше - human learning, то бишь банальный подбор параметров вручную, ибо писать автомат заломало плюс созерцание игры доставляло эстетическое удовольствие. Во второй программе даже присутствовала оптимизация удара по мячу (!), правда, на соревнованиях это почему-то не помогло, хотя в "домашних" условиях работало превосходно.

А вот у АВСТ она выигрывала не случайно и очень даже статистически значимо - раза в полтора. Потом появились (немного) более сильные команды (ffteam, bgtu, vst2), но одновременно с этим мне это дело наскучило, а потом и сам проект почему-то заглох.
(Ответить) (Parent) (Thread)
[User Picture]
From:wormball
Date:Декабрь 10, 2008 02:33 am
(Link)
Кстати говоря, всем сколько-либо заинтересовавшимся настоятельно советую скачать собственно саму программу - помнится, она там на сайте выложена. Можно созерцать игру и даже попробовать свои силы, в том числе против творений вашего покорного слуги.
(Ответить) (Parent) (Thread)
[User Picture]
From:wormball
Date:Декабрь 10, 2008 03:07 am
(Link)
Совсем забыл. Одна небольшая деталь - в первой моей команде противник вовсе не учитывается. Во второй учитывается, но только как нечто, могущее догнать мяч при ударе по воротам.

Кстати говоря, я несколько погорячился, отнеся VST2 к сильным командам. Сейчас запустил - аврал её рвёт фактически всухую.
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Декабрь 10, 2008 12:10 pm
(Link)
VST2 это, насколько помню, собственно и есть дебажная версия AVST. Павловский почему-то настоял на включении оной в соревнования в качестве отдельной боевой единицы :)
(Ответить) (Parent) (Thread)
[User Picture]
From:elephantum
Date:Сентябрь 18, 2008 07:27 am
(Link)
скажи, а 1000 это качественное (просто очень большое число) или количественное (можно обосновать почему 1000 подходит, а 800 - нет) следствие из трех сигм? а то я себя опять не очень умным чувствую.
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Сентябрь 18, 2008 07:30 am
(Link)
Количественное.
Там, по-моему, считали так: если вероятность для команд А и Б забить гол 45% vs 55%, то получалось нужно забить около 1000 голов суммарно до достижения 3sigma, чтобы однозначно определить по счету, какая из двух команда А, а какая Б. Мне сейчас лень проверять, так что я могу ошибаться раза в три (но все-таки не на порядок).
(Ответить) (Parent) (Thread)
[User Picture]
From:elephantum
Date:Сентябрь 18, 2008 07:47 am
(Link)
ясно. то есть с потолка была взята именно разница вероятности выиграть в 10% =)

ценно. спасибо
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Сентябрь 18, 2008 07:51 am
(Link)
Не то чтобы с потолка, просто это типичное значение прироста/падения качества для итерации.
(Ответить) (Parent) (Thread)
From:sleepy_drago
Date:Сентябрь 18, 2008 08:42 am
(Link)
Спасибо за пост.
Так и хочется сказать "как же я не увидел это раньше" годика 3-4 назад ...
(Ответить) (Thread)