Назад | Содержание| Вперёд 15. 4. Минимаксные игровыепрограммы: усовершенст...

Назад | Содержание| Вперёд

15. 4.    Минимаксные игровыепрограммы: усовершенствования и ограничения

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

Для оценки терминальных

поисковых позиций использоватьподобранную специально для данной игры

оценочнуюфункцию

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

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

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

.

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

.

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

он облегчает контроль времени: в момент, когда время истекает, всегда имеется некоторый ход - лучший из всех, найденных к настоящему моменту;

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

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

Для наших программ, основанных на описанной

выше схеме, существует проблема,известная как

"эффект горизонта"

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

обе

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

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

Знания в минимаксных игровых программах имеютследующие три основные формы:

оценочная функция

эвристики для отсечения ветвей

эвристики для распознавания спокойных позиций

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

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

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