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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Г. Стратегии

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На рис. 3.6 изображено дерево этой игры. Чтобы облегчить ее описание, мы обозначили узлы действия специальными символами. Эмили делает ход в начальном узле a, а ветви, соответствующие двум имеющимся у нее вариантам выбора («внести вклад» и «не вносить вклад»), ведут к узлам b и c. В каждом из них должна сделать ход Нина и выбрать один из представленных вариантов. Ее выбор приводит к узлам d, e, f и g, в каждом из которых наступает очередь Талии ходить. Имеющиеся у Талии варианты выбора приводят к восьми концевым узлам, где мы показываем выигрыш в таком порядке: (Эмили, Нина, Талия). Например, если Эмили решает инвестировать в создание сада, Нина нет, а Талия да, то красивый декоративный сад будет разбит и две участницы, внесшие вклад в его создание, получат выигрыш 3 каждая, а участница, которая решила сэкономить, — свой максимальный выигрыш 4. В данном случае список выигрышей выглядит так: (3, 4, 3).

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

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

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

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

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

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

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

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

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

ВВВВ, ВВВН, ВВНВ, ВВНН, ВНВВ, ВНВН, ВННВ, ВННН, НВВВ, НВВН, НВНВ, НВНН, ННВВ, ННВН, НННВ, НННН.

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

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

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

В итоге мы имеем три разные концепции:

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

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

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

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

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

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

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

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

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

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

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

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

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

Б. Шахматы

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

В шахматах в распоряжении игроков (условно называемых «белые» и «черные») имеются наборы из 16 фигур разной формы, которые передвигаются по шахматной доске восемь на восемь клеток (рис. 3.8) в соответствии с заданными правилами. Белые ходят первыми, черные — вторыми, и так далее по очереди. Все ходы видны другому игроку, и ничего не оставлено на волю случая, как в карточных играх, где карты перетасовываются и сдаются. Кроме того, шахматная партия должна заканчиваться за конечное число ходов. Согласно правилам, при троекратном повторении одной и той же позиции в течение игры объявляется ничья. Ввиду наличия конечного количества способов разместить 32 фигуры (или меньше, если некоторые фигуры побиты) на 64 клетках шахматной доски, партия не может продолжаться бесконечно долго без возникновения подобной ситуации. Поэтому в принципе шахматы поддаются полному анализу методом обратных рассуждений.

Однако этот анализ так и не проведен. Шахматы не «решены» так, как в свое время крестики-нолики, а причина в том, что, несмотря на простоту правил, шахматы — чрезвычайно сложная игра. Из начальной позиции набора фигур, показанных на рис. 3.8, белые могут сделать любой из 20 ходов, а черные — ответить любым из 20 ходов. Следовательно, из первого узла исходят 20 ветвей, каждая ведет ко второму узлу, из которого исходят еще 20 ветвей. Всего после двух ходов образуется 400 ветвей, и каждая ведет к узлу, из которого исходят очередные ветви. Общее же количество возможных ходов в шахматах составляет, по примерным оценкам, 10¹²⁰, то есть единицу со 120 нулями. Суперкомпьютеру, в тысячу раз превышающему ваш ПК по быстродействию и выполняющему один триллион операций в секунду, понадобилось бы более 10¹⁰⁰ лет, чтобы проверить все ходы. Астрономы отводят нам менее 10¹⁰ лет до того момента, когда Солнце превратится в красный гигант и поглотит Землю.

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

Когда стало ясно, что компьютеры способны выполнять сложные вычисления в науке и бизнесе, многие математики и программисты решили, что вскоре компьютерная шахматная программа победит именитых гроссмейстеров. Но это произошло не так быстро, хотя компьютерные технологии развивались стремительными темпами, тогда как человеческое мышление несколько поотстало. В конце концов в декабре 1992 года немецкая компьютерная программа под названием Fritz2 выиграла у чемпиона мира Гарри Каспарова несколько блицпартий. Согласно обычным правилам, каждому игроку предоставляется 2,5 часа на выполнение 40 ходов, и люди дольше удерживали превосходство. Команда специалистов, финансируемая компанией IBM, вложила немало усилий и ресурсов в разработку специализированного компьютера (получившего название Deep Blue) для игры в шахматы и соответствующего программного обеспечения. В феврале 1996 года Deep Blue выступил в роли противника Гарри Каспарова в матче из шести партий и произвел сенсацию, выиграв первую партию, но Каспаров быстро выявил его слабые места, улучшил контрстратегии и мастерски выиграл остальные партии. На протяжении следующих 15 месяцев команда IBM совершенствовала аппаратное и программное обеспечение компьютера, после чего в мае 1997 года модифицированный Deep Blue выиграл у Каспарова очередной матч из шести партий.

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

При обдумывании хода в шахматах крайне трудно (для обоих: и людей, и компьютеров) заранее предвидеть исход игры. Но как насчет того, чтобы просчитать часть ходов, скажем 5−10, вперед и проанализировать игру в обратном порядке из этой позиции? Игра необязательно должна закончиться в рамках этого ограниченного периода; иными словами, узлы, которых вы достигнете через 5−10 ходов, не будут концевыми. Однако в соответствии с правилами игры выигрыши указываются только для концевых узлов. Следовательно, необходим некий косвенный способ присвоения правдоподобных выигрышей неконцевым узлам, поскольку вы не можете проанализировать все дерево игры методом обратных рассуждений с самого конца. Правило, согласно которому присваиваются промежуточные выигрыши, называется функцией промежуточной оценки.

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

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

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

Именно на стадии миттельшпиля на первый план выходит искусство игры в шахматы. У лучших шахматистов развивается интуиция, которая позволяет им распознавать хорошие возможности и избегать скрытых ловушек на уровне, с которым компьютерным программам сложно конкурировать. Программисты обнаружили, что в большинстве случаев компьютеры трудно обучить тем навыкам распознавания образов, которые люди развивают и используют инстинктивно, — например, когда они узнают лица и связывают их с именами. Искусство ведения игры на стадии миттельшпиля в шахматах — это распознавание и оценка комбинаций столь же загадочным способом. Именно в этом состояло самое большое преимущество Каспарова перед Fritz2 или Deep Blue. Это также объясняет, почему компьютерные программы показывают более высокие результаты в игре с людьми в блицпартиях или партиях с ограниченным временем обдумывания ходов: человеку просто не хватает времени, чтобы применить свое искусство ведения игры на стадии миттельшпиля.

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

В последнее время компьютеры начали накапливать больше знаний. В процессе модификации Deep Blue в 1996–1997 годах специалисты IBM заручились поддержкой экспертов по шахматам для улучшения функции промежуточной оценки в своих программах. Консультанты много раз играли в шахматы с компьютером, отмечали его слабые места и подсказывали, как изменить функцию оценки, чтобы устранить дефекты. Deep Blue явно пошел на пользу вклад экспертов и их тонкое мышление, ставшее результатом многолетнего опыта и знания сложных взаимо­связей между фигурами на шахматной доске.

Если люди, постепенно формулируя свои глубинные знания, передают их компьютерам, то на что рассчитывать шахматистам, не получающим от ПК аналогичной помощи? В момент первой встречи с Deep Blue в 1997 году Каспаров был поражен человеческим или даже сверхчеловеческим качеством игры компьютера. Он даже увидел в одном из его ходов «руку Бога». А ведь ситуация может усугубиться еще сильнее: способность компьютеров просчитывать ходы методом грубой силы стремительно повышается, причем одновременно, хотя и медленнее, они обретают тонкость мышления, свойственную человеку.

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

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

В. Шашки

Невероятное количество компьютерных и человеко-часов ушло на поиск решения игры в шахматы. С не меньшим упорством исследователи работали и над решением несколько более простой игры — в шашки, и в 2007 году объявили, что оно найдено.

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

Хотя сложность шашек меркнет на фоне шахмат (количество вероятных позиций в шашках приблизительно равно квадратному корню из количества позиций в шахматах), существует 5 × 10²⁰ возможных позиций, так что о построении дерева игры не может быть и речи. Если исходить из здравого смысла и результатов чемпионатов мира по шашкам за многие годы, то хорошая игра должна приводить к ничьей, но это не было доказано. Однако спустя какое-то время программисту из Канады все же удалось получить такое доказательство — компьютерную программу Chinook, которая способна обеспечить гарантированную ничью.

Chinook появилась в 1989 году, а в 1992-м впервые сразилась с чемпионом мира по шашкам Марионом Тинсли (проиграв со счетом 4:2 при 33 ничьих), а затем еще раз в 1994 году (когда во время серии ничьих у Тинсли пошатнулось здоровье). В период с 1997 по 2001 год работа над программой была приостановлена, поскольку ее создатели ждали усовершенствования компьютерных технологий. И наконец весной 2007 года Chinook продемонстрировала беспроигрышный алгоритм игры в шашки, использующий комбинацию анализа методом обратных рассуждений с конца игры и прямого анализа игры с исходной позиции наряду с эквивалентом функции промежуточной оценки для отслеживания лучших ходов в базе данных, включающей все возможные позиции на доске.

Создатели Chinook называют полную игру в шашки «слабо решенной»; они знают, что могут обеспечить ничью, и у них есть стратегия ее достижения с исходной позиции. Для всех 39 × 10¹² возможных позиций с наличием 10 или менее шашек на доске они описывают игру как «строго решенную». В этом случае они знают, что могут не только сыграть вничью, но и достичь ее из любой позиции, сформировавшейся после того, как на доске останется не более 10 шашек. Этот алгоритм сначала решил эндшпиль с 10 шашками, а затем вернулся к началу игры, чтобы найти те ее пути, на которых оба игрока делают оптимальный выбор. Механизм поиска, включающий комплексную систему оценки каждой промежуточной позиции, неизбежно приводил к тем позициям с 10 шашками, которые гарантировали ничью.

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

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

6. Фактические данные, касающиеся метода обратных рассуждений

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

Например, в ходе многих экспериментов разыгрывалась состоящая из одного раунда переговорная игра, где двух игроков, А и Б, выбирали из группы студентов или добровольцев. Затем экспериментатор давал им один доллар или другую оговоренную сумму, которую следовало разделить между двумя игроками по следующей схеме: игрок А предлагает, скажем, вариант «75 центов мне и 25 центов игроку Б». Если Б принимает это предложение, то доллар делится именно так, если отклоняет, то никто ничего не получает.

В данном случае анализ методом обратных рассуждений говорит о том, что игроку Б следует принять любую сумму, какой бы маленькой она ни была, поскольку альтернатива еще хуже (то есть 0), и исходя из этого игрок А вообще должен предложить «99 центов мне и 1 цент Б». Однако подобного исхода почти никогда не бывает. Большинство игроков, выступающих в роли игрока А, предлагают более справедливое, близкое к равному разделение суммы. На самом деле 50:50 — самый распространенный вариант. Мало того, большинство участников, будучи в роли игрока Б, отклоняют предложения, оставляющие им менее 25% от общей суммы, и уходят ни с чем, а некоторые отвергают даже 40%.

Многие специалисты по теории игр не согласны, что эти выводы подрывают теорию, аргументируя свою точку зрения примерно так: «Эти суммы настолько малы, что разум игроков воспринимает происходящее как нечто тривиальное. Игрок Б теряет 25 или 40 центов, что практически равно нулю, но при этом, возможно, испытывает определенное удовлетворение от того, что отказался от столь унизительного предложения. Если бы на кону стояла тысяча долларов и 25% составляли бы приличную сумму, то любой игрок Б принял бы такое предложение». Но этот аргумент нельзя считать бесспорным. Эксперименты с гораздо более высокими ставками демонстрируют аналогичные результаты. В Индонезии, например, оперировали суммами, не очень большими в долларах, но составлявшими трехмесячный заработок участников экспериментов. И тем не менее их результаты не показали явной склонности игроков А делать предложения о менее равноценном дележе общей суммы, хотя по мере ее увеличения игроки Б были готовы принимать несколько меньшую долю. Аналогичные эксперименты, проведенные в Словацкой Республике, доказали, что серьезное изменение выигрышей не влияет на поведение неопытных игроков.

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

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

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

Еще одна экспериментальная игра со столь же парадоксальными результатами проходит по следующей схеме: выбираются два игрока, А и Б. Экспериментатор кладет на стол монету в 10 центов. Игрок А может ее взять или пропустить ход. Если игрок А берет монету, игра закончена; при этом А получает 10 центов, а Б — ничего. Если игрок А пропускает ход, экспериментатор кладет на стол еще одну монету в 10 центов, и теперь игроку Б предстоит выбирать, взять ли ему обе монеты или пропустить ход. Игроки действуют по очереди, а стопка монет растет до тех пор, пока не достигнет определенной предельной суммы (например, одного доллара), заранее известной обоим игрокам.

Дерево этой игры показано на рис. 3.10. Из-за его внешнего вида игры такого типа часто называют игра «стоножка». Возможно, вам даже не понадобится строить дерево игры, чтобы проанализировать ее методом обратных рассуждений. Очевидно, что игрок Б возьмет один доллар на последнем этапе, поэтому игроку А следует взять 90 центов на предпоследнем этапе и т. д. Следовательно, игрок А должен взять монету в 10 центов в самом начале и закончить игру.

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

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

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

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

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

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

7. Стратегии в реалити-шоу Survivor

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

Летом 2000 года телеканал CBS показал первое реалити-шоу Survivor, которое моментально обрело популярность и способствовало созданию нового телевизионного жанра — «реалити-ТВ». Если опустить множество сложных деталей и некоторые более ранние этапы шоу, не имеющие отношения к нашей цели, то его концепция состояла в следующем. Группу участников под названием «племя» отправляли на необитаемый остров, где они должны были сами добывать себе пищу и искать крышу над головой. Каждые три дня члены племени путем голосования исключали из своих рядов одного из товарищей. Человек, набравший наибольшее количество голосов против, становился жертвой дня. Однако перед каждым собранием совета племени продержавшиеся до этого момента состязались в игре, требовавшей наличия физических или психических навыков, придуманной продюсерами специально для данного случая. Ее победитель получал иммунитет от предстоящего голосования. Кроме того, никто не имел права голосовать против себя. И наконец, когда оставалось всего два участника шоу, семь выбывших ранее членов племени возвращались в игру в качестве жюри, чтобы выбрать одного из них как ее победителя и обладателя приза в миллион долларов.

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

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

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

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

В итоге Рик умышленно сошел с опоры и впоследствии совершенно четко объяснил причины своего решения перед камерой. Его расчет оказался верным. Келли выиграла испытание и проголосовала против Руди. А в решающем голосовании жюри с перевесом в один голос отдало звание победителя Рику.

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

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

В начальном узле Рик решает, стоит ли продолжать участвовать в испытании на получение иммунитета. В любом случае возможного победителя с уверенностью предсказать нельзя, что отображено на дереве игры и позволяет сделать выбор «природе», как в ситуации с подбрасыванием монеты на . Если Рик продолжит игру, «природа» выберет победителя из трех участников состязания. Поскольку фактические значения вероятности нам неизвестны, мы возьмем конкретные значения для наглядности и укажем важные исходные предположения. Первое состоит в том, что Келли обладает высокой выносливостью, а Руди, будучи самым старшим, вряд ли победит. Поэтому мы присваиваем следующие значения вероятности победы в случае, если Рик решит продолжить игру: Келли — 0,5 (50%), Рик — 0,45 и Руди — всего 0,05. Если Рик сойдет с дистанции, «природа» случайным образом выберет победителя из двух оставшихся игроков. Здесь мы основываемся на предположении, что Келли выиграет с вероятностью 0,9, а Руди — 0,1.

Остальные ветви дерева исходят из узлов, соответствующих трем возможным победителям испытания. Если выиграет Руди, он, как и обещал, поддержит Рика, и жюри проголосует за Рика. Если иммунитет получит Рик, ему придется решать, кого поддержать — Келли или Руди. Если Руди, то жюри за него и проголосует. Если Келли, то неизвестно, кого предпочтет жюри. Мы предполагаем, что Рик, выступив против Руди, утратит расположение некоторых членов жюри и, несмотря на большую благосклонность со стороны жюри по сравнению с Келли, получит голоса его членов с вероятностью всего 0,4. Точно так же, если иммунитет достанется Келли, она может поддержать либо Руди и потерять голоса членов жюри, либо Рика. Если Келли выберет Рика, его вероятность получить голоса членов жюри повысится — 0,6, поскольку в этом случае жюри ему больше симпатизирует и он не голосовал против Руди.

Как насчет фактических выигрышей игроков? Мы можем с уверенностью предположить, что и Рик, и Келли стремятся максимизировать вероятность того, что в конечном счете кто-то из них выиграет 1 миллион долларов. Руди тоже хочет получить этот приз, но для него крайне важно сдержать данное Рику слово. С учетом этих предпочтений игроков Рик может выполнить анализ дерева игры методом обратных рассуждений, чтобы определить свой первоначальный выбор.

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

Каковы шансы Рика, рассчитанные в начальном узле? Если Рик выбирает в нем вариант «прекратить», у него остается только один путь к победе: Келли получает иммунитет (вероятность 0,9), после этого поддерживает Рика (вероятность 1), и жюри голосует за него (вероятность 0,6). Поскольку победа Рика зависит от совокупности этих трех событий, общая вероятность его победы представляет собой произведение трех вероятностей: 0,9 × 1 × 0,6 = 0,54. Если Рик в начальном узле выбирает вариант «продолжить», это открывает ему два пути к победе. Во-первых, он победит, если выиграет испытание на получение иммунитета (вероятность 0,45), после чего устранит Руди (вероятность 1) и все же получит голоса жюри в противостоянии с Келли (вероятность 0,4); общая вероятность победы при таком развитии событий составляет 0,45 × 0,4 = 0,18. Во-вторых, он станет победителем, если Келли выиграет испытание на получение иммунитета (вероятность 0,5), затем избавится от Руди (вероятность 1), а Рику достанутся голоса жюри (вероятность 0,6); в этом случае общая вероятность составляет 0,5 × 0,6 = 0,3. Общая вероятность победы Рика при выборе варианта «продолжить» представляет собой сумму вероятностей двух путей к победе, а именно 0,18 + 0,3 = 0,48.

Теперь Рик может сравнить вероятность выигрыша миллиона долларов при выборе варианта «прекратить» (0,54) с вероятностью победы в случае выбора варианта «продолжить» (0,48). С учетом предполагаемых значений различных вероятностей на дереве игры у Рика больше шансов на победу, если он откажется от участия в испытании на получение иммунитета. Следовательно, «прекратить» — его оптимальная стратегия. Хотя этот результат основан на присвоении определенных предполагаемых значений вероятностям тех или иных событий, он остается для Рика лучшим при выполнении следующих условий: 1) Келли с большой вероятностью выиграет испытание на получение иммунитета, если Рик откажется от дальнейшего участия в нем; 2) победа Рика в последнем голосовании жюри более вероятна в случае, если Келли, а не Рик, проголосует против Руди.

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

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

Резюме

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

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

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

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

Ключевые термины

Ветвь

Дерево игры

Дерево решений

Концевой узел

Корень (дерева)

Метод обратных рассуждений

Начальный узел

Обратная индукция

Отсечение (ветвей)

Преимущество второго хода

Преимущество первого хода

Путь игры

Равновесие обратных рассуждений

Равновесный путь игры

Узел

Узел действия

Узел принятия решений

Функция промежуточной оценки

Ход

Экстенсивная форма

Упражнения с решениями

S1. Предположим, два игрока, Гензель и Гретель, участвуют в игре с последовательными ходами. Гензель ходит первым, Гретель — второй, причем каждый ходит только раз.

a) Нарисуйте дерево игры, в которой у Гензеля есть два возможных действия («вверх» или «вниз») в каждом узле, а у Гретель — три («вверх», «посредине» или «вниз»). Сколько узлов каждого типа (узлов принятия решений и концевых узлов) присутствует в дереве этой игры?

b) Нарисуйте дерево для игры, в которой у Гензеля и Гретель по три возможных действия («сидеть», стоять» и «прыгать») в каждом узле. Сколько узлов двух типов присутствует в дереве такой игры?

c) Нарисуйте дерево для игры, в которой у Гензеля четыре возможных действия («север», «юг», «восток», «запад») в каждом узле, а у Гретель — два («стоять» или «идти»). Сколько узлов двух типов присутствует в дереве такой игры?

S2. Определите, сколько чистых стратегий (исчерпывающих планов действий) находится в распоряжении каждого игрока в следующих играх. Перечислите все чистые стратегии каждого игрока.

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

S4. Рассмотрим соперничество между Airbus и Boeing в сфере разработки нового коммерческого реактивного самолета. Предположим, что Boeing лидирует в этом процессе, а в Airbus размышляют, стоит ли вступать в конкурентную борьбу. В случае отказа Airbus получит нулевую прибыль, тогда как Boeing станет монополистом и заработает 1 миллиард долларов. Если Airbus решит вступить в борьбу и создать конкурентоспособный самолет, то Boeing придется решать, уладить ли разногласия с Airbus мирным путем или развязать ценовую войну. Мирная конкуренция обеспечит каждой компании прибыль в 300 миллионов долларов, а ценовая война приведет к потере каждой из них 100 миллионов долларов, поскольку цены на самолеты настолько сильно упадут, что ни одна из них не сможет возместить затрат на разработку самолета.

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

S5. Рассмотрим игру, в которой два игрока, Фред и Барни, по очереди извлекают спички из кучки. Изначально там находится 21 спичка, и Фред ходит первым. На каждом ходе каждый игрок может убрать одну, две, три или четыре спички. Побеждает тот, кто забрал последнюю спичку.

a) Предположим, осталось шесть спичек и пришла очередь Барни ходить. Какой ход он должен сделать, чтобы обеспечить себе победу? Объясните логику своих рассуждений.

b) Допустим, осталось 12 спичек и настала очередь Барни ходить. Какой ход он должен сделать, чтобы обеспечить себе победу? (Совет: используйте свой ответ в пункте a и примените метод обратных рассуждений.)

c) Теперь начните с исходной точки игры. Если оба игрока выберут оптимальный способ ее ведения, то кто из них победит?

d) Какие оптимальные стратегии (исчерпывающие планы действий) есть в распоряжении каждого игрока?

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

a) Нарисуйте дерево этой игры, начиная с пяти спичек.

b) Найдите для нее равновесие обратных рассуждений, начиная с пяти спичек.

c) Можно ли сказать, что в этой игре с пятью спичками существует преимущество первого или второго хода?

d) Объясните, почему вы нашли более одного равновесия обратных рассуждений. Как ваш ответ связан с оптимальными стратегиями, которые вы определили в пункте с предыдущего упражнения?

S7. Элрой и Джуди играют в игру, которую Элрой называет «гонка до 100». Элрой ходит первым, и игроки по очереди выбирают числа от одного до девяти, на каждом ходе прибавляя новое число к промежуточной сумме. Победителем становится тот, кто увеличит промежуточную сумму ровно до 100.

a) Если оба игрока ведут игру оптимальным способом, то кто из них вы­играет? Есть ли преимущество первого хода в этой игре? Объясните логику своих рассуждений.

b) Каковы оптимальные стратегии (исчерпывающие планы действий) для каждого игрока?

S8. В римском Колизее только что бросили раба на съедение львам. Три льва посажены на цепь в ряд, причем льву 1 до раба ближе всего. Длина цепи каждого льва такова, что он может дотянуться лишь до двух находящихся рядом с ним игроков.

Игра проходит следующим образом. Сначала лев 1 решает, съесть ли ему раба. Если он съедает, тогда лев 2 решает, съесть ли ему льва 1 (который стал слишком тяжелым, чтобы защищаться). Если лев 1 не съедает раба, тогда у льва 2 не остается выбора: бесполезно пытаться съесть льва 1, поскольку в драке погибнут они оба. Точно так же, если лев 2 съедает льва 1, то лев 3 решает, съесть ли ему льва 2.

Предпочтения каждого льва вполне естественны: лучший исход игры (4) — кого-то съесть и остаться в живых; следующий приемлемый исход (3) — выжить, но остаться голодным; следующий исход (2) — съесть кого-то и быть съеденным; худший исход (1) — остаться голодным и быть съеденным.

a) Нарисуйте дерево этой игры с выигрышами для трех участников.

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

c) Есть ли в этой игре преимущество первого хода? Объясните, почему есть или почему нет.

d) Сколько полных стратегий у каждого льва? Перечислите их.

S9. Три крупных универмага (Big Giant, Titan и Frieda’s) планируют открыть филиал в одном из двух новых торговых центров в районе Бостона. Торговый центр Urban Mall не очень большой и может вместить максимум два универмага в качестве «якорей», но зато он расположен рядом с крупным богатым населенным пунктом. Торговый центр Rural Mall находится дальше, в сельской сравнительно бедной местности и может вместить три якорных магазина. Ни один из трех универмагов не хочет открывать филиалы в обоих торговых центрах, потому что их сегменты покупателей частично пересекаются, а значит, размещение филиалов в обоих торговых центрах будет означать конкуренцию с самим собой. Каждый универмаг склонен работать в торговом центре вместе с одним или несколькими универмагами, а не в одиночку, поскольку такой торговый центр привлекает намного больше покупателей, что увеличивает прибыль каждого магазина. Кроме того, каждый универмаг предпочитает Urban Mall из-за более богатого контингента покупателей. Каждый универмаг должен выбрать между попыткой получить торговую площадь в Urban Mall (зная, что в случае неудачи можно попробовать побороться за место в Rural Mall) и ее получением в Rural Mall сразу же (даже не пробуя попасть в Urban Mall).

В данном случае универмаги так ранжируют пять возможных исходов этой игры: 5 (лучший исход) — в торговом центре Urban Mall вместе с другим универмагом; 4 — в торговом центре Rural Mall вместе с еще одним или двумя универмагами; 3 — один в Urban Mall; 2 — один в Rural Mall; 1 (худший исход) — один в Rural Mall после неудачной борьбы за место в Urban Mall, тогда как другие магазины уже получили лучшие якорные места в Urban Mall.

Поскольку в этих трех магазинах различные системы управления, они с разной скоростью готовят необходимые документы для получения торговой площади в новом торговом центре. В Frieda’s с этим справляются быстрее всех, затем следует Big Giant и наконец Titan, в котором процесс подготовки плана размещения филиала наименее эффективен. После подачи ими заявок на предоставление торговой площади торговый центр решает, какие универмаги выбрать. Учитывая узнаваемость названий Big Giant и Titan среди потенциальных покупателей, торговый центр выберет либо одного из них, либо обоих, прежде чем рассматривать запрос Frieda’s. Следовательно, Frieda’s не получит одну из торговых площадей в Urban Mall, если все три универмага подадут на них заявки; так будет даже в случае, если Frieda’s первым сделает свой ход.

a) Нарисуйте дерево этой игры с размещением универмагов в торговом центре.

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

S10 (дополнительное упражнение). Рассмотрим следующую ультимативную игру с переговорами, которая изучалась в ходе лабораторных экспериментов. Игрок, делающий предложение, ходит первым и предлагает разделить сумму в 10 долларов между собой и вторым игроком. Принцип дележа может быть любым. Например, игрок может оставить себе все 10 долларов, или взять себе 9 долларов и отдать 1 доллар оппоненту, или 8 долларов себе и 2 доллара другому игроку и т. д. (Обратите внимание, что в этом случае у предлагающего игрока одиннадцать возможных вариантов выбора.) Второй игрок, получив предложение о разделении общей суммы, может либо принять, либо отвергнуть его. Если он его примет, оба игрока получат предложенную сумму. Если отвергнет, оба не получат ничего.

a) Постройте дерево этой игры.

b) Сколько полных стратегий находится в распоряжении каждого игрока?

c) В чем состоит равновесие обратных рассуждений в этой игре при условии, что игроков интересует исключительно денежный выигрыш?

d) Предположим, второй игрок, Рейчел, примет любое предложение в 3 (или больше) доллара и отклонит любое предложение в 2 (или меньше) доллара. Допустим, предлагающий игрок, Пит, знает о стратегии Рейчел и хочет получить максимальный денежный выигрыш. Какую стратегию он применит?

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

f) В ходе лабораторных экспериментов игроки, как правило, не придерживаются равновесия обратных рассуждений. Игроки, делающие предложение, обычно предлагают соперникам сумму от 2 до 5 долларов. А те часто отклоняют предложения 3, 2 и особенно 1 доллар. Объясните, почему, по вашему мнению, происходит именно так.

Упражнения без решений

U1. «В игре с последовательными ходами игрок, делающий ход первым, непременно выиграет». Это утверждение истинно или ложно? Обоснуйте свой ответ посредством нескольких кратких предложений и приведите пример, иллюстрирующий его.

U2. Сколько стратегий (исчерпывающих планов действий) в каждой из представленных ниже игр имеется в распоряжении каждого игрока? Перечислите все чистые стратегии каждого игрока.

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

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

Исход	Конгресс	Президент
А становится законом	4	1
Б становится законом	1	4
А и Б становятся законами	3	3
Ни одно предложение не становится законом (сохраняется статус-кво)	2	2

a) Ходы в этой игре выполняются по следующей схеме. Сначала Конгресс решает, принимать ли законопроект и должен ли он включать в себя предложение А, или Б, или оба. Затем президент решает, подписать ли законопроект или наложить на него вето. У Конгресса нет достаточного количества голосов для преодоления вето. Нарисуйте дерево этой игры и найдите равновесие обратных рассуждений.

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

c) Объясните на интуитивном уровне, в чем разница между этими двумя равновесиями.

U5. Два игрока, Эми и Бет, играют в игру, в которой разыгрывается банка с сотней монет номиналом 1 цент. Игроки делают ходы по очереди; Эми ходит первой. Каждый раз, когда наступает очередь одной из участниц ходить, она берет из банки от 1 до 10 центов. Побеждает тот, после чьего хода банка опустеет.

a) Если игроки ведут игру оптимальным способом, то кто из них выиграет? Есть ли в этой игре преимущество первого хода? Объясните логику своих рассуждений.

b) Какие оптимальные стратегии (исчерпывающие планы действий) имеются в распоряжении каждого игрока?

U6. Рассмотрим несколько измененный вариант игры, представленной в упражнении U5. Теперь игрок, опустошивший банку, проигрывает.

a) Присутствует ли преимущество первого хода в этой игре?

b) Какие оптимальные стратегии есть в распоряжении каждого игрока?

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

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

b) Какие оптимальные стратегии есть в распоряжении каждого игрока? (Совет: сначала проанализируйте исходную ситуацию, в которой в обеих банках одинаковое количество монет, затем когда их количество от 1 до 10 центов и наконец когда число монет свыше 10 центов.)

U8. Измените таким образом, чтобы в нем было четыре льва.

a) Постройте дерево игры с выигрышами для этих четырех участников.

b) Какое равновесие обратных рассуждений имеет в ней место? Обязательно опишите стратегии, а не только выигрыши.

c) Дополнительный лев — это хорошо или плохо для раба? Обоснуйте свой ответ.

U9. Для того чтобы предоставить маме один день отдыха, отец планирует устроить своим детям, Барту и Кэсси, воскресную экскурсию. Барт предпочитает поход в парк развлечений (Р), а Кэсси — в музей науки (Н). Каждый ребенок получит 3 единицы полезности за более предпочтительное занятие и только 2 единицы — за менее предпочтительное. Отец — 2 единицы полезности за любое из занятий.

Чтобы определиться с планами на воскресенье, отец намерен сначала спросить Барта о его предпочтениях, а затем Кэсси, после того как она узнает, что выбрал Барт. Каждый ребенок может выбрать либо парк развлечений (Р), либо музей науки (Н). Если оба остановятся на одном и том же, то именно туда все и пойдут. Если возникнут разногласия, тогда отец примет окончательное решение. У него как у отца есть дополнительный вариант действий: он может предложить парк развлечений, музей науки или поход в горы, причем за поход получит 3 единицы полезности, а Барт и Кэсси по 1.

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

a) Постройте дерево с выигрышами для этой игры с тремя участниками.

b) Какое равновесие обратных рассуждений имеет в ней место? Обязательно опишите стратегии, а не только выигрыши.

c) Сколько разных полных стратегий находится в распоряжении Барта? Обоснуйте свой ответ.

d) Сколько разных полных стратегий у Кэсси? Обоснуйте ответ.

U10 (дополнительное, более трудное упражнение). Рассмотрим дерево игры Survivor, представленное на . Мы могли не угадать точные значения, которые Рик присвоил вероятностям различных исходов, поэтому давайте обобщим это дерево, проанализировав другие возможные значения. В частности, предположим, что вероятность победы в испытании на получение иммунитета в случае, если Рик выберет вариант «продолжить», составляет x для Рика, y для Келли и 1 – x – y для Руди; точно так же вероятность победы в случае отказа Рика от дальнейшей борьбы равна z для Келли и 1 – z для Руди. Далее допустим, что шанс Рика на то, что его выберет жюри, составляет p, если он выиграет испытание на получение иммунитета и проголосует за изгнание Руди с острова, и q, если Келли выиграет испытание и проголосует за изгнание Руди с острова. Предположим также, что, если Руди выиграет испытание на получение иммунитета, он поддержит Рика с вероятностью 1 и станет победителем в игре с вероятностью 1, если войдет в число двух финалистов. Обратите внимание, что в примере, отображенном на , были такие значения: x = 0,45, y = 0,5, z = 0,9, р = 0,4 и q = 0,6. (В общем случае переменные p и q необязательно должны в сумме составлять 1, хотя именно так получилось на .)

a) Найдите алгебраическую формулу, выраженную через x, y, z, p, q, для определения вероятности того, что Рик выиграет миллион долларов, если выберет вариант «продолжить». (Обратите внимание: формула может включать в себя не все переменные.)

b) Найдите аналогичную алгебраическую формулу для определения вероятности того, что Рик выиграет миллион долларов, если выберет вариант «прекратить». (Опять же, формула может не включать в себя все переменные.)

c) Используйте эти результаты для поиска алгебраического неравенства, указывающего, при каких обстоятельствах Рику следует выбрать вариант «прекратить».

d) Предположим, значения всех переменных те же, что и на , кроме z. Насколько высоким или низким может быть значение z, чтобы Рик по-прежнему предпочел вариант «прекратить»? Объясните на интуитивном уровне, почему при некоторых значениях z Рику лучше выбрать вариант «продолжить».

e) Допустим, значения всех переменных те же, что и на , за исключением p и q. Предположим также, что, поскольку жюри с большей вероятностью выберет того, кто не станет голосовать против Руди, значения p и q должны удовлетворять условию p > 0,5 > q. При каких значениях коэффициента p/q Рику следует выбрать вариант «прекратить»? Объясните на интуитивном уровне, почему при некоторых значениях p и q для Рика предпочтительнее вариант «продолжить».

Отправить