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

Рассмотрим три случая, когда игроку А можно гарантировать выигрыш. Четно-нечетный случай, когда выигрывает В, оставим в качестве упражнения.

Цель игрока А - управлять игрой так, чтобы вынудить В оставлять нечетное число нечетно-нечетных областей после каждого хода. Так как 1 - наименьшее нечетное число, А всегда будет иметь хотя бы одну незанятую клетку, доступную на каждом ходе, т. е. у игрока А всегда будет ход.

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

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

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

Чтобы доказать, что А выиграет, мы должны показать, что В всегда оставляет нечетное число нечетно-нечетных областей. Мы уже убедились, что любой первоначальный ход А оставляет четное число (возможно, 0) нечетно-нечетных областей. Путем исчерпывающего рассмотрения возможностей игрока В можно доказать, что В должен изменить четность числа нечетно-нечетных областей и что А может опять изменить четность. При своем ходе В встретится с четным числом нечетно-нечетных областей и с произвольным числом нечетно-четных областей. Если В делает следующий ход в нечетно-нечетной области, то он уничтожит область совсем (если нечетный размер 1), превратит ее в нечетно-четную область (если В сделал ход у одной из границ области) или превратит ее в две нечетно-нечетные области (если В сделал ход внутри области). Если В делает ход в нечетно-четнОй области, В

должен создать нечетно-нечетную область (если В сделал ход у одной из границ области) или одну нечетно-нечетную область и одну нечетно-четную область (если В сделал ход внутри области). В любом случае В должен изменить четность числа нечетно-нечетных областей. Относительно стратегии игрока А можно заметить, что А всегда может оставить игрока В с четным числом нечетно-нечетных областей.

Формулировка этого алгоритма (в дальнейшем называемого EXNIM) и его машинная реализация оставлены в качестве упражнений. Сложность алгоритма сильно зависит от методов его реализации. Основная проблема, разумеется, состоит в том, чтобы обеспечить процедуру, быстро идентифицируюш,ую нечетно-нечетные области и обновляющую поле.

Тройная дуэль

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

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

Если С стреляет первым, у него нет лучшего выбора, чем убить Б. В самом деле, если он убьет Д, то Б (с вероятностью 0,8) получит право следующего выстрела и должен целиться в С (так как Д уже убит). Ясно, что С предпочтет, чтобы стрелял Д.

Аналогично, если Б стреляет первым, он попытается убить С. Если он этого не сделает, то С наверняка убьет его при первой возможности, ведь С - снайпер.

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

®

СуШетР,

iTAPT

С убикш 1

С перВыи

Д пронажСаеглся л

1 БубибаетС Д лромалцбается С убибает Б Д промахиБпется

Д промахаВаешся Б промахи-Ерется i

♦Бубибоеш Д©

Д убибает Б

БубиВает Д (2) Д убибает Б

\ С убцВает Б Д протхиВается

Д убц аегп С

Рис. 6.1.6. Дерево вероятностей для тройной дуэли.

Мы моделируем ход дуэли деревом, которое первоначально имеет только две ветви, так как Д на самом деле не вступает в дело, пока не убит С или Б. В этом случае дерево остается двоичным и довольно маленьким.

Каждая вершина дерева означает событие (например, Д убивает Б), а ребра имеют веса, равные вероятностям событий на их концах (в вершинах, наиболее далеких от корня СТАРТ), при условии, что произошло событие, расположенное в начале ребра (вершина, ближайшая к корню). Дерево дуэли приведено на рис. 6.1.6.

Пунктирная ветвь в верхней правой части рис. 6.1.6 означает бесконечное повторение основной последовательности, в которой Б к Д продолжают стрелять друг в друга (и, возможно, промахиваются до бесконечности).

Теперь мы вычислим различные вероятности выживания. Первым рассмотрим С. Существуют два пути в дереве, означающие победу С, они отмечены символами * и Так как эти два пути представляют взаимно исключающие события, то их вероятности аддитивны. Рассмотрим событие *. По определению условной вероятности получим (см. определение в разд. 2.4):

Р (к) = Р(С первый) X Р{С убьег Б \ С первый) X Р(Д промах-