И. Братко
Программирование на языке Пролог
для искусственного интеллекта
*** 1990 ***
|
ФPAГMEHT КНИГИ (...) Пусть N - число терминальных поисковых позиций, для которых вычислялись статические оценки алгоритмом минимаксного полного перебора. Было доказано, что в лучшем случае, когда самые сильные ходы всегда рассматриваются первыми, альфа-бета алгоритм вычисляет статические оценки только для N позиций.
Этот результат имеет один практический аспект, связанный с проведением турниров игровых программ. Шахматной программе, участвующей в турнире, обычно дается неиоторое определенное время для вычисления очередного хода, и доступная программе глубина поиска зависит от этого времени. Альфа-бета алгоритм сможет пройти при поиске вдвое глубже по сравнению с минимаксным полным перебором, а опыт показывает, что применение той же оценочной функции, но на большей глубине приводит к более сильной игре. Экономию, получаемую за счет применения альфа-бета алгоритма, можно также выразить в терминах более эффективного коэффициента ветвления дерева поиска (т. е. числа ветвей, исходящих из каждой внутренней вершины). Пусть игровое дерево имеет единый коэффициент ветвления, равный Ь. Благодаря эффекту отсечения альфа-бета алгоритм просматривает только некоторые из существующих ветвей и тем самым уменьшает коэффициент ветвления. В результате коэффициент Ь превратится в А (в лучшем случае). В шахматных программах, использующих альфа-бета алгоритм, достигается коэффициент ветвления, равный 6, при наличии 30 различных вариантов хода в каждой позиции. Впрочем, на этот результат можно посмотреть и менее оптимистично: несмотря на применение альфа-бета алгоритма, после каждого продвижения вглубь на одни полуход число терминальных поисковых вершин увеличивается примерно в 6 раз. Проект Рассмотрите какую-нибудь игру двух лиц (например, какой-нибудь нетривиальный вариант крестиков-ноликов). Напишите отношения, задающие правила этой игры (разрешенные ходы и терминальные позиции). Предложите статическую оценочную функцию, пригодную для использования в игровой программе, основанной на альфа-бета алгоритме. 15.4. Минимаксные игровые программы: усовершенствования и ограничения Минимаксный принцип и альфа-бета алгоритм лежат в основе многих удачных игровых программ, чаще всего шахматных. Общая схема подобной программы такова: произвести альфа-бета поиск из текущей позиции вплоть до некоторого предела по глубине (диктуемого временными ограничениями турнирных правил). Для оценки терминальных поисковых позиций использовать подобранную специально для данной игры оценочную функцию. Затем выполнить на игровой доске наилучший ход, найденный альфа-бета алгоритмом, принять ответный ход противника и запустить тот же цикл с начала. Таким образом, две основных составляющих игровой программы - это альфа-бета алгоритм и эвристическая оценочная функция. Для того, чтобы создать действительно хорошую программу для такой сложной игры, как шахматы, необходимо внести в эту базовую схему много различных усовершенствований. Ниже приводится краткое описание некоторых из стандартных приемов. Многое зависит от оценочной функции. Если бы мы располагали абсолютно точной оценочной функцией, мы могли бы ограничить поиск рассмотрением только непосредственных преемников текущей позиции, фактически исключив перебор. Но для таких игр, как шахматы, любая оценочная функция, имеющая практически приемлемую вычислительную сложность, по необходимости будет всего лишь эвристической оценкой. Такая оценка базируется на «статических» свойствах позиции (например, на количестве фигур) и в одних позициях работает надежнее, чем в других. Допустим, например, что мы имеем именно такую оценочную функцию, основанную иа соотношении материала, и представим себе позицию, в которой у белых лишний конь. Ясно, что оценка будет в пользу белых. Здесь все в порядке, если позиция «спокойная» и черные не располагают какой-либо сильной угрозой. Но, с другой стороны, если иа следующем ходу черные могут взять белого ферзя, то такая оценка может привести к фатальному просмотру из-за своей неспособности к динамическому восприятию позиции. Очевидно, что в спокойных позициях мы можем доверять такой статической оценке в большей степени, чем в активных позициях, когда с каждой из сторон имеются непосредственные угрозы взятия фнгур. Поэтому статическую, оценку Следует использовать только для спокойных позиций. Что же касается активных позиций, то здесь существует такой стандартный прием: следует продолжить поиск из активной позиции за пределы ограничения по глубине и продолжать его до тех пор, пока не встретится спокойная позиция. В частности, таким образом производится просчет разменов фигур в шахматах. Еще одно усовершенствование - эвристическое отсечение (ветвей). Целью его является достижение большей предельной глубины поиска за счет отбрасывания менее перспективных продолжений. Этот метод позволяет отсекать ветви в дополнение к тем, которые отсекаются самим альфа-бета алгоритмом. В связи с этим возникает риск пропустить какое-нибудь хорошее продолжение и неправильно вычислить минимаксную оценку. Существует еще одни прием, называемый последовательным углублением. Программа многократно выполняет альфа-бета поиск сначала до некоторой небольшой глубины, а затем, увеличивая предел по глубине при каждой итерации. Процесс завершается, когда истекает время, отведенное для вычисления очередного хода. Выполняется иаилучший ход, найденный при наибольшей глубине, достигнутой программой. Этот метод имеет следующие преимущества: • он облегчает контроль времени: в момент, когда время истекает, всегда имеется некоторый ход - лучший из всех, найденных к настоящему моменту; • минимаксные оценки, вычисленные во время предыдущей итерации, можно, использовать для предварительного упорядочивания позиций в следующей итерации, что помогает альфа-бета алгоритму следовать стратегии «самые сильные ходы - первыми». Метод последовательного углубления влечет за собой некоторые накладные расходы (из-за повторного поиска в верхней части игрового дерева), но они незначительны по сравнению с суммарными затратами. Для наших программ, основанных на описанной выше схеме, существует проблема, известная как «эффект горизонта». Представьте себе шахматную позицию, в которой программе грозит неминуемая потеря коня, однако эту потерю можно отложить, пожертвовав какую-либо менее ценную фигуру, скажем пешку. Эта немедленная жертва сможет отодвинуть потерю коня за пределы доступной глубины поиска (за «горизонт» программы). Не видя грозящей опасности, программа отдаст предпочтение продолжению с жертвой пешки, чтобы избежать быстрой гибели своего коня. В действительности программа потеряет обе фигуры - и пешку (без необходимости), и коня. Эффект горизонта можно несколько смягчить за счет углубления поиска вплоть до спокойных позиций. Существует, однако, более фундаментальное ограничение на возможности минимаксных игровых программ, проистекающее нз той ограниченной формы представления знаний, которая в них используется. Это становится особенно заметным при сравнении лучших шахматных программ с шахматными мастерами (людьми). Хорошая программа просматривает миллионы (и даже больше) позиций, прежде чем принимает решение об очередном ходе. Психологические опыты показали, что шахматные мастера, как правило, просматривают десятки (максимум, несколько сотеи) позиций. Несмотря на эту явно меньшую производительность, мастера-шахматисты обыгрывают программы без особых усилий. Преимущество их состоит в их знаниях, значительно превосходящих знания шахматных программ. Игры между машинами и сильными шахматистами показали, что огромное превосходство в вычислительной мощности не способно скомпенсировать недостаток знаний. Знания в минимаксных игровых программах имеют следующие три основные формы: • оценочная функция • эвристики для отсечения ветвей • эвристики для распознавания спокойных позиций Оценочная функция сводит все разнообразные аспекты игровой ситуации к одному числу, и это упрощение может нанести вред. В противоположность этому хороший игрок обладает пониманием позиции, охватывающим многие «измерения». Вот пример из области шахмат: оценочная функция оценивает позицию как равную и выдает значение 0. Оценка той же позиции, данная мастером-шахматнстом, может быть значительно более информативной, а также может указывать на дальнейший ход игры, например: у белых лишняя пешка, но черные имеют неплохие атакующие возможности, что компенсирует материальный перевес, следовательно, шансы равны. Минимаксные шахматные программы часто хорошо проявляют себя в острой тактической борьбе, когда решающее значение имеет точный просчет форсированных вариантов. Их слабости обнаруживаются в спокойных позициях, так как они не способны к долговременному планированию, преобладающему при медленной, стратегической игре. Из-за отсутствия плана создается внешнее впечатление, что программа все время перескакивает с одной идеи иа другую. Особенно это заметно в эндшпилях. В оставшейся части главы мы рассмотрим еще один подход к программированию игр, основанный иа внесении в программу зиаиий о типовых ситуациях при помощи так называемых «советов». 15.5.Знания о типовых ситуациях и механизм «советов» В этом разделе рассматривается метод представления знаний о конкретной игре с использованием семейства Языков Советов. Языки Советов (Advice Languages) дают возможность пользователю декларативным способом описывать, какие идеи следует использовать в тех или иных типовых ситуациях. Идеи формулируются в терминах целей и средств, необходимых для нх достижения. Интерпретатор Языка Советов определяет при помощи перебора, какая идея «работает» в данной ситуации. 15.5.1. Цели и ограничения на коды Основное понятие Языка Советов - «элементарный совет». Элементарный совет содержит указание о том, что следует делать (или пытаться делать) в некоторой типовой ситуации. Совет выражается в терминах тех целей, которые необходимо достичь, и тех средств, которые следует применять для этого. Мы называем участников игры «игроком» и «противником»; совет всегда относится к «игроку». Каждый элементарный совет имеет следующие четыре составные части; • главная цель: цель, к которой нужно стремиться; • цель-поддержка: цель, которая должна постоянно удовлетворяться в процессе достижения главной цели; • ограничения на ходы игрока: предикат, определяющий некоторое подмножество ходов из всех разрешенных ходов игрока (ходы, представляющие интерес с точки зрения достижения указанных целей). • ограничения на ходы противника: предикат, выбирающий ходы, которые должен рассмотреть противник (ходы, препятствующие достижению указанных целей). Рассмотрим, например, шахматный эндшпиль «король и пешка против короля». Здесь применима следующая очевидная идея: провести пешку в ферзи, продвигая ее вперед. В форме совета это выражается так: • главная цель: провести пешку; • цель-поддержка: не потерять пешку; • ходы игрока: продвигать пешку; • ходы противника: приближаться королем к пешке. • В даннной главе мы составили следующие программы: программная реализация минимаксного принципа и альфа-бета процедуры, интерпретатор языка AL0 и таблица советов для окончания «король и ладья против короля». • Были введены и обсуждены следующие понятия: игры двух лиц с полной информацией игровые деревья оценочная функция, минимаксный принцип статические оценки, рабочие оценки альфа-бета алгоритм последовательное углубление, эвристическое отсечение, эвристики для обнаружения спокойных позиций Языки Советов цели, ограничения, элементарные советы, таблица советов Литература Минимаксный принцип, реализованный в форме альфа-бета алгоритма, - это наиболее популярный метод в игровом программировании. Особенно часто он применяется в шахматных программах. Минимаксный принцип был впервые предложен Шенноном (Shannon 1950). Возникновение и становление альфа-бета алгоритма имеет довольно запутанную историю. Несколько исследователей независимо друг от друга открыли либо реализовали этот метод полностью или частично. Эта интересная история описана в статье Knuth and Moore (1978). Там же приводится более компактная формулировка альфа-бета алгоритма, использующая вместо минимаксного принципа принцип «него-макса» ("neg-max" principle), и приводится математический анализ производительности алгоритма. Наиболее полный обзор различных минимаксных алгоритмов вместе с их теоретическим анализом содержится в книге Pearl (1984). Существует еще один интересный вопрос, относящийся к минимаксному принципу. Мы знаем, что статическим оценкам следует доверять только до некоторой- степени. Можно ли считать, что рабочие оценки являются более надежными, чем исходные статические оценки, из которых они получены? В книге Pearl (1984) собран ряд математических результатов, имеющих отношение к ответу иа этот вопрос. Приведенные в этой книге результаты, касающиеся распространения ошибок по минимаксному дереву, объясняют, в каких случаях и почему минимаксный принцип оказывается полезным. Сборник статей Вгатег (1983) Охватывает несколько аспектов игрового программирования. Frey (1983) - хороший сборник статей по шахматным программам. Текущие разработки в области машинных шахмат регулярно освещаются в серии Advances in Computer Chess и в журнале ICCA. Метод Языка Советов, позволяющий использовать знания о типовых ситуациях, был предложен Д. Мики. Дальнейшее развитие этого метода отражено в Bratko and Michi (1980 a,b) и Bratko (1982, 1984, 1985). Программа для игры в эндшпиле «король и ладья против короля», описанная в этой главе, совпадает с точностью до незначительных модификаций с таблицей советов, корректность которой была математически доказана в статье Bratko (1978). Ван Эмден также запрограммировал эту таблицу советов на Прологе (van Emden 1982). |
