Промышленный лизинг Промышленный лизинг  Методички 

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

произвольное число предметов. Игрок, берущий последние предметы, выигрывает. Анализ этой игры дал Мур в 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. Если каждую диаграмму изобразить точкой и соединить направленными дугами каждую из диаграмм со всеми теми диаграммами* в которые из нее можно перейти за один ход, то мы получим ориентиро-



ванный граф. Обозначим его через (Г, X). Фиксируем в окончательных диаграммах этого графа (т. е. в таких диаграммах, из которых ни в какую другую диаграмму перейти уже нельзя) выигрыш того или иного игрока. Пусть каждый игрок (мы ограничиваемся описанием случая, который можно назвать симметричным) выигрывает в диаграммах из множества К при своем ходе и в диаграммах из множества L при ходе противника. Сказанное определяет некоторую игру, которую будем обозначать через

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

Пусть для данной игры (Г, X, К, L) функция Гранди существует. Как показал впоследствии М. Ричардсон [1, 2], для этого достаточно, чтобы в графе (Г, X) при любом х £ X множество Г х и множество всех тех у £ X, для которых х £ Ту, были конечными, а также чтобы этот граф не содержал контуров нечетной длины.

Множество диаграмм, которые являются множеством нулей функции Гранди, обладает свойством двоякой устойчивости.

В самом деле, предположим, что какому-либо игроку (пусть для определенности первому) удается при некотором своем ходе создать диаграмму а, для которой g (а) = 0. Тогда второй игрок выбирает некоторую диаграмму Ъ £ Га. Но, по определению функции Гранди, равное нулю значение g (а) отлично от всех чисел вида g (z) для z £ Га. В частности, должно быть g (Ъ) Ф 0.

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

Пусть теперь первый игрок оказывается в позиции Ъ, для которой g (Ъ) Ф 0. Он выбирает Некоторое с £ ТЪ. Если бы среди диаграмм ТЪ не нашлось такой диаграммы z, что g (z) = 0, то было бы g (Ъ) = 0, чего, однако, нет. Следовательно, существует такое с £ ТЪ, что g (с) = 0.

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

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

1. Фактор случайности является определяющим во всех азартных играх (не лишним будет здесь напомнить, что по-французски hasard значит случай и происходит от арабского слова азар - az-zahr, означающего трудный ; первоначально этот термин употреблялся как характеристика наиболее редких случаев).

(Г, X, К, L).


0, если x£L;

1, если х£К;

наименьшему из натуральных чисел, отличных от чисел вида g(y), где у£Тх.

§ 3. АЗАРТНЫЕ ИГРЫ



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