Разработка программного обеспечения, реализующего математический аппарат теории игр

Министерство обороны Российской Федерации Военная академия войск радиационной, химической и биологической защиты и инженерных войск имени Маршала Советского Союза

С.К. Тимошенко

Дипломная работа

Разработка программного обеспечения, реализующего математический аппарат теории игр

Кострома 2010

Введение

Глава 1. Анализ математического аппарата и метода, используемых при решении задач теории игр

1.1 Основные понятия и элементарные приемы решения игр

1.2 Решение игр в «чистых» и «смешанных» стратегиях

1.3 Графическое решение игр Глава 2. Разработка алгоритма программного обеспечения, реализующего математический аппарат теории игр

2.1 Основные понятия алгоритмизации

2.2 Разработка алгоритма Глава 3. Разработка программного обеспечения, реализующего математический аппарат теории игр

3.1 Выбор инструмента программирования Delphi

3.2 Разработка программного обеспечения Заключение Список использованных источников Приложение А

Перечень принятых сокращений

ПО — программное обеспечение ГОСТ — государственный стандарт ЭВМ — электронно-вычислительная машина ТИ — теория игр СП — среда программирования

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

В качестве основных направлений в разработке философских проблем теории игр, как Н. Воробьев, так и Г. Клаус берут проблемы всестороннего анализа адекватного отражения теоретико-игровыми моделями моделируемых ими явлений, а также диалектического противоречия, считая, что любая игра содержит в себе диалектическое противоречие конфликтных сторон. Объектом специального исследования стали принципы изучения конфликтов в теории игр в работах Г. Смоляна, который пытается подойти к анализу конфликта с несколько иных позиций, отличных от методологических позиций Воробьева и Клауса. Это связано, прежде всего, с потребностью исследования духовной деятельности людей, интеллектуальных, этических и психологических сторон этой деятельности, приобретающих в конфликтной ситуации резко очерченные формы. Подходя с психологических позиций к рефлексивному пониманию конфликта, Смолян приходит в своих работах к изображению конфликта как интеллектуального взаимодействия сторон, что является новой и важной стороной в системном представлении конфликта.

Весьма многообещающими для дальнейшего философского осмысления теории игр, представляются работы Х. Либшера. Он убедительно доказывает необходимость принципиальной философской основы при рассмотрении математической теории игр. Либшер считает, что пора приступать к созданию основ математической ТИ на базе марксистско-ленинской философии, что на сегодняшний день уже «создана возможность предварительной работы для преследующей математической разработки, и идейные посылки, лежащие в основе теории игр, позволяют также без всякой математики проникнуть в суть соответствующих конфликтных ситуаций и создать возможность принятия обоснованных решений». Одним из главнейших объектов теории игр является игра, одним из фундаментальнейших теоретико-игровых понятий, соответственно, понятие игры. Либшер указывает, что философский анализ построения теоретико-игровой модели должен включать в себя детальное исследование образования этого понятия. Это явится первым шагом в целостном теоретическом осмыслении предмета теории игр. Теория игр является результатом математизации целого ряда отраслей науки. В процессе становления конкретного понятия игры происходит формализация конфликта, благодаря которой изменяется понятийное содержание теории игр. Это изменение происходит как процесс конкретизации, «обогащения» основного понятия игры и требует анализа и модификации всей понятийной системы теории игр. Приоритет содержательного над формальным не сводится только к тому, что содержательные идеи и представления об игре предшествуют формальному исследованию конфликта. Формальное предполагает содержательное также в качестве средства построения и исследования своих собственных дедуктивных возможностей. Тут уже содержательное выступает своеобразным эталоном, от степени соответствия которому зависят в значительной мере достоинства формализованной теории игр. Теория игр на сегодняшний день представляет собой сеть различных классов теоретико-игровых моделей и принципов.

Глава 1. Анализ математического аппарата и метода, используемых при решении задач теории игр

1.1 Основные понятия и элементарные приемы решения игр

Теория игр — это математическая теория конфликтных ситуаций, т. е. таких ситуаций, в которых сталкиваются интересы двух или более сторон, преследующих различные цели. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышув зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учетом представлений о других участниках, их ресурсах и их возможных поступках. Чаще всего методы теории игр находят применение в экономике, чуть реже в других общественных науках — социологии, политологии, психологии, этике и других. Начиная 1970;х годов ее взяли на вооружение биологи для исследования поведения животных и теории эволюции. Очень важное значение она имеет для искусственного интеллекта и кибернетики, особенно с проявлением интереса к интеллектуальным агентам. Теория игр берет свое начало из неоклассической экономики. Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона Фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение». Эта область математики нашла некоторое отражение в общественной культуре. Из определения теории игр видно, что она рассматривает задачи, типичные для военного дела.

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

Игра «Ультиматум» в экстенсивной форме Игра в экстенсивной, или расширенной форме представляются в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной.

Игра «Ультиматум" — игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает — выбрать стратегию, А или R. Скорее всего первый игрок выберет U, а второйА (для каждого из них это оптимальные стратегии); тогда они получат соответственно 8 и 2 очка.

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

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

Пример:

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

Кооперативная игра (математика) Игра называется кооперативной, или коалиционной, если игроки могут объединяться в группы. Беря на себя некоторые обязательства перед другими игроками и координируя свои действия. Этим она отличается от некооперативных игр, в которых каждый обязан играть за себя. Примером такой игры может являться карточная игра в дурака «двое на двое» или «трое на трое», либо разыгрывание «втемную» виста в преферансе. Развлекательные игры редко являются кооперативными, однако такие механизмы нередки в повседневной жизни. Часто предполагают, что кооперативные игры отличаются именно возможностью общения игроков друг с другом. В общем случае это неверно. Существуют игры, где коммуникация разрешена, но игроки преследуют личные цели, и наоборот. Из двух типов игр, некооперативные описывают ситуации в мельчайших деталях и выдают более точные результаты. Кооперативные рассматривают процесс игры в целом. Попытки объединить два подхода дали немалые результаты. Так называемая программа Нэша уже нашла решение некоторых кооперативных игр как ситуации равновесия некооперативных игр. В теории игр равновесием Нэша (названным в честь Джона Форбса Нэша, который предложил его) называется тип решений игры двух или более игроков, в котором ни один участник не может увеличить выигрыш, изменив свое решение в одностороннем порядке, когда другие участники не меняют решения. Такая совокупность стратегий выбранных участниками и их выигрыши называются равновесием Нэша. Концепция равновесия Нэша (PH) впервые использована не Нэшем; Антуан Огюст Курно показал, как найти то, что мы называем равновесием Нэша, в игре Курно. Соответственно, некоторые авторы называют его равновесием Нэша-Курно. Однако Нэш первым показал в своей диссертации некооперативные игры (1950), что равновесия Нэша должны существовать для всех конечных игр с любым числом игроков. До Нэша это было доказано только для игр с 2 участниками с нулевой суммой Джоном фон Нейманом и Оскаром Моргенштерном (1947).

Формальное определение:

Допустим, (S, f) — игра n лиц в нормальной форме, где Sнабор чистых стратегий, а fнабор выигрышей. Когда каждый игрок i{1,…, n} выбирает стратегию х_iS_в профиле стратегий х=(х₁,…, х_n), игрок i получает выигрыш f_i(x). Выигрыш зависит от всего профиля стратегий: не только от стратегии, выбранной самим игроком i, но и от чужих стратегий. Профиль стратегий х^* является равновесием по Нэшу, если изменение своей стратегии не выгодно ни одному игроку, то есть для любого i f_i(x^*)?f_i(x_i, x^*_-i).

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

Гибридные игры включают в себя элементы кооперативных и некооперативных игр. Например, игроки могут образовывать группы, но игра будет вестись в некооперативном стиле. Это значит, что каждый игрок будет преследовать интересы своей группы, вместе с тем стараясь достичь личной выгоды. В кооперативных играх с трансферабельной полезностью, то есть возможностью передачи средств от одного игрока к другому, невозможно применять понятие индивидуальных платежей. Вместо этого используют так называемую характеристическую функцию, определяющую выигрыш каждой коалиции игроков. При этом предполагается, что выигрыш пустой коалиции равен нулю. Основания такого подхода можно найти еще в книге Фон Неймана и Моргенштерна. Изучая нормальную форму для коалиционных игр, они рассудили, что если в игре с двумя сторонами образуется коалиция С, то против нее выступает коалиция N/С. Образуется как бы игра для двух игроков. Но так как вариантов возможных коалиций много (а именно 2^N, где N-количество игроков), то выигрыш для С будет некоторой характеристической величиной, зависящей от состава коалиции. Формально игра в такой форме (также называемая TUигрой) представляется парой (N, v), где Nмножество всех игроков, а v:2^N>Rэто характеристическая функция. Подобная форма представления может быть применена для всех игр, в том числе без трансферабельной полезности. В настоящее время существуют способы перевести любую игру из нормальной формы в характеристическую, но преобразование в обратную сторону возможно не во всех случаях.

Решение кооперативных игр:

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

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

Симметричные и несимметричные игры

Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроковсимметричные. В частности, таковыми являются: «Дилемма заключенного», «Охота на оленя», «Ястребы и голуби». В качестве несимметричных игр можно привести «Ультиматум» или «Диктатор». Дилемма заключенного (реже употребляется название «дилемма бандита») — в теории игр некооперативная игра, в которой игроки стремятся получить выгоду, сотрудничая друг с другом или предавая. Как во всей теории игр, предполагается что игрок («заключенный») максимизирует свой собственный выигрыш, не заботясь о выгоде других. В дилемме заключенного предательство строго доминирует над сотрудничеством, поэтому единственное возможное равновесие — предательство обоих участников. Проще говоря, неважно, что сделает другой игрок, каждый выиграет больше, если предаст. Поскольку в любой ситуации предать выгоднее, чем сотрудничать, все рациональные игроки выберут предательство.

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

Игры с нулевой суммой и с ненулевой суммой

Игры с нулевой суммой — особая разновидность игр с постоянной суммой, то есть таких, где игроки не могут увеличить или уменьшить имеющиеся ресурсы, или фонд игры. В этом случае сумма всех выигрышей равна сумме всех проигрышей при любом ходе. Многие изучаемые математиками игры, в том числе уже упоминавшаяся «Дилемма заключенного», иного рода: в играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. Исход такой игры может быть меньше или больше нуля. Такие игры могут быть преобразованы к нулевой суммеэто делается введением фиктивного игрока, который «присваивает себе» излишек или восполняет недостаток средств. Еще игрой с отличной от нуля суммой является торговля, где каждый участник извлекает выгоду. Сюда также относятся шашки, шахматы; в двух последних игрок может превратить свою рядовую фигуру в более сильную, получив преимущество. Во всех этих случаях сумма игры увеличивается. Широко известным примером, где она уменьшается, является война.

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

Игры с полной или неполной информацией Важное подмножество последовательных игр составляют игры с полной информацией. В такой игре участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры. Полная информация не доступна в параллельных играх, так как в них неизвестны текущие ходы противников. Большинство изучаемых в математике игрс неполной информацией. Например: «Дилемма заключенного» заключается в неполноте информации. В то же время есть интересные примеры игр с полной информацией: «Ультиматум», шахматы, шашки и другие.

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

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

Платежной матрицей называется матрица, показывающая платеж одной стороны другой при условии, что первая сторона выбрала стратегию A_i, а вторая B_i.Если сторона A имеет m стратегий, а сторона B-n стратегий, то такая игра называется mЧn.

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

Решить игру — значит найти оптимальные стратегии обеих сторон и определить цену игры: ожидаемый выигрыш стороны A или проигрыш стороны B.

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

При рассмотрении платежной матрицы следует сразу же отбросить дублирующие и доминирующие стратегии.

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

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

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

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

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

Принцип выбора каждой стороной наиболее осторожной («перестраховочной») стратегии называется «принципом минимакса».

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

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

Если б=в, то решение игры находится в области чистых стратегий, в противном случае в области смешанных.

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

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

Игрок A располагает p чистыми стратегиями A₁,…A_i,…, A_p, а игрок Bсоответственно q чистыми стратегиями B₁,…, B_k,…, B_q. Первый игрок может выбрать любую стратегию A_i, в ответ на которую второй игрок может выбрать любую стратегию B_k. Сочетание этих стратегий (A_i, B_k) приведет к некоторому числовому результату («платежу»), который обозначим через a_ik и будем называть его «выигрышем» игрока A. Игра с «нулевой суммой» означает, что при этом «выигрыш» игрока B составитa_ik (числа a_ik могут быть и отрицательными, поэтому слово «выигрыш» взято в кавычки). Матрица П=¦a_ik¦ порядка pq называется платежной матрицей, или матрицей игры:

Число a_i=a_ik и b_k=a_ik указывают минимально гарантированный выигрыш для игрока A применяющего стратегию A_i,и минимально гарантированный проигрыш игроком B при использовании им стратегии B_k.

Величина б=б_i=(a_ik) называется нижней ценой игры, максиминным выигрышем A, или коротко максимином, а соответствующая ему стратегия (строка) — максиминной. Аналогично в =в_k= (a_ik) называется верхней ценой игры, минимаксным проигрышем B, или минимаксом, а соответствующая стратегия игрока Bминимаксной. Всегда б? в.

Принцип, согласно которому игроки выбирают эти стратегии, называется принципом максимина (для A) или минимакса (для B). Если игрок A выбирает свою максиминную стратегию, то при любой стратегии, выбираемой игроком B, ему обеспечивается выигрыш не менее чем a. Аналогично для игрока B, при выборе им стратегии, при которой достигается в =в_k обеспечивается проигрыш (или выигрыш игрока A) не более чем b.

Если a=b, то игра называется с седловой точкой, а общее значение a и b, которое будем обозначить через нценой игры. В этом случае оптимальным решение игры для обоих игроков является выбор максиминной (для A) и минимаксной (для B) стратегий. Любое отклонение для каждого игрока от этих стратегий не может оказаться выгодным.

Пример1. Игра заключается в том, что игрок A записывает числа 1 (стратегия А₁), или 2 (А₂), или 3 (А₃). Игрок В, в свою очередь, может записать числа 1 (В₁), 2 (В₂), 3 (В₃), или 4 (В₄).

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

Решение. Согласно условию, платежная матрица игры имеет следующий вид:

Нижняя цена игры: б=б_i=-5;

Верхняя цена игры: в=в_k=4

Следовательно, для игрока, А максиминными стратегиями являются А₁ или А₂, при которых ему обеспечен «выигрыш» не менее -5(т.е. проигрыш не более 5).

Для игрока В соответственно минимаксными стратегиями являются В₁ или В₂, которые обеспечивают ему проигрыш не более 4.

Игра не имеет седловой точки (б<�в).

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

Смешанной стратегией игрока, А называется применение им своих чистых стратегий А_1,…, А_i,…, А_p c частостями х₁,…, х_i,…, х_р (причем Ух_i=1). Ее записывают в виде А₁,…, А_i,…, А_р

х₁,…, х_i,…, х_р ,

или

=(х₁,…, х_i,…, х_р).

Аналогично вектором

(y₁,…, у_k,…, y_q) (Уу_k=1)

Определяется смешанная стратегия игрока В, где у_k есть частость использования стратегии В_k. Чистые стратегии являются частным случаем смешанной стратегии, задаваемой единичным вектором.

Функцией выигрыша, или платежной функцией f (,) игры с матрицей П=¦a_k¦ при применении игроком, А смешанной стратегии, а игроком Всмешанной стратегии, называется средняя величина выигрыша игрока, А (проигрыша игрока В), подсчитываемая по формуле:

а (б)=У У ч_шн_лф_шл= П ю

_{i k}

Стратегии ^*и * называются оптимальными, если выполняются неравенства

f (, ^*)?f (^*, ^*)?f (^*,),

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

Совокупность оптимальных стратегий (^*,^*) называется оптимальным решением, или просто решением игры, а значение платежной функции при этомценой игры:

V=f (^*,^*).

Фундаментальная теорема Неймана утверждает, что каждая конечная матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

Пример. Исследовать игры, заданные следующими матрицами:

8 6 4 7 7 2 -1 3 -2 8 4 3 7

1) 5 4 3 4 6; 2) 4 1 5 -1; 3) 7 6 8 9 .

4 3 2 3 4 3 -2 4 -3 8 2 4 6

7 2 6 5 9 3 -1 5 2 6 3 2 5

Решение. 1) 1-я строка доминирует над 2-й и 3-й, так как все ее элементы соответственно не меньше элементов 2-й и 3-й строк. Поэтому стратегии А₂ и А₃ заведомо менее выгодны, чем А₁, и могут быть исключены. В результате получаем матрицу

8 6 4 7 7

7 2 6 5 9

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

6 4, в которой нет доминирующих стратегий.

2 6

Определив нижнюю и верхнюю цены игры, получим б₁=min{6,4}=4, б₂=min{2,6}=2, откуда б= max{4,2}=4. Аналогично, в₁=max{6,2}=6, в₂=max{4,6}=6, откуда в=min{6,6}=6.

Так как б? в, то игра не имеет седловой точки и ее решением будет смешанная стратегия.

2) Стратегия А₂, доминирует над А₁ и А₃. Следовательно, исключив последние, получим матрицу

4 1 5 -1.

3−1 5 2

В этой матрице можно исключить В₁и В₃, доминирующие над В₂.Окончательно получим 1 -1 .

— 1 2

Перейдем к исследованию седловой точки, располагая числа б_i и в_k справа и снизу матрицы: 1 -1 -1

— 1 2 -1

1 2

Получим б= -1 и в=1, следовательно, седловой точки нет.

3) Стратегия А₄ заведомо невыгодна по сравнению с А₁ и может быть исключена. В оставшейся матрице 8 4 3 7 можно исключить

7 6 8 9

8 2 4 6

доминирующие стратегии В₁ и В₄. После их исключения получаем матрицу

4 3

6 8 ,

2 4

в которой вновь оказались заведомо невыгодными стратегии А₁ и А₃. Их исключение дает матрицу (6 8). Теперь для игрока, А осталась одна стратегия А₂ (в первоначальной нумерации) и для игрока В, очевидно, выгодной является стратегия В₂, обеспечивающая ему проигрыш 6, вместо 8 при В₃. Окончательно получили решение игры в виде чистых стратегий А₂ и В₂ и цену игры н=6. Полученное решение в виде чистых стратегий говорит о том, что исходная матрица имела седловую точку а₂₂=6,что можно было бы установить прямым исследованием:

8 4 3 7 3 3

7 6 8 9 6 6

8 2 4 6 2 2

6 3 2 5 2 2

8 6 8 9 6

Следовательно, б=max б_i=6, в=min в_k=6, и б=в=6=н.

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

Пусть имеются две системы оружия A₁ и A₂ (например, ЗРК), одна из которых эффективна против одного вида целей (например, низколетящих), вторая более эффективна против других (например, высоколетящих).

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

Выбрав минимум из каждой строки, находим нижнюю цену игры б=max_бi, а выбрав максимум из каждого столбца, находим верхнюю цену игры в=min в_i.

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

Для игры 22 имеется аналитическое решение. Частоты применения стороной A стратегий равны Р₁=.

Цена игры в этом случае н=a ₁₁P₁+a ₂₁P₂,

Оптимальные частоты применения стороной B стратегий равны

q₁=

Пример. Имеются две системы ЗРК. Одни (выбор ихстратегия A₁), более эффективны против высоколетящих целей, другие (выбор их — стратегия A₂) против низколетящих. Противник может лететь на малых (стратегия B₁) и больших (стратегия B₂) высотах.

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

Требуется найти оптимальные стратегии сторон и цену игры.

Согласно написанным выше формулам получаем

P₁=

P₂=1- =

н =0,4+ 0,2= ;

q₁=

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

В случае игры mn, где m>2 и n>2, решение оказывается более сложным (если верхняя и нижняя цены игры не совпадают).

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

Задача теории игр может быть описана следующей системой уравнений:

a ₁₁ x ₁ + a ₂₁ x ₂ +…+ a _m 1 x _m > =1;

…

a _{1 n} x ₁ + a _{2 n} x ₂ +…+a _{m n} x _m >1,

где x_i =, x_i = и требуется найти минимум линейной формы

M= x₁ + x₂ +…x_n.

Существуют и приближенные методы задач теории игр, в частности итеративные методы Неймана, Брауна и другие. Таким образом, игра mЧn может быть решена, причем трудоемкость этого решения (машинное время) возрастает с увеличением mn.

Случай игр с несколькими ходами.

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

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

Пусть у стороны A есть при первом ходе две стратегии (например, сосредоточение артиллерии на одном A^/₁₁ или на другом направлении A^/₁₂) и при втором ходе тоже две стратеги (например, подать бронебойные снаряды A^/₂₁ или осколочно-фугасные A^/₂₂). У стороны B при первом ходе две стратегии (например, послать танки на одно B^/₁ или на другое B^/₂ направление). Известен платеж для любого варианта ходов (например, ущерб, наносимый стороне B).

Рассмотрим теперь все возможные стратегии стороны A:

A₁-выбирается A^/₁₁ или A^/₂₁ независимо от поведения стороны B;

A₂-выбирается A^/₁₁, а второй ход по правилу: если B^/₁, то A^/₂₁; если B^/₂, то A^/₂₂;

A₃-то же, но второй ход делается наоборот по сравнению с предыдущим порядком;

A₄-выбирается A^/₁₁ и A^/₂₂ независимо от поведения стороны B;

A₅-выбирается A^/₁₂ и A^/₂₂ независимо от поведения стороны B;

A₆-выбирается A^/₁₂, а второй ход по правилу: если B^/₁, то A^/₂₁;если B^/₂, то A^/₂₂;

A₇— то же, но второй ход делается наоборот по сравнению с предыдущем порядком;

A₈-выбирается A^/₁₂ и A^/₂₂ независимо от поведения стороны B

У стороны B четыре возможные стратегии:

B₁-выбрать B^/₁ независимо от поведения стороны A;

B₂-если A^/₁₁, то B^/₁, а если A^/₁₂, то B^/₂;

B₃— то же, но наоборот;

B₄-выбрать B^/₂ независимо от поведения стороны A.

Теперь можно составить платежную матрицу, пользуясь рис. 34 и обозначениями стратегий сторон.

Вместо матрицы 22, которая имела место при одноходовой игре, получена более громоздкая матрица 84. Игра может проводиться при наличии полной информации, при наличии информации о первом ходе и при отсутствии информации. Если информация полная, то возможны все стратегии сторон A и B, указанные выше. Если у стороны A информации перед вторым ходом нет, то стратегии A₂, A₃, A₆ и A₇ пропадают, так как в них сторона делает ход в зависимости от первого хода стороны B и имеет место игра 42. Если нет информации у стороны B, то у нее остаются только две стратегии B₁ и B₄ и имеет место игра 82. Наконец, при полном отсутствии информации имеет место игра 42.

Пример. Для ситуации, описанной выше, заданы математические ожидания потерь стороны B: a₁=10; a₂=2; a₃=5; a₄=9; a₅=6; a₆=4; a₇=10; a₈=2.

Определить цену игры н в случаях:

1) полной информации (обе стороны знают о каждом ходе друг друга);

2) у стороны A нет информации перед вторым ходом (она не знает, как поступила сторона B);

3) у стороны B нет информации перед первым ходом (она не знает, как поступила сторона A).

Не останавливаясь на вычислениях, приводим окончательные результаты: н₁=7; н₂=5,9; н₃=9,2.

Итак, за счет скрытности действий сторона B уменьшает свой проигрыш с 7 до 5,9, т. е. на 16%, а сторона A увеличивает выигрыш с 7 до 9,2, т. е. на 30%.

Случай игр с бесконечным числом стратегий.

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

v (F, G)=[ dG (y).

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

Точное решение бесконечных игр с отсутствием информации удается получить только в отдельных случаях. Определенный интерес в исследовании операций могут представить результаты теории бесконечных игр для разного вида дуэлей.

Общая схема дуэлей такова. Два противника сближаются начиная от определенного рубежа. Вероятность поражения до того, как достигнут рубеж, P₁(0)=P₂(0)=0. Далее эти функции возрастают в зависимости от пройденного противником расстояния соответственно на величины к и ?, которые меняются от 0 до 1 и составляют на конечном рубеже P₁(1)=P₂(1)=1. Противники могут сделать по одному выстрелу или более (m_в и n_в соответственно), могут иметь или не иметь информацию о том, произвел противник выстрел или нет. Цена игры принимается +1 при поражении противника и -1 при своем поражении.

Рассмотрим случай одного выстрела. Если противники имеют информацию о проведении выстрела, то игра имеет чистую стратегию, причем о₀ определяется из соотношения

P₁(о₀)+ P₂(о₀)=1.

Оптимальным моментом выстрела для второго игрока (в случае его выживания) является з₀=1.

Цена игры определяется из выражения н =2P₁(о₀)-1.

Пример 1. Определить оптимальные моменты проведения противниками выстрелов, если известно, провел противник выстрел или нет, а вероятность поражения возрастает линейно от пройденного расстояния, т. е.

P₁=о; P₂=з.

Пользуясь соотношением для вероятностей, получаем о ₀+о ₀=1,

откуда о ₀=0,5 т. е. целесообразно провести выстрел, пройдя половину расстояния до противника. Цена игры н=20,5−1=0.

Пример 2. Решить ту же задачу, что и в примере 1, если P₁=о, а P₂=з², т. е. вероятность поражения выстрелом второй стороны возрастает пропорционально квадрату расстояния (с учетом того, что з?1, медленнее, чем у первой стороны).

Пользуясь соотношением для вероятностей, получаем о ₀+о²₀=1,

откуда о ₀= - ±()²+1=0,62.

Второй корень отбрасывается, как не имеющий физического смысла (0?о₀?1).

Цена игры н=20,62−1=0,24, т. е. первая сторона в 24% случаев выигрывает.

Если игроки не имеют информации о проведении выстрелов (выстрелы «бесшумны»), задача также имеет решение.

В частности, при P₁(о)=P₂(о)=о плотности оптимальных стратегий (здесь они смешанные) запишутся в следующем виде:

0 0? о?;

f (о)=

о^-3 ?о?1.

н=0

Если один игрок имеет информацию о проведении выстрела противником, а другой нет и P₁(о)=P₂(о)=о, то оптимальная стратегия первого игрока характеризуется плотностью

F (о)= (о²+2о-1)^-

А второго

F (з)= (з²+2з-1).

Цена игры н=0,11, т. е. отсутствие информации при прочих равных условиях приводит к проигрышу той стороны, которая не располагает информацией.

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

1.2 Решение игр в «чистых» и «смешанных» стратегиях

Мы знаем, что если нижняя цена игры a равна верхней b (максимин равен минимаксу) то игра имеет седловую точку и по крайней мере одно решение в чистых стратегиях. А если б? в? Можно доказать, что и в этом случае решение всегда есть, только оно лежит не в области чистых, а в области смешанных стратегий. Решение игры называется такая пара стратегийв общем случае смешанных, систематическое применение которых обеспечивает каждой стороне максимально возможный для нее по условиям игры выигрыш, определяемый ценой игры. Если же одна из сторон отступает от своей оптимальной стратегии (в то время как другая продолжает придерживаться своей), то это ни в коем случае не может быть выгодно для отступающего; это либо оставит его выигрыш неизменным, либо уменьшит. Таким образом, каждая конечная игра имеет решение (возможно, в области смешанных стратегий). Это положение называется основной теоремой теории игр. Введем специальное обозначение для смешанных стратегий. Пусть K применяет свои стратегии K_1,K₂, K₃ с частотами соответственно p₁, p₂, p₃(p₁+p₂+p₃=1). Эту смешанную стратегию будем обозначать:

K₁

K₂

S_k= K₃

p₁

p₂

p₃

Аналогично смешанную стратегию игрока C будем обозначать:

C₁C₂

C₃

S_c= q₁

q₂

q₃

где

q₁+q₂+q₃=1

Очевидно, любая чистая стратегиячастный случай смешанной, в которой все частоты, кроме одной, равны 0, а одна-1.

Решение игрыпару оптимальных стратегийбудем обозначать S_k^* и S_c^*, а соответствующий ему выигрыш (цену игры) v.

Очевидно, что цена игры v не может быть меньше нижней и больше верхней цены: б? v?в. В первом примере решение игры должно быть:

K₁K₂ C₁C₂

S_k^*=; S_c^*= ,

а цена игры v=0. Проверим это Пусть мы («красные») держимся своей стратегии S_k^*, т. е. ищем C в убежище 1 и 2 одинаково часто, чередуя эти стратегии случайным образом. Может ли C улучшить свое положение (повысить свой выигрыш), отступая любым образом от своей стратегии S_c^*? Очевидно, нет. А если одностороннее отступление от стратегии S_k^* произойдет (в то время как C будет держаться стратегии S_c^*), то это невыгодно. Значит мы нашли решение игры и ее цену v=0.

Пользуясь чистыми максиминно-минимаксными стратегиями, в общем случае невозможно получить оптимальные решения игры, появилась идея использования смешанных стратегий. Каждый игрок вместо выбора одной из чистых стратегий может выбирать любую из них с заранее заданными вероятностями. Пусть x=(x₁, x₂,…, x_m) и y=(y₁, y₂,…, y_n) — наборы вероятностей, с которыми игроки A и B соответственно выбирают свои чистые стратегии. Тогда

₁==1,

x_i,, y_j?0 для всех i и j. Если a_ij-(i, j)-й элемент матрицы игры, то платежная матрица будет иметь следующий вид:

B

y₁ y₂ … y _n

x₁ a₁₁ a₁₂ … a_1n

x₂ a₂₁ a₂₂ … a_2n

A * * * *

x_m a_m1 a_m2 … a_mn

Подход к определению решения игры при смешанных стратегиях основывается на критерии минимакса. Единственная разница заключается в том, что игрок, А выбирает x_i так, чтобы максимизировать наименьший ожидаемый выигрыш по столбцам, тогда как игрок Выбирает y_i с целью минимизировать наибольший ожидаемый проигрыш по строкам. Математически критерий минимакса при смешанных стратегиях может быть описан следующим образом. Игрок, А выбирает стратегия x_i(x_i?0, x_i=1), дающую

{min (a_i1 x_i, a_i2 x_i,…, a_in x_i)},

а игрок В выбирает стратегию

y_j(y_j?0,y_j=1),

дающую Хьфч (ф_1о н_об ф_2о н_об…бф_ьо н_о)Ъю Эти величины определяются соответственно как ожидаемые максиминные и минимаксные платежи. Как и в случае чистых стратегий, выполняется соотношение: минимаксный ожидаемый проигрыш? максиминный ожидаемый выигрыш. Когда х_i и y_j соответствуют оптимальным решениям, выполняется строгое равенство, и результирующее значение равно ожидаемому (оптимальному) значению игры. Если х_i^*и y_j^*-оптимальные решения для обоих игроков, каждому элементу платежной матрицы а_ij соответствует вероятность х_i^*y_j^*. Следовательно, оптимальное ожидаемое значение игры:

v^*= a_ij x_i^* y_j^*.

1.3 Графическое решение игр

Этот метод применим только к играм, в которых хотя бы один игрок имеет только две стратегии. Рассмотрим игру вида 2n:

В у₁ у₂ … у_n

х₁ а₁₁ а₁₂ … а_1n

А х₂=1-х₁ а₂₁ а₂₂ … а_2n

Эта игра не имеет седловой точки. Поскольку игрок, А имеет только две стратегии, то х₂=1-х₁, х₁?0,х₂?0. Ожидаемые выигрыши игрока А, соответствующие чистым стратегиям игрока В, представлены в таблице:

Таблица 1.3.1

Ожидаемые выигрыши игрока А, соответствующие чистым стратегиям игрока В

Отсюда видно, что ожидаемый выигрыш игрока, А линейно зависит от х₁.

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

Пример. Рассмотрим игру вида 24.

В

1 2 3 4

1 2 2 3 -1

A 2 4 3 2 6

Эта игра не имеет седловой точки. Ожидаемые выигрыши игрока А, соответствующие чистым стратегиям В представлены в таблице.

Таблица 1.3.2

Ожидаемые выигрыши игрока А, соответствующие чистым стратегиям игрока В

Изображены четыре прямые, являющиеся графиками этих функций от х₁. Максимин достигается при х₁^*=. В этой точке пересекаются любые две из прямых 2,3 и 4. Следовательно, оптимальной стратегией игрока, А является (х₁^*=, х₂^*=) и значение игры находится подстановкой х₁ в уравнение любой из прямых, проходящих через максиминную точку.

-+3=

Это дает

v^*= +2=

— 7()+6=.

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