Prolog

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

        V( Р)  =  v( P)

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

        V( Р)  =  max V( Р_i )

                           ⁱ

если  P  -  позиция с ходом МАКС'а

        V( Р)  =  min V( Р_i )

                           ⁱ

если  Р  -  позиция с ходом МИН'а

% Минимаксная процедура: минимакс( Поз, ЛучшПоз, Оц)

% Поз - позиция, Оц - ее минимаксная оценка;

% лучший ход из Поз ведет в позицию ЛучшПоз

        минимакс( Поз, ЛучшПоз, Оц) :-

                ходы( Поз, СписПоз),  !,

                                        % СписПоз - список разрешенных ходов

                лучш( СписПоз, ЛучшПоз, Оц);

                стат_оц( Поз, Оц).                 % Поз не имеет преемников

        лучш( [Поз], Поз, Оц) :-

                минимакс( Поз, _, Оц),  !.

        лучш( [Поз1 | СписПоз], ЛучшПоз, ЛучшОц) :-

                минимакс( Поз1, _, Оц1),

                лучш( СписПоз, Поз2, Оц2),

                выбор( Поз1, Оц1, Поз2, Оц2, ЛучшПоз, ЛучшОц).

        выбор( Поз0, Оц0, Поз1, Оц1, Поз0, Оц0) :-

                ход_мина( Поз0), Оц > Оц1,  !;

                ход_макса( Поз0), Оц < Оц1,  !.

        выбор( Поз0, Оц0, Поз1, Оц1, Поз1, Оц1).

Рис. 15. 3.  Упрощенная реализация минимаксного принципа.

Программа на Прологе, вычисляющая минимаксную рабочую оценку для некоторой заданной позиции, показана на рис. 15.3. Основное отношение этой программы -

        минимакс( Поз, ЛучшПоз, Оц)

где Оц  -  минимаксная оценка позиции Поз, а ЛучшПоз - наилучшая позиция-преемник позиции Поз (лучший ход, позволяющий достигнуть оценки Оц). Отношение

        ходы( Поз, СписПоз)

задает разрешенные ходы игры: СписПоз - это список разрешенных позиций-преемников позиции Поз. Предполагается, что цель ходы имеет неуспех, если Поз является терминальной поисковой позицией (листом дерева поиска). Отношение

        лучш( СписПоз, ЛучшПоз, ЛучшОц)