А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
11.1.3. Изменим условия игры: пусть взявший последнюю спичку проигрывает. Кто теперь выигрывает при правильной игре? 11.1.4. Пусть теперь игрокам разрешено брать 1, 2 или 4 спички, а кто не может сделать ход, проигрывает. Кто выигрывает при пра- вильной игре, если вначале было 20 спичек? Решение. Здесь уже не так просто сразу указать выигрышную стра- тегию для первого или второго. Начнём с небольшого числа спичек, изобразив разрешённые ходы в виде стрелок (рис. 11.1 ): Игрок, ока- завшийся в позиции 0, проигрывает (таковы правила), поэтому соот- ветствующий кружок пометим буквой П. Игрок, оказавшийся в пози- циях 1, 2 или 4, выигрывает, поскольку он может забрать все спички и перевести противника по стрелке в позицию 0. Поэтому мы пометим 11.1. Примеры игр 211 0 1 2 3 4 5 6 7 8 9 П В В В П В В П В П Рис. 11.1. Игра со спичками. эти позиции буквой В. Теперь ясно, что позиция 3 является проигрыш- ной: из неё можно пойти только в 1 и 2, и тогда противник (как мы уже знаем) выиграет. Пометим её буквой П. Далее замечаем, что по- зиции 4, 5 и 7 будут выигрышными (поскольку из них можно попасть в проигрышную для противника позицию 3; заметим, что из позиции 4 можно выиграть и быстрее, пойдя в 0). Теперь видно, что позиция 6 проигрышная (все стрелки из неё ведут в выигрышные для противника позиции), 8 | выигрышная, 9 | проигрышная и так далее с периодом 3. Таким образом, если число спичек делится на 3, то позиция про- игрышная, если нет | то выигрышная. Поэтому в игре с 20 спичками первый игрок выигрывает. 11.1.5. Как он для этого должен играть? Решение. Ставить противника в проигрышную позицию, то есть следить, чтобы после его хода число спичек было кратно трём (в част- ности, в начале игры взять 2 спички, чтобы осталось 18). 11.1.6. На столе лежат две кучки спичек: в одной 𝑚, в другой 𝑛. За один ход разрешается взять любое (ненулевое) число спичек, но только из одной кучки (можно взять все спички в ней); кто не может сделать ход, проигрывает. Кто выигрывает при правильной игре? Ответ: при 𝑚 = 𝑛 выигрывает второй, при 𝑚 ̸= 𝑛 | первый. 11.1.7. На шахматной доске стоит ладья, которую игроки по очере- ди двигают, при этом разрешено сдвигать её влево и вниз (оставлять на месте нельзя); кто не может сделать ход, проигрывает. Кто выигры- вает при правильной игре? [Указание. Как эта игра связана с предыдущей?] 11.1.8. (Игра «ним») Имеется 𝑘 кучек из 𝑛 1 , . . . , 𝑛 𝑘 спичек; за один ход можно взять любое (ненулевое) число спичек, но только из одной кучи (можно взять все спички в ней); кто не может сделать ход, про- игрывает. Кто выигрывает при правильной игре? 212 11. Анализ игр Решение. Запишем числа 𝑛 1 , . . . , 𝑛 𝑘 в двоичной системе счисления друг под другом, как если бы мы собирались их складывать. Если в ка- ждом разряде при этом оказалось чётное число единиц, то выигрывает второй, в остальных случаях | первый. В самом деле, если во всех разрядах чётное число единиц, то после уменьшения одного из чисел какой-то из его разрядов изменится и в этом разряде получится не- чётное число единиц. (Это соответствует тому, что из проигрышной позиции любой ход ведёт в выигрышную.) Если же в некоторых («пло- хих») разрядах нечётное число единиц, возьмём старший плохой разряд и то из чисел, которое содержит в этом разряде единицу. Тогда, изме- нив в этом числе все плохие разряды, получим меньшее число, которое поставит противника в проигрышную позицию. (См. правила для вы- игрышных и проигрышных позиций в следующем разделе.) 11.1.9. В ряд лежат 𝑁 ящиков, в каждом из них по монете. За один ход игрок может взять любую монету или любые две монеты из сосед- них ящиков; кто не может сделать ход, проигрывает. Кто выигрывает при правильной игре? Решение. Первый: он должен взять одну или две монеты в центре, а потом симметрично повторять ходы второго. 11.2. Цена игры Анализируя игры в предыдущем разделе, мы использовали следую- щие (очевидные) правила: 1. Если из некоторой позиции 𝑝 можно пойти (по стрелкам) в некото- рую проигрышную (для попавшего в неё игрока) позицию, то позиция 𝑝 является выигрышной (для попавшего в неё). 2. Если из некоторой позиции 𝑝 можно пойти только в выигрышные позиции, то позиция 𝑝 является проигрышной. 11.2.1. Докажите, что если число позиций в игре конечно, нет ци- клов (нельзя вернуться в однажды пройденную позицию) и про все заключительные позиции (где нельзя сделать хода) известно, кто вы- игрывает, то правила 1 и 2 однозначно разбивают все позиции на вы- игрышные и проигрышные. Решение. Будем применять эти правила, пока это возможно. Ясно, что никакая позиция не будет объявлена одновременно выигрышной и проигрышной (для попавшего в неё). Надо лишь доказать, что не останется «сомнительных» позиций (не отнесённых ни к выигрышным, 11.2. Цена игры 213 ни к проигрышным). Заметим, что из каждой сомнительной позиции ведёт стрелка хотя бы в одну сомнительную позицию. (В самом деле, если все стрелки ведут в несомненные позиции, то либо все они вы- игрышные, либо есть хоть одна проигрышная, и можно было бы вос- пользоваться одним из двух правил.) Значит, идя по стрелкам в сомни- тельные позиции, мы рано или поздно получим цикл, что противоречит предположению. 11.2.2. Сформулируйте и докажите аналогичное утверждение для игр, допускающих ничьи. Игры с ничейным исходом являются частными случаями конечных игр с полной информацией и нулевой суммой, рассматриваемых в тео- рии игр. Чтобы задать такую игру, необходимо: 1) указать конечное множество, элементы которого называются по- зициями; 2) для каждой позиции указать, является ли она заключительной (игра закончена) или нет; 3) для каждой заключительной позиции указать результат игры (чи- сло); это число понимается как сумма денег, которую один игрок платит другому; 4) для каждой незаключительной позиции указать, кто из игроков должен делать ход в этой позиции и какие разрешены ходы (в ка- кие позиции этот игрок может перейти); 5) указать начальную позицию игры. При этом требуется, чтобы не было циклов (нельзя было вернуться в уже пройденную позицию после нескольких ходов). Позиции игры удобно рассматривать как вершины графа и изобра- жать точками; возможные ходы при этом становятся рёбрами графа и изображаются стрелками. Игру можно рассматривать как передви- жение фишки, обозначающей текущую позицию игры, по этому графу. В каждой вершине написано, кто должен делать ход (если игра не кон- чилась) или кто и сколько выиграл (если игра кончилась). Одна из вершин указана как начальная позиция. Будем называть игроков Макс и Мин и считать, что результат игры определяет, сколько Мин платит Максу. (Мотивировка: Макс хочет, чтобы это число было максимальным, а Мин | минимальным | а луч- ше всего отрицательным, поскольку тогда он получает деньги!) Кто 214 11. Анализ игр из игроков делает первый ход, определяется начальной позицией. За- метим, что мы теперь не предполагаем, что игроки ходят по очереди: один и тот же игрок может делать несколько ходов подряд. (Тем самым, например, в игре со спичками каждый кружок на ри- сунке 11.1 теперь превращается в две позиции: с ходом Макса и с ходом Мина.) Игра, в которой один из игроков выигрывает, а другой проигрыва- ет, соответствует значениям ±1 в заключительных вершинах (+1 озна- чает выигрыш Макса, −1 означает выигрыш Мина). Игры с ничейными исходами получатся, если приписать число 0 ничейным позициям. Определим теперь понятие стратегии. Стратегия для Макса (или Мина) определяет, как он должен ходить в каждой из позиций (где ход за ним); формально это функция 𝑠, определённая на множестве позиций, где ход за ним. Значениями этой функции являются позиции, при этом ходы должны быть допустимыми, то есть из 𝑝 в 𝑠(𝑝) должна вести стрелка. Стратегии такого типа называют в теории игр позиционными, под- чёркивая, что выбор хода зависит лишь от текущей позиции, но не от истории игры (как мы в эту позицию попали). (Другие страте- гии нам не понадобятся, так что слово «позиционная» мы будем опус- кать.) Если фиксировать стратегии для Макса и Мина, то исход игры пре- допределён: эти стратегии однозначно определяют последовательность позиций («партию») и результат игры. 11.2.3. Докажите, что для любой игры 𝐺 можно найти число 𝑐 и стратегии 𝑀 и 𝑚 для Макса и Мина, при которых: (1) Макс, пользуясь стратегией 𝑀, гарантирует себе выигрыш не менее 𝑐, как бы ни играл Мин; (2) Мин, пользуясь стратегией 𝑚, гарантирует себе проигрыш не более 𝑐, как бы ни играл Макс. Число 𝑐 называют ценой игры 𝐺. Заметим, что цена игры опре- деляется однозначно: из условий (1) и (2) следует, что у Макса нет стратегии, гарантирующей ему выигрыш больше 𝑐 (поскольку она не может это сделать против стратегии 𝑚), а у Мина нет стратегии, га- рантирующей ему проигрыш меньше 𝑐. Для игр с двумя исходами утверждение задачи (называемое тео- ремой Цермело) означает, что ровно у одного из игроков имеется вы- игрышная стратегия. Если разрешить и ничьи, то либо у одного из игроков есть выигрышная стратегия, либо у обоих есть стратегия, га- рантирующая ничью. 11.2. Цена игры 215 Решение. Пусть 𝑝 | произвольная позиция игры 𝐺. Рассмотрим игру 𝐺 𝑝 , которая отличается от 𝐺 лишь начальной позицией, и эта на- чальная позиция есть 𝑝. (Если 𝑝 | заключительная вершина, то игра 𝐺 𝑝 тривиальна: игра кончается, не начавшись, и игрокам сообщается ре- зультат игры.) Как мы сейчас увидим, цену игры 𝐺 𝑝 (как функцию от 𝑝) можно определить рекурсивно, начиная с заключительных пози- ций. Более точно, рассмотрим следующее рекурсивное определение неко- торой функции 𝑐, определённой на вершинах графа: ∙ 𝑐(𝑝) равно выигрышу Макса (=проигрышу Мина) в позиции 𝑝, если позиция 𝑝 является заключительной; ∙ 𝑐(𝑝) = max{𝑐(𝑝 ′ )}, если в вершине 𝑝 ходит Макс; максимум берёт- ся по всем вершинам 𝑝 ′ , в которые Макс может пойти из 𝑝 по правилам игры; ∙ 𝑐(𝑝) = min{𝑐(𝑝 ′ )}, если в вершине 𝑝 ходит Мин; минимум берётся по всем вершинам 𝑝 ′ , в которые Мин может пойти из 𝑝 по прави- лам игры. Лемма. Это определение корректно: существует и единственна функция 𝑐 (аргументы | вершины графа, значения | числа), удовле- творяющая указанным требованиям. Доказательство леммы. Назовём рангом вершины максимальное чи- сло ходов, которое можно сделать из этой вершины. Поскольку по пред- положению в игре нет циклов, то ранг любой вершины не больше числа вершин. Докажем индукцией по 𝑘, что существует и единственна функ- ция 𝑐, определённая на вершинах ранга не больше 𝑘 и удовлетворяющая рекурсивному определению. Для 𝑘 = 0 это очевидно. Шаг индукции ис- пользует такое (очевидное) замечание: если из вершины 𝑝 можно сде- лать ход в вершину 𝑝 ′ , то ранг вершины 𝑝 ′ меньше ранга вершины 𝑝. Поэтому рекурсивное определение однозначно задаёт значения на вер- шинах ранга 𝑘, если известны значения на вершинах меньших рангов. Лемма доказана. Осталось доказать, что значение 𝑐(𝑝) является ценой игры 𝐺 𝑝 . Рас- смотрим следующую (позиционную) стратегию для Макса: из верши- ны 𝑝 ходить в ту вершину 𝑝 ′ , для которой значение 𝑐(𝑝 ′ ) максимально (и равно 𝑐(𝑝)). Если Макс следует этой стратегии, то независимо от ходов Мина значение 𝑐(𝑞) для текущей вершины 𝑞 не убывает в ходе игры (при ходах Мина оно убывать вообще не может, при ходах Мак- са оно не убывает по построению стратегии). Тем самым в вершине 𝑝 216 11. Анализ игр Максу гарантирован выигрыш не меньше 𝑐(𝑝). Аналогичным образом, если Мин ходит в ту вершину 𝑝 ′ , где достигается минимум 𝑐(𝑝 ′ ) (рав- ный 𝑐(𝑝)), то значение 𝑐(𝑞) не возрастает в ходе игры и потому Мин проигрывает не более 𝑐(𝑝). Теорема Цермело доказана. 11.2.4. Игра в крестики-нолики состоит в следующем: на большом квадратном поле два игрока по очереди ставят крестики и нолики в ещё не занятые клетки (начинают крестики). Выигрывает тот, кто первым поставит пять своих знаков подряд (по вертикали, горизонтали или диагонали). Если всё поле заполнено, а такого не случилось, партия считается ничейной. Докажите, что у крестиков есть стратегия, га- рантирующая им ничью или выигрыш. Решение. Согласно теореме Цермело, в противном случае у ноликов есть стратегия, гарантирующая им выигрыш. Покажем, что крести- ки могут использовать по существу ту же стратегию, забыв о своём первом ходе. А именно, представим себе, что крестики делают про- извольный первый ход (карандашом), а затем отвечают (чернилами) на ходы ноликов по выигрышной стратегии для ноликов (считая ходы ноликов крестиками и забыв о своём первом ходе). Может ли при этом первый ход помешать? Может, если стратегия указывает как раз на ту клетку, где уже стоит карандашный крестик. В этом случае надо карандашный крестик обвести чернилами, а каран- дашом сделать ход в любую свободную клетку. Если свободных клеток нет, то позиция соответствует (с точностью до замены крестиков на нолики) заключительной позиции в выигрышной партии для ноликов, и потому является выигрышной. Кроме того, игра может кончиться раньше времени, если карандаш- ный крестик образует выигрышный ряд с чернильными | но это нам только лучше. Таким образом, мы доказали, что если у ноликов есть выигрыш- ная стратегия, то и у крестиков есть выигрышная стратегия | и если дать этим стратегиям играть друг против друга, получится противо- речие. 11.2.5. Докажите, что цена любой игры равна выигрышу в одной из заключительных вершин. 11.2.6. Покажите, что теорема Цермело вытекает из своего част- ного случая игр с двумя исходами (выигрыш первого и второго). [Указание. Для каждого Ó будем считать выигрыш меньше 𝑐 про- игрышем, а больше 𝑐 | выигрышем.] 11.2. Цена игры 217 11.2.7. Пусть дана некоторая игра 𝐺. Выберем одну из заключи- тельных вершин и будем менять выигрыш в этой вершине: положив его равным 𝑐, получим игру 𝐺[𝑐]. Рассмотрим цену этой игры как функцию от 𝑐. Что это может быть за функция? Ответ. Цена игры 𝐺[𝑐] равна ближайшей к 𝑐 точке некоторого от- резка [𝑎, 𝑏] (зависящего от игры 𝐺). Вот ещё один пример игры, где теорема Цермело позволяет до- казать существование выигрышной стратегии для первого игрока. Эта игра названа в книгах М. Гарднера («Математические досуги», М.: Мир, 1972; «Математические головоломки и развлечения», М.: Мир, 1971) игрой Гейла или «бридж-ит». Рассмотрим прямоугольную сеть из пунктирных линий высоты 𝑛 и ширины 𝑛 + 1 (рис. 11.2 ); вершины Рис. 11.2. Игра Гейла. сети соединены пунктирными отрезками длины 1. Первый игрок ка- ждым своим ходом обводит (сплошной линией) один из отрезков. Его задача | соединить сплошными линиями левую и правую стороны пря- моугольника. Задача второго игрока | ему помешать; каждым своим ходом он стирает один из отрезков (лишая первого возможности впо- следствии его обвести). Игра заканчивается, когда все отрезки обведе- ны или стёрты; первый выиграл, если при этом левая и правая стороны прямоугольника соединены. 11.2.8. Используя теорему Цермело, докажите, что первый игрок имеет выигрышную стратегию. [Указание. Игру можно представить в более симметричном виде, ес- ли добавить сетку для второго игрока (рис. 11.3 ) и считать, что второй хочет соединить верхнюю и нижнюю стороны своей сетки, а линиям первого и второго игроков запрещено пересекаться (тем самым прове- дя свою линию, второй игрок как бы стирает пересекающую её линию 218 11. Анализ игр первого). Если игра закончилась (в каждой возможной точке пересече- ния проведена вертикальная или горизонтальная линия), то ровно один из игроков выиграл: можно пройти по линиям или слева направо, или сверху вниз, но не одновременно. Аккуратное доказательство этого ин- туитивно ясного топологического факта, впрочем, не так просто.] Рис. 11.3. Игра Гейла, симметричный вариант. Как пишет Гарднер, Клод Шеннон (создатель теории информации) придумал для этой игры любопытную «физическую» стратегию, кото- рая легко обобщается на любую сеть линий. Представим себе, что все стороны всех клеток сети (для первого игрока) представляют собой резисторы одинакового сопротивления, кроме левой и правой сторон прямоугольника, которые сделаны из провода нулевого сопротивления. Первый игрок своим ходом закорачивает эти сопротивления, а второй игрок разрывает их (делает бесконечными). Стратегия первого игрока состоит в том, что надо подключить напряжение между левой и правой сторонами прямоугольника, и закорачивать (обводить) то сопротивле- ние, через которое идёт максимальный ток (или, что то же самое, на котором падает наибольшая разность потенциалов). Если таких сопро- тивлений оказалось несколько, можно закорачивать любое из них. Из книг Гарднера не ясно, является ли эта стратегия выигрыш- ной. Зато там приведена явная выигрышная стратегия (со ссылкой на О. Гросса). Чтобы объяснить её, будем считать, что целью первого игрока является не дать второму соединить верх и низ. (Мы уже упо- минали, что эта цель равносильна исходной.) Начальный ход первого игрока показан на рис. 11.4 ; этот ход запрещает одно из рёбер второго игрока. Разделим остальные рёбра второго игрока на пары соседних, как показано на том же рисунке. Первый игрок препятствует второ- му провести оба ребра какой-либо пары: если второй провёл одно из 11.2. Цена игры 219 рёбер пары, первый не даёт провести второе ребро этой пары (прове- дя пересекающее его своё ребро). Следующая задача показывает, что Рис. 11.4. Игра Гейла: выигрышная стратегия. эта стратегия является выигрышной (первый игрок не даёт второму соединить верх и низ и потому соединяет левую и правую стороны). 11.2.9. Докажите, что любой путь по линиям пунктирной сетки, соединяющий верх и низ рисунка 11.4 , обязательно покрывает два ребра одной пары. Решение. Для ясности оставим на рисунке только пунктирные ли- нии и соответствующие вершины (рис. 11.5 ). Отметим серую область, как показано на рисунке; тем самым рёбра делятся на серые и белые. Рис. 11.5. Игра Гейла: анализ выигрышной стратегии. Предположим, что имеется путь снизу вверх, который не покрывает ни одной пары рёбер. Можно считать, что этот путь не проходит дваж- ды через одну вершину (выбросим циклы). Каждый шаг на этом пути 220 11. Анализ игр может относиться к одной из восьми категорий: четыре направления (север, восток, юг и запад) комбинируются с двумя цветами (серым и белым). Как видно из рисунка, путь должен начинаться с серого ша- га на север, а заканчиваться белым шагом на север. Покажем, что это невозможно в силу наших ограничений (нельзя использовать два ребра одной пары и нельзя дважды проходить через одну вершину). Что, к примеру, может следовать за серым шагом на север? Ещё один серый шаг на север, серый шаг на запад или белый шаг на восток. За серым шагом на запад может следовать серый шаг на запад или серый шаг на север. Разбирая поочерёдно все варианты, легко убедиться, что путь, начавшись серым шагом на север, никогда не выйдет (если не нарушит правил) за пределы множества { серый шаг на север, серый шаг на запад, белый шаг на восток, белый шаг на юг}. Поэтому белый шаг на север (который должен быть последним в пути) невозможен, и мы доказали, что верх и низ рисунка нельзя соединить путём, не проходящим по двум рёбрам одной пары. 11.2.10. Двое играют на бесконечной клетчатой бумаге, по очереди обводя красным и синим стороны клеток (за один ход можно обвести одну сторону любой клетки, если она ещё не обведена). Докажите, что второй может воспрепятствовать первому построить замкнутый путь из линий своего цвета. [Указание. Он может помешать первому, например, повернуть с за- пада на север, разбив все стороны клеток на пары и не давая покрыть оба члена пары.] 11.2.11. (Для знакомых с теорией вероятностей) На поле для игры Гейла (рис. 11.2 ) каждая из пунктирных линий обведена с вероятно- стью 1/2 независимо от других. Докажите, что путь от левой до правой стороны (по обведённым линиям) существует с вероятностью 1/2. 11.3. Вычисление цены: полный обход Как видно из доказательства теоремы Цермело, для нахождения оптимальной стратегии достаточно уметь вычислять цены всех вер- шин. В этом разделе мы рассмотрим случай, когда позиции игры обра- зуют дерево (ведущие вверх рёбра дерева соответствуют возможным 11.3. Вычисление цены: полный обход 221 в данной позиции ходам) и покажем, как применить программу обхода дерева (глава 3 ). Напомним, что мы рассматривали Робота, который в каждый мо- мент находится в одной из вершин дерева и умеет выполнять команды вверх налево, вправо и вниз. Робот начинает работу в корне дерева (роль которого теперь играет начальная позиция игры). Раньше Робот умел ещё обрабатывать вершины; теперь мы предполагаем, что он мо- жет определить тип текущей вершины (один из трёх: max, min и final, что соответствует вершинам Макса, Мина и заключительным) и может определить стоимость текущей вершины, если она является заключи- тельной. 11.3.1. Напишите программу, которая управляет Роботом и вычи- сляет цену игры. Решение. Напишем рекурсивную процедуру, которая, начав с неко- торой вершины, обходит поддерево этой вершины, возвращает Робота на место и сообщает цену вершины (где она начала и кончила): procedure find_cost (var c: integer) var x: integer; begin if тип = final then begin c:= стоимость; end else if тип = max then begin вверх_налево; find_cost (c); {c = максимум цен текущей вершины и братьев слева} while есть_справа do begin вправо; find_cost (x); c := max (c,x); end; {c=цена вершины под текущей} вниз; end else begin {тип = мин} ...аналогично с заменой max(c,x) на min(c,x) end; end; Мы пользуемся тем, что у вершин типа max и min есть хотя бы один сын (вершины без сыновей должны быть заключительными, и мы предполагаем, что они отнесены к типу final). 222 11. Анализ игр 11.3.2. Напишите нерекурсивную программу для вычисления цены игры (заданной деревом, по которому ходит Робот). Решение. Как обычно, рекурсию можно устранить, используя стек. В данном случае каждый элемент стека будет хранить информацию об одном из предков текущей вершины (чем дальше, тем глубже | на дне стека будет информация о корне). Когда мы находимся в корне, стек пуст, при движении вверх по дереву он удлиняется, при движении вниз | укорачивается. Каждый элемент стека представляет собой пару; первый элемент | тип соответствующей вершины (min/max), а второй элемент | мини- мум/максимум значений всех её сыновей левее текущего. В программе из главы 3 существенную роль играли два утверждения: ОЛ означало, что обработаны все вершины левее текущей (те, путь в которые от- клоняется налево от пути в текущую); ОЛН означало, что обработаны все вершины левее и над текущей (это бывало, когда мы проходили вершину второй раз). Помимо стека (который всегда будет хранить данные, указанные выше) программа использует ещё переменную c. В ситуации ОЛ эта переменная не используется, а в ситуации ОЛН она хранит цену те- кущей вершины. Покажем, как можно поддерживать это, описав дей- ствия с переменной и стеком для каждого варианта движения Робота (ср. с. 64 ): ∙ { ОЛ, не есть сверху} обработать {ОЛН}: в переменную c записываем цену текущего листа; ∙ { ОЛ, есть сверху} вверх налево {ОЛ}: перед тем, как идти вверх, добавляем в стек тип текущей вершины (max/min) и значение −∞/+∞ соответственно, имея в виду, что максимум пустого множества равен −∞, а минимум равен +∞; ∙ { есть справа, ОЛН} вправо {ОЛ}: обновляем значение в вершине стека, беря максимум или мини- мум (в зависимости от типа вершины стека) со значением пере- менной c; ∙ { не есть справа, есть снизу, ОЛН} вниз {ОЛН}: в переменную c помещаем максимум/минимум (в зависимости от типа вершины стека) её прежнего значения и значения на вершине стека (оно забирается из стека, и стек укорачивается). 11.4. Альфа-бета-процедура 223 Легко видеть, что при этом утверждения о содержании стека и зна- чении переменной c не нарушаются, и по окончанию работы программы стек будет пуст, а значение переменной c будет равно цене игры. 11.4. Альфа-бета-процедура Мы видели, как можно вычислить цену игры, обойдя все вершины её дерева. Однако иногда можно сэкономить и часть дерева не посещать. Пусть, например, игра имеет два исхода (выигрыш и проигрыш) и мы обнаружили (после просмотра части дерева), что некоторый ход явля- ется для нас выигрышным. Тогда нет смысла рассматривать остальные ходы. Более общо, если мы нашли ход, гарантирующий нам максималь- ный выигрыш (допускаемый правилами игры), то нет смысла искать дальше. Подобная оптимизация возможна не только в тех случаях, когда мы знаем максимально возможный выигрыш. Пусть, например, дере- во игры имеет такой вид, как на рис. 11.6 , причём 𝑎 > 𝑏 и мы обходим вершины дерева слева направо. Тогда после просмотра вершины 𝑎 мы max min 𝑎 𝑏 Рис. 11.6. Оптимизация возможна при 𝑎 > 𝑏. знаем, что цена корневой вершины не меньше 𝑎. Перейдя к min-вершине и просмотрев её первого сына 𝑏, мы определяем, что цена min-вершины не больше 𝑏 и (при 𝑏 6 𝑎) она не может повлиять на цену корня. Поэтому следующие вершины (серая область на рисунке) и их поддеревья нам просматривать не нужно. Применённую в обоих случаях оптимизацию можно описать так. Приступая к оценке некоторой вершины, мы знаем некоторый про- межуток [𝑚, 𝑀], в пределах которого нас интересует цена этой вер- шины | либо потому, что она заведомо не может выйти за пределы 224 11. Анализ игр промежутка (как в первом случае, когда лучше выигрыша ничего не бывает), либо потому, что это нам ничего не даёт (как во втором слу- чае, когда все цены меньше 𝑎 для нас неотличимы от 𝑎). Более формально, введём обозначение 𝑥 [𝑎,𝑏] , где 𝑥 | число, а [𝑎, 𝑏] | промежуток: 𝑥 [𝑎,𝑏] = ⎧ ⎪ ⎨ ⎪ ⎩ 𝑎, если 𝑥 6 𝑎; 𝑥, если 𝑎 6 𝑥 6 𝑏; 𝑏, если 𝑏 6 𝑥. Другими словами, 𝑥 [𝑎,𝑏] | ближайшая к 𝑥 точка промежутка [𝑎, 𝑏], ко- торую можно назвать «приведённым к [𝑎, 𝑏] значением 𝑥». Теперь можно сказать, что после просмотра вершины 𝑎 на рисунке 11.6 нас интересу- ет приведённая к [𝑎, +∞] цена min-вершины (все значения, меньшие 𝑎, безразличны), а после просмотра вершины 𝑏 эта приведённая цена уже известна (равна 𝑎). Аналогичным образом цена игры с двумя исходами ± 1 равна её приведённой к отрезку [−1, +1] цене, и после обнаружения выигрышного хода становится ясным, что эта цена равна +1. Используя это соображение, напишем оптимизированный алгоритм, в котором рекурсивно определяется приведённая к промежутку [𝑎, 𝑏] цена игры в текущей вершине: procedure find_reduced_cost (a,b: integer; var c: integer) var x: integer; begin if тип = final then begin c:= стоимость, приведённая к [a,b] end else if тип = max then begin вверх_налево; find_reduced_cost (a,b,c); {c = максимум цены вершины и братьев слева, приведённый к [a,b] while есть_справа and (c c := x; end; {c=цена вершины под текущей, приведённая к [a,b]} вниз; end else begin {тип = мин} ...симметрично end; end; 11.4. Альфа-бета-процедура 225 Естественный вопрос: насколько такого рода оптимизация помога- ет уменьшить перебор? Мы рассмотрим простейший пример. Пусть игра имеет фиксированную длину, из каждой позиции возможны два хода, игроки ходят по очереди, каждый делает 𝑛 ходов и цены листьев равны 0 или 1. Дерево такой игры | полное двоичное дерево, min- и max-уровни чередуются, в листьях написаны нули и единицы, и нужно вычислить значение в корне. (Если считать, что 1 = истина, 0 = ложь, то максимум и минимум соответствуют операциям OR (ИЛИ) и AND (И), поэтому иногда говорят об AND-OR-дереве.) Сколько листьев нужно посетить, чтобы вычислить значение в кор- не? Напомним, что всего листьев 2 2𝑛 для дерева с 2𝑛 уровнями (каждый из игроков делает 𝑛 ходов). 11.4.1. Докажите, что для любых значений в листьях описанный нами оптимизированный алгоритм просматривает не менее 2 𝑛 листьев. Решение. На уровне 2 находятся четыре вершины. В ходе работы алгоритм должен узнать цену игры хотя бы в двух из них. В самом деле, пусть нижняя вершина есть min-вершина. Если в ней нуль, то в одном из её сыновей тоже нуль. А раз это max-вершина, то для уста- новления этого факта нужно знать цену обоих сыновей (равную нулю). Второй случай: в корне единица. Тогда в обеих его сыновьях должна быть единица, и чтобы быть в этом уверенным, нужно в каждом из них посмотреть как минимум одного сына. Аналогично ради каждого значения на уровне 2 нужны два значе- ния на уровне 4 и так далее | в конце концов на уровне 2𝑛 нужно знать 2 𝑛 значений. Для наглядности мы говорили о конкретном алгоритме, описанном выше. Но справедлив и более общий факт: любой набор значений в ли- стьях, который однозначно определяет значение в корне, содержит не менее 2 𝑛 значений. 11.4.2. Проведите аккуратное доказательство этого утверждения. [Указание. По существу уже всё доказано, надо только это офор- мить.] Только что полученная оценка относилась к самому благоприятному случаю. Утверждение следующей задачи, напротив, говорит о наихуд- шем случае. 11.4.3. Пусть у нас спрашивают значения в листьях AND-OR-дерева в заранее неизвестном нам порядке, и мы можем называть эти значения по собственному усмотрению. Докажите, что мы можем действовать 226 11. Анализ игр так, чтобы до последнего момента (пока есть хоть одно не названное значение) цена корня оставалось бы неизвестной (то есть могла быть и нулём, и единицей в зависимости от ещё не названных значений). Эта задача показывает, что любой алгоритм отыскания цены кор- ня в наиболее неблагоприятном случае вынужден обходить все листья (в частности, наш оптимизированный алгоритм никакого выигрыша не даёт). Решение. Будем доказывать это индукцией по высоте дерева. Пусть корень является AND-вершиной. Тогда будем оттягивать (по предполо- жению индукции) определение значений в детях корня, а когда дальше оттягивать будет нельзя (последний лист поддерева становится извест- ным), сделаем так, чтобы это поддерево было истинным. Тем самым значение в корне совпадает со значением в другом поддереве и может оставаться неопределённым до последнего момента. Более интересной является оценка среднего числа опрошенных ли- стьев. Будем считать, что алгоритм find reduced cost применяет- ся к некоторому фиксированному AND-OR-дереву (с фиксированны- ми значениями в листьях), но для каждой вершины порядок просмотра двух её детей выбирается случайно. Тогда общее число просмотренных листьев становится случайной величиной. 11.4.4. Докажите, что математическое ожидание этой случайной величины (среднее по всем порядкам просмотров) для любого AND- OR-дерева высоты 2𝑛 (с 4 𝑛 вершинами) не превосходит 3 𝑛 Решение. Рассмотрим сначала случай 𝑛 = 1, то есть дерево глуби- ны 2. Пусть его корень является AND-вершиной. Если в корне находит- ся 0, то на первом уровне 0, 0 или 0, 1. В первом случае нам достаточно просмотреть две вершины (найдя первый нуль, мы не ищем второй). Во втором случае с вероятностью 1/2 нам хватит двух, а с вероятно- стью 1/2 понадобится три или четыре. Если же в AND-корне находит- ся 1, то в обеих OR-вершинах первого уровня находится единица, и на каждую из них нужно в среднем не больше 3/2 просмотров листьев (с вероятностью не менее 1/2 мы сразу попадаем в лист с единицей и второй лист не смотрим). Дальнейшее рассуждение легко происходит по индукции. Пусть среднее значение числа запрашиваемых листьев для любого дерева глу- бины 2𝑘 не превосходит 3 𝑘 . Рассмотрим дерево глубины 2𝑘 + 2 с фик- сированными значениями в листьях. Для каждого выбора порядка на 11.5. Ретроспективный анализ 227 первых двух уровнях известно, какие из четырёх вершин высоты 2 бу- дут рассмотрены. По предположению среднее число использованных ли- стьев при рассмотрении каждой вершины высоты 2 (усреднение по всем порядкам обхода) не больше 3 𝑘 . Дополнительно усредняем по порядкам на двух первых уровнях и замечаем, что в среднем рассматривается не больше трёх вершин высоты 2. 11.4.5. Получите более точную оценку для числа просмотренных листьев в предыдущей задаче. [Указание. Используйте разные оценки в зависимости от значения в корне; это позволит заменить √ 3 в оценке на меньшее число (1 + √ 33)/4.] 11.5. Ретроспективный анализ Существенно ли описанное в прошлом разделе улучшение алгорит- ма (переход от полного перебора к 𝛼-𝛽-процедуре)? С одной стороны, да: в нашем примере переход от 4 𝑛 к 3 𝑛 даёт выигрыш в (4/3) 𝑛 раз, а (4/3) 𝑛 экспоненциально растёт с ростом 𝑛. С другой стороны, экс- понента остаётся экспонентой, даже если её показатель уменьшается с 4 до 3, поэтому надежды полностью проанализировать даже не очень сложную и долгую игру таким способом почти нет. Поэтому на практике обычно выбирают некоторую оценку пози- ции | легко вычислимую функцию, которая по мнению практиков как-то отражает преимущество того или иного игрока (скажем, мате- риальный перевес в шахматах). Затем вместо настоящей игры рассма- тривают ограниченную игру, в которой делается сравнительно неболь- шое число 𝑘 ходов, а затем результатом игры считается оценка полу- ченной позиции, и в этой игре выполняют перебор (применяя 𝛼-𝛽-опти- мизацию). Конечно, это ничего не гарантирует в настоящей игре, но что поделаешь. Бывают, однако, и ситуации, когда удаётся определить цену данной позиции точно. Это удаётся сделать для шахматных эндшпилей с не- большим числом фигур | например, можно рассчитать, за какое ми- нимальное число ходов можно поставить мат королём, слоном и конём против одинокого короля в заданных начальных условиях. Заметим, что при этом число ходов может измеряться десятками, а каждый ход имеет десятки вариантов, поэтому о полном переборе (или даже о не- сколько сокращённом) не может идти и речи. 11.5.1. Придумайте другой подход, использующий ограниченность общего числа возможных позиций (скажем, для четырёх упомянутых 228 11. Анализ игр фигур на шахматной доске это 64 4 = 2 24 = 16 «мегапозиций»; с учётом очерёдности хода будет 32 мегапозиции; массив такого размера поме- щается в память современных компьютеров без труда). Решение. Заведём массив, отведя ячейку для каждой позиции. Про- смотрим его один раз и отметим все матовые позиции (записав туда число 0 в знак того, что позиция проиграна и больше ходить нельзя). Затем просмотрим массив ещё раз и пометим как выигрышные все по- зиции, из которых можно пойти в матовые (напишем там 1 в знак того, что можно выиграть за 1 ход). Затем отметим все (ещё не отмеченные) позиции, из которых все ходы ведут в позиции с меткой 1, написав там −2; они проигрываются в два хода. Затем | позиции, из которых есть ход в позиции с меткой −2 (написав там 3), после этого | позиции, из которых все ходы ведут в 1- или 3-позиции (написав там −4) и т. п. Так будем делать до тех пор, пока будут появляться новые пометки. Как только это кончится, для каждой позиции будет известно, можно ли в ней выиграть и сколько ходов для этого нужно. Фактически эта процедура повторяет доказательство теоремы Цер- мело (но дополнительно мы получаем информацию о том, сколько ходов до выигрыша или проигрыша при наилучшей игре). |