Программирование игр и головоломок

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

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

В описании игры можно выделить следующие элементы:

1) коалиции  действий - совокупность действующих  совместно в данной конфликтной ситуации субъектов;

2) коалиции  интересов - множество одинаково  заинтересованных в исходе конфликта  сторон;

3) множества  возможных выборов каждой из  коалиций действия;

4) описание  предпочтений каждой из коалиций  интересов;

5) множество  возможных исходов конфликта.

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

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

Для принятия решений необходимо обладать определенной информацией. При этом как сам выбор из множества стратегий, так и ожидаемый результат зависят в значительной степени от информации, которой обладает игрок к моменту принятия решения: о множествах выбора, мотивах поведения или принципе оптимальности игроков, о природных неопределенных факторах, той информации, которую сейчас игрок не имеет, но которая будет поступать к нему, в том числе та, которой он будет обладать в результате добровольного обмена или ее добывания. Поэтому целесообразно дать общее определена стратегии. Если множество Bi описывает информацию, которую коалиция (игрок) i использует при принятии решений, то под стратегией будем понимать отображение : → , где - множество выборов или управлений коалиции действия i. В результате выбора каждой коалиции действия элемента и множества управлений определяется исход конфликта. Соответственно выбор коалициями действия стратегии определяет ситуацию в множестве стратегий . Таким образом, можно трактовать множество управлений U как "физические", а множество стратегий U как "физические" и информационные возможности.

Заинтересованность j-го субъекта формализуется, как правило, функцией

выигрыша, которая определяется отображением : U → R, где U – множество исходов. Выбор стратегии или управления определяется принципом оптимальности.

Таким образом, для описания конфликтной ситуации необходимо задал

систему:

Г={N,,,{∈,{∈, S},

где

N - множество игроков,

- множество коалиций  действия,

- множество коалиций  интересов,

- множество выборов  коалиции i∈Kg ,

- функция выигрыша  коалиции j∈Kи ,

S - множество  возможных исходов игры.

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

динамическими.

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

В качестве первого классификационного признака возьмем множество игроков. Различают игры 2-х лиц и игры n лиц (n>2). Игры 2-х лиц называются антагонистическими, если игроки преследуют противоположные цели. Если в антагонистической игре игрок 1 стремится максимизировать свой выигрыш g1, то целью игрока 2 является минимизация выигрыша игрока 1, так что g1 = -g2. Поэтому антагонистическую игру можно задать следующим образом:

Г=(U1,U2,g),

где g - выигрыш игрока 1.

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

Можно говорить так же о неантагонистических играх 2-х лиц (g1 ≠ -g2).

Другой важный принцип классификации связан с вопросом о допустимости образования тех или иных коалиций. Если в игре образование коалиций недопустимо, то такая игра называется бескоалиционной. Она определяется заданием множества игроков, пространств их стратегий и набором их функций выигрыша.

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

Отдельный класс составляют игры с бесконечным числом игроков.

Следующим признаком классификации являются стратегии. Если множество стратегий всех игроков конечно, то игра называется конечной. Когда хотя бы одно из множеств , i = n, бесконечно, игра называется бесконечной. Для теоретического анализа более удобны конечные игры, однако они имеют меньшую практическую ценность, чем бесконечные.

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

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

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

Существует два способа реализации смешанных стратегий:

1) введение  искусственной рандомизации, т. е. использование  функции распределения на исходном множестве управлений;

2) введение повторения, т.е. проведения конфликта многократно.

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

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

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

расширения класса стратегий.

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

 

1.3 Бесконечные и  конечные игры

 

Существует, по меньшей мере, два типа игр. Один можно назвать конечными играми, а другой – бесконечными.

В конечные игры играют с целью добиться выигрыша, а в бесконечные – для того чтобы продолжать играть.

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

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

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

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

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

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

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

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

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

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

 

1.4 Антагонистические игры

 

   

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

Формально антагонистическая игра может быть представлена тройкой <X, Y, F>, где X и Y — множества стратегий первого и второго игроков, соответственно; F — функция выигрыша первого игрока, ставящая в соответствие каждой паре стратегий (ситуации) (x и y),  x X, y Y действительное число, соответствующее полезности первого игрока при реализации данной ситуации. Так как интересы игроков противоположны, функция F одновременно представляет и проигрыш второго игрока.

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

Игра с нулевой суммой (zero-sum game) - состязание, в котором проигрыш одного игрока равнозначен выигрышу другого. Игры можно разделить на две категории: с нулевой и с ненулевой суммой. Если сумма выигрышей всех игроков остается постоянной при любых вариантах исхода игры, ее относят к категории игр с постоянной суммой. Но поскольку математически выплаты могут быть смещены по шкале, удобнее и нормальнее называть их играми с нулевой суммой. В игре с нулевой суммой при любом варианте ее исхода выигрыш победителя (победителей) всегда равен убытку проигравшего (проигравших). Большинство игр в обычном смысле слова, без избирательного вмешательства извне, являются именно такими играми. К ним принадлежат, в частности, шахматы и футбол (даже если какая-то посторонняя организация присуждает за победу установленную награду). Однако футбольная игра, в которой игрокам платят за то, чтобы они сыграли вничью, или игра в слова (в которой игроки получают очки, составляя слова из случайных разрозненных букв), где награда дается за наибольшую сумму набранных очков, представляют собой примеры игр с нулевой суммой. Такое определение предпочтительнее чем "с положительным результатом" или "с отрицательным результатом". Несмотря на широкое употребление двух последних определений, они обычно создают путаницу, а иногда и оказываются неверными, т.к. не дают точного определения тому, с чем сравнивать положительный результат. В 1944 г. Дж. фон Нейман и О. Моргенштерн выдвинули теорию, согласно которой во всех играх с нулевой суммой и двумя участниками существует особое равновесие, когда каждый участник выбирает стратегию, которая сводит до минимума его потери при любой возможной стратегии противника (см. также: "Минимакс"; "максимин"). Это элегантное математическое построение имеет ограниченное практическое значение, хотя и свидетельствует о существовании оптимальной стратегии игры в шахматы. К счастью, эта стратегия до сих пор не найдена. Игры с нулевой суммой имеют в политике менее формальное значение. Если в игре участвуют два партнера, объединение между ними не возможно; при большем количестве игроков возникают широкие, часто безграничные возможности создания временных коалиций одной части игроков против другой. Поэтому игры с образованием коалиций имеют нулевую сумму. Некоторые авторы причисляют к этой категории и другие политологические игры, например, гонку вооружений или промышленный конфликт. Это неизменно приводит к мрачным прогнозам, поскольку в данных случаях исключается длительное взаимодействие. Игры с ненулевой суммой дают игрокам возможность взаимодействия для получения оптимального результата. Это остается в силе независимо от того, подразумевает игра взаимодействие или нет. Даже в игре без взаимодействия, например в "дилемме заключенных" (prisoners dilemma), игроки имеют возможность размышлять о ходе мыслей противника. В повторяющихся играх без взаимодействия игроки могут координировать свои действия на основе равновесия взаимодействия (более высокого по уровню). Большинство политологических игр, кроме игр с образованием коалиций, наверное, лучше всего рассматривать как игры с ненулевой суммой".