Глава 22. Ведение игры

3. Перейти вниз к позиции й.

4. Выбрать максимальное значение для одного из преемников d, что приводит к получению V(d) = 4.

5. Выполнить возврат к позиции Ь, а затем спуститься вниз к позиции е.

6. Рассмотреть первого преемника е, значение которого равно 5. В данный мо­мент для игрока М А Х (который должен сделать ход в позиции е) гарантирова­но, по меньшей мере, значение 5 в позиции е, если даже не учитывать того, что из позиции е исходят другие (возможно лучшие) альтернативы. Эта оценка является достаточной для игрока MIM, чтобы понять, что в узле Ь альтернатива е хуже, чем d, даже не зная точного значения е,

На этом основании можно пренебречь вторым преемником позиции е и присвоить позиции е ориентировочное значение 5. Но такая замена точного значения прибли­зительным не влияет на расчетное значение b и, следовательно, на значение а.

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

Хол игрока МАХ

с Ход игрока MIN

МАХ

• i •)

Рис. 22.3. Дерево, приведенное на рис. 22.2, поиск в котором осуществляется с по­мощью алъфабстаалгоритма. При этот поиске отсекаются узлы, обозначенные штриховыми линиями, поэтому общий объем поиска уменьшается. В результате некоторые из зафиксированных значений становятся неточными (в частности, это характерно для узлов с, е, f; см рис. 22.2). Но, несмотря на такое снижение точности, дерево содержит достаточно информации для правильного определения значении корневого узла и поиска основного варианта

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

как Alpha и Beta. Эти ограничения имеют следующее значение: Alpha — это мини­мальное значение, достижение которого уже гарантировано для игра MAX, a Beta — максимальное значение, которого может надеяться достичь игрок МАХ Если позиция рассматривается с точки зрения игрока W I N, то Веса — это наихудшее значение для

Часть It. Применение языка Prolog а области искусственного интеллекта

M I K, достижение которого гарантировано для игрока M I H. Поэтому фактическое зна­чение (которое должно быть найдено) лежит в пределах от P.lpha до Beta. Если ока­залось, что некоторая позиция имеет значение, лежащее за пределами интервала Alpha-Beta, то этого достаточно, чтобы определить, что данная позиция не относит­ся к основному варианту, даже не зная точного значения этой позиции. Точное значе­ние позиции необходимо знать только в том случае, если оно находится между Alpha и Beta. Понятие достаточно хорошего зафиксированного значения V(P, Alpha, Beta) позиции Р по отношению к ограничениям Alpha и Beta можно определить фор­мально как любое значение, которое удовлетворяет следующим требованиям:

Vt P, Alpha, Beta) < Alpha, если V(P> < Alpha V<P,Alpha,Beta) = v(p), если Alpha < V[P) < Beta V(P, Alpha, Beta) > Beta, еслк V(P) > Beta

Безусловно, мы можем всегда вычислить точное значение V(P) корневой позиции Р, задавая для нее пределы следующим образом: V(P, -бесконечность, +оесконечность} = V(P)

В листинге 22,3 приведена реализация альфа-бета-ал го ритма на языке Prolog. Ос­новным отношением в этой программе является следующее: alphabets [ Pos, Alpha, Beta, GoodPos, Val)

где GoodPos - достаточно хороший преемник Роз, поэтому его значение Val соот­ветствует требованиям, указанным выше, следующим образом: Val = V(Pos, Alpha, Beta)

Листинг 22.3. Реализация альфа-бета-алгоритма

% Альфа-бета-алгоритм

alpbabeta(Pos, Alpha, Beta, GoodPos, Val):-moves(Pos, PcsList),!,

boundedbeat(PosList, Alpha, Beta, GoodPos, Val);
Staticval(Pos, Val). % Статическое значение позиции Pcs

boundedbestf [Pos 1 PosList], Alpha, Beta, GoodPos, GoodVal):-alphabeta{ Pos, Alpha, Beta, _, Val), goodenougH PosList, Alpha, Beta, Pos, Val, GoodPcs, Good val].

goodenough([], _, _, Pos, Val, Pos, Val):-!. % Другой кандидат отсутствует

goodenoughl _, Alpha, Beta, Роз, Val, Pos, Val):-

min to move (Pos), Val > Beta,! $ Верхняя граница, достигнутая

~~ ~~ % максимизирующим оператором

max_to moue (Pos), Val < Alpha,!, * Нижняя граница, достигнутая

% минимизирующим оператором

goodenoughi PosList, Alpha, Beta, Роз, Val, GoodPos, GoodVal):-

neutrounds(Alpha, Beta, Pos, Val, NewAlpha, MewBeta), % Уточнить границы boundedbest[ PosList, NewAlpha, MewBeta, Posl, Vail), betterofl Pos, Val, Posl, Vail, GoodPos, GoodVal).

newbounds(Alpha, Beta, Pos, Val, Val, Beta):-

min_to_move'{ Pos), Val > Alpha,!. * Максимизирующий оператор

2 увеличил нижнюю границу

newbounds(Alpha, Beta, Pos, Val, Alpha, Val):-

max to move! Pos), Val < Beta,!. I Минимизирующий оператор

% уменьши верхнюю границу

newbounds(Alpha, Beta, _, _, Alpha, Beta). I В противном случае границы

% не изменились

Глава 22. Ведение игры

betteroft Pos, Val, Posl, Vail, Pos, Val):- % Позиция Eos лучше, чем Posl min_to_itLove! Pos), Val > Vail,!

max_to_move(Pos), Val < Vail,!.

betteroft _, _, Posl, Vail, Posl, Vail). % В противном случае лучше

% позиция Posl

Процедура baundedbest(PosList, Alpha, Beta, GbodPos, Val)

находит достаточно хорошую позицию GoodPos в списке PosList таким образом, что зафиксированное значение Val позиции GoodPos является достаточно хорошим при­ближением по отношению к Alpha и Beta.

Альф а-бета-интервал может стать более узким (но ни в коем случае не более ши­роким!) при больших по глубине рекурсивных вызовах альфа-бета-процедуры. Отно­шение newbounds[ Alpha, Beta, Pos, Val, NewAlpha, NewBeta)

определяет новый интервал (NewAlpha, NewBeta), который всегда меньше или ра­вен старому интервалу [ Alpha, Beta). Поэтому по мере перехода на более глубо­кие уровни дерева поиска пределы Alpha-Beta сужаются и позиции этих глубоких уровней оцениваются в более узких пределах. Из-за сужения интервалов количество приближенных оценок увеличивается и поэтому отсечение поддеревьев в дереве ста­новится все более интенсивным. В связи с этим возникает интересный вопрос: "Какой объем работы позволяет сэкономить альфа-бета-алгоритм по сравнению с про­граммой исчерпывающего поиска по принципу минимакса, приведенной в листин­ге 22.2?" Эффективность поиска с использованием альфа-бет а-алгоритм а зависит от того, в каком порядке происходит перебор позиций. Выгоднее всего в первую очередь рассматривать самые сильные ходы для каждого из игроков. Можно легко показать на примерах, что если порядок перебора окажется неудачным, то альфа-бета-процедуре потребуется перебрать все позиции, рассматриваемые при исчерпывающем минимаксном поиске. Это означает, что з худшем случае альфа-бета-ал го ритм не имеет преимуществ над исчерпывающим поиском по принципу минимакса. Но если порядок является благоприятным, экономия усилий может оказаться весьма значи­тельной. Предположим, что N - количество заключительных позиций поиска, ста­тически оцениваемых с помощью исчерпывающего минимаксного алгоритма. Было доказано, что в наилучшем случае, когда вначале всегда рассматривается самый сильный ход, альфа-бет а-алгоритм требует статической оценки лишь %/N ПОЗИЦИЙ.

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

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

Часть И. Применение языка Prolog в области искусственного интеллекта

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

Проект

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

22.4. Программы, основанные на принципе минимакса: усовершенствования и ограничения

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

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

Многое зависит от функции оценки. Если бы у нас была идеальная функция оценки, то достаточно было бы рассмотреть только непосредственных преемников те­кущей позиции, фактически устранив при этом поиск. Но в таких играх, как шах­маты, любая функция оценки с практически приемлемой вычислительной сложно­стью обязательно должна быть просто эвристической функцией оценки. Эта оценка основана на "статических" свойствах позиции (в частности, числа фигур на доске) и поэтому в некоторых позициях является более надежной, чем в других. Например, рассмотрим подобную функцию оценки для шахмат, основанную на учете количества фигур (как принято называть их в шахматах — материала) и представим себе пози­цию, в которой белые имеют лишнего коня. Безусловно, что эта функция оценит по­зицию белых как более благоприятную. Разумеется, такая оценка является вполне приемлемой, если игра развивается спокойно и черные не имеют в своем распоряже­нии внезапных угроз, С другой стороны, если на следующем ходе черные могут взять ферзя белых, то такая оценка может привести к роковой ошибке, поскольку она не позволяет оценить позицию динамически. Безусловно, что статической оценке можно скорее доверять в спокойной игре, а не в резко изменяющихся позициях острой борьбы, когда каждая из сторон непосредственно угрожает взять фигуры противни­ка. Очевидно, что статическая оценка может использоваться только в спокойных по­зициях. Поэтому стандартный прием состоит в том, что поиск в опасных позициях должен продлеваться за пределы глубины до тех пор, пока не будет достигнута спо­койная позиция. В частности, для применения этого расширения необходимо запро­граммировать последовательности взятия фигур с обеих сторон (обмена фигурами) в шахматах.

Еще одним усовершенствованием является эвристическое отсечение. Оно предна­значено для достижения большего предела глубины благодаря исключению из рас-

Глава 22. Ведение игры

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

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

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

• Минимаксные значения предыдущей итерации могут использоваться для предварительного упорядочения позиций в следующей итерации, что позволя­ет в альфа-бета-алторитме в первую очередь выполнять поиск среди самых сильных ходов.

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

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

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

Знания, которые могут быть введены в программы, основанные на принципе ми­нимакса, принимают следующие основные формы.

• Функция оценки.

• Эвристические методы отсечения поддеревьев дерева.

• Эвристические методы поиска спокойных позиций.

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

542 Часть II. Применение языка Prolog в области искусственного интеллекта

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

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

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