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