Лекция: Игровые модели и их классификация.

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

Большое место в теории игр занимают так называемые неанта­гонucmuческие игры или игры против, природы. Характерной осо­бенностью этого класса игр является наличие частично противо­положных и частично совпадающих интересов «играющих» сторон. Так, например, если создается игровая модель исследования че­ловеком явлений природы, или модель освоения природных ресур­сов, то при этом интересы двух сторон (человека и природы) частично совпадают, частично противоположны. Дело в том, что природа как бы скрывая свои закономерности от человека, по остроумному выражению А. Эйнштейна, ведет себя коварно, но не злонамеренно. Следует заметить, что методы принятия решений в конфликтных или частично противоречивых ситуациях разрабатывались также в математической статистике, теории оптимизации и т. д. Самый про­стейший случай игры — это антагонистическая игра двух лиц с нулевой суммой. Игра двух сторон представляет собой совокуп­ность (х, у) правил поведения при конфликтной или противоречи­вой ситуации. Эти правила устанавливают выбор образа действия игроков на каждом этапе, что задается значениями переменных х и у и функцией платежа Н (х, у) для каждого игрока на любом этапе игры. Под стратегией игрока понимается совокупность ре­комендаций по ведению игры от начала до конца. Рекомендации должны быть «всеобъемлющими», т. е. содержать инструкции, как действовать в любой ситуации, которая может возникнуть в процессе игры.

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

В общем случае игра псторон может быть задана в виде мно­жества

{x1, х2, ..., хn, Н (x1, х2, ..., хn )},

где Н — платеж игры, который, в частности, может быть задан в виде матрицы;

хi — множество стратегий i-й стороны;

п-. число играющих сторон.

Если множества стратегий конечны, то игра считается конечной, если множества стратегий бесконечны, то имеет место бесконечная игра.

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

а)

б)

Рисунок 10.20 Классификация моделей игр.

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

Рассмотрим матричную игру двух сторон или лиц. Пусть «синие» имеют п стратегий, каждая из которых обозначается буквой j = 1, 2, ..., п, а «красные» — тстратегий, каждая из которых обозначается буквой i = 1, 2, ..., т.На первом ходу «красные» выбирают какую-то стратегию i. На следующем ходу «синие», зная какой выбор сделали «красные», выбирают стратегиюj.

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

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

Пусть aij-платеж «красных». Так как рассматривается игра с нулевой суммой, когда обе стороны ведут расчеты только между собой, то платеж «синих» равен — aij.Поэтому в общем случае такая игра определяется платежной матрицей вида

Стратегия «синих»

a11 a12 … a1n

a21 a22 … a2n

А = .................................

an1 an2 … ann

«Красные» стремятся к тому, чтобы значенйе aij(платеж) было максимальным, но они распоряжаются только своей стратегией i, «синие», наоборот, стремятся к тому, чтобы платеж aijбыл как можно меньше, но они распоряжаются только своей стратегией j.

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

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

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

Однако имеются чисто случайные (второй тип неопределенности) по своей природе игры. Ставить вопрос об оптимальности или пра­вильности выбора стратегий в такой игре неразумно, так как исход игры не зависит от поведения игрока. К этой категории относятся игры в кости, орлянку, рулетку, простейшие «азартные» карточные игры типа «очко», «трех карт» и т. д.

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

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

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

Существуют реальные игры, в которых имеют место все три вида неопределенности. Так, в карточной игре «преферанс» слу­чайный аспект неопределенности определяется случайным раскла­дом карт, стратегический — в правилах «сноса» карт и «заказа»игры И комбинаторный — в сложности определения поведения при открытых картах.

Антагонистические и неантагонистические игры встречаются только в играх двух лиц. В случае игр nлиц имеют место некоали­ционные (некооперативные ) и коалиционные (кооперативные) игры (рис. 10.20, а). В зависимости от формы задания игры делятся на: игры в нормальной форме (или матричные), когда игра задается в виде матрицы платежей, и динамические игры (или позиционные), геометрически изображающиеся в виде графа (рис. 10.21.).

Рисунок 10.21. Представление игры в виде графа.

В случае динамической игры она представляется в виде не которого поэтап­ного многошагового процесса, который, как правило, задается в виде разностных (рекуррентных) уравнений. Эти уравнения могут иметь вид функционального уравнения Беллмана в динамическом программировании, дифференциально-разностных урав­нений Понтрягина в дискретном принципе максимума или в виде соотношений задач математического программирования (нелинейного, линейного, целочисленного и т. д. Число стратегий здесь задается множеством допустимых решений, которое может

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

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

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

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

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

Целую группу игр составляют выпуклые, полиномиальные и «вырожденные» игры, которые соответственно обладают выпуклой платежной функцией, платежной функцией в виде полинома и «вы­рожденной» платежной функцией относительно переменных, опре­деляющих стратегию, т. е.

k

Н (x1, х2, ..., хn ) = å j1i (x1), j2i (х2), ..., jni(хn).

i=l

.

Один класс антагонистических непрерывных игр называется играми с выбором временидействия (игры типа дуэли). Чем позже выстрелит каждый из участников дуэли, тем больше вероятность успешного выстрела (противники сходятся к барьеру). Но при этом противник может выстрелить раньше. Если противник слышит выстрелы, дуэль называется «шумной», В противном случае­ дуэль называется «бесшумной».

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

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