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

мешает( X1 : Y, X2 : Y, Х3 : Y) :-

упоряд( X1, Х2, Х3), !.

мешает( X : Y1, X : Y2, X : Y3) :-

упоряд( Y1, Y2, Y3).

упоряд( N1, N2, N3) :-

N1 < N2, N2 < N3;

N3 < N2, N2 < N1.

коорд( 1). коорд( 2). коорд( 3). коорд( 4).

коорд( 5). коорд( 6). коорд( 7). коорд( 8).

% Предикаты целей

любая_поз( Поз).

ход_противника( б.._ ). % Противник ходит белыми

мат( Поз) :-

чей_ход( Поз, ч),

шах( Поз),

not разрход( Поз, _, _ ).

пат( Поз) :-

чей_ход( Поз, ч),

not шах( Поз),

not разрход( Поз, _, _ ).

уменьш_простр( Поз, КорнПоз) :-

простр( Поз, Пр),

простр( КорнПоз, КорнПр),

Пр < КорнПр.

ладья_под_боем( ЧейХод..Б..Л..Ч.._ ) :-

расст( Б, Л, P1),

расст( Ч, Л, Р2),

( ЧейХод = б, !, P1 > Р2 + 1;

ЧейХод = ч, !, P1 > Р2 ).

ближе_к_клетке( Поз, КорнПоз) :-

расст_до_клетки( Поз, P1),

расст_до_клетки( КорнПоз, Р2),

P1 < Р2.

расст_до_клетки( Поз, Мрасст) :-

% Манхеттеновское расстояние

бк( Поз, БК), % между БК и критической клеткой

кк( Поз, КК), % Критическая клетка

манх_расст( БК, КК, Мрасст).

раздел( _..Бх : Бу..Лх : Лу.. Чх : Чу.._ ) :-

упоряд( Бх, Лх, Чх), !;

упоряд( Бу, Лу, Чу).

l_конфиг( _..Б..Л..Ч.._ ) :- % L - конфигурация

манх_расст( Б, Ч, 2),

манх_расст( Л, Ч, 3).

не дальше_от_ладьи( _..Б..Л.._, _..Б1..Л1.._ ) :-

расст( Б, Л, P),

расст( Б1, Л1, P1),

P =< P1.

простр_больше_2( Поз) :-

простр( Поз, Пр),

Пр > 2.

наш_король_на_краю( _..X : Y.._ ) :-

% Белый король на краю

( X = 1, !; X = 8, !; Y = 1, !; Y = 8).

король_противника_на_краю( _..Б..Л..X : Y.._ ) :-

% Черный король на краю

( X = 1, !; X = 8, !; Y = 1, !; Y = 8).

короли_рядом( Поз) :- % Расстояние между королями < 4

бк( Поз, БК), чк( Поз, ЧК),

расст( БК, ЧК, P),

P < 4.

потеря_ладьи( _..Б..Л..Л.._ )- % Ладья взята

потеря_ладьи( ч..Б..Л..Ч.._ ) :-

сосед( Ч, Л), % Черный король напал на ладью

not сосед( Б, Л). % Белый король не защищает ладью

расст( X : Y, X1 : Y1, P) :- % Расстояние до короля

абс_разн( X, X1, Рх),

абс_разн( Y, Y1, Ру),

макс( Рх, Ру, P).

абс_разн( А, В, С) :-

А > В, !, С is A - В;

С is В - А.

макс( А, В, М) :-

А >= В, !, М = А;

М = В.

манх_расст( X : Y, X1 : Y1, P) :- % Манхеттеновское расстояние

абс_разн( X, X1, Рх),

абс_разн( Y, Y1, Ру),

P is Рх + Ру.

простр( Поз, Пр) :-

% Область, в которой "заперт" черный король

бл( Поз, Лх : Лу),

чк( Поз, Чх : Чу),

( Чх < Лх, СторонаХ is Лх - 1;

Чх > Лх, СторонаХ is 8 - Лх ),

( Чу < Лу, СторонаY is Лу - 1;

Чу > Лу, СторонаY is 8 - Лу ),

Пр is СторонаХ * СторонаY, !;

Пр = 64. % Ладья и черный король на одной линии

кк( _..Б..Лх : Лу.. Чх : Чу.._, Кх : Ку) :-

% Критическая клетка

( Чх < Лх, !, Кх is Лх - 1; Кх is Лх + 1),

( Чу < Лу, !, Ку is Лу - 1; Ку is Лу + 1).

% Процедуры для отображения позиций

отобр( Поз) :-

nl,

коорд( Y), nl,

коорд( X),

печ_фиг( X : Y, Поз),

fail.

отобр( Поз) :-

чей_ход( Поз, ЧХ), глуб( Поз, Г),

nl, write( 'ЧейХод='), write( ЧХ),

write( 'Глубина='), write( Г), nl.

печ_фиг( Клетка, Поз):-

бк( Поз, Клетка), !, write( 'Б');

бл( Поз, Клетка), !, write( 'Л');

чк( Поз, Клетка), !, write( 'Ч');

write( '.').

показать_ход( Ход) :-

nl, write( Ход), nl.

Рис. 15.10. Библиотека предикатов для окончания "король и ладья против короля".

Рассмотрите какой-нибудь другой простой эндшпиль, например "король и пешка против короля", и напишите для него программу на языке AL0 (вместе с определениями соответствующих предикатов).

• Игры двух лиц поддаются формальному представлению в виде И/ИЛИ-графов. Поэтому процедуры поиска в И/ИЛИ-графах применимы для поиска в игровых деревьях.

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

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