Читаем Prolog полностью

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

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

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

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

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

15. 5.    Знания о типовых ситуациях и механизм "советов"

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

15. 5. 1.    Цели и ограничения на ходы

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

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

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

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

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

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

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

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

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

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

15. 5. 2.    Выполнимость совета

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

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

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

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

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

корень дерева  Т  -  позиция  Р;

все позиции из  Т  удовлетворяют цели-поддержке;

все терминальные позиции из  Т   удовлетворяют главной цели (что, однако, неверно ни для одной внутренней вершины);

для каждой внутренней позиции игрока в дереве Т указан только один ход, причем он удовлетворяет ограничениям на ходы игрока;

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