Читать книгу Стратегические игры. Доступный учебник по теории игр - Авинаш Диксит - Страница 20

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

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

А. Узлы, ветви и пути игры

На рис. 3.1 изображено дерево конкретной игры с последовательными ходами. Мы не будем здесь описывать ее историю, поскольку хотим опустить многочисленные детали, чтобы вы могли сфокусироваться на общих концепциях. В игре участвуют четыре человека: Энн, Боб, Крис и Деб. Согласно правилам игры, первый ход делает Энн; это показано в крайней левой точке дерева, или узле под названием начальный узел или корень дерева игры. В этом узле, который еще можно называть узлом действия или узлом принятия решений, у Энн есть два доступных варианта выбора. Они обозначены как «стоп» и «вперед» (не забывайте, что это абстрактные обозначения и они не обязательно должны иметь какой-то смысл) и показаны на рисунке в виде ветвей, исходящих из начального узла.

.

Рис. 3.1. Иллюстративное дерево игры

Если Энн выберет «стоп», наступит очередь Боба делать ход. У него в узле действия есть три варианта выбора, обозначенные как 1, 2 и 3. Если Энн выбирает «вперед», то следующий ход делает Крис с вариантами выбора «рискованно» и «безопасно». Другие узлы и ветви следуют друг за другом, но вместо того чтобы их перечислять, мы просто обратим ваше внимание на некоторые характерные особенности данного дерева.

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

Б. Неопределенность и «ходы природы»

Если Энн выберет ход «вперед», а Крис – «рискованно», произойдет случайное событие, например подбрасывание монеты, и исход игры будет зависеть от того, выпадет орел или решка. Этот аспект игры представляет собой пример внешней неопределенности и отображается на дереве игры посредством введения внешнего игрока под названием «природа». Ему передается контроль над случайным событием, и он как будто выбирает одну из ветвей, каждую с вероятностью 50 %. Вероятность здесь определяется посредством случайного события одного типа, а именно подбрасывания монеты, но в других обстоятельствах могут использоваться и события иных типов. Например, в случае бросания игральных костей «природа» могла бы указать шесть возможных вариантов, каждый с вероятностью 16²/₃ процента. Использование игрока под названием «природа» позволяет ввести в игру фактор внешней неопределенности и предоставляет в наше распоряжение механизм, который делает возможным наступление событий, находящихся вне контроля реальных участников игры.

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

В. Исходы и выигрыши

В последнем узле каждого пути, так называемом концевом узле, ни один игрок не может сделать очередной ход. (Обратите внимание, что именно этим концевые узлы отличаются от узлов действия.) Вместо этого мы показываем в этом узле исход определенной последовательности действий, выраженный в выигрышах игроков. Выигрыши наших четырех героев перечислены в таком порядке: Энн, Боб, Крис, Деб. Важно указать, какой выигрыш соответствует каждому игроку. Обычно выигрыши принято указывать в том порядке, в каком игроки делают ходы. Однако иногда этот метод бывает неоднозначным; в нашем примере непонятно, кто должен делать следующий ход, Боб или Крис. Поэтому мы перечислили их в алфавитном порядке (англ. Ann, Bob, Chris, Deb), а кроме того, использовали цветную маркировку информации об игроках. Так, имя Энн, ее варианты выбора и выигрыши выделены черным цветом, Боба – темно-серым, Криса – светло-серым, а Деб – серым. При построении деревьев для игр, которые вы будете анализировать, можно выбрать любую понравившуюся вам систему обозначений, но вы должны четко сформулировать и объяснить ее тому, кто будет читать дерево игры.

Выигрыш – это числовая величина, и, как правило, для каждого игрока чем она больше, тем лучше исход игры. Таким образом, для Энн самый нижний путь (выигрыш 3) лучше самого верхнего (выигрыш 2). Однако выигрыши разных игроков не обязательно должны быть сопоставимы. В данном примере неочевидно, что в конце самого верхнего пути Боб (выигрыш 7) добивается большего, чем Энн (выигрыш 2). Иногда, например если выигрыш исчисляется в денежных единицах, сравнение выигрышей может иметь смысл.

Игроки используют информацию о выигрышах при выборе доступных действий. Включение случайного события (выбор, сделанный «природой») означает, что игрокам необходимо определить, что они получат в среднем, когда «природа» сделает свой ход. Например, если Энн выберет «вперед» в качестве первого хода в игре, Крис может выбрать «рискованно», что приведет к подбрасыванию монеты и выбору «природой» варианта «хорошо» или «плохо». В такой ситуации Энн в половине случаев может рассчитывать на выигрыш 6 и в половине случаев – на выигрыш 2; иными словами, статистическое среднее, или ожидаемый выигрыш, составит 4 = (0,5 × 6) + (0,5 × 2).

Г. Стратегии

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

На данном дереве игры Боб, Крис и Деб получают возможность сделать ход максимум один раз; например, Крис будет ходить только в случае, если Энн в качестве первого хода выберет «вперед». Для этих игроков между ходом и стратегией нет разницы. Мы можем определить ход, указав условие, при котором он будет сделан; так, в случае Боба может быть следующая стратегия: «Выбрать 1, если Энн выберет “стоп”». Однако у Энн есть две возможности сделать ход, поэтому ее стратегия требует более полного описания. Одна из стратегий Энн: «Выбрать “стоп”, а если Боб выберет 1, выбрать “вниз”».

В более сложных играх, таких как шахматы, где есть длинные последовательности ходов с большим количеством вариантов выбора в каждой, описание стратегий усложняется; мы обсудим данный аспект более подробно далее в этой главе. Однако общий принцип построения стратегий достаточно прост, за исключением одной особенности. Если Энн выберет «вперед» на первом ходе, она так и не получит шанса сделать второй ход. Следует ли в стратегии, согласно которой она выбирает «вперед», указывать то, что Энн сделала бы в гипотетическом случае, если бы каким-то образом оказалась в узле своего второго действия? Возможно, ваша интуиция скажет «нет», но формальная теория игр говорит «да» по двум причинам.

Во-первых, выбор Энн варианта «вперед» в качестве первого хода может зависеть от ее рассуждений о том, что ей пришлось бы сделать на втором ходе, если бы она изначально предпочла вариант «стоп». Например, тогда Боб мог бы выбрать 1, и Энн получила бы второй ход, а ее лучшим выбором стал бы вариант «вверх», обеспечивающий ей выигрыш 2. Если Энн для первого хода выберет «вперед», Крис выберет вариант «безопасно» (поскольку его выигрыш 3 в случае варианта «безопасно» больше, чем ожидаемый выигрыш от варианта «рискованно»), и такой исход игры обеспечит Энн выигрыш 3. Для того чтобы процесс размышлений был понятнее, можно сформулировать стратегию Энн так: «Выбрать “вперед” на первом ходе и выбрать “вверх”, если появится возможность походить еще раз».

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

Д. Построение дерева

Теперь подытожим общие концепции, проиллюстрированные деревом, представленным на рис. 3.1. Дерево игры состоит из узлов и ветвей. Узлы соединены между собой ветвями и бывают двух типов. Узел первого типа обозначается термином «узел принятия решений». Каждый такой узел соответствует игроку, который выбирает в нем действие. Каждое дерево имеет один узел принятия решений – это начальный узел дерева, отправная точка игры. Узел второго типа называется «концевой узел». Каждому концевому узлу соответствует совокупность исходов игры для ее участников; эти исходы представляют собой выигрыши, полученные каждым игроком, если игра проходила по ветвям, приведшим к данному концевому узлу.

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

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