Математическая морфология.

Электронный математический и медико-биологический журнал. - Т. 15. -

Вып. 2. - 2016. - URL:

http://www.smolensk.ru/user/sgma/MMORPH/TITL.HTM

http://www.smolensk.ru/user/sgma/MMORPH/N-50-html/TITL-50.htm

http://www.smolensk.ru/user/sgma/MMORPH/N-50-html/cont.htm

 

УДК 519.813

 

СПОСОБ И АЛГОРИТМ ПРИНЯТИЯ СТРАТЕГИЧЕСКИХ И ОПЕРАТИВНЫХ РЕШЕНИЙ ИНТЕЛЛЕКТУАЛЬНЫМ АГЕНТОМ В СТРАТЕГИЧЕСКИХ КОМПЬЮТЕРНЫХ ИГРАХ

 

© 2016г.  Захаров В. А., Зернов М. М.

 

(zakharov.docx)

 

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

Ключевые слова: интеллектуальный агент, принятие решений, искусственный интеллект, стратегические компьютерные игры.

 

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

 

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

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

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

Принятие решения в стратегических играх осложняется в силу нескольких факторов:

-          стохастичности среды, в которой принимается решение (как внешней так и внутренней);

-          неопределенности результатов с точки зрения возможности реализации принятых решений;

-          возможности неверных решений ЛПР, данных на исполнение ИА по ошибке или неверной трактовке фактов.

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

 

Способ принятия стратегических и оперативных решений интеллектуальным агентом в стратегических компьютерных играх

 

Рассмотрим предлагаемый способ принятия стратегических и оперативных решений интеллектуальным агентом в стратегических компьютерных играх.

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

 

 

Рисунок 1 – Блок принятия стратегических решений

        

В качестве входных параметров для принятия стратегического решения у нас выступают:

- цели надсистемы – требования, которые предъявляются надсистемой (собрать ресурсы, вести армию в бой…);

- собственные предпочтения – характер ИА (закладывается изначально);

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

В состав целей надсистемы входит и условие победы ­– глобальная цель, руководствуясь которой надсистема ставит задачи ИА, и к которой ИА стремится самостоятельно и помимо указаний (возможно ошибочных) надсистемы.

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

Сформированные параметры оценки отправляются на оперативный уровень принятия решения, на котором принимаются решения о том, какие действия необходимо совершить на текущем ходу. На рисунке 2 представлена общая схема принятия решения.

 

 

Рисунок 2 – Общая схема принятия решения

 

В процессе принятия оперативного решения вначале, на основе исходных данных, определяются значения частных показателей оценивания оперативных действий.

Затем проводится свёртка оценок частных показателей в обобщённый в соответствии с алгоритмом многокритериального оценивания на основе графа согласованности показателей [1].

 

Алгоритм принятия стратегических и оперативных решений интеллектуальным агентом в стратегических компьютерных играх

 

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

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

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

- оборонительные/атакующие;

- передвижение.

А постройки в свою очередь на 3 типа:

- оборонительного типа;

- ресурсодобывающие;

- юнитные (наймы и улучшение).

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

Цель надсистемы может быть 2х типов:

- милитаристская(пойти, завоевать, убить, отвоевать …);

- ресурсодобывающая(накопить нужное количество ресурсов к ходу N, построить определенное здание …).

Собственные предпочтения, а именно характер интеллектуального агента может быть также 2 типов:

- военный;

- экономический.

Стратегическая обстановка может быть 3 типов:

- наше государство слабее противника;

- государство приблизительно равно по силам противнику;

- наше государство могущественнее противника.

Условие победы может быть 2 типов:

- военное(завоевать всех противников, захватить определенную точку на карте);

- экономическое (собрать определенное количество ресурсов к ходу N).

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

1.       Если Цель надсистемы и характера интеллектуального агента совпадают, решающими факторами становятся – стратегическая обстановка. В зависимости от оценки обстановки – слабее, равны, сильнее изменяется коэффициент.

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

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

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

1.2.1    Коэффициент важности типов действия юнита при равенстве сил распределяется следующим образом: действия направленные на захват ресурсодобывающих объектов – высокий, атака противника – средний, помощь союзникам – средний.

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

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

2.                Цель надсистемы и личные предпочтений агента не совпадают. Цель надсистемы экономическая, а характер ИА – военный тогда значения коэффициента построек распределяются следующим образом:

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

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

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

2.2.1. Коэффициент важности типов действия юнита при равенстве сил распределяется следующим образом: действия, направленные на захват ресурсодобывающих объектов – высокий, атака противника – высокий, помощь союзникам – средний.

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

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

3. Условие победы – военное, цель надсистемы и ИА совпадают.

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

3.1.2. Стратегическая обстановка - собственное государство слабее коэффициент найма юнитов и их улучшения – высокий, коэффициент ресурсодобывающих построек – средний, коэффициент оборонительных построек – средний.

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

3.2.1 Коэффициент важности типов действия юнита. Стратегическая обстановка – приблизительное равенство сил: действия направленные на захват ресурсодобывающих объектов – средний, атака противника – высокий, помощь союзникам – высокий.

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

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

4. Условие победы – военные. Цели надсистемы и ИА(характер экономный) – не совпадают.

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

4.1.2. Стратегическая обстановка - собственное государство слабее: коэффициент найма юнитов и их улучшения – средний, коэффициент ресурсодобывающих построек – высокий, коэффициент оборонительных построек – средний.

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

4.2.1. Коэффициент важности типов действия юнита. Стратегическая обстановка – приблизительное равенство сторон: действия направленные на захват ресурсодобывающих объектов – высокий, атака противника – средний, помощь союзникам – низкий.

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

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

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

 

 

Рисунок 3 – Блоки принятия оперативных решений

 

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

На принятие решения о том, какое действие стоит выполнить с юнитами влияет 2 основных фактора, являющихся входными параметрами, это:

- характеристика действия, включающая в себя:

         - дальность перемещения;

         - характеристики юнита (здоровье, защита, атака);

         - тип действия (оборонительное/атакующее или передвижение);

- оперативная обстановка включает в себя:

         - угроза юниту от вражеских отрядов;

         - угроза юнитом вражеским отрядом;

         - возможность помощи союзным юнитам;

         - доступные объекты.

Процесс принятия оперативного решения о действиях с юнитами происходит следующим образом.

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

2.       Выбирается юнит с наибольшей угрозой, для него просматривается возможность отступления, если это невозможно, то принимается решение о сражении.

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

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

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

6.       Выбирается наилучшее с точки зрения обобщённого показателя решение.

Рассмотрим процесс принятия решения интеллектуальным агентом при постройке/развитии базы. У нас все также остаются 2 главных фактора, это характеристика действия и оперативная обстановка, но при выборе решения по развитию базы в эти факторы входят другие показатели, а именно:

- характеристика действия:

         - тип постройки;

         - рейтинг постройки;

         - расход ресурсов.

- оперативная обстановка включает в себя:

         - угроза базе;

         - имеющиеся ресурсы.

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

Процесс принятия оперативного решения о возведении постройки происходит следующим образом:

1.                Сравнивается цена каждой возможной постройки или улучшения с имеющимися ресурсами, если цена менее 15% от имеющихся ресурсов, то показатель относительной цены постройки устанавливается низким, от 15 до 40% - средним, свыше 40% - высоким.

2.                Для каждой постройки устанавливается значение показателя важности постройки в зависимости от текущей оперативной обстановки.

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

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

3.       Для каждой постройки дается обобщённая оценка посредством свёртки частных показателей на основе графа согласованности частных показателей.

4.       Выбирается наилучшее с точки зрения обобщённого показателя решение.

Таким образом ИА принимает решения на оперативном уровне о том, какие действия ему совершать в той или иной ситуации.

Для свертки частных показателей оперативного уровня на основе графа согласованности, составлены таблицы согласованности [1], приведенные ниже.

 

Таблица 1. Матрица согласованности показателей постройки

 

№

Показатель

1

2

3

1

К цены постройки

x

2

1

2

Кважности постройки

2

x

2

3

Кстратегическая обстановки

0

0

x

 

Таблица 2. Матрица согласованности показателей действия юнитов

 

№

Показатель

1

2

3

4

1

К угрозы

x

2

1

1

2

К помощи

2

x

1

1

3

К рейтинга объектов

1

1

x

1

4

К атаки противника

2

2

1

х

 

Операцию свертки h для каждой степени согласованности приходится строить как нечеткую продукционную модель в виде FIS-структуры, описываемой оценочной таблицей или на основе нейро-нечёткой ANFIS-модели на основе алгоритма Сугэно 0-го порядка, обучаемой на основе оценочной таблицы. Вектор весовых коэффициентов для каждого случая получаем на основе метода парных сравнений Саати [2]

 

Заключение

 

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

 

литература

 

1. Зернов М. М. Способ построения нечёткой многокритериальной оценочной модели// Нейрокомпьютеры: Разработка и применение. – №1 – 2007. – C. 40–49.

2. Саати Т. Принятие решений. Метод анализа иерархий. – М.: Радио и связь, 1993

 

METHOD AND ALGORITHM OF MAKING STRATEGIC AND OPERATIVE DECISIONS BY AN INTELLECTUAL AGENT IN STRATEGIC COMPUTER GAMES

 

Zakharov V. A., Zernov M. M.

 

Method and algorithm of making strategic and operative decisions by an intellectual agent in strategic computer games offered. The method allows  possibility of intellectual agent’s aims and the aims of higher rank system coordination in the stochastic conditions.

Key words:  intellectual agent, making decision, artificial intelligence, strategic computer games.

 

Сведения об авторах:

Захаров Виталий Александрович, магистрант, филиал ФБГОУ ВО «НИУ «МЭИ» в г. Смоленске, e-mail: vet-zaharov@mail.ru

Зернов Михаил Михайлович, к.т.н., доцент кафедры вычислительной техники, филиал ФБГОУ ВО «НИУ «МЭИ» в г. Смоленске,  e-mail: zmmioml@yandex.ru

 

Филиал ФГБОУ ВО «Национальный исследовательский университет «МЭИ»» в г. Смоленске

Поступила в редакцию  13.06.2016.