назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [ 208 ] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]


208

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

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

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

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

§ 2. КОМБИНАТОРНЫЕ ИГРЫ

1. По-видимому, первое появление комбинаторной игры в облике математической задачи относится к началу XVII века. В известном «Сборнике математических развлечений» Баше де Мезирака, вышедшем в свег в 1612 г. [1], помещена задача следующего содержания: двое называют поочередно числа от единицы до десяти и выигрывает тот, кто первый доведет до ста сумму чисел, названных обоими игроками.

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

Очевидно, эту игру можно интерпретировать как процесс поочередного взятия игроками от одного до 10 предметов из кучи, насчитывающей первоначально 100 предметов.

Более сложной является игра «фан-тан», по-видимому, китайского* происхождения. В этой игре игроки имеют дело с тремя кучами предметов; они выбирают на каждом ходе любое число предметов из произвольной кучи. Выигрывает игрок, забирающий последние предметы. Полная теория этой игры была опубликована в 1902 г. Баутоном [1].

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



произвольное число предметов. Игрок, берущий последние предметы, выигрывает. Анализ этой игры дал Мур в 1909 г. [1].

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

В частности, в игре Баше де Мезирака таким классом выигрывающих позиций оказались те, при которых сумма всех названных игроком чисел имеет вид 100 - 11а.

Изложенная идея двоякой устойчивости оказалась весьма плодотворной в теории игр. Мы будем к ней неоднократно возвращаться.

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

На этот путь встал Э. Цермело. В 1912 г. на Пятом международном конгрессе математиков он выступил с докладом: «О применении теории множеств к теории шахматной игры» [1], в котором изложил следующий подход к комбинаторным играм.

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

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

Пусть некоторый эндшпиль q = (g, g4, g2, . . .) принадлежит Ur (g), qK - некоторая встречающаяся в q позиция с очередью хода черных и черные ходят из позиции q% в позицию g+i- Рассмотрим другую позицию, gi+ь в которую черные, в соответствии с правилами игры, также могли бы пойти из да,. Тогда среди эндшпилей из Ur (g) найдется такой эндшпиль q, который начинается с позиций д, д4, . . ., дь qi+i. Возможность форсированного выигрыша белыми за г ходов из позиции g означает при этом Ur (g) Ф 0.

Если общее число всех возможных позиций в игре равно t, то из возможности форсированного выигрыша белыми из позиции g за конечное число ходов вытекает аналогичная возможность не более чем за t ходов. Таким образом, выигрышность позиции g для белых равносильна U (д) = = Ut (д) ф 0.

Сходным образом определяется множество V (g) zd U (д) начинающихся из д эндшпилей, в которых белые форсируют ничью. Ничья для белых достижима, если V (д) Ф 0. Если же V (д) = 0, то в позиции д выигрыш форсируют черные.



Таким образом, Цермело установил, что в каждой позиции q имеег место одна из трех возможностей: либо белые обеспечивают себе выигрыш (это будет, если U (q) Ф 0), либо они обеспечивают себе ничью, ноне выигрыш (т. е. и черные обеспечивают себе ничью, но не выигрыш; это будет, если U (q) = 0, но V (q) Ф 0), либо выигрыш обеспечен черным (это будет, если V (д) = 0). Этот же вопрос можно поставить и применительно к начальной позиции. Цермело замечает по этому поводу, что ответ на этот вопрос полиостью лишил бы шахматы характера игры.

3. В 1925 г. Штейнгауз опубликовал статью «Определения теории игр и преследования» [1], которая долгие годы оставалась известной лишь весьма узкому кругу лиц, пока не была переиздана в 1960 г. в английском переводе. В этой статье Штейнгауз вводит (для определенности - применительно к тем же шахматам) понятие «способа игры» как «списка всех возможных обстоятельств с предпочитаемым ходом для каждого из них». За наилучшую стратегию признается та, в которой максимальное число ходов, какое может продержаться противник, минимизируется. В сущности, в этих определениях уже содержатся идеи стратегии и принципа максимина.

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

4. В рассуждениях Цермело переход от форсирования выигрыша за конечное число шагов к форсированию выигрыша за ограниченное число шагов не был должным образом обоснован. В 1927 г. Д. Кёниг [1] произвел точное доказательство этого утверждения на основе одной своей теоремы из теории бесконечных графов. На возможность применения этой теоремы к играм ему указал Дж. фон Нейман. По-видимому, именно в этой статье Кёнига имя фон Неймана впервые упоминается в печати в связи с играми. Впрочем, интерес к игровым вопросам фон Нейман проявил еще раньше. Подробнее об этом будет сказано в 1.4.1.

Справедливость требует отметить, что Цермело, ознакомившись с работой Кёнига до ее опубликования, предложил собственное, независимое, весьма короткое и изящное недостающее доказательство, которое Кёниг приводит в приложении к своей статье [1]. По свидетельству Кёнига, доказательство, основанное на этой идее, было известно и фон Нейману.

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

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

6. Формализацию рассуждений, касающихся двоякой устойчивости выигрывающих множеств в играх двух лиц позиционного типа с поочередными ходами, осуществил П. Гранди [1, 2].

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

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [ 208 ] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]