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

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

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

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

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

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

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

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

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

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

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

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

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

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

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