10.3.2. Деревья игр

В чисто конфликтной ситуации два противника делают ходы и контрходы, приближаясь к конечной ситуации, желательной только для одного из них. Если ставки невелики и правила точно определены, мы называем это игрой. Деловые отношения, конфликты между людьми, войны сходны с играми, хотя допустимые ходы, правила определения преимущества или ущерба и сами рамки таких серьезных конфликтов обычно нечетки. Тем не менее заманчиво считать задачи принятия решений в реальных жизненных ситуациях, содержащих конфликт, играми; это позволило бы анализировать их математически. Так как в некоторых важных типах конфликтов необходимо быстро принимать решения, требующие обработки огромного объема данных, и так как любой процесс принятия решения с помощью ЭВМ должен быть математически обоснован, то вопрос о том, как ЭВМ должна разыгрывать сложные игры, очень важен для практики. Кроме того, и игры, и работа с ЭВМ являются своего рода вызовом человеческому интеллекту. Довольно трудно научить ЭВМ хорошо играть в интересные игры, но именно эта трудность и может доставить удовольствие некоторым из нас.

Формально мы будем заниматься вычислимыми стратегиями для игр двух лиц с нулевой суммой и с полной информацией (Льюс и Райфа, 1957). Менее формально мы будем рассматривать задачу программирования стратегии поведения для условной игры на доске при следующих правилах: два игрока ходят по очереди, выбирая ходы из заданного множества возможных ходов; любой проигрыш материала, позиции в игре для одного партнера является прямым выигрышем для другого; каждый ход сразу же становится известен; результат каждого хода детерминирован. Последнее означает, что позиция игроков в результате предложенного хода полностью предсказуема в отличие от предсказуемости с точностью до случайного события. В качестве иллюстрации последнего ограничения можно привести разновидность игры в шашки, в которой ходы не детерминированы. Пусть, например, съеденная шашка снимается с доски только после того, как бросается игральная кость и выпадает 4 или больше; ясно, что результат хода можно предсказать только с некоторой вероятностью. Можно было бы расширить обсуждение и рассмотреть вероятностные исходы, но это уведет нас от искусственного интеллекта в область теории игр.

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

заключительных позиций. Каждой заключительной позиции приписывается число, которое можно назвать исходом игры. Игрок А стремится максимизировать исход, игрок В — минимизировать его. Во многих ситуациях можно просто приписать всем заключительным позициям, выигрышным для А, —1 всем заключительным позициям, выигрышным для Б, и 0 для ничьих. Стратегия минимакса считается разумной фактически для всех таких игр. Грубо говоря, всегда надо играть так, как будто противник ответит на ваш ход наилучшим для него способом. Другими словами, после вашего хода противник может заставить вас понести потери, и размер этих потерь зависит, естественно, от того, насколько искусно он выбрал свой ход. Безопаснее всего рассчитывать на то, что противник может ответить своим лучшим ходом. Поэтому при определении хода вы должны выбрать тот, который минимизирует максимальные потери от следующего хода противника. Отсюда и происходит название — стратегия минимакса.

В качестве примера рассмотрим игру, заданную в матричной форме в табл. 10.1. Ее можно интерпретировать так.

Таблица 10.1

Упрощенная игра в матричной форме

Каждый из игроков А и В выбирает один из двух ходов соответственно. Цена игры определяется выбором обоих игроков. Так, при ходах цена игры равна 4. Пусть игрок А ходит первым. Как он должен пойти? Ответ: так как если сделан ход то В, имея возможность выбрать цену 10 или 4, предпочтет, конечно, 4, а если сделан ход то минимально возможная цена игры равна 5.

Эту игру можно представить также и в виде дерева (рис. 10.7). Отметим квадратами узлы, представляющие ходы игрока А, кружочками — ходы игрока В. Листья отмечены числами, показывающими исходы игры.

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

обратном направлении, начиная от исходов игры. Исходам непосредственно предшествует ход игрока В. Какова цена каждого из этих ходов? Поскольку каждая позиция представляет выбор для В, а В пытается минимизировать результат этого выбора, то цена позиции, разумеется, равна наименьшему из исходов, которых В может достичь из этой позиции. Поэтому, если множество исходов для то он выберет 4. Величина, определяемая таким способом, называется обращенной ценой позиции. Обращенные цены позиций показаны в скобках рядом с узлами на рис. 10.7.

Рис. 10.7. Дерево игры, заданной в табл. 10.1.

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

Идея метода применима ко всем играм на доске. Можно представить себе, что мы исследуем все допустимые дебютные последовательности ходов в шахматах, все возможные ответы на них и т. д. до тех пор, пока не находим гарантированную выигрышную последовательность ходов, если такая существует. Если ее нет, это тоже станет известно. Смысл игры в шахматы пропадет. К счастью для любителей шахмат, на практике такой метод совершенно непригоден. В наиболее интересном случае в шахматах достаточно рассмотреть 20 дебютных ходов и 20 ответов на них. По оценке Минского, соответствующее дерево состоит из 10120 узлов — гораздо больше, чем в состоянии просмотреть человек или ЭВМ. В практической программе для игры должна определяться стратегия, т. е. в высшей степени избирательный поиск содержательных последовательностей ходов, допускающий возможность того, что правильный ответ не будет найден.

Одна из таких простых стратегий — просмотр на шагов вперед. Предположим, что в некоторой незаключительной позиции очередь хода за игроком А. Он рассматривает все возможные ситуации, достижимые за шагов, где выбрано достаточно малым, чтобы с получившимся деревом еще можно было работать. Незаключительные позиции в дереве для шагов затем оцениваются с помощью эвристической функции, которая каждой позиции, достижимой за шагов, приписывает „предсказуемый исход". Если заключительная позиция достижима, производится прямое вычисление. Для незаключительных позиций, однако, требуется найти метод их оценивания без исследования оставшейся части игры. Такой метод, несомненно, должен учитывать специфику игры. Например, в шашках можно использовать функцию

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

Будем использовать просмотр на 1 шаг вперед. Для оценки позиции берем функцию

Игрок А ставит X и стремится максимизировать Игрок В ставит 0 и стремится минимизировать Начальная позиция Р — чистая доска. — позиции на доске с единственным крестиком в одной из клеток. Если сосчитать их по положениям х в принятом порядке перечисления, то получим для

(так как прямые можно провести по диагонали, горизонтали и вертикали от крестика),

Так как — максимальная цена для множества то А выбирает Игрок В может теперь выбирать из 8 ходов Например,

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

у В теперь есть 6 ответов. То, что В должен сделать ход

„ясно для всех", но не для функции! Для сравнения:

Ведь если В минимизирует он выберет и А следующим ходом выигрывает!

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

поиска на дереве. При составлении оценки сначала А исследует девять позиций, затем В — восемь, затем А — семь и т. д. до общего числа позиций. Если применяется просмотр на 2 шага вперед, это число увеличится до Но ведь это очень простая игра!

Одна из наиболее сложных проблем, возникающих при написании игровых программ, состоит в том, чтобы избежать просмотра бесперспективных путей и связанной с этим потери времени. Среди методов поиска, рассчитанных на это, наиболее широко распространена альфа-бета-процедура. Она основана на идее о том, что не следует продолжать исследование некоторого множества путей, если можно показать, что все они хуже какого-либо другого, уже исследованного пути. Этот метод можно проиллюстрировать, не углубляясь в детали конкретной игры, так как альфа-бета-процедура позволяет осуществлять поиск на любом дереве игры. Рассмотрим абстрактную игру, схема которой приведена на рис. 10.8. Число 10 соответствует выигрышу игрока А, —10 соответствует выигрышу игрока В. Для того чтобы найти общую эвристическую функцию, сделаем интуитивно разумное допущение о том, что игрок может определять среднюю цену позиций Р, достижимых из Р, не анализируя каждую из следующих позиций. Таким образом, эвристическая оценка позиции Р с следующими за ней позициями равна

если Р — не концевая точка. Если же Р — концевая точка, то значение положим равным этому исходу. На рис. 10.9 каждый внутренний узел Р дерева помечен его истинным значением если дерево рассматривается полностью и все узлы оцениваются по формуле (57).

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

(кликните для просмотра скана)

провернет ветви слева направо. Обозначим соответствующие ходы в этом же порядке. А замечает, что если он делает свой первый ход по левой ветви то может выбирать из множества оценок позиций А предполагает, что В будет минимизировать цену по этому множеству, и потому приписывает ходу цену —5. Поскольку это лучший ход для А, известный к текущему моменту, число —5 считается альфа-отсечением. Затем А обращается к ходу Обнаруживается, что если А делает ход А2, то В отвечает ходом ; цена этой последовательности будет равна —7. Это меньше альфа-отсечения. Практически это означает, что безотносительно того, какие у еще есть возможности ответить на ход он всегда причинит А больший ущерб, чем в ответ на ход Поэтому другие ответы на ход А 2 не следует рассматривать, так как известно, что предпочтительнее, чем Переходим к Контрходы на превышают альфа-отсечение, однако последовательность приводит А к позиции худшей, чем та, которая могла бы получиться при ходе Поэтому А выбирает ход Теперь А располагает неполным знанием о дереве игры; это изображено на рис. 10.8, где приведены позиции, фактически оцененные игроком , и их цены.

5 теперь просматривает два хода вперед после позиции Напомним, что стремится минимизировать исходы. Если сделает ход , игра перейдет в позицию исследует позиции, возникающие после и обнаруживает, что их максимальная цена равна 0. Разумеется, А добьется этого, если сможет, поэтому цена позиции для равна 0. Это пока наименьшая цена, поэтому она считается бета-отсечением. В обращается теперь к позиции возникающей после хода . Если в ответ на делается ход то возникает позиция с ценой 10. Это превышает бета-отсечение и показывает, что у А против хода есть ответ, наносящий больший ущерб, чем самый лучший ход против . Поэтому можно исключить из рассмотрения. По этим же причинам не рассматривается и (позиция На рис. 10.10 суммированы знания об игре, которыми располагает к этому моменту В. Выбирается ход и наступает очередь игрока А делать ход в позиции На этот раз А может осуществить просмотр до концевых точек и увидеть, что независимо от того, как он сыграет, В может добиться выигрыша. Поэтому А сдается.

В связи с этим примером необходимо отметить следующее. Первое и самое важное: рассмотрены лишь немногие из всех возможных ходов. Второе: картина игры меняется по мере ее развития. Если бы мы вычислили для всего дерева (как на рис. 10.9), оказалось бы, что начальная позиция предпочтительнее для А. В ходе игры, однако, положение складывается в пользу затем выравнивается и в конце концов оказывается, что победа за В. Третье, очень существенное: эффективность и

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

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

Рис. 10.10. Информация игрока В об игре (В делает свой первый ход).

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

Применяя альфа-бета-процедуру для того, чтобы не исследовать бесперспективные пути, можно повысить ее эффективность, упорядочивая поиск так, чтобы окончательное отсечение выясня

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

В заключение приведем некоторые комментарии по поводу игры ЭВМ в конкретные игры. Для большинства реальных игр альфа-бета-процедуры, даже включающей динамическое упорядочение, недостаточно для уменьшения до разумных пределов числа ходов, которые надо рассмотреть. Поэтому в программу обычно вводится специальный блок, „предлагающий ходы". Он выделяет ходы, направленные на достижение некоторой разумной цели в игре. Примеры из шахмат: безопасность короля, овладение центром, материальное превосходство. Ходы, которые надо рассмотреть, выбираются из множества ходов, порожденного таким блоком, а не из всего множества возможных ходов. Это значительно уменьшает число ходов, которые надо рассмотреть. В идее такого блока заложено также то, что хорошая программа конкретной игры будет приспособлена специально к ней, поскольку программа должна содержать много сведений о данной игре. Это в особенности относится к шахматам, наиболее подробно изученной игре. Чаще всего упоминающаяся американская шахматная программа „Мэк-Хэк", созданная в МТИ, как и большинство современных программ, хороша тем, что содержит большие массивы данных о возможных ходах для применения их в различных ситуациях (Гринб-латт и др., 1968). Другими словами, хороший шахматист знает много о шахматах. Спорным пока является вопрос о том, каким образом программа должна приобретать эти знания. Один путь,

несомненно, состоит в том, чтобы добавлять некоторые записи в исходную программу. Это до некоторой степени уже осуществлено. Большинство шахматных программ содержат последовательности ходов и контрходов для стандартных защит. Ситуация в миттельшпиле сложнее из-за огромного числа возможных позиций. Один из подходов к решению этой проблемы — представить ее как задачу распознавания образов. Программа обычно играет много партий сама с собой или с человеком. Встречающиеся позиции записываются и предпринимается попытка найти правило классификации, чтобы определить, когда тот или иной ход целесообразен. Это оправдало себя при создании программ, играющих в шашки (Сэмюэль, 1967). Зобрист и Карлсон (1973) предложили, чтобы в более сложной шахматной игре противником был опытный игрок и чтобы у него была возможность „обращать внимание» обучаемой машины на ключевые особенности различных позиций на доске, в то время как программа накапливает опыт и оценивает его.

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

Ньюэлл и Саймон (1965, 1972) и Де Гроот (1966) противопоставляли человеческую и машинную игры. Де Гроот, в частности, исследовал игру многих шахматных мастеров. Он заметил, что их игра стереотипна, и предположил, что она по меньшей мере представляет особое умение, которое так же сильно зависит от знания шахматной литературы, как и от владения общими игровыми стратегиями. Ньюэлл и Саймон, однако, считают, что наблюдаемые ими игроки обнаруживают по крайней мере зачатки элементов игровых программ, в особенности правило минимакса и идею просмотра до статической позиции. Основное различие между игрой человека и алгоритмами, которые мы обсуждали, состоит в том, что людям, видимо, свойственна некоторая инертность: если уж они начали разрабатывать какую-то линию игры, они продвигаются по ней достаточно глубоко и лишь затем возвращаются назад, чтобы проверить, не помешает ли им противник. Таким образом, оказывается, что люди более, чем хорошо запрограммированная ЭВМ, расположены к методу перебора в глубину.

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

и/или создание легко программируемого способа оценивания позиции. Есть основания считать, что оба эти события могут произойти. Гиллогли (1972) сообщил об удивительно эффективной шахматной программе, применяющей прямой перебор, а алгоритм оценивания был разработан Хансом Берлинером, чемпионом мира по игре в шахматы по переписке! Аналогичный подход избрал советский гроссмейстер Ботвинник (1970), возможно, самый лучший игрок, активно занимающийся шахматными программами. Программа, предложенная Ботвинником, основана на употреблении сложных оценок, а не на запоминании предыдущих позиций. Неизменным остается то обстоятельство, что хорошая шахматная программа должна располагать обширной информацией относительно шахмат. При этом она может использовать информацию совсем не так, как это делал бы человек.