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

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

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