там схема даст нам возможность определить некоторые важные свойства игры Г.

Докажем прежде всего, не вдаваясь в дальнейшие подробности, что игра Г вполне определена. Доказательство проведем полной индукцией по длине игры v (см. п. 15.1.2). Оно будет состоять в доказательстве двух утверждений:

(15:С:а) Это справедливо для игр минимальной длины, т. е. для случая v = 0.

(15:С:Ь) Из того, что это справедливо для игр длины v - 1 при некотором v =1, . . ., 2, . . ., следует его справедливость для игр длины V.

Доказательство (15:С:а). Если длина игры Г равна нулю, то игра не содержит ни одного хода и состоит в выплате игрокам 1 и 2 некоторых фиксированных сумм w и -w г). Следовательно, р4 = 32 =.1> Xi = х2 =1, Ж (ti, т2) =w2), и, таким образом,

Vi = v2 = w;

т. е. игра Г вполне определена, и v == w 3).

Доказательство (15:С:Ь). Пусть Г имеет длину v. Тогда каждая из игр Га1 имеет длину v - 1. Следовательно, по предположенному игры Га1 вполне определены. Поэтому vai/i = vai/2. Теперь формула (15:8) из п. 15.5.3 показывает 4), что v4 = v2. Следовательно, игра Г также вполне! определена, и доказательство завершено.

15.6.2. Перейдем теперь к более подробному и явному выводу равенства v4 = v2 = v для игры Г. Для этого нам не понадобится даже результат п. 15.6.1.

Составим, как мы это делали в конце п. 15.3.2, последовательность игр

(15:9) Г, Г, Га1)(72, Гаь о2, стз> Vb... <jv 5)

длины которых соответственно равны

v, V - 1, V -2, . .., 0. Обозначим величины v4 и v2 для этих игр через

Vfe, vai/fe, vai, (j2/fe, vais аг,.. ., crv/k

Для проведения индуктивного перехода, описанного в конце п. 15.3.2, применим формулу (15:8), заменив при любом к =1, . . ., v выражения ai, Г, Г01 из п. 15.5.3 на а , Гаь .... ок ±, TGl.....<Vi V Тогда

kt из п. 15.5.3 относится к первому ходу в Гаь а 4, т. е. к ходу оМу игры Г. Поэтому его удобно обозначить через кн(ои . . ., 0Х 4) (см. п. 7.2.1). Следовательно, заменяя М*\ из п. 15.5.3, сконструируем

х) См. игру из замечания на странице 102 или Г - - из п. 15.3.1. В тер-

минах разбиений и множеств (10:l:f), (10:ljg) из п. 10.1.1 показывают, что при v=0 множество Q содержит только один элемент я. Таким образом, w = Si (я), -w = 2 (я) играют указанную выше роль.

2) То есть каждый игрок имеет по одной стратегии, состоящей в том, чтобы ничего не делать.

3) Это, разумеется, очевидно. Существенным шагом является (15:С:Ь).

4) См. замечание в конце п. 15.5.3. Формула при любых значениях к± одна и та же для к = 1, 2.

5) См. сноску 3 на странице 144.

операцию MG На этом пути мы получим

(15:10) v0lf..., o/k = А*£*(<ТЬ Ч*...., crx/fc Для Л = 1, 2.

Рассмотрим теперь последний член последовательности (15:9), игру Гаь...,суу- Она подпадает под рассмотрение (15:С:а) из п 15.5.1; эта игра вовсе не содержит ходов. Обозначим единственную возможную в ней партию через л = я (о1? . . ., crv) х). Следовательно w в ней фиксировано 2) и равно 3Fi (я (аь . . ., crv))- Таким образом, мы получаем

(15:11) vaif...>av/i = v(yif...f(yv/2 = ri(Ji(alf av)).

Применим теперь (15:10) при x = v к (15:11; и далее последовательно к к = у- 1, 2, 1. Таким способом мы получим

(15:12) Vl = v3 = v = M(ai) ... Jlf£(ei ffv-l)jF1(n(<rJ, <rv)).

Это еще раз доказывает, что игра Г вполне определена и дает в то же время явное выражение для значения игры.

15.7. Применение к шахматам

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

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

В связи с этим стоит рассмотреть более подробно игру в шахматы.

Исходы игры в шахматы, т. е. множество значений функций из п. 6.2.2 или п. 9.2.4, ограничиваются тремя числами 1, 0, -1 4). Таким образом, функции &ь из п. 11.2.2 принимают те же значения, и, поскольку случайные ходы отсутствуют, то же самое верно и для функций Жъ. из п. 11.2.3 5). Далее мы будем пользоваться функцией Ж = Ж± из

г) См. замечания по поводу Г- - в п. 15.3.1.

cTi.....аг

2) См. (15.С:а) из п. 15.6.1, в частности, сноску 1 на стр. 150.

3) В основном это связано с тем, что v чудовищно велико. По поводу шахмат см. соответствующую часть замечания 1 на стр. 85. Фигурирующее там v* совпадает с нашим v; см. конец п. 7.2.3.

4) Это наиболее простой способ интерпретации понятий выигрыш , ничья , проигрыш .

5) Каждое значение Sft является также значением cFk, каждое значение при отсутствии случайных ходов является значением При наличии случайных ходов значением Жк была бы вероятность выигрыша минус вероятность проигрыша , т. е. некоторое число, лежащее между 1 и -1.

п. 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.