«Стратегические игры. Доступный учебник по теории игр». Отрывок

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

Глава 3. Игры с последовательными ходами

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

Большинство реальных игр сочетают в себе аспекты игр как с последовательными, так и с одновременными ходами. Однако концепции и методы анализа легче понять, если сначала они вводятся отдельно для двух чистых типов игр. С учетом этого факта в данной главе мы рассматриваем только игры с последовательными ходами. Главы 4 и 5 целиком и полностью посвящены играм с одновременными ходами, а в главе 6 и в некоторых разделах главы 7 показано, как объединить эти два типа анализа в более реалистичных смешанных ситуациях. Анализ, представленный в данной главе, можно использовать каждый раз, когда игра включает в себя последовательное принятие решений. Кроме того, анализ игр с последовательными ходами позволяет определить, когда игроку выгодно делать ход первым, а когда вторым. Далее игроки могут разработать способы манипулирования порядком игры в свою пользу. Анализ таких способов, которые обозначаются термином «стратегические ходы», представлен в главе 9.

1. Дерево игры

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

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

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

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

Если Энн выберет «стоп», наступит очередь Боба делать ход. В узле действия Боба у него есть три варианта выбора, обозначенные как 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. Дерево игры состоит из узлов и ветвей. Узлы соединяются друг с другом ветвями и бывают двух типов. Узел первого типа обозначается термином «узел принятия решений». Каждый узел принятия решений соответствует игроку, который выбирает действие в данном узле. Каждое дерево имеет один узел принятия решений, который является начальным узлом дерева, отправной точкой игры. Узел второго типа обозначается термином «концевой узел». Каждому концевому узлу соответствует совокупность исходов игры для ее участников; эти исходы представляют собой выигрыши, полученные каждым игроком, если игра проходила по ветвям, которые привели к данному концевому узлу.

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

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

2. Решение игр с помощью деревьев

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

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

Узлы и ветви обозначены имеющимися в распоряжении Кармен вариантами выбора, однако нам необходимо объяснить выигрыши. Возьмем исход игры «никогда не курить» в качестве эталона для сравнения и присвоим ему выигрыш 0. У числа 0 в этом контексте нет никакого особого смысла; все, что имеет значение для сравнения исходов, а значит и для решения Кармен —соответствующий выигрыш больше или меньше остальных. Предположим, Кармен больше всего нравится исход игры, при котором она попробует курить какое-то время, но не станет продолжать. Причина может быть в том, что Кармен предпочитает испытывать все на собственном опыте, или в том, что это позволит ей более убедительно заявить «Я это пробовала и знаю, что ничего хорошего в этом нет», когда в будущем она попытается отговорить своих детей от курения. Присвоим этому исходу выигрыш +1. Худший исход игры — когда Кармен попробует курить и продолжит делать это и дальше. Даже если оставить в стороне вред, который курение может нанести здоровью в долгосрочной перспективе, существуют и более актуальные проблемы: волосы и одежда Кармен будут неприятно пахнуть, а друзья будут избегать ее. Присвоим такому исходу выигрыш −1. В таком случае выбор Кармен кажется очевидным: она должна попробовать курить, но ей не стоит продолжать делать это.

Однако в этом анализе не учитывается проблема зависимости. Как только Кармен попробует курить какое-то время, у нее сформируются другие вкусы и изменятся выигрыши. Решение о том, стоит ли продолжать курить, будет принимать не нынешняя Кармен с ее текущей оценкой исходов игры в таком виде, как показано на рис. 3.2, а будущая Кармен, которая по-другому оценит будущие альтернативы. Делая выбор в настоящее время, Кармен должна проанализировать последствия этого выбора в будущем и учесть это в текущем решении, которое она должна принять на основании текущих предпочтений. Другими словами, проблема выбора, касающаяся курения — это на самом деле не решение в том смысле, о котором шла речь в главе 2 (выбор, сделанный в нейтральной среде), а игра в формальном смысле, также представленная в главе 2, в которой другой игрок — это будущее «я» Кармен со своими собственными особыми предпочтениями. Когда нынешняя Кармен принимает решение, она должна вести игру с будущей Кармен.

В начальном узле нынешняя Кармен принимает решение, следует ли ей пробовать курить. Если она решает попробовать, тогда появляется будущая Кармен, попавшая в зависимость от курения, и принимает решение о том, продолжать ли курить. Давайте изобразим здоровую, не загрязняющую окружающую среду нынешнюю Кармен, ее действия и выигрыши синим цветом, а пристрастившуюся к курению будущую Кармен, ее действия и выигрыши — черным цветом (такими стали ее легкие). Выигрыши нынешней Кармен остались прежними. Однако будущей Кармен понравится курить и дальше, а если она попытается бросить, у нее наступит ужасный абстинентный синдром. Пусть выигрыш будущей Кармен в случае выбора варианта «курить» составляет +1, а выигрыш в случае выбора «не курить» −1.

Учитывая предпочтения будущей Кармен, пристрастившейся к курению, в узле принятия решений она выберет вариант «продолжать». Нынешняя Кармен проанализирует эту перспективу и примет ее во внимание во время принятия текущего решения, осознавая тот факт, что решение попробовать курить неизбежно приведет к тому, что она и впредь будет курить. Нынешняя Кармен не хочет продолжать курить в будущем, учитывая ее текущие предпочтения, однако она не сможет реализовать свой текущий предпочтительный выбор в будущем, поскольку будущая Кармен, у которой совсем другие предпочтения, сделает именно такой выбор. Следовательно, нынешняя Кармен должна предвидеть то, что выбор варианта «попробовать» приведет к дальнейшему выбору «продолжать» и обеспечит ей выигрыш −1 по ее текущим оценкам, тогда как выбор варианта «нет» даст выигрыш 0. Таким образом, Кармен следует выбрать второе.

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

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

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

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

Когда все участники игры выполняют анализ методом обратных рассуждений для выбора оптимальных стратегий, мы называем такую совокупность стратегий равновесием обратных рассуждений в данной игре; исход игры, полученный в результате выполнения этих стратегий — это исход равновесия обратных рассуждений. В более сложных учебниках по теории игр эта концепция обозначается как совершенное равновесие под-игры; возможно, ваш преподаватель отдает предпочтение именно этому термину. Мы приводим более формальное объяснение и анализ совершенного равновесия под-игры в главе 6, но мы предпочитаем более простой и интуитивно понятный термин «равновесие обратных рассуждений». Теория игр прогнозирует такой исход в качестве равновесия в игре с последовательными ходами, в которой все игроки являются рациональными вычислителями, стремящимися к получению максимального выигрыша. Немного ниже в данной главе мы проанализируем, как этот прогноз подтверждается практикой. А пока вам следует знать, что во всех конечных играх с последовательными ходами, представленных в данной книге, имеет место минимум одно равновесие обратных рассуждений. В действительности в большинстве игр присутствует в точности одно такое равновесие. В игре может быть больше одного равновесия обратных рассуждений только в исключительных случаях, когда игрок получает одинаковые выигрыши в результате двух или более наборов ходов, а значит не может отдать явное предпочтение ни одному из них.

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

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

3. Увеличение количества игроков

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

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

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

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

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

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

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

Очевидно, что первый из всех этих исходов игры самый лучший, тогда как последний — самый худший. Мы хотим, чтобы более высокие показатели выигрышей соответствовали более благоприятным исходам, поэтому мы присваиваем первому исходу в списке выигрыш 4, а последнему — выигрыш 1. (В некоторых случаях выигрыши соответствуют порядковому номеру исхода в списке исходов. Следовательно, при наличии четырех исходов первый был бы наилучшим, а четвертый самым худшим, а меньшие числа обозначали бы более предпочтительные исходы. Читая книгу по теории игр, обратите особое внимание на то, какую систему обозначений использует автор; если вы пишете о теории игр, вам следует точно указать, какую систему обозначений вы используете.)

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

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

Для того чтобы применить к этой игре метод обратных рассуждений, мы начнем с тех узлов действия, которые расположены непосредственно перед концевыми узлами, а именно — с узлов d, e, f и g. Талия делает ход в каждом из этих узлов. В узле d она сталкивается с ситуацией, в которой и Эмили, и Нина внесли вклад в создание сада. Этот сад уже наверняка будет красивым, поэтому выбрав вариант «не вносить вклад», Талия получит свой максимальный выигрыш 4, тогда как выбрав вариант «внести вклад», она получит следующий по размеру выигрыш 3. Следовательно, предпочтительный вариант выбора Талии в данном узле — «не вносить вклад». Мы отображаем это предпочтение, выделив соответствующую вервь жирной линией и прибавив к ней стрелку; любого из этих способов было бы достаточно для того, чтобы проиллюстрировать выбор Талии. В узле e Эмили выбрала вариант «внести вклад», а Нина — «не вносить вклад», поэтому вклад Талии крайне важен для создания красивого сада. Талия получит выигрыш 3, если выберет «внести вклад» и выигрыш 2, если выберет «не вносить вклад». Ее предпочтительный вариант выбора в узле e — «внести вклад». Точно так же можно проверить выбор Талии в двух оставшихся узлах.

Теперь давайте перенесем анализ на предшествующий этап — а именно, на узлы b и c, в которых наступает очередь Нины делать выбор. В узле b Эмили решила внести вклад в создание сада. Теперь Нина рассуждает так: «Если я выберу вариант "внести вклад", это приведет игру в узел d, в котором, насколько мне известно, Талия выберет "не вносить вклад", и мой выигрыш составит 3. (Сад будет красивым, а я смогу сэкономить на расходах в связи с моим вкладом.) Следовательно, я должна выбрать вариант "не вносить вклад"». Аналогичные рассуждения показывают, что в узле c Нина выберет вариант «внести вклад».

И наконец, рассмотрим выбор Эмили в начальном узле a. Эмили может предвидеть последующий выбор как Нины, так и Талии. Она знает, что если выберет вариант «внести вклад», далее Нина выберет «не вносить вклад», а Талия — «внести вклад». Если две участницы игры внесут свой вклад в создание сада, это будет красивый сад, но Эмили понесет издержки, а значит ее выигрыш составит 3. Если Эмили выберет вариант «не вносить вклад», тогда в двух следующих друг за другом узлах будет выбран вариант «внести вклад», и при наличии красивого сада и отсутствии издержек ее выигрыш составит 4. Таким образом, предпочтительный выбор Эмили в узле a — вариант «не вносить вклад».

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

Анализ методом обратных рассуждений прост и привлекателен. Ниже представлены некоторые важные аспекты такого анализа. Во-первых, обратите внимание на то, что на равновесном пути игры с последовательными ходами отсутствует большинство ветвей и узлов. Однако вычисление лучших действий, которые были бы предприняты, если бы игра все же достигла этих узлов — это важная часть процесса поиска окончательного равновесия. На ранних этапах игры ее участницы делают выбор под влиянием своих ожиданий в отношении того, что произошло бы, если бы они выбрали действие, отличающееся от самого лучшего действия, а также ожиданий в отношении того, что произошло бы, если бы любая из остальных участниц игры предпочла сделать нечто такое, что не было бы для нее самым лучшим. Эти ожидания, основанные на прогнозируемых действиях в узлах, расположенных вне равновесного пути игры (то есть в узлах, которые соответствуют ветвям, отсеченным в процессе анализа методом обратных рассуждений) позволяют участницам игры выбирать оптимальные действия в каждом узле. Например, оптимальный выбор Эмили «не вносить вклад», сделанный в первом узле, зависит от понимания того, что если она выберет вариант «внести вклад», тогда Нина выберет вариант «не вносить вклад», после чего Талия выберет «внести вклад»; эта последовательность обеспечит Эмили выигрыш 3 вместо выигрыша 4, который она могла бы получить, выбрав вариант «не вносить вклад» на первом ходе.

Равновесие обратных рассуждений обеспечивает исчерпывающее описание всего процесса анализа посредством формулировки оптимальной стратегии для каждого игрока. Мы уже говорили о том, что стратегия — это исчерпывающий план действий. Эмили делает первый ход и у нее есть два варианта выбора, а значит ее стратегия достаточно проста и по существу сводится к одному ходу. Однако Нина, которая делает второй ход, совершает действие в одном из двух узлов: в одном — если Эмили выбрала вариант «внести вклад», а в другом — если Эмили выбрала вариант «не вносить вклад». В исчерпывающем плане действий Нины должно быть оговорено, что она должна сделать в каждом из этих случаев. Один такой план, или стратегия, сводится к следующему: «Выбрать "внести вклад", если Эмили выбрала "внести вклад", и выбрать "не вносить вклад", если Эмили выбрала "не вносить вклад"». Благодаря анализу методом обратных рассуждений мы знаем, что Нина не выберет эту стратегию, но на данном этапе нам необходимо описание всех возможных стратегий, из которых Нина сможет сделать выбор согласно правилам игры. Мы можем сократить описание стратегий, используя обозначение «В» вместо «внести вклад» и «Н» вместо «не вносить вклад». В таком случае упомянутую выше стратегию можно описать так: «В если Эмили выберет В, а значит игра перейдет в узел b, Н если Эмили выберет Н и игра перейдет в узел с», или еще проще — «В вb, Н в c», или даже «ВН», если обстоятельства, при которых каждое из указанных действий, очевидны или были разъяснены ранее. Теперь можно увидеть, что поскольку у Нины есть два варианта выбора в каждом из двух узлов, в которых она может действовать, в ее распоряжении есть четыре плана действий, или стратегии: «В вb, В вc»; «В вb, Н в c»; «Н в b, В вc» и «Н в b, Н в c», или «ВВ», «ВН», «НВ» и «НН». Анализ методом обратных рассуждений, а также стрелки в узлах b и c на рис. 3.6 показывают, что оптимальная стратегия Нины — «НВ».

В случае Талии ситуация еще сложнее. Когда наступит ее очередь, история игры может представлять собой любой из четырех возможных вариантов. Очередь действовать переходит к Талии в одном из четырех узлов дерева: один после того, как Эмили выбрала В и Нина выбрала В (узел d); второй после В Эмили и Н Нины (узел e); третий после Н Эмили и В Нины (узел f) и четвертый после того, как и Эмили, и Нина выбрали Н (узел g). Каждая из стратегий (или исчерпывающих планов действий) Талии должна определять одно из двух действий по каждому из этих четырех сценариев, или одно из двух действий в каждом из возможных узлов действия. При наличии четырех узлов, в которых необходимо указать действие, и двух действий, из которых необходимо выбрать одно каждом узле, существует 2 × 2 × 2 × 2, или 16 возможных комбинаций действий. Следовательно, в распоряжении Талии есть 16 возможных стратегий. Одну из них можно было бы записать так:

«В вd, Н в e, Н в f, Ввg» или для краткости «ВННВ»

Здесь мы зафиксировали последовательность четырех сценариев (историй ходов Эмили и Нины) в порядке расположения узлов d, e, f и g. Далее с помощью такой же сокращенной формы записи можно составить список всех 16 стратегий, имеющихся в распоряжении Талии:

ВВВВ, ВВВН, ВВНВ, ВВНН, ВНВВ, ВНВН, ВННВ, ВННН, НВВВ, НВВН, НВНВ, НВНН, ННВВ, ННВН, НННВ, НННН

Анализ методом обратных рассуждений дерева игры на рис. 3.6, а также стрелки в узлах узлов d, e, f и g показывают, что оптимальная стратегия Талии — НВВН.

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

Мы можем объединить оптимальные стратегии участниц игры с тем, чтобы найти фактический путь игры, который приведет к равновесию обратных рассуждений. Эмили начнет с выбора Н. Нина, придерживаясь своей стратегии НВ, выберет действие Вв ответ на действие Эмили Н. (Помните: стратегия НВ Нины означает «выбрать Н, если Эмили выбрала В, и выбрать В, если Эмили выбрала Н»). Согласно принятой нами договоренности, фактическое действие Талии после Н Эмили и В Нины (из узла f) обозначается третьей буквой в нашем состоящем из четырех букв описании ее стратегий. Поскольку оптимальная стратегия Талии — НВВН, ее действие по пути игры — В. Таким образом, фактический путь игры состоит из действия Н, выбранного Эмили, и действия В, выбранного Ниной и Талией.

Итак, мы имеем три разные концепции.

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

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

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

4. Преимущества порядка

В равновесии обратных рассуждений в игре «уличный сад» Эмили получает самый лучший исход (выигрыш 4), поскольку она может воспользоваться возможностью сделать первый ход. Приняв решение не вносить свой вклад в создание сада, Эмили перекладывает бремя ответственности на двух других участниц игры: каждая из них может получить следующий лучший исход только при условии, если они обе выберут вариант «внести вклад». Большинство людей, не имеющих опыта ведения стратегических игр, придерживаются предвзятого мнения, будто такое преимущество первого хода должно присутствовать во всех играх. Однако на самом деле это не так. Можно без труда найти игры, в которых преимущество состоит в возможности сделать ход вторым. Представьте себе стратегическое взаимодействие между двумя компаниями, которые продают аналогичные товары по каталогам — скажем, Land’sEnd и L.L. Bean. Если бы одна компания выпустила свой каталог первой, вторая еще до выпуска своего каталога получила бы возможность узнать, какие цены установила первая компания. Это позволило бы второй компании предложить более низкие цены на все товары, чем у конкурента, и получить огромное конкурентное преимущество.

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

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

5. Увеличение количества ходов

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

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

А. Крестики-нолики

Начнем с игры в крестики-нолики, самой простой из упомянутых выше игр, и рассмотрим более легкий вариант игры, в которой каждый из двух игроков (Х и О) пытается первым заполнить двумя своими символами любой столбец, ряд или диагональ в игре на поле два на два. У первого игрока есть четыре возможных действия или позиции, в которых он может поставить свой крестик. В таком случае у второго игрока есть три возможных действия в каждом из четырех узлов принятия решений. Когда первый игрок получает право сделать второй ход, у него есть два возможных действия в каждом из 12 (4 × 3) узлов принятия решений. Как показано на рис. 3.7, даже у этой мини-игры «крестики-нолики» очень сложное дерево игры. На самом деле это дерево не такое уж сложное, поскольку игра обязательно закончится, после того как первый игрок сделает второй ход. Тем не менее, на этом дереве все же есть 24 концевых узла, которые необходимо проанализировать.

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

Хотя у этой версии игры в крестики-нолики интересное дерево, ее решение не отличается особой содержательностью. Первый игрок всегда выигрывает, поэтому выбор, сделанный обоими игроками, не может повлиять на конечный результат. Большинству из нас больше знакома игра в крестики-нолики на поле три на три. Для того чтобы проиллюстрировать эту версию деревом игры, нам пришлось бы показать, что у первого игрока есть девять возможных действий в начальном узле, у второго игрока есть восемь возможных действий в каждом из девяти узлов принятия решения, а затем у первого игрока на его втором ходе есть семь возможных действий в каждом из 8 × 9 = 72 узлов, тогда как у второго игрока на втором ходе есть шесть возможных действий в каждом из 7 × 8 × 9 = 504 узлов. Эта закономерность продолжается до тех пор, пока дерево не прекратит стремительно разрастаться, поскольку определенные комбинации ходов приводят к победе первого игрока, после чего игра заканчивается. Однако минимум до пятого хода победа невозможна. Для того чтобы нарисовать полное дерево этой игры, понадобился бы очень большой лист бумаги или очень мелкий почерк.

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

Книгу можно купить онлайн на сайте издательства