ВЫСШАЯ ШКОЛА МАЙНОР

Институт инфотехнологии
Веб программирование

Александр Мочёнов
IT-3-Q-V-Tal

Искусственный интеллект в играх на примере

игры “Войны планет”

Курсовая работа

Руководитель: Zahhar Kirillov, MSc

Таллинн 2010
 Искусственный интеллект в играх

Оглавление

Резюме 2

Введение 3

1 Введение в предметную область 5

1.1 Подходы к написанию ИИ . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Символьный и логический подходы . . . . . . . . . . . . . . . . 6
1.1.2 Квазибиологическая парадигма . . . . . . . . . . . . . . . . . . 6
1.1.3 “Хороший” или развлекательный игровой ИИ . . . . . . . . . . 7
1.2 Агентно-ориентированный подход . . . . . . . . . . . . . . . . . . . . . 8

2 Практическая часть 10
2.1 Об игре “Войны планет‘‘ . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.1 Сущности игры . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.2 Правила игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.3 Технические данные . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Подготовка к написанию ИИ . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Подготовка окружения для разработки . . . . . . . . . . . . . . 15
2.2.2 Процесс разработки . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Выбор типа ИИ и метода его написания . . . . . . . . . . . . . . 17
2.2.4 Характер среды . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Стратегия и тактика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Первый ход и расширение . . . . . . . . . . . . . . . . . . . . . 20
2.3.2 Самооборона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.3 Защита своих войск . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.4 Атака . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.5 Перегруппировка . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.6 Хитрость и тактические приёмы . . . . . . . . . . . . . . . . . . 27
2.4 Внутреннее строение бота . . . . . . . . . . . . . . . . . . . . . . . . . 28

Заключение и выводы 31

Литература 33

1
 Искусственный интеллект в играх

РЕЗЮМЕ

Данная работа состоит в целом из: 2 частей, более чем 6300 слов, 1 таблицы и 10 кар-
тинок.

Ключевые слова: искусственный интеллект, игра, теори игр, google ai challenge

В данной работе рассматриваются вопросы и проблемы создания игрового Искусствен-

ного Интеллекта. Эта область науки является сравнительно молодой областью, и в
ней до сих пор много вопросов без ответов, что делает ей актуальной и привлекатель-
ной для автора. Сегодня искусственный интеллект есть во всех играх, и их популяр-
ность напрямую зависит от качества искусственного интеллекта. Это делает тему ис-
кусственного интеллекта в играх востребованной.

Целью данной работы является знакомство автора с темой и применение полу-

ченных знаний при участии в соревновании “Google AI Challenge” и написании
собственного искусственного интеллекта в виде бота для игры “Войны Планет”.

В дополнение к основной целе работы автор ставит перед собой следующие задачи:

• Изучение и применение на практике компьютерной верстки LATEX;

• Переписывание игрового движка, доработка визуализатора игры и прочее при
подготовки окружения для разработки;
• Проверить применимость знание о военном ремесле при разработки стратегии
ведения игры;
• Использование системы версионирования исходного кода git при разработки про-
граммы;

В ходе работы автор приходит к выводу, что для его задачи современные способы напи-
сания искусственного интеллекта не подходят. Структура полученного искусственно-
го интеллекта представляет собой стратегический план и делиться на 6 частей: первый
шаг, самооборона, защита своих войск, атака, перегруппировка и хитрость. Программ-
ный код составляет более 1000 строк, написанных на языке Python.

В ходе испытаний автор убедился в жизнеспособности своего алгоритма, что является

главным выводом данной работы.

2
 Искусственный интеллект в играх

ВВЕДЕНИЕ

С созданием первого программируемого компьютера сразу после окончания Второй

Мировой Войны (1940-1950 гг.) возникла область науки изучающая компьютерные
программы, обладающие способностью “мыслить” в том или ином смысле. Эту науку
и технологию назвали Искусственный интеллект (ИИ). Её основоположниками явля-
ются многие учёные, стоящие за созданием тех же первых компьютеров (Алан Тюринг,
Джон Маккарти, Марвин Мински и др.)

История ИИ знала более 5 периодов упадка (т.н. “Зима в ИИ”) и столько же возрожде-
ний, каждый раз меняя вектор в изучения ИИ. По-этому до сих пор эта наука является
областью в которой имеется множество вопросов без ответов, а добиться результата
может каждый (Russell and Norvig, 1995), в отличии от более старых и фундаменталь-
ных областей вроде физики и химии. “Искусственный интеллект, с другой стороны,
всё ещё открывает возможности для проявления талантов нескольких настоящих Эйн-
штэйнов” (Russell and Norvig, 1995) Это всё делает ИИ для автора исключительно ин-
тересной областью для изучения.

Практически сразу после основания ИИ появились первые программы, играющие в

игры. В 1957-ом году Кристофер Стрэчи написал игру, играющую в шашки. Тогда же
был написан первый ИИ, примитивно играющий в шахматы. (Russell and Norvig, 1995)
ИИ в компьютерных играх с тех пор значительно развился. Тем не менее, шахматную
программу сильнее человека смогли написать лишь в 1997-ом году, когда DeepBlue
одержала победу над Гарри Каспаровым. Это стало возможным лишь благодаря увели-
чению компьютерных мощностей. Но этот успех был возможен также благодаря новым
алгоритмам и подходам1 . В любом случае не стоит полагать, что развитие компьютер-
ной техники является “серебряной пулей” в решении всех проблем в компьютерных
ИИ. Например, игра “Го”2 до сих пор является нерешённой задачей для программистов
ИИ. Самая умная на сегодняшний день играет в неё на любительском уровне. (Russell
and Norvig, 1995)

Сегодня индустрия компьютерных игр практически не обходится без применения ИИ.

Он в играх, на ряду с графическими и прочими характеристиками, является важным
качественным показателем и напрямую влияет на их конкурентно-способность и успех.
Это делает игровой ИИ востребованным. Игры по своей природе зачастую имеют не
1
Хотя сами создатели не считали свой творение “интеллектуальным”Moravec (1998)
2
Го - это стратегическая настольная игра. Го является одной из наиболее распространённых настоль-
ных игр на Земле GoGameWiki

3
 Искусственный интеллект в играх

только развивающую, но и развлекательную составляющую, по-этому автору данная

тема особенно интересна.

Целью автора является знакомство с областью науки ИИ, изучение её основ с после-
дующим применением полученных знаний на практике в ходе разработки и написания
собственного ИИ, играющего в игру с другими себе подобными. Для практического
задания автор участвует в соревновании “Google AI Challenge” ([Link]
com/), в ходе которого разрабатывает ИИ для игры “Войны планет”. Написание про-
граммы, которая играет в игру в качество одно из игроков, обладающему знаниями в
программировании автору, представляется не только интересным, но и весёлым заня-
тием. Такую программу принято называть ботом (сокращение от слова робот). Мето-
дология, применяемая автором, в основном квалитативна и выводы по большей части
представляют, основанное на полученных результатах, субъективное мнение автора.

ИИ является чрезвычайно широкой сферой науки, и для написания игрового ИИ мож-

но применять множество кардинально отличных друг от друга подходов и алгоритмов.
Для написания ИИ автор использует символьно-логический, агенто-ориентированный
подход без алгоритмов поиска. Автор не делает глубокого анализа принимая это реше-
ние, что бы не выйти за рамки допустимых объёмов работы. Тем не менее он объясняет
причину своего выбора. Так же в работе применяются понятии из теории игр.

“Войны планет” – так называется игра для которой автор пишет ИИ. Как следует из
названия в каком-то смысле игра о войне. По-этому как дополнение к написанию своего
бота, автор ставит задачу проверки применимости знаний о военном ремесле, взятых
из древнего трактата Сунь Дзы “Искусство войны”, к дизайну стратегий и тактик ИИ.

Так же автор ставит задачу изучения системы компьютерной вёрстки LATEX, приме-
нения её в ходе написания данной работы. Эта система широко применяется в науч-
ной среде для написания статей, книг и прочих научных работ, по-этому такие знание
должны быть полезны автору в целом и как тренировка перед написанием дипломной
работы.

Для эффективного управления версиями исходного кода при написании используется

система версионирования git. А для вспомогательных программ (всё за исключением
исходного кода самого бота) автор выложил на сайте GitHub3 ([Link]
soswow/python-ai-challenge).

Данная работа будет полезна всем, кому интересна тема ИИ. Ознакомившись с дан-
ной работой, можно сложить представление о том, что можно сделать и с чего можно
начать, если стоит задача в написании игрового ИИ.
3
Сайт на котором можно делать git хранилище и делиться открытым исходным годом с обществом

4
 Искусственный интеллект в играх

1 ВВЕДЕНИЕ В ПРЕДМЕТНУЮ ОБЛАСТЬ

Прежде чем подойти к описанию выбранной игры и непосредственному написанию

игрового ИИ для неё, необходимо ознакомиться с некоторыми теоретическими аспек-
тами вопроса. Так что же такое ИИ? Чёткого ответа на этот вопрос нет. Есть 4 основных
вида определений, которые можно обобщить следующим образом: (Russell and Norvig,
1995) Искусственный интеллект это:

• Системы, которые думают подобно людям

• Системы, которые думают рационально
• Системы, которые действуют подобно людям
• Системы, которые действуют рационально

Есть мнение, что искусственный интеллект даёт возможность компьютерам выполнять

мыслительные задачи, на которые способны люди и животные.(Millington and Funge,
2009)

“Может ли машина мыслить?” – этим вопросом задался Алан Тюринг в 1950 году в ста-
тье “Вычислительная машина и интеллект” (Alan, 1950), в которой он предлагает тест
на способность машины проявлять интеллектуальность. Суть теста такова: человеку
даётся возможность пообщаться с кем-то через текстовую консоль (чат), после чего
человека спрашивают - говорил ли он с ИИ или с человеком? Если ИИ заставляет по-
верить, что он - настоящий человек или даже просто засомневаться, то тест считается
пройденным. Этот тест является основой в философии об искусственном интеллекте,
хотя и подвергался неоднократной критике. (Searle, 1980) На данный момент ни один
ИИ не справился с ним на 100 процентов.

1.1 Подходы к написанию ИИ

Как уже было сказано выше ИИ развивается с 50-ых годов ХХ века. За это время сло-
жилось два основных направления в написании ИИ.

5
 Искусственный интеллект в играх

1.1.1 Символьный и логический подходы

Символьный подход в написании ИИ сформировался в начале 50-ых. Этот подход за-

ключается в разделении ИИ на две части: база знаний и набор механизмов, которые
этими знаниями манипулируют, что бы получить решение проблемы или новые зна-
ния. Такими механизмами часто являются алгоритмы поиска.

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

ИИ можно сделать также с небольшим количеством знаний (или их полным отсутстви-

ем) и мощными алгоритмами поиска. Такие алгоритмы не полагаются на уже имеющи-
еся знания, а пытаются найти решение проблемы обладая только входными данными.
Такой подход часто становиться основой для ИИ в настольных играх (шашки, реверси,
шахматы).

Возможны и комбинированные решения. Так, например, вышеупомянутая программа

DeepBlue умела как очень эффективно искать1 , так и обладала базой знаний эндшпи-
лей, дебютов. А также применяла базу данных из 700 000 игр гроссмейстеров, из ко-
торых программа брала согласованные рекомендации. (Russell and Norvig, 1995)

1.1.2 Квазибиологическая парадигма

До 80-ых годов символьный подход служил опорой для написания ИИ, которые реша-
ли не сложные задачи, что с учётом компьютерной техники того времени считалось
большим достижением. Когда набор проблем, которые пытались решить с помощью
ИИ начал расширяться и усложняться, символьно-логический подход уже не мог спра-
виться с многими из них.

Символьному на смену пришла эпоха моделирования биологических систем, как с при-

менением реальных биологических элементов (Рамбиди et al., 2002), так и просто копи-
1
до 30 миллиардов позиций в расчёте на каждый ход, обычно достигая глубины поиска 14

6
 Искусственный интеллект в играх

рованием систем и процессов из природы. К таким алгоритмам в частности относятся:

• Искусственные нейронные сети

• Генетические алгоритмы
• Эволюционные вычислени

Искусственные нейронные сети (ИНС) представляют собой попытку скопировать вза-

имосвязи и принципы действия биологических нейронов (нервных клеток). ИНС пред-
ставляют собой математическую функцию, где на вход подаётся некий вектор; ИНС
пропускает данные через ряд межнейронных связей, преобразуя данные и на выход
выдаёт некий выходной вектор, что и является решением задачи.Haykin (1994)

Генетические алгоритмы и эволюционные вычисления копируют или напоминают эво-

люционные механизмы в природе. Применяются такие понятия как: мутации, скре-
щивание, индивидуум, популяции и прочее. В процессе работы алгоритма на разных
этапах поиска лучшие решения могут совмещаться, образую новое, улучшенное поко-
ление, а какие-то решения могут случайных образом меняться, т.е. мутировать, внося
тем самым положительный стахостический элемент.(Russell and Norvig, 1995)

Стоит заметить, что нейронные сети, например, были предложены и разработаны ещё
в 1943 г. (McCulloch and Pitts, 1943) Кто-то считает движение от символьного исчисле-
ния к биологическим прогрессом, а кто-то полагает, что это просто дань моде, разной в
разные времена. (Millington and Funge, 2009) Автор лично придерживается мнения, что
какие-то задачи хороши для решения старым, проверенным методом символьной логи-
ки. При этом с использованием биологических моделей решение получается не столь
эффективным и требует больше усилий, а другие наоборот. Другие же задачи наобо-
рот лучше решать современным методами. Например многие задачи компьютерного
зрения хорошо решаются искусственными нейронными сетями. (Haykin, 1994)

1.1.3 “Хороший” или развлекательный игровой ИИ

Все ИИ написанные для игр можно разделить на две категории: “Хороший” и развле-
кательный ИИ.(Johnson, 2010) При этом “хороший” тут не качественный показатель, а
имя собственное. Это зависит от типа игры и от ожиданий игрока.

Основной задачей “хорошего” ИИ является победить игрока-соперника, будь-то че-

ловек или другой ИИ. Примером такого ИИ может служить программа играющая в
шахматы, шашки и другие настольные игры. Люди играют с таким ИИ с целью или

7
 Искусственный интеллект в играх

попрактиковаться или они просто испытывают напряжение играя с людьми. (Johnson,

2010)

Целью же развлекательного ИИ, как следует из названия, является развлечь игрока.

Таким ИИ обычно обладает большинство современных игр. В таких играх как “Sims”
или “Half-Life” есть компьютерные игроки, которых называют “персонажами”. Задача
программистов этих игр сделать персонажей максимально реалистичными и ведущи-
ми себя как если бы это был реальный герой. Например, если по персонаж - охранник,
то он не должен забывать про игрока, как только он пропадёт из поля зрения игро-
ка, а должен стараться подать сигнал тревоги. Игрок не должен ощущать, что с ним
играет компьютер, который пользуется информацией недоступной самому игроку. В
противном случае интерес к игре пропадёт. Что бы обеспечить адекватность и рацио-
нальность решений и действий персонажей с ИИ, программисты, например, ограничи-
вают доступ к информации об окружающем мире: ИИ может “видеть” только то, что
находиться в поле его зрения; ИИ может слышать звуки, что слышат все. Т.е. объём
информации доступной ИИ должен быть схож с тем, что может позволить себе игрок.
(Buckland, 2005)

1.2 Агентно-ориентированный подход

Агентно-ориентированный подход (АОП) в написании ИИ появился в 1990 г. Он со

состоит в разработке агентов, которые составляют суть всего АОП. “Агентом является
всё, что может рассматриваться как воспринимающее свою среду с помощью датчиков
и воздействующее на эту среду с помощью исполнительных механизмов” (Russell and
Norvig, 1995) Т.е. ИИ должен иметь доступ к информации о среде в которой он функ-
ционирует, на которую он сможет влиять каким-то способом. Схематично это показано
на рис 1.1.

Рис. 1.1: Агент взаимодействует со средой с помощью датчиков и исполнительных ме-

ханизмов (Russell and Norvig, 1995)

8
 Искусственный интеллект в играх

Такой ИИ представляет собой математическую функцию агента, реализовать которую

должен программист в виде программы агента. Агент может накапливать информа-
цию о полученных состояниях среды, что называется последовательностью актов
восприятия. Он может использовать их при принятие решения и осуществлении от-
ветных действий.

Для успешного выполнения поставленной задачи агент должен быть рациональным.

“Рациональность - это максимизация ожидаемой производительности, а совершенство
- максимизацией фактической производительности” (Russell and Norvig, 1995) Рацио-
нальный выбор агента зависит только от последовательности актов восприятия, сфор-
мированного к данному моменту. Например, если человек переходит дорогу и не по-
смотрит по сторонам (и попадёт под машину) - это будет нерациональный поступок,
т.к. он мог это сделать и повысить ожидаемую производительность. А если он посмот-
рим по сторонам, и при этом на него упадёт метеорит, то это будет всё равно рацио-
нальный поступок.(Russell and Norvig, 1995)

Что бы говорить о рациональности, как следует из определения, необходимо опреде-

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

Как будет видно из 2 части, механизмами восприятия и воздействия в данной игре будет
являться программный API. Описание конкретной среды, в которой находиться ИИ и
критерии производительности так же будут описаны ниже.

9
 Искусственный интеллект в играх

2 ПРАКТИЧЕСКАЯ ЧАСТЬ

Для того чтобы более конкретно представить себе хотя бы частично как создаётся ИИ и
с какими проблемами приходиться сталкивать автор выбирает в качестве практическо-
го задания написание ИИ для какой-либо игры. Для этого автор принимает участие в со-
ревновании “Google AI Challenge” ([Link] организованном ком-
пьютерным клубом при Университете Уотерлоу (англ. “University of Waterloo”). Ком-
пания Google является лишь спонсором проводимого мероприятия. (AIChallangeFAQ)

Данное соревнование является одним из многих, суть которых заключается в написа-

нии ИИ для игры с двумя или более игроками. Участник конкурса должен написать по
сути программу агента, которая будет реализовать функцию агента, что часто необхо-
димо сделать в буквальном смысле, реализовав какой-то итерфейс с одной функцией
вроде “Decition doTurn(gameState)”. После чего ИИ сражаются друг с другом.

Подобные конкурсы встречаются и у нас в Эстонии. Например, на первом курсе Тал-

линского Технологического Университета на предмете по программированию в конце
курса всем студентам предлагается написать свой ИИ для игры в шашки, после чего
все написанные ИИ сражаются друг с другом в турнире.

Подобные соревнования представляются автору наиболее интересным видом практи-

ческого задания по нескольким причинам. Во-первых это возможность применить зна-
ния о программировании и об ИИ. Во-вторых здесь присутствует соревновательский
дух, что является несомненно положительным вектором. И на конец речь идёт об играх
- а значит это интересно и весело.

2.1 Об игре “Войны планет‘‘

Игра “Войны планет” (далее ВП или просто игра) - это пошагавая стратегическая игра
для 2-ух и более игроков (рис. 2.1a). Она основана компьютерной игре “Galcon”
([Link] рис. 2.1b), специально переработанная для
соревнования. В частности, в оригинале игра реального времени, что для упрощения
процесса было заменено пошаговым стилем, давая тем самым право хода каждому
игроку-боту по очереди.

10
 Искусственный интеллект в играх

(a) Визуализатор игры на сайте конкурса (b) Flash игра “Galcon” на офциальном сайте

Рис. 2.1: Фрагменты игр “Galcon” (a) и “Войны планет” (b)

2.1.1 Сущности игры

ВП представляют собой 2D холст или карту, где происходит сама игра, на котором дей-
ствуют следующие сущности (рис. 2.2):

Планета
Планета может

• принадлежать одному из игроков или быть ничейной (нейтральной);

• хранить, и если не нейтральная, то и производить корабли с константной
скоростью1 ;
• выпускать корабли для: атаки противника, захвата нейтральных планет или
для перегруппировки;
• становиться чьей-то в случае нейтральности или менять хозяина в случае
успешной атаки;

В начале игры все планеты располагаются на карте и до конца игры не меня-

ют своего положения. Расстоянием между планетами считается как округлённое
физическое расстояние между координатами планет. Планеты располагаются та-
ким образом, что как бы делят карту на две симметричные половины. Все плане-
ты, кроме двух изначально нейтральные и обладают определённым количеством
1
Коэффициент роста или просто рост - это то, сколько кораблей будет появляться на планете за
один ход. Обычно варьируется от 0 до 5.

11
 Искусственный интеллект в играх

кораблей. У каждого участника в начале игры есть в наличии по одной планете с

сотней кораблей.

Флотилия и корабль
Флотилия - это группа кораблей, которые планета источник пустила по направ-
лению к планете приёмнику. Флотилия “живёт” количество ходов, равное рассто-
янию между планетами источника и приёмника, перемещаясь за каждый ход на
одну единицу2 по направлению к цели. С момента выпуска флотилии с ней ни-
чего нельзя сделать: ни поменять направления, ни отменить решения. Корабль
- это разменная единица, из которых “состоят” флотилии и которые производят
планеты участников.

Выбор
Решение, которое принимает ИИ игрока на каждом полу-ходу3 партии (см. 2.3).
Он состоит из набора новых флотилий, выпускаемых на этом ходу игроком.

Рис. 2.2: Схематичное представление сущностей игры. Легенда справа.

На рисунке 2.2 схематично изображена карта игры со всеми её сущностями. Планеты

2 и 4 принадлежат одному игроку, а 1 и 7 другому. Остальные планеты (3,5,6,8) - ней-
тральные. Точечной диагональной линией показана воображаемая линия симметрии.
Стрелочками обозначены выпущенные или уже летящие флотилии кораблей. В част-
ности игрок играющий светлыми, на этом ходу выпускает флотилию из 26-и кораблей
с планеты 7 по направлению планеты 1 (7-1). А флотилия выпущенная ранее вторым
2
Имеется ввиду единица расстояния. Например, если расстояние между планетами равняется 5, то
флотилия пролетает от одной до другой за 5 ходов.
3
Это половинка всего хода, состоящая из решения одного из игроков

12
 Искусственный интеллект в играх

игроком со 2-ой планеты на планету 6 перемещается на одну единицу. Таким обра-

зом выбором первого игрока является отсылка одной флотилии 7-1, а выбором второго
флотилия 2-5. В визуализаторах размер планеты пропорционален зависит от её росту.

2.1.2 Правила игры

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

Когда флотилия достигает места назначения она исчезает, изменяя статус для планеты
приёмника. Это изменение зависит от сопренадлежности флотилии и планеты приём-
ника к игрокам. Могут произойти следующие варианты:

• Если флотилия прилетела на свою же планету, то корабли флотилии добавляются

к кораблям на планете.
• Если флотилия прилетела на планету противника, то корабли минусуются и на
планете остаётся разница. В случае, если кораблей больше во флотилии, то пла-
нета меняет хозяина на того чья флотилия это была.
• Если на планету в один ход прилетает сразу несколько флотилий разных принад-
лежностей, то работают более сложные правила, которые можно найти на сайте
соревнования (PlanetWarsSpec).

Цель игры - захватить как можно больше планет за максимум 200 ходов. На каждый ход
игроку даётся одна секунда. Игра заканчивается или по истечению одного из лимитов,
или если у одного из игроков закончатся корабли (как на планетах, так и во флотилиях).
(PlanetWarsSpec)

2.1.3 Технические данные

Для участия в соревновании необходимо зарегистрироваться на сайте соревнования.

Далее надо скачать начальный пакет, состоящий из игрового движка (написанного на
Java), нескольких очень простых ботов, набора из сотни карт и шаблона для написания
своего бота. Для разных языков программирования готовых стартовых пакетов имеется

13
 Искусственный интеллект в играх

четыре варианта для: C++, Java, Python, C#. Основной движок конкурса поддерживает
запуск ботов, написанных также на: Haskell, Ruby, Javascript, PHP, Perl, OCaml и Lisp’е.
Стартовые пакеты для них можно найти на форуме соревнования. Автор другим языкам
предпочитает Python, по-этому именно на нём он пишет своего бота.

Для того, что бы участвовать в конкурсе в одном из файлов необходимо заполнить ло-
гикой метод “def DoTurn(pw): ... ”, где на вход поступает объект в котором имеется
API для доступа ко всей информации об игровом состоянии среды. С помощью этого
API можно узнать где, какие планеты располагаются, сколько у кого кораблей, от куда
куда движутся флотилии, когда прибудут и т.д.

После реализации бота все необходимые файлы для его запуска надо запаковать в архив
и залить на официальный сервер, где бот игрока будет периодически играть с другими
ботами, имеющих примерно тот же рейтинг. В зависимости от исхода каждой партии
меняется количество очков участника, что сдвигает его в общей рейтинговой таблице.

Во время игры обмен информацией о состоянии игры и выборах игроков в игровом

движке происходит следующим образом (рис. 2.3):

Рис. 2.3: Процесс работы игрового движка

На рисунке 2.3 вдно, что в начале игры читается файл с описанием начальной карты, ко-
торая составляет начальное состояние игры. Это состояние передаётся первому игроку,
который делает свой выбор и отдаёт назад приказы об отправлении новых флотилий,
после чего всё тоже самое повторяется для второго игрока. Далее движок обрабатыва-
ет полученные выборы, применяя их к текущему состоянию игры, а так же он делает
передвижение уже имеющихся флотилий, происходит прирост кораблей на планетах

14
 Искусственный интеллект в играх

и обработка прибытий флотилий на планеты. После чего он проверяет терминальное

состояние, т.е. не закончена ли игра (см. раздел 2.1.2).

Перед началом игры движок запускает программы игроков в отдельных процессах и

устанавливает с ними связь через стандарт ввода-вывода, в последствии общаясь по
ним с процессами ботов, передовая состояния и зачитывая выборы игроков.

2.2 Подготовка к написанию ИИ

Прежде чем приступить к написанию бота, необходимо решить некоторые дополни-

тельные задачи: подготовить дополнительные средства для помощи в разработки; опре-
делиться со средой, в которой функционирует бот для конкретной игры; выбрать ме-
тодологию написания ИИ и методы принятия решения о выборе;

2.2.1 Подготовка окружения для разработки

В ходе первых попыток написания собственного бота, автор столкнулся с рядом слож-
ностей, в связи с чем составил список того, что необходимо сделать для успешного
завершения проекта прежде чем приступать к непосредственному писанию ИИ.

Журналирование
Система при которой игровой движок общается с ботами в виде отдельных про-
цессов через стандартный ввод-вывод означает отсутствие возможности поша-
говой отладки даже во время тестирования на локальном компьютере. По-этому
автор с самого начала создал систему журналирования (или логов), которая до-
статочно полно раскрывала процессы, происходящие во время игры.

Свой движок
Чтение логов утомительный процесс и занимает слишком много времени. Для
решения этой проблемы и для более глубокого понимания процессов, происхо-
дящих в движке игры автор решил переписать движок на языке Python. Это поз-
волило подключать ИИ напрямую к движку в качестве библиотеки, тем самым
довая возможность для отладки.

Модификации в визуализаторе
Так же для удобства разработки автор модифицировал визуализатор сыгранных
игр, написаны на Java и поставляемый в стандартном наборе (рис. 2.4).

15
 Искусственный интеллект в играх

Рис. 2.4: Фрагмент модифицированного визуализатора

В частности:

• Была добавлена возможность менять скорость воспроизведения при помо-

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

Написание тестов
В подобной задаче безусловным подспорьем являются модульные тесты, кото-
рые также присутствуют в написанном ИИ

Система игры на всех картах

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

16
 Искусственный интеллект в играх

2.2.2 Процесс разработки

Процесс разработки бота можно разделить на несколько этапов:

1. Написание первого бота и тестирование его на всех картах против всех простых
ботов, что идут в начальном наборе.
2. Улучшение бота до тех пора, пока он не будет побеждать в 100% случаях.
3. “Замораживание” бота в его текущем состоянии и установка его на место про-
тивника и переход к пункту 2. Т.е. теперь задача играть против своего же бота, и
улучшая следующее поколение прийти к полной победе над ним.
4. Периодически пользоваться TCP Server’ом ([Link]
Это неофициальный централизованный сервер, на котором можно в реальном
времени сразиться с другими клиентами сервера. Главное отличие от официаль-
но сервера заключается в следующем:
(a) В скорости. Подключившись игра начинается практически сразу, в отличии
от официального сервера, где каждый бот играет в среднем раз в пол часа.
(b) Не нужно заливать свой программный код на сервер. Код бота запускает-
ся на компьютере его владельца, тем самым давая возможность записывать
логи для последующего анализа.
(c) Игроки на TCP Server’е зачастую очень сильные, по-этому для бота это всё
равно что стресс тестирование.
5. Если появляется ощущение, что бот уже достаточно работоспособный, его можно
упаковывать и засылать на официальный сервер и переходить к пункту 3.

2.2.3 Выбор типа ИИ и метода его написания

На рисунке 1.1 (стр. 8) показана модель простейшего агента. Если сравнить её с рисун-
ком 2.3 (стр. 14), то можно заметить, что схема игрока №1 емеет те же составные части
(вход, выход, принятие решения), что и агент. По-этому автор считает уместным в дан-
ной задаче применение агентно-ореинтированного подхода. По сути надо реализовать
белый ящик со знаком вопроса на рисунке 1.1 или более формально функцию агента.

Характеристики игры очень похожи на свойства среды, в которых функционирует агент,

играющий в шахматы за одним важным исключением. Средний коэффициент ветв-
ления в шахматах примерно равен 35. Т.е. в среднем на каждом полу-ходу игрок мо-
жет выбирать среди 35 возможных решений, что даёт приблизительно 35100 различных
комбинаций состояний игры. (Russell and Norvig, 1995) При этом программа DeepBlue
могла просмотреть только на 14 ходов вперёд.

17
 Искусственный интеллект в играх

Изучая вопрос эффективности различных методов и подходов для написания ИИ, автор
ознакомился с некоторыми мнениями специалистов. Так, Антон Сафонов (MSc, маги-
стерская работа которого была посвящена комбинированию методов оптимизации роя
частиц и монте-карло метода) считает, что данная задача должна решаться “современ-
ными способами, т.е. необходимо сделать так, что бы не нужно было говорить про-
грамме как решать задачу, а что бы программа сама находила пути её решения”. Т.е.
его идея заключалась в применении оптимизированных алгоритмов поиска, абстраги-
руясь от конкретных планет и флотилий до понятий вроде “скопление сил”, решая тем
самым проблему чрезмерного коэффициента ветвления в ВП. Автору такой подход,
ввиду отсутствия необходимых познаний в данной области, показался слишком слож-
ным и непонятным. Более того, ему кажется, что именно “ручной” способ написания
ИИ в данном случае будет более эффективным.

Для написания агента с использованием конкретных правил и законов, а иначе говоря

используя стратегию и тактику, необходимо использовать знания о том “как работа-
ет мир”. Такой агент называется агентов основанным на модели. (Russell and Norvig,
1995) С учётом того, что автор не собирается использовать алгоритмов поиска, для
просмотра всех вариантов развития событий, то для такого агента достаточно разрабо-
тать систему рефлексов, т.е. механизмы реагирующие исключительно на текущее акты
восприятия. Хотя некоторые аспекты алгоритма всё же можно рассматривать как пред-
сказание, когда система защиты строится на предположении относительно некоторых
планет (см. 2.3.2).

2.2.4 Характер среды

“Критерии успеха, наряду с описанием среды, а также датчиков и исполнительных ме-

ханизмов агента, предоставляют полную спецификацию задачи, с которой сталкивает-
ся агент” (Russell and Norvig, 1995) Критерием успеха или показателем производитель-
ности в случае игры ВП является счёт на конец соревнования в итоговой рейтенговой
таблице, а так же результат каждой сыгранной партии. Во время локального тестирова-
ния на всех картах такими показателями являются также количество ходов, за которое
бот победил и проиграл.

Существуют характеристики, по которым можно классифицировать среды в которых

оперируют ИИ. (Russell and Norvig, 1995) В данном случае имеет место форма взаи-
модействия ИИ-ов, представляющая собой детерминированную, поочередную, охва-
тывающие двух игроков игру с нулевой суммой и с полной информацией. (Russell and
Norvig, 1995; Morgenstern and Von Neumann, 1947) Эти и другие свойства среды и их
значения, применительно к данной игре приведены в таблице 2.1 (стр. 19).

18
 Искусственный интеллект в играх

Свойство среды Значение для Почему?

среды
Наблюдаемая Полностью ИИ имеет доступ ко всем данным, необ-
полностью или наблюдаемая ходимых для принятия решения.
частично
Детерминированная, Стратегическая Является таковой, если “среда являет-
стохастическая или ся детерминированной во всех отно-
стратегическая шениях, кроме действий других аген-
тов”(Russell and Norvig, 1995)
Эпизодическая или Последователь- Т.к. выбор игрока на каждом ходу влияет
последовательная ная на все будущие решения
Статическая или Полудинамичес- Т.к. “с течением времени сама сре-
динамическая кая да не изменяется, а изменяются по-
казатели производительности”. (Russell
and Norvig, 1995) Выбор принимается в
условиях ограниченного времени.
Дискретная или Дискретная Т.к. игра “имеет конечное количество
непрерывная различимых состояний” и она “связана
с дискретным множеством восприятий и
действий“ (Russell and Norvig, 1995)
Одноагентная или Конкурентная Т.к. имеет место соперничающая сущ-
мультиагентная мультиагентная ность Б, которая пытается максимизиро-
среда вать показатели своей производимости
за счёт минимизации показателей сущ-
ности А

Таблица 2.1: Характеристики среды игры ВП

2.3 Стратегия и тактика

В этом разделе описаны стратегии и тактики, которые автор применил и реализовал в

своём агенте. Так же тут делается попытка связать их со знаниями о военном ремесле,
описанными в трактате “Искусство Войны” (5-6 вв. до н. э.).

“Если используешь их[войска] в битве, но победа долго не приходит, их

оружие притупляется, а рвение - ослабевает. Если осаждаешь города, их
силы истощаются. Если подвергаешь войско длительной войне, запасов го-
сударства не хватит ... Поэтому я слышал об успехе быстрых военных по-
ходов, и не слышал об успехе затяжных.” (Tzu, 6 век до Н.Э.)

Это правило действительно и тут, потому что игра продолжается максимум 200 ходов.
Что бы достичь победы, медлить нельзя. В этой игре быстрота развёртывания сил и
захвата планет очень важен. В момент главного сражения разница в одну планету может
решить исход исход партии.

19
 Искусственный интеллект в играх

Как уже говорилось ранее в начале игры у обоих игроков условия совершенно идентич-
ные. У каждого есть по планете с сотней кораблей, а все остальные планеты находятся
на равных расстояниях от начальных планет игроков, т.к. карта симметричная. Из этого
можно ещё раз подчеркнуть мысль, что исход каждого поединка зависит исключитель-
но от алгоритмов игроков.

Общую стратегию, можно охарактеризовать как “играть, что бы не проиграть”, т.к. по

мнению автора главное в этой игре - правильная оборона, что будет раскрыто ниже (см.
2.3.2).

Вся стратегия автора делиться на 6 этапов или элементов. Алгоритм проходит через все
эти этапы принимает решение о выборе. Каждый из них описан далее более подробно.

2.3.1 Первый ход и расширение

Самым первым этапом игры является фаза “развёртывания”, в которой особенно важ-
но самый первый выбор. Причина тому в симметричности первоначального состояния
игры для обоих игроков. По-этому очень важно с первых секунд игры попытаться по-
лучить преимущество, выбрав планеты для первой атаки наиболее эффективно.

“Тому, кто первым приходит на поле сражения и ожидает врага, будет легко;
тот, кто приходит после и должен спешить в бой, будет утомлен”
(Tzu, 6 век до Н.Э.)

В отличая от шахмат в этой игре нету игрока идущего первым, оба игрока делаю свой
первый плоху-ход не зная о решении противника. Неправильное решение на первом
шаге может закончиться быстрой победой противника. Пример на рисунке 2.5.

Рис. 2.5: Ошибка первого игрока (светло-серый) на первом шаге

В показанной ситуации начальные планеты игроков находятся очень близко друг от

друга и один из участников не обращая на это внимание рассылает бо́льшую часть

20
 Искусственный интеллект в играх

своих кораблей на захват нейтральных. В то же время его противник не спешит рас-

пускать все корабли. В результате ошибки второй игрок следующим ходом захватит
изначальную планету первого игрока и получи тем самым победное преимущество,
т.к. начальные планеты имеют высокий коэффициент роста (обычно 5).

На самом деле при хорошей самообороне и правильно выбранной функции выбора цели
для атаки (см. 2.3.4) никакой особой логики в первый ход вкладывать не обязательно
(будет видно далее). Хотя автор всё же разработал рефлекс4 который срабатывает на
первом и последующих ходах, если ситуация такая как описана выше. Он оставляет
все корабли на первом ходу, а на втором посылает все корабли на главную планету
противника.

2.3.2 Самооборона

Самооборону можно считать пожалуй самым важным этапом всей стратегии. От то-
го как хорошо и безошибочно реализован этот модуль алгоритма зависит результатив-
ность всего бота. Побеждает тот, у кото суммарный прирост кораблей на всех планетах
больше. По-этому потеря любой своей планеты ведёт к изменению этого отношения, а
значит этого нельзя допустить ни в кое случае.

“Поэтому тот, кто преуспел в войне, первым делом выбирает позицию, где
он не может быть разбит, вместе с тем не упуская [любой возможности]
разбить врага.”
(Tzu, 6 век до Н.Э.)

Суть самообороны в том, что бы на планете всегда оставалось достаточно кораблей,

что бы смочь отбить любую атаку. Для этого прежде всего надо посмотреть сколько и
какие флотилии летят на данный момент на планету и представив, что более никакая
планета не выпустит флотилий по данному направлению, просимулировать все прилё-
ты кораблей получив в результате чёткое представление о судьбе этой планеты.

Для удобства была написана специальная функция, которая занимается симуляцией

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

На рисунке 2.6 упрощенно объясняется как работает алгоритм симуляции.

4
и назвал его “блицкриг”, хотя название “вобанк” тут тоже подходит

21
 Искусственный интеллект в играх

Рис. 2.6: График работы симуляции прибывающих кораблей.

На верхней шкале показано будущее планеты с изначально 25-ью кораблями и подле-

тающими 4 флотилиями (чёрточка на отрезке), 3 из которых чужие (со знаком минус)
и одна своя (со знаком плюс). На нижней шкале между чёрточками показано сколько
планета успевает набрать (со знаком плюс) между прилётами кораблей; верхние цифры
показывают сколько кораблей было к момент прилёта флотилии; снизу показано сколь-
ко кораблей осталось после вычитания (или сложение) с прилетевшей флотилией.

Прирост у планеты составляет 5 кораблей, следовательно к прилёту первой флотилии

на планете уже будет 40 кораблей. Корабли противника вычитаются и на планете оста-
ётся 10 кораблей (под шкалой) и так далее.

Для принятия решения о том сколько кораблей необходимо забронировать для защиты
надо найти минимальное количество кораблей, какое будет в будущем у планеты. В
данному случае это число 3. Следовательно, что бы к этому моменту планета осталась
наша (пусть даже без кораблей) сейчас на ней должно остаться 25 − 3 = 22 корабля, а
остальными уже можно пользоваться.

“Стратегия ведения войны такова: не полагайся на то, что враг не прийдет,

полагайся на средства, которыми располагаешь, чтобы принять его. Не по-
лагайся на то, что враг не нападет; полагайся на то, чтобы наши позиции
были неуязвимы для нападения.
…
С теми, кто рядом, ожидай далекого; с отдохнувшими ожидай усталого; с
сытыми ожидай голодного. В этом путь управления силой.”
(Tzu, 6 век до Н.Э.)

Что бы максимально обезопасить себя от захвата планеты можно посмотреть на бли-

жайшие планеты противника и предположить, что они на следующем ходу выпустят

22
 Искусственный интеллект в играх

всё что у них есть по направлению к данной планете. Потенциальной угрозой мож-
но считать все планеты противника, что находятся ближе чем первая ближайшая своя
планеты. Это показано на рисунке 2.7.

Рис. 2.7: Учёт потенциальной угрозы со стороны ближайших планет противника.

На рисунке видно, что потенциальной угрозой можно считать две нижних планеты,
верхняя же планета противника (тёмная) не является угрозой, т.к. на подмогу централь-
ной успеет прийти своя же планета (сверху светло-серая).

Бронирование кораблей необходимо делать в отдельном цикле так, что бы все другие
этапы уже имели информацию о том, на сколько кораблей они могут рассчитывать.

Теперь должно быть понятно, почему использование особой логике на первом шагу
не обязательно. В случае первого шага данный алгоритм самозащиты увидит стоящую
рядом планету противника и рассчитает сколько ему можно пустить на расширение
так, что бы в случае если все 100 кораблей полетят на него, он бы смог отбиться.

2.3.3 Защита своих войск

“Непобедимость заключена в самом себе; возможность победы зависит от

врага.
…
Поэтому сказано, что стратегию победы над врагом можно познать, но не
всегда можно применить.”
(Tzu, 6 век до Н.Э.)

Написать идеальные алгоритм бронирования кораблей для самозащиты невозможно.

Всегда будет вероятность при которой, симулируя исход для планеты, окажется, что
планета всё таки переходит к противнику. В случае, когда из симмуляции следует, что

23
 Искусственный интеллект в играх

в обозримом будущем планета перейдёт к противнику, то в таком случае необходимо

взять все свои ближайшие планеты и отсортировав их по мере удаления от неё. После
отправить с каждой по мере возможности столько кораблей, сколько нужно, что бы в
конце планеты осталась у прежнего игрока.

2.3.4 Атака

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

Например: Планета противника находиться на расстоянии 3 шагов с 10-ью кораблями

и приростом в 2 планеты. Таким образом для того, что бы её захватить необходимо
выслать 10 + (3 ∗ 2) + 1 = 17 кораблей. Если на планете игрока нет такого количества,
то в качестве цели рассматривается следующая не своя планета.

Важно понимать, что отправлять флотилию для атаки можно только будучи уверенном
в её захвате, иначе игрок просто потеряет корабли, ничего не получив в замен.

Оценочную функцию можно занять из экономики, на основе которой появилась нау-

ка “Теория Игр”. Все не свои планеты можно представить в виде фондов или недви-
жимости, вобщем всего того, что приносит деньги и является целью для инвестиций.
Корабли при этом представляют собой деньги. В момент отсылки кораблей деньги тра-
тятся. Находясь в полёте денег уже нет. Долетев до цели планета меняет владельца -
происходит инвестирование средств. Через какое-то время (зависит от роста планеты)
на планете возникнет сумма, которую мы изначально потратили. Это называется оку-
паемостью инвестиций. В случае игры она измеряется в ходах (т.е. за сколько ходов
этот вклад самоокупиться) (см. формулу 2.1, стр. 25).

24
 Искусственный интеллект в играх

Sq
kpq = dpq + ( ) (2.1)
Gq

где kpq – коэффициент для планеты-цели q относительно планеты p

dpq – расстояние в ходах между планетами p и q
Sq – количество кораблей на планете q
Gq – скорость прироста на планете q

Таким образом не всегда самые близкие и самые слабые планеты становятся более же-
лаемой целью, как показано на рисунке 2.8.

Рис. 2.8: Планета с коэффициентом = 15 является более приоритетной целью. (Здесь

Gr - это скорость роста (англ. Growth Rate)

Эту функцию оценки нельзя использовать в чистом виде, т.к. могут возникнуть ситуа-
ции, когда планета с самым низким коэффициентом находится ближе к противнику чем
к вам. В таком случае такая атака может провалиться. Причиной тому хитрость под на-
званием “перехват”, которая будет рассмотрена ниже (см. 2.3.6). А пока можно просто
ввести как правило, что атаковать планеты, которые ближе к противнику чем к игроку
- нельзя. Особенно это касается первых ходов, когда планеты с хорошим коэффици-
ентом находятся как на одной так и на другой “сторонах поля”. Так же нежелательны
любые длинные перелёты кораблей, т.к. это ведёт к потери контроля над ситуацией, и
за время полёта флотилии противник успеет сгруппироваться и защититься. Для этого в
оценочную функцию можно внести зависимость от расстояние. Например, умножение
расстояние на некий коэффициент больше нуля, таким образом заставляя увеличивать
результат функции по мере увеличения расстояния.

2.3.5 Перегруппировка

Как и инвесторы не любят, когда их деньги лежат и “не работают”, так и игрок должен
заботиться о том, что бы все генерируемые корабли приносили свой вклад в победу. В
частности может возникнуть ситуация, когда рядом с данной планетой нету ни одной

25
 Искусственный интеллект в играх

нейтральной или планеты противника. В таком случае все свободные корабли должны
быть переправлены ближе к “линии фронта”, которая часто образуется в игре между
достаточно развитыми ботами.

“Если мы можем идти вперед и противник тоже может продвигаться, это

называется “доступной местностью”. На такой местности, первым делом
занимай высоты и [строну] ян, а также обеспечь пути для подвоза прови-
анта. Тогда, если мы вступим в битву, за нами будет преимущество.”(Tzu,
6 век до Н.Э.)

Что бы перегруппировать корабли необходимо найти цель, которую надо атаковать, по-
сле чего найти ближайшую к нему свою планету. Эта планета называется атакующей.
Зная атакующую планету необходимо найти к ней наиболее подходящий путь. Для это-
го можно представить все планеты в виде полносвязного графа, где вершинами являют-
ся планеты, а все возможные пути между ними рёбрами. Тогда можно воспользоваться
одним из имеющихся алгоритмов поиска кратчайшего пути между вершинами.
(Cormen, 2001)

Но для упрощения задачи можно найти такой путь более простым способом. Он схе-
матично изображён на рисунке 2.9.

Рис. 2.9: Выбор потенциального звена при перегруппировки сил по направлению к ата-
кующему

Алгоритм заключается в следующем. Берутся все планеты игрока и сортируются по

расстоянию до атакующего. По одному проверяется угол между планетой, кандида-
том и атакующем. Если угол больше или равен 120o , значит это и есть искомое звено,
куда надо отправить свободные корабли. Данный угол был получен опытным путём.
Объяснить такой выбор можно тем, что это достаточно тупой угол, и при нём не созда-
ётся слишком длинных маршрутов. Таким образом каждая планета отвечает только за
правильную доставку до следующего звена.

26
 Искусственный интеллект в играх

2.3.6 Хитрость и тактические приёмы

“Война - это путь обмана. Поэтому, даже если [ты] способен, показывай
противнику свою неспособность. Когда должен ввести в бой свои силы,
притворись бездеятельным. Когда [цель] близко, показывай, будто она дале-
ко; когда же она действительно далеко, создавай впечатление, что она близ-
ко.”
(Tzu, 6 век до Н.Э.)

В игре ВП возможно применять так же и некоторые хитрости и тактические приёмы.

Одна такая хитрость называется “перехват”. Суть её в том, что бы перехватывать толь-
ко что захваченные врагом планеты. Т.к. чаще всего игроки захватывают планеты с
минимальным количеством кораблей во флотилии, то на планетах, сразу после захвата
практически нет кораблей. Если такой случай вовремя предвидеть, и вовремя послать
свои корабли, прилетающие туда же на один ход позже, то можно небольшой жертвой
захватить новую планету.

Другая хитрость касается эффективной защиты от нападения. Если противник высыла-

ет флотилию достаточную для захвата планеты игрока, то в таком случае если игрок тут
же вышлет подмогу, это сразу может увидеть противник и дослать ещё кораблей. Та-
кая череда дополнительных флотилий со стороны подмоги и досылки для атаки будет
постоянной. Тут можно сделать следующее - необходимо дождаться такого момента
высылки подмоги, когда она придёт точно в тот же момент, что и атакующая флоти-
лия. Таким образом можно выиграть время, т.к. противник увидит, что кораблей для
захвата не хватает только в самый последний момент.

Самооборону противника можно ослепить, если выслать атакующий флот не на пря-

мую на планету противника, а на соседнюю от неё нейтральную, а по прибытию на
неё тут же выслать все корабли на противника. Простые алгоритмы проверяют лишь
непосредственную угрозу, а в такой ситуации она будет незамеченной и противник не
успеет подготовиться достаточно кораблей для обороны.

Важно отметить, что от каждой придуманной тактики и хитрости должна быть проду-
мана и реализована эффективная защита.

27
 Искусственный интеллект в играх

2.4 Внутреннее строение бота

Внутренняя структура программы бота дублирует стратегический план, описанный

выше, разбивая процесс принятия решения на отдельные блоки, что показано на ри-
сунке 2.10.

Рис. 2.10: Упрощённая архитектура классов наследования бота

На рисунке видно, что класс с самим ботом MyBot унаследуется от класса Bot, который
является подобием интерфейса (в Python нету понятия интерфейса как такового). Bot
нследуется напрямую от класса PlanetWars, хранящего состояние игры и все необхо-
димые API для работы с ним: методы восприятие среды и воздействие на неё. В част-
ности, в PlanetWars хранится список планет и список флотилий. Сам PlanetWars
наследуется от класса Debbugable, который отвечает за обеспечение условного жур-
налирования и вывода на экран отладочных данных. Пример исходного кода приведён
в листинге 2.1.
1 def sim_arrivals(self, distances, p):
2 ”””Simulate end state of the game for given planet.
3
4 distances: List of tuples of objects are going to this planet.
5 p: planet for simulation
6 ”””
7 history = []
8 prev_distance = 0
9 [Link](([Link], p.num_ships, 0))
10 for dist_group in distances:

28
 Искусственный интеллект в играх

11 diff_distance = dist_group[0][1] - prev_distance

12 if [Link] != 0:
13 p.num_ships += p.growth_rate * diff_distance #next group came
14 prev_distance = dist_group[0][1]
15
16 participants = {[Link]:p.num_ships}
17 for obj in dist_group:
18 if not obj[0] in participants:
19 participants[obj[0]] = obj[2]
20 else:
21 participants[obj[0]] += obj[2]
22
23 winner = (0, 0)
24 second = (0, 0)
25 for k, v in [Link]():
26 if v > second[1]:
27 if v > winner[1]:
28 second = winner
29 winner = (k, v)
30 else:
31 second = (k, v)
32
33 if winner[1] > second[1]:
34 p.num_ships = winner[1] - second[1]
35 [Link] = winner[0]
36 else:
37 p.num_ships = 0
38 [Link](([Link], p.num_ships, dist_group[0][1]))
39 return history

Listing 2.1: Метод симулирующий прибытия флотилий

В листинге приведёт метод, который на вход принимает список объектов, имеющих

время прибытие, количество кораблей и принадлежность. В этом списке могут быть
как флотилии так и планеты противника представляющие потенциальную угрозу. На
строке 10 эти объекты итерируются, где каждый проходит ряд изменений и вычис-
лений, идентичных тем, что производит игровой движок, когда во время применения
решений игроков (рис. , стр. ) считает итоге прилётов флотилий на планеты. А имен-
но: строки 12-14 икрементирует рост планеты, 16-21 разбивает по группам всех участ-
ников локального боя (какой игрок сколько кораблей привносит), 23-31 рассчитывают
победителя и проигравшего (тот кому достанется планета), 33-37 вычитает корабли и
меняет владельца планеты, 38 добавляет результат от прилёта флотилии(ий) в резуль-
тативный список.

На данный момент реализованы все основные механизмы игры, за исключением хит-

29
 Искусственный интеллект в играх

ростей и тактичесих манёвров. Автор планирует закончить до окончания соревнования.

30
 Искусственный интеллект в играх

ЗАКЛЮЧЕНИЕ И ВЫВОДЫ

Результатом исследования автора стали более глубокие и широкие познания в области

искусственного интеллекта. Прочитанные книги, статьи, просмотренные выступления
специалистов на тему искусственного интеллекта были не бесполезны лично автору.
Он познакомился с этой областью науки, что являлось одной из целей этой работы.

Полученные знания помогли автору в написании практического задания и участие в

конкурсе “Google AI Challenge”. Изученный материал позволил более чётко предста-
вить себе все возможные направления при написании ИИ. Были рассмотрены основ-
ные направления при написании ИИ и классификация сред, в которых функционируют
ИИ. По предложенной классификации были рассмотрены характеристики конкретной
игры. Были сделаны предположения о неэффективности в данном случае более совре-
менных методов создания ИИ.

Всё это помогло автору выбрать направление, наиболее простое, но тем не менее по
мнение автора эффективное. Так это или не так покажет время, но на данный мо-
мент возможности ИИ автора не предвещают полной неудачи на конкурсе, что говорит
о жизнеспособности выбранного пути написания ИИ. Профиль автора и все сыгран-
ные его ботом игры можно найти по адресу [Link]
user_id=3984

На момент написания работы автор всё ещё занимается разработкой ИИ, т.к. сорев-
нование заканчивается в декабре 2010 года. На данный момент более 1000 строк кода
написано и потрачено более 100 человеко-часов. По условиях конкурса и исходя из
здравого смысла выкладывать код самого ИИ нельзя, по-этому его нет на сайте github.
Тем не менее полный исходный код бота можно найти по адресу [Link]
ee/ai/[Link].

Все дополнительные задания по написанию собственного игрового движка, доработ-

ке стандартного визуализатора, созданию процесса инкрементальной разработки ИИ
были выполнены и безусловно помогли автору в написании и улучшении бота. Пере-
писанный автором движок на языке Python код можно найти на сайте git-hub по адресу
[Link]

При изучении древнего трактата о военном ремесле Сунь Дзыня “Искусство войны”
автор обнаружил несколько подходящих под описание стратегии игры мыслей. Пусть

31
 Искусственный интеллект в играх

игра называется “Войны планет”, всё же нельзя говорить, что описанные советы и за-
коны могут один в один лечь в основу стратегии ИИ. Впрочем это и ожидаемо, игра
слишком проста, что бы в ней можно было применить всю глубину мудрости описан-
ного в трактате.

Написание работы на LATEXстало не таким простым занятием. Основная проблема, с

которой пришлось столкнуться автору - это обеспечение всех официальных и необ-
ходимых требований к оформлению работы. С большей частью удалось справиться,
но некоторые недочёты останутся по всей видимости до следующей работы. Исход-
ный код данной курсовой работы также находиться на GitHub’е по адресу https://
[Link]/soswow/ai-paper.

32
Литература

AIChallangeFAQ. Google ai challenge faq, 10 2010. URL [Link]

[Link].

M. Alan. Turing. Computing machinery and intelligence. Mind, 59(236):433–460, 1950.

M. Buckland. Programming game AI by example. Wordware, 2005. ISBN 1556220782.

T.H. Cormen. Introduction to algorithms. The MIT press, 2001. ISBN 0262032937.

GoGameWiki. Go, 2010. URL [Link]

S. Haykin. Neural networks: a comprehensive foundation. Prentice Hall PTR Upper Saddle
River, NJ, USA, 1994. ISBN 0023527617.

Soren [Link] to lose: Ai and “civilization”, 09 2010. URL [Link]

[Link]/watch?v=IJcuQQ1eWWI.

W.S. McCulloch and W. Pitts. A logical calculus of the ideas immanent in neural nets. Bulletin
of Mathematical Biophysics, 5(1):15–137, 1943.

I. Millington and J. Funge. Artificial intelligence for games. Morgan Kaufmann, 2009.

H. Moravec. When will computer hardware match the human brain. Journal of Evolution
and Technology, 1(1), 1998.

O. Morgenstern and J. Von Neumann. Theory of games and economic behavior. Princeton
University Press Princeton, NJ, 1947.

PlanetWarsSpec. Planet wars specification, 10 2010. URL [Link]

com/[Link].

S.J. Russell and P. Norvig. Artificial intelligence: a modern approach. Prentice hall, 1995.

J.R. Searle. Minds, brains, and programs. Behavioral and brain sciences, 3(03):417–424,
1980.

S. Tzu. The art of war. 6 век до Н.Э.

НГ Рамбиди, ЕП Гребенников, АИ Адамацкий, АГ Девятков, and ДВ Яковенчук. Био-

молекулярные нейросетевые устройства. Радиотехника М, 2002.

33