п. 14.1.1. Поскольку Ж принимает только значения 1, 0, -lt число (15.13) v = max пипрЖ1 (т4, т2) = minmax Ж (т1? т2)
Tl Т2 Т2 Ti
равно однохму из чисел
v = l,Off-1.
Мы предоставляем читателю провести простые рассуждения о том, что (15:13) означает следующее:
(15:D:a) Если v = 1, то игрок (белые) обладает стратегией, при которой он «выигрывает» независимо от действий второго игрока (черных).
(l5:D:b) Если v =*0, то каждый из игроков обладает стратегией, при которой он может гарантировать ничейный исход (или выигрыш) независимо от действий другого игрока.
(l5:D:c) Если v = - 1, то игрок2 (черные) обладает стратегией, при которой он «выигрывает» независимо от действий первого игрока (белых) *).
15.7.2. Мы видим, что если теория шахмат была бы уже полностью известна, то в эту игру было бы неинтересно играть. Эта теория показала бы, какая из трех возможностей (15:D:a), (15:D:b), (15:D:c) в действительности имеет место, и исход партии стал бы известен до начала игры: в случае (15:D:a) им был бы выигрыш белых, в случае (15:D:b) - ничья, и в случае (15:D:c) - выигрыш черных.
Однако наше доказательство, гарантирующее осуществление одного и* только одного из этих трех исходов, не дает практического метода отыскания истинного исхода. Такая относительная трудность делает необходимым использование неполных, эвристических методов игры, которые и составляют «хорошую» игру в шахматы; без этого в шахматах не было бы элементов неожиданности и борьбы.
15.8. Другой подход. Словесные рассуждения
15.8.1. Закончим этот параграф одним более простым и менее формальным подходом к нашему основному результату о том, что игра двух лиц с нулевой суммой с полной информацией всегда вполне определена.
Можно оспаривать доказательность приводимой аргументации; мы предпочитаем сформулировать ее как правдоподобное рассуждение, с помощью которого оказывается возможным приписать значение каждой партии любой игры Г указанного вида, и оставляем возможность ее критики. Мы не считаем необходимым показывать во всех деталях опровержение этой критики, поскольку мы получаем то яе значение для партии игры Г, что и в пп. 15.4-15.6, где было дано вполне строгое доказательство,
*) При наличии случайных ходов Ж (т т2) выражает превышение Берсяткссти «выигрыша» над вероятностью «проигрыша». Игроки стремятся максимизировать или соответственно минимизировать это число, и строгая трихотомия, описанная в (15:D:a) - (15:D:c), вообще говоря, не получается.
Хотя трик-трак является игрой с полной информацией, содержащей случайные ходы, ее нельзя считать удачным примером для иллюстрации описанной выше возможности. Трик-трак играется с целью получения различных выигрышей, а не просто «выигрыша», «ничьей», «проигрыша», т. е. возможные значения функции %Fh не ограничиваются числами 1, 0, -1.
§ 15] игры с полной информацией 453
основанное на четко определенных понятиях. Ценность приводимых правдоподобных рассуждений заключается том, что они легче уясняются и MOfyTf быть повторены применительно к другим играм с полной информацией, выходящим за пределы класса игр двух лиц с нулевой суммой. Мы хотим здесь подчеркнуть, что та же критика приложима и в общем случае и что ее нельзя оставить без опровержения. Действительно, решение в общем случае (даже для игр с полной информацией) будет найдено совсем иным путем. Наши рассуждения прояснят природу различия между случаем игр двух лиц с нулевой суммой и общим случаем. Это будет достаточно важным для обоснования существенно отличающихся друг от друга методов, которые будут применяться в общем случае (см. § 24).
15.8.2. Рассмотрим игру двух лиц с нулевой суммой Г с полной информацией. Воспользуемся обозначениями} п. 15.6.2, указав аЖи с#2, . . ., qMv; оь а2, . . ., crv; ки к2 Ю, . . ., К (ои а2, . . ., а);
вероятности; операторы Mov М02 , . . ., MGv ; последо-
вательность игр (15:9), полученную из Г, и функцию JF± (л (оь . . ., ov)).
Начнем исследование игры Г с последнего хода e#v, после чего пойдем в обратном направлении через ходы c#V-i, <М 2, ... Предположим сначала, что выборы о4, о2, ..., ov i соответственно при ходах <Jiu М2, ...
qMv-i уже сделаны и совершается выбор ov (при ходе ©#v).
Если ход eSv случайный, т. е. если fev(i, о2, av i) = 0, то ov будет принимать значения 1, 2, a>v(ou av 4) соответственно с вероятностями /?v(l), jPv(2), Pv(&v(Gti •v-i))- Поэтому математическое ожидание выигрыша (игрока 1) (л(а1? av b av)) будет равно
av!(ai,..., av-1)
2 Pv (<*v) «Fi (Я ((Ti, . . ., Ov.!, 0V)).
Если o/fiv является личным ходом игрока £1 или 2, т. е. если К(ои 0 = 1 или 2, то игрок будет при выборе 0V максимизировать или минимизировать i{n(ou ..., ov i, av)), т. е. исходом игры будет maxJr1(n(o1, 0v i, cv)) или тт#1(л(01, ov-1, ov)).
Таким образом, во всех случаях математическое ожидание выигрыша (после выборов 04, 0V 4) равно
"(nfr, .... 0V)).
Предположим, далее, что выбраны только 01г ov 2 (при ходах
аМу 2) и предстоит выбрать о (при ходе e#V-i). Поскольку определенный выбор ov-i приводит, как мы уже видели,
к исходу ((Tli (я (a1? av)), который является функцией
только от 04, ov-1 (так как операция MGv связывает пере-
менную av), мы можем поступить так же, как и раньше. Нам нужно только заменить v; a4, ..., av; Мо1<Tv"l)i (л (a4, ..., av)) соответственно на v - 1; alf ..., av-i; (01," " (°b *" °v-4У 4 (л (a4,. .. ov)). Следовательно, ожидаемый выигрыш в игре после выполнения
выборов ai, av 2 равен
<::(0b--av-X(aie.(SK
Аналогично математическое ожидание выигрыша в игре после выборов а1? ..., av 3 равно
<:22(aiMlnf1.....•••••a~)*l(«(ot,crv)).
Наконец, математическое ожидание выигрыша во всей игре -перед тем как она началась - равно
М%М*™ ... Mlnf1"Mlf1av-l)t(n(at, av)).
А это в точности совпадает со значением v из (15:12) в п. 15.6.2 1).
15.8.3. Основным возражением , против процедуры, описанной в п. 15.8.2, является то, что этот подход к «значению» для партии игры Г предполагает наличие «рационального» поведения всех игроков; иными словами, стратегия игрока 1 основана на предположении об оптимальности стратегии игрока 2, и наоборот.
Положим, в частности, kv-i (al7 . . ., crv 2) = 1, kv (a4, . . ., av i) = = 2. Тогда игрок 1 при ходе выбирает av 4 в предположении, что
игрок 2 при ходе oMv выбирает av «рациональным» образом. Единственным оправданием для такого предположения является то, что выбор av 4 приводит к выигрышу min $F ± (я (аи . . ., av)), т. е.
к MaJ(ai av l) (я (а4, . . ., av)) (см. определение в п. 15.8.2).
Во второй части п. 4.2.1 мы пришли к заключению, что гипотезы о «рациональном» поведении противников следует избегать. Аргументация в п. 15.8.2 не удовлетворяет этому требованию.
Однако можно согласиться с тем, что в игре двух лиц с нулевой суммой можно предположить рациональность поведения противника, поскольку ошибки противника никогда не вредят игроку. Действительно, так как речь идет об игре с двумя участниками, и сумма их выигрышей равна нулю, любые потери, которые несет один игрок (в том числе вследствие своей неразумности), необходимо оборачиваются равным по величине выигрышем другого игрока 2). В таком виде этому соображению далеко до полноты, но оно может быть тщательно разработано. Однако для нас нет необходимости проводить здесь строгие рассуждения: мы располагаем доказательством пп. 15.4-15.6, которое для такой критики неуязвимо 3).
г) Представляя себе применение указанной процедуры в какой-либо конкретной игре, следует помнить, что длина игры Г предполагается фиксированной. Если v является в действительности переменной, как это имеет место в большинстве игр (см. замечание 1 на стр. 85), то следует сделать ее постоянной, дополнив игру фиктивными бессодержательными ходами, как это описано в конце п. 7.2.3. Только после этого становится допустимым обратное движение через ходы o#v, gv i, . . <М±. Для практических построений эта процедура, конечно, не лучше, чем описанная в пп. 15.4-15.6.
Возможно, некоторые простые игры типа игры в крестики и нолики могут быть эффективно исследованы таким способом.
2) Это не обязательно так, если игра не является игрой с нулевой суммой или же если она имеет более двух игроков.
3) См. в связи с этим (14:D:a), (14:D:b), (14:C:d), (14:С:е) в п. 14.5.1 и (14:С:а), 14:С:Ь) в п. 14.5.2.