Искусственный интеллект и экспертные системы. Курс лекций [Автор неизвестен] (doc) читать постранично, страница - 16
- Искусственный интеллект и экспертные системы. Курс лекций 115 Кб скачать: (doc) - (doc+fbd) читать: (полностью) - (постранично) - Автор неизвестен
Книга в формате doc! Изображения и текст могут не отображаться!
[Настройки текста] [Cбросить фильтры]
всегда выбирает ход с максимальной оценкой; в противоположность ему МИН всегда выбирает ход с минимальной оценкой. Пользуясь этим принципом (минимаксным принципом) и зная значения оценок для всех вершин "подножья" дерева поиска, можно определить оценки всех остальных вершин дерева. На рис. 2.11 показано, как это делается. На этом рисунке видно, что уровни позиций с ходом МАКСа чередуются с уровнями позиций с ходом МИНа. Оценки вершин нижнего уровня определяются при помощи оценочной функции. Оценки всех внутренних вершин можно определить, двигаясь снизу вверх от уровня к уровню, пока мы не достигнем корневой вершины. в результате, как видно на рис. 2.11, оценка корня оказывается равной 4, и, соответственно, лучшим ходом МАКСа из позиции a - a-b. Лучший ответ МИНа на этот ход - b-d, и т.д. Эту последовательность ходов называют также основным вариантом. Основной вариант показывает, какова "минимаксно-оптимальная" игра для обоих участников. Обратите внимание на то, что оценки всех позиций, входящих в основной вариант совпадают.
Рис. 2.11. Статический (нижний уровень) и минимаксные рабочие
оценки вершин дерева поиска. Выделенные ходы образуют
основной вариант, т. е. минимаксно-оптимальную игру
с обеих сторон
Мы различаем два вида оценок: оценки вершин нижнего уровня и оценки внутренних вершин (рабочие оценки). Первые из них называют также "статическими", так как они вычисляются при помощи "статической" оценочной функции, в противоположность рабочим оценкам, получаемых "динамически" при распространении статических оценок вверх по дереву.
Правила распространения оценок можно сформулировать следующим образом. Будем обозначать статическую оценку позиции P через v(P), а ее рабочую оценку - через V(P). Пусть P1, P2, … Pn - разрешенные преемники позиции P. Тогда соотношения между статическими и рабочими оценками можно записать так:
V(P) = v(P)
если P - терминальная вершина позиции дерева поиска (n=0);
V(P) = V(Pi)
если P - позиция с ходом МАКСа;
V(P) = V(Pi)
если P - позиция с ходом МИНа.
Приведем упрощенную программу на Прологе, вычисляющую минимаксную рабочую оценку для некоторой заданной позиции.
% Минимаксная процедура: minimax(P,GP,V)
% P - позиция, V - ее минимаксная оценка;
% лучший ход из позиции P ведет в позицию GP
minimax(P,GP,V):-
'ходы'(P,List),!, % List - список разрешенных ходов
'лучшая'(List,GP,V);
'статическая оценка'(P,V). % позиция P не имеет преемников
'лучшая'([P],P,V):-
minimax(P,_,V),!.
'лучшая'([P1|List],GP,GV):-
minimax(P1,_,V1),
'лучшая'(List,P2,V2),
'выбор'(P1,V1,P2,V2,GP,GV).
'выбор'(P0,V0,P1,V1,P0,V0):-
'ход МИНа'(P0),V0>V1,!;
'ход МАКСа'(P0),V0
Рис. 2.11. Статический (нижний уровень) и минимаксные рабочие
оценки вершин дерева поиска. Выделенные ходы образуют
основной вариант, т. е. минимаксно-оптимальную игру
с обеих сторон
Мы различаем два вида оценок: оценки вершин нижнего уровня и оценки внутренних вершин (рабочие оценки). Первые из них называют также "статическими", так как они вычисляются при помощи "статической" оценочной функции, в противоположность рабочим оценкам, получаемых "динамически" при распространении статических оценок вверх по дереву.
Правила распространения оценок можно сформулировать следующим образом. Будем обозначать статическую оценку позиции P через v(P), а ее рабочую оценку - через V(P). Пусть P1, P2, … Pn - разрешенные преемники позиции P. Тогда соотношения между статическими и рабочими оценками можно записать так:
V(P) = v(P)
если P - терминальная вершина позиции дерева поиска (n=0);
V(P) = V(Pi)
если P - позиция с ходом МАКСа;
V(P) = V(Pi)
если P - позиция с ходом МИНа.
Приведем упрощенную программу на Прологе, вычисляющую минимаксную рабочую оценку для некоторой заданной позиции.
% Минимаксная процедура: minimax(P,GP,V)
% P - позиция, V - ее минимаксная оценка;
% лучший ход из позиции P ведет в позицию GP
minimax(P,GP,V):-
'ходы'(P,List),!, % List - список разрешенных ходов
'лучшая'(List,GP,V);
'статическая оценка'(P,V). % позиция P не имеет преемников
'лучшая'([P],P,V):-
minimax(P,_,V),!.
'лучшая'([P1|List],GP,GV):-
minimax(P1,_,V1),
'лучшая'(List,P2,V2),
'выбор'(P1,V1,P2,V2,GP,GV).
'выбор'(P0,V0,P1,V1,P0,V0):-
'ход МИНа'(P0),V0>V1,!;
'ход МАКСа'(P0),V0
Последние комментарии
3 часов 38 минут назад
3 часов 58 минут назад
4 часов 53 минут назад
7 часов 51 минут назад
7 часов 52 минут назад
8 часов 49 секунд назад