Анализ игр

11.2.4. Игра в крестики-нолики состоит в следующем: на большом квадратном поле два игрока по очереди ставят крестики и нолики в еще не занятые клетки (начинают крестики). Выигрывает тот, кто первым поставит пять своих знаков подряд (по вертикали, горизонтали или диагонали). Если все поле заполнено, а такого не случилось, партия считается ничейной. Доказать, что у крестиков есть стратегия, гарантирующая им ничью или выигрыш.

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

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

Кроме того, игра может кончиться раньше времени, если карандашный крестик образует выигрышный ряд с чернильными - но это нам только лучше.

Таким образом, мы доказали, что если у ноликов есть выигрышная стратегия, то и у крестиков есть выигрышная стратегия - и если дать этим стратегиям играть друг против друга, получится противоречие.

11.2.5. Доказать, что цена любой игры равна выигрышу в одной из заключительных вершин.

11.2.6. Показать, что теорема Цермело вытекает из своего частного случая игр с двумя исходами (выигрыш первого и второго).

Указание. Для каждого $$с$$ будем считать выигрыш меньше $$c$$ проигрышем, а больше $$c$$ - выигрышем.

11.2.7. Пусть дана некоторая игра $$G$$. Выберем одну из заключительных вершин и будем менять выигрыш в этой вершине: положив его равным $$c$$, получим игру $$G[c]$$. Рассмотрим цену этой игры как функцию от $$c$$. Что это может быть за функция?

Ответ. цена игры $$G[c]$$ равна ближайшей к $$c$$ точке некоторого отрезка $$[a,b]$$ (зависящего от игры $$G$$ ).

Вот еще один пример игры, где теорема Цермело позволяет доказать существование выигрышной стратегии для первого игрока. Эта игра названа в книгах М. Гарднера ("Математические досуги", М.: Мир, 1972; " Математические головоломки и развлечения", М.: Мир, 1971) игрой Гейла или "бридж-ит". Рассмотрим прямоугольную сеть из пунктирных линий высоты $$n$$ и ширины $$n+1$$ ( рис 11.2.(рис 11.2) Игра Гейлавершины сети соединены пунктирными отрезками длины $$1$$. Первый игрок каждым своим ходом обводит (сплошной линией) один из отрезков. Его задача - соединить сплошными линиями левую и правую стороны прямоугольника. Задача второго игрока - ему помешать; каждым своим ходом он стирает один из отрезков (лишая первого возможности впоследствии его обвести). Игра заканчивается, когда все отрезки обведены или стерты; первый выиграл, если при этом левая и правая стороны прямоугольника соединены.

11.2.8. Используя теорему Цермело, доказать, что первый игрок имеет выигрышную стратегию.

Указание. Игру можно представить в более симметричном виде, если добавить сетку для второго игрока (рис. 11.3.) и считать, что второй хочет соединить верхнюю и нижнюю стороны своей сетки, а линиям первого и второго игроков запрещено пересекаться (тем самым проведя свою линию, второй игрок как бы стирает пересекающую ее линию первого). Если игра закончилась (в каждой возможной точке пересечения проведена вертикальная или горизонтальная линия), то ровно один из игроков выиграл: можно пройти по линиям или слева направо, или сверху вниз, но не одновременно. Аккуратное доказательство этого интуитивно ясного топологического факта, впрочем, не так просто.(рис 11.3) Игра Гейла, симметричный вариантКак пишет Гарднер, Клод Шеннон (создатель теории информации) придумал для этой игры любопытную "физическую" стратегию, которая легко обобщается на любую сеть линий. Представим себе, что все стороны всех клеток сети (для первого игрока) представляют собой резисторы одинакового сопротивления, кроме левой и правой сторон прямоугольника, которые сделаны из провода нулевого сопротивления. Первый игрок своим ходом закорачивает эти сопротивления, а второй игрок разрывает их (делает бесконечными). Стратегия первого игрока состоит в том, что надо подключить напряжение между левой и правой сторонами прямоугольника, и закорачивать (обводить) то сопротивление, через которое идет максимальный ток (или, что то же самое, на котором падает наибольшая разность потенциалов). Если таких сопротивлений оказалось несколько, можно закорачивать любое из них.

Из книг Гарднера не ясно, является ли эта стратегия выигрышной. Зато там приведена явная выигрышная стратегия (со ссылкой на О. Гросса). Чтобы объяснить ее, будем считать, что целью первого игрока является не дать второму соединить верх и низ. (Мы уже упоминали, что эта цель равносильна исходной.) Начальный ход первого игрока показан на рис. 11.4.; этот ход запрещает одно из ребер второго игрока. Разделим остальные ребра второго игрока на пары соседних, как показано на том же рисунке. Первый игрок препятствует второму провести оба ребра какой-либо пары: если второй провел одно из ребер пары, первый не дает провести второе ребро этой пары (проведя пересекающее его свое ребро).(рис 11.4) Игра Гейла: выигрышная стратегияСледующая задача показывает, что эта стратегия является выигрышной (первый игрок не дает второму соединить верх и низ и потому соединяет левую и правую стороны).

11.2.9. Доказать, что любой путь по линиям пунктирной сетки, соединяющий верх и низ рисунка 11.4., обязательно покрывает два ребра одной пары.

Решение. Для ясности оставим на рисунке только пунктирные линии и соответствующие вершины (рис. 11.5.). Отметим серую область, как показано на рисунке; тем самым ребра делятся на серые и белые. Предположим, что имеется путь снизу вверх, который не покрывает ни одной пары ребер. Можно считать, что этот путь(рис 11.5) Игра Гейла: анализ выигрышной стратегиине проходит дважды через одну вершину (выбросим циклы). Каждый шаг на этом пути может относиться к одной из восьми категорий: четыре направления (север, восток, юг и запад) комбинируются с двумя цветами (серым и белым). Как видно из рисунка, путь должен начинаться с серого шага на север, а заканчиваться белым шагом на север.

Покажем, что это невозможно в силу наших ограничений (нельзя использовать два ребра одной пары и нельзя дважды проходить через одну вершину). Что, к примеру, может следовать за серым шагом на север? Еще один серый шаг на север, серый шаг на запад или белый шаг на восток. За серым шагом на запад может следовать серый шаг на запад или серый шаг на север. Разбирая поочередно все варианты, легко убедиться, что путь, начавшись серым шагом на север, никогда не выйдет (если не нарушит правил) за пределы множества$$\begin{center} \{серый шаг на север, серый шаг на запад,\qquad\\ \qquad белый шаг на восток, белый шаг на юг\}. \end{center}$$ Поэтому белый шаг на север (который должен быть последним в пути) невозможен, и мы доказали, что верх и низ рисунка нельзя соединить путем, не проходящим по двум ребрам одной пары.

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

Указание. Он может помешать первому, например, повернуть с запада на север, разбив все стороны клеток на пары и не давая покрыть оба члена пары.

11.2.11. (Для знакомых с теорией вероятностей) На поле для игры Гейла (рис. 11.2.) каждая из пунктирных линий обведена с вероятностью $$1/2$$ независимо от других. Доказать, что путь от левой до правой стороны (по обведенным линиям) существует с вероятностью $$1/2$$.

11.3. Вычисление цены: полный обход

Как видно из доказательства теоремы Цермело, для нахождения оптимальной стратегии достаточно уметь вычислять цены всех вершин. В этом разделе мы рассмотрим случай, когда позиции игры образуют дерево (ведущие вверх ребра дерева соответствуют возможным в данной позиции ходам) и покажем, как применить программу обхода дерева (лекция 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 ).

11.3.2. Написать нерекурсивную программу для вычисления цены игры (заданной деревом, по которому ходит Робот).

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

Каждый элемент стека представляет собой пару; первый элемент - тип соответствующей вершины ( min/max ), а второй элемент - минимум/максимум значений всех ее сыновей левее текущего. В программе из лекции 3 существенную роль играли два утверждения: ОЛ означало, что обработаны все вершины левее текущей (те, путь в которые отклоняется налево от пути в текущую); ОЛН означало, что обработаны все вершины левее и над текущей (это бывало, когда мы проходили вершину второй раз).

Помимо стека (который всегда будет хранить данные, указанные выше) программа использует еще переменную c. В ситуации ОЛ эта переменная не используется, а в ситуации ОЛН она хранит цену текущей вершины. Покажем, как можно поддерживать это, описав действия с переменной и стеком для каждого варианта движения Робота (ср. задача 3.1.1. свойства команд Робота):

Легко видеть, что при этом утверждения о содержании стека и значении переменной c не нарушаются, и по окончанию работы программы стек будет пуст, а значение переменной c будет равно цене игры.

11.4. Альфа-бета-процедура

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

Подобная оптимизация возможна не только в тех случаях, когда мы знаем максимально возможный выигрыш. Пусть, например, дерево игры имеет такой вид, как на рис. 11.6, причем $$a\ge b$$ и мы обходим вершины дерева слева направо.(рис 11.6) Оптимизация возможна если a не меньше bТогда после просмотра вершины $$a$$ мы знаем, что цена корневой вершины не меньше $$a$$. Перейдя к min-вершине и просмотрев ее первого сына $$b$$, мы определяем, что цена min-вершины не больше $$b$$ и (при $$b\le a$$ ) она не может повлиять на цену корня. Поэтому следующие вершины (серая область на рисунке) и их поддеревья нам просматривать не нужно.

Примененную в обоих случаях оптимизацию можно описать так. Приступая к оценке некоторой вершины, мы знаем некоторый промежуток $$[m,M]$$, в пределах которого нас интересует цена этой вершины - либо потому, что она заведомо не может выйти за пределы промежутка (как в первом случае, когда лучше выигрыша ничего не бывает), либо потому, что это нам ничего не дает (как во втором случае, когда все цены меньше $$b$$ для нас неотличимы от $$b$$ ).

Более формально, введем обозначение $$x_{[a,b]}$$, где $$x$$ - число, а $$[a,b]$$ - промежуток:$$$$ x_{[a,b]}=\begin{cases} a, \text{если $x\le a$;}\\ x, \text{если $a\le x\le b$;}\\ b, \text{если $b\le x$.} \end{cases} $$$$ Другими словами, $$x_{[a,b]}$$ - ближайшая к $$x$$ точка промежутка $$[a,b]$$, которую можно назвать "приведенным к $$[a,b]$$ значением $$x$$ ". Теперь можно сказать, что после просмотра вершины $$a$$ на рисунке 11.6. нас интересует приведенная к $$[a,+\infty]$$ цена min-вершины (все значения, меньшие $$a$$, безразличны), а после просмотра вершины $$b$$ эта приведенная цена уже известна (равна $$a$$ ). Аналогичным образом цена игры с двумя исходами $$\pm 1$$ равна ее приведенной к отрезку $$[-1,+1]$$ цене, и после обнаружения выигрышного хода становится ясным, что эта цена равна $$+1$$.

Используя это соображение, напишем оптимизированный алгоритм, в котором рекурсивно определяется приведенная к промежутку $$[a,b]$$ цена игры в текущей вершине:

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<b) do begin
| | | вправо;
| | | find_reduced_cost (c,b,x);
| | | c := x;
| | end;
| | {c=цена вершины под текущей, приведенная к [a,b]}
| | вниз;
| end else begin {тип = мин}
| | ...симметрично
| end;
end;

Естественный вопрос: насколько такого рода оптимизация помогает уменьшить перебор? Мы рассмотрим простейший пример. Пусть игра имеет фиксированную длину, из каждой позиции возможны два хода, игроки ходят по очереди, каждый делает $$n$$ ходов и цены листьев равны $$0$$ или $$1$$. Дерево такой игры - полное двоичное дерево, min- и max-уровни чередуются, в листьях написаны нули и единицы, и нужно вычислить значение в корне. (Если считать, что $$1=\text{истина}$$, $$0=\text{ложь}$$, то максимум и минимум соответствуют операциям OR (ИЛИ) и AND (И), поэтому иногда говорят об AND-OR-дереве.)

Сколько листьев нужно посетить, чтобы вычислить значение в корне? Напомним, что всего листьев $$2^{2n}$$ для дерева с $$2n$$ уровнями (каждый из игроков делает $$n$$ ходов).

11.4.1. Доказать, что для любых значений в листьях описанный нами оптимизированный алгоритм просматривает не менее $$2^n$$ листьев.

Решение. На уровне $$2$$ находятся четыре вершины. В ходе работы алгоритм должен узнать цену игры хотя бы в двух из них. В самом деле, пусть нижняя вершина есть min-вершина. Если в ней нуль, то в одном из ее сыновей тоже нуль. А раз это max-вершина, то для установления этого факта нужно знать цену обоих сыновей (равную нулю). Второй случай: в корне единица. Тогда в обеих его сыновьях должна быть единица, и чтобы быть в этом уверенным, нужно в каждом из них посмотреть как минимум одного сына.

Аналогично ради каждого значения на уровне $$2$$ нужны два значения на уровне $$4$$ и так далее - в конце концов на уровне $$2n$$ нужно знать $$2^n$$ значений.

Для наглядности мы говорили о конкретном алгоритме, описанном выше. Но справедлив и более общий факт: любой набор значений в листьях, который однозначно определяет значение в корне, содержит не менее $$2^n$$ значений.

11.4.2. Провести аккуратное доказательство этого утверждения.

Указание. По существу уже все доказано, надо только это оформить.

Только что полученная оценка относилась к самому благоприятному случаю. Утверждение следующей задачи, напротив, говорит о наихудшем случае.

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

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

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

Более интересной является оценка среднего числа опрошенных листьев. Будем считать, что алгоритм find_reduced_cost применяется к некоторому фиксированному AND-OR-дереву (с фиксированными значениями в листьях), но для каждой вершины порядок просмотра двух ее детей выбирается случайно. Тогда общее число просмотренных листьев становится случайной величиной.

11.4.4. Доказать, что математическое ожидание этой случайной величины (среднее по всем порядкам просмотров) для любого AND-OR-дерева высоты $$2n$$ (с $$4^n$$ вершинами) не превосходит $$3^n$$.

Решение. Рассмотрим сначала случай $$n=1$$, то есть дерево глубины $$2$$. Пусть его корень является AND-вершиной. Если в корне находится $$0$$, то на первом уровне $$0, 0$$ или $$0,1$$. В первом случае нам достаточно просмотреть две вершины (найдя первый нуль, мы не ищем второй). Во втором случае с вероятностью $$1/2$$ нам хватит двух, а с вероятностью $$1/2$$ понадобится три или четыре. Если же в AND-корне находится $$1$$, то в обеих OR-вершинах первого уровня находится единица, и на каждую из них нужно в среднем не больше $$3/2$$ просмотров листьев (с вероятностью не менее $$1/2$$ мы сразу попадаем в лист с единицей и второй лист не смотрим).

Дальнейшее рассуждение легко происходит по индукции. Пусть среднее значение числа запрашиваемых листьев для любого дерева глубины $$2k$$ не превосходит $$3^k$$. Рассмотрим дерево глубины $$2k+2$$ с фиксированными значениями в листьях. Для каждого выбора порядка на первых двух уровнях известно, какие из четырех вершин высоты $$2$$ будут рассмотрены. По предположению среднее число использованных листьев при рассмотрении каждой вершины высоты $$2$$ (усреднение по всем порядкам обхода) не больше $$3^k$$. Дополнительно усредняем по порядкам на двух первых уровнях и замечаем, что в среднем рассматривается не больше трех вершин высоты $$2$$.

11.4.5. Получить более точную оценку для числа просмотренных листьев в предыдущей задаче. Используйте разные оценки в зависимости от значения в корне; это позволит заменить $$\sqrt{3}$$ в оценке на меньшее число $$(1+\sqrt{33})/4$$.]

11.5. Ретроспективный анализ

Существенно ли описанное в прошлом разделе улучшение алгоритма (переход от полного перебора к $$\alpha-\beta$$ -процедуре)? С одной стороны, да: в нашем примере переход от $$4^n$$ к $$3^n$$ дает выигрыш в $$(4/3)^n$$ раз, а $$(4/3)^n$$ экспоненциально растет с ростом $$n$$. С другой стороны, экспонента остается экспонентой, даже если ее показатель уменьшается с $$4$$ до $$3$$, поэтому надежды полностью проанализировать даже не очень сложную и долгую игру таким способом почти нет.

Поэтому на практике обычно выбирают некоторую оценку позиции - легко вычислимую функцию, которая по мнению практиков как-то отражает преимущество того или иного игрока (скажем, материальный перевес в шахматах). Затем вместо настоящей игры рассматривают ограниченную игру, в которой делается сравнительно небольшое число $$k$$ ходов, а затем результатом игры считается оценка полученной позиции, и в этой игре выполняют перебор (применяя $$\alpha-\beta$$ -оптимизацию). Конечно, это ничего не гарантирует в настоящей игре, но что поделаешь.

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

11.5.1. Придумать другой подход, использующий ограниченность общего числа возможных позиций (скажем, для четырех упомянутых фигур на шахматной доске это $$64^4=2^{24}=16$$ "мегапозиций"; с учетом очередности хода будет $$32$$ мегапозиции; массив такого размера помещается в память современных компьютеров без труда).

Решение. Заведем массив, отведя ячейку для каждой позиции. Просмотрим его один раз и отметим все матовые позиции (записав туда число $$0$$ в знак того, что позиция выигрышная и до выигрыша осталось $$0$$ ходов). Затем просмотрим массив еще раз и пометим как проигрышные все позиции, из которых можно пойти лишь в матовые (напишем там $$-1$$ в знак того, что можно протянуть лишь еще $$1$$ ход). Затем отметим все позиции, из которых есть ход в позиции с числом $$-1$$, написав там $$2$$. Затем - позиции, из которых все ходы ведут в позиции $$0$$ или $$2$$, написав там $$-3$$, и т.п. Так будем делать до тех пор, пока будут появляться новые пометки. Как только это кончится, для каждой позиции будет известно, можно ли в ней выиграть и сколько ходов для этого нужно.

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

11.5.2. Могут ли при этом остаться неотмеченные позиции и чему они соответствуют?

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

А.Л. Брудно заметил, что есть ситуация, в которой такой анализ требует совсем небольших ресурсов и может быть реализован на очень небольшой памяти, хотя для человека соответствующая задача не проста: пусть белые имеют короля на поле c3, которого им запрещено двигать, и ферзя (на каком-то другом поле) и хотят поставить мат одинокому черному королю. Ограничение (неподвижность короля), затрудняющее жизнь человеку-шахматисту, облегчает анализ (уменьшая количество позиций почти что в $$64$$ раза за счет того, что не надо рассматривать разные положения короля!)

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