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


         

и зная значения оценок для


принципом) и зная значения оценок для всех вершин "подножья" дерева поиска, можно определить оценки всех остальных вершин дерева. На рис. 15.2 показано, как это делается. На этом рисунке видно, что уровни позиций с ходом МАКС'а чередуются с уровнями позиций с ходом МИН'а. Оценки вершин нижнего уровня определяются при помощи оценочной функции. Оценки всех внутренних вершин можно определить, двигаясь снизу вверх от уровня к уровню, пока мы не достигнем корневой вершины. В результате, как видно из рис. 15.2, оценка корня оказывается равной 4, и, соответственно, лучшим ходом МАКС'а из позиции  а  -  a-b. Лучший ответ МИН'а на этот ход  -  b-d, и т.д. Эту последовательность ходов называют также основным вариантом. Основной вариант показывает, какова "минимаксно-оптимальная" игра для обоих участников. Обратите внимание на то, что оценки всех позиций, входящих в основной вариант, совпадают.



Рис. 15. 2.  Статические (нижний уровень) и минимаксные рабочие

оценки вершин дерева поиска. Выделенные ходы образуют основной

вариант, т. е. минимаксно-оптимальную игру с обеих сторон.

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

Правила распространения оценок можно сформулировать следующим образом. Будем обозначать статическую оценку позиции  Р

  через  v( P),  а ее рабочую оценку - через   V( Р).  Пусть  Р1,   ...,  Рn  -  разрешенные преемники позиции  Р.  Тогда соотношения между статическими и рабочими оценками можно записать так:

        V( Р)  =  v( P)

если  Р  -  терминальная позиция дерева поиска (n=0)


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