Программирование на языке Пролог для искусственного интеллекта

отведенное для вычисления очередного хода. Выполняется наилучший ход, найденный при наибольшей глубине, достигнутой программой. Этот метод имеет следующие преимущества:

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

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

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

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

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

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

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

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

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

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

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

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

15.5. Знания о типовых ситуациях и механизм 'советов'

В этом разделе рассматривается метод представления знаний о конкретной игре с использованием семейства Языков Советов. Языки Советов (Advice Languages) дают возможность пользователю декларативным способом описывать, какие идеи следует использовать в тех или иных типовых ситуациях. Идеи формулируются в терминах целей и средств, необходимых для их достижения. Интерпретатор Языка Советов определяет при помощи перебора, какая идея 'работает' в данной ситуации.

15.5.1. Цели и ограничения на ходы

Основное понятие Языка Советов — 'элементарный совет'. Элементарный совет содержит указание о том, что следует делать (или пытаться делать) в некоторой типовой ситуации. Совет выражается в терминах тех целей, которые необходимо достичь, и тех средств, которые следует применять для этого. Мы называем участников игры 'игроком' и 'противником'; совет всегда относится к 'игроку'. Каждый элементарный совет имеет следующие четыре составные части:

• главная цель: цель, к которой нужно стремиться;

• цель-поддержка: цель, которая должна постоянно удовлетворяться в процессе достижения главной цели;

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

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

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

• главная цель: провести пешку;

• цель-поддержка: не потерять пешку;

• ходы игрока: продвигать пешку;

• ходы противника: приближаться королем к пешке. 

15.5.2. Выполнимость совета

Мы говорим, что элементарный совет выполним в данной позиции, если игрок может форсированным образом достигнуть главной цели, указанной в совете, при условии, что:

(1) ни разу не нарушается цель-поддержка;

(2) все ходы игрока удовлетворяют наложенным на них ограничениям;

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

С выполнимостью элементарного совета связано понятие форсированного дерева. Форсированное дерево задает детальную стратегию, которая гарантирует достижение главной цели при выполнении всех ограничений, содержащихся в элементарном совете. Таким образом, форсированное дерево указывает, как именно должен ходить игрок при любых ответах противника. Более точно, форсированное дерево T для заданной позиции P и элементарного совета А есть такое поддерево