Самостійне проектування

Резюме

Абс_разн( X, X1, Рх), абс_разн(Y, Y1, Ру), P is Рх + Ру.

Расст( X : Y, X1 : Y1, Р) :- % Відстань до короля абс_разн( X, X1, Рх),абс_разн( Y, Y1, Ру),макс( Рх, Ру, Р).

L_конфиг( _..Б..Л..Ч.._ ) :- % L - конфігурація манх_расст( Б, Ч, 2),манх_расст( Л, Ч, 3).

Расст_до_клетки( Поз, Мрасст) :- % Манхеттенська відстань бк( Поз, БК), % між БК і критичною кліткою кк( Поз, КК), % Критична клітка манх_расст( БК, КК, Мрасст).

Пат( Поз) :- чей_ход( Поз, ч),not шах( Поз),not разрход( Поз, _, _ ).

Мат( Поз) :- чей_ход( Поз, ч), шах( Поз),not разрход( Поз, _, _ ).

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

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

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

Мешает( X : Y1, X : Y2, X : Y3) :-упоряд( Y1, Y2, Y3).

Мешает( X1 : Y, X2 : Y, Х3 : Y) :-упоряд( X1, Х2, Х3), !.

Мешает( S, S1, S1) :- !.

Разрход( Поз, Ход, Поз1) :-ход( разреш, Поз, Ход, Поз1).

Ход( разреш, ч..Б..Л..Ч..Г, Ч-Ч1, б..Б..Л..Ч1..Г1) :-Г1 is Г + 1,сосед( Ч, Ч1),not шах( б..Б..Л..Ч1..Г1).

шах( _..Б..Лх : Лу..Чх : Чу.._ ) :-
сосед( Б, Чх : Чу); % Королі поряд
( Лх = Чх; Лу = Чу),
Лх : Лу \== Чх : Чу, % Нема взяття тури
not мешает( Лх : Лу, Б, Чх : Чу).

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

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

ход_противника( б.._ ). % Супротивник ходить білими

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

ладья_под_боем( ЧейХод..Б..Л..Ч.._ ) :-
расст( Б, Л, Р1),
расст( Ч, Л, Р2),
( ЧейХод = б, !, Р1 > Р2 + 1;
ЧейХод = ч, !, Р1 > Р2 ).

раздел( _..Бх : Бу..Лх : Лу.. Чх : Чу.._ ) :-
упоряд( Бх, Лх, Чх), !;
упоряд( Бу, Лу, Чу).

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

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

наш_король_на_краю( _..Х : Y.._ ) :-
% Білий король на краю
( X = 1, !; X = 8, !; Y = 1, !; Y = 8).

король_противника_на_краю( _..Б..Л..Х : Y.._ ) :-
% Чорний король на краю
( X = 1, !; X = 8, !; Y = 1, !; Y = 8).

короли_рядом( Поз) :- %Відстань між королями < 4
бк( Поз, БК), чк( Поз, ЧК),
расст( БК, ЧК, Р), Р < 4.

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

потеря_ладьи( ч..Б..Л..Ч.._ ) :-
сосед( Ч, Л), % Чорний король напав на туру
not сосед( Б, Л). % Білий король не захищає туру

абс_разн( А, В, С) :- А > В, !, С is A - В; С is В - А.

макс( А, В, М) :-А >= В, !, М = А;М = В.

манх_расст( X : Y, X1 : Y1, Р) :- % Манхеттенська

відстань

простр( Поз, Пр) :-
% Область, в якій "запертий" чорний король
бл( Поз, Лх : Лу),
чк( Поз, Чх : Чу),
( Чх < Лх, СторонаХis Лх - 1;
Чх > Лх, СторонаХis 8 - Лх ),
( Чу < Лу, СторонаY is Лу - 1;
Чу > Лу, СторонаY is 8 - Лу ),
Прis СторонаХ * СторонаY, !;
Пр = 64. % Тура і чорний король на одній лінії

§ Ігри двох осіб піддаються формалізації у формі І/Або-графів. Тому процедури пошуку в І/Або-графах застосовні для пошуку в ігрових деревах.

§ Простий алгоритм пошуку вглиб в ігрових деревах легко програмується, але для ігор, що представляють інтерес, він не ефективний. Більш реалістичний підхід - мінімаксний принцип у комбінації з оцінюючою функцією й пошуком, обмеженим по глибині.

§ Альфа-бета алгоритм є ефективною реалізацією мінімаксного принципу. Ефективність альфа-бета алгоритму залежить від порядку, у якому проглядаються варіанти ходів. Застосування альфа-бета алгоритму, у найкращому разі, зменшує коефіцієнт розгалуження дерева пошуку до значення, що є коренем квадратним від коефіцієнта розгалуження мінімаксного дерева пошуку.

§ В альфа-бета алгоритм можна внести ряд удосконалень. Серед них:

o продовження пошуку за межі обмеження по глибині аж до спокійних позицій,

o послідовне поглиблення й

o евристичне відсікання гілок.

§ Числова оцінка позицій є досить обмеженою формою подання знань про конкретну гру. Більш змістовний за своїми можливостями метод подання знань має передбачати внесення в програму знань про типові ситуації. Мова порад (Advice Language) реалізує такий підхід. На цій мові знання представляються в термінах цілей і засобів для їхнього досягнення.

§ У даній главі подано наступні програми: програмна реалізація мінімаксного принципу і альфа-бета процедури, інтерпретатор мови AL0 і таблиця порад для ендшпілю "король і тура проти короля".

§ Були введені й обговорені наступні поняття:

ігри двох осіб з повною інформацією

ігрові дерева

оцінююча функція, мінімаксний принцип

статичні оцінки, робочі оцінки

альфа-бета алгоритм

послідовне заглиблення,

евристичне відсікання,

евристики для виявлення спокійних позицій

Мови порад

цілі, обмеження, елементарні поради, таблиця порад

1. Напишіть програму для якої-небудь простої гри (такої, як ним), що використає спрощений алгоритм пошуку в І/Або-дереві.

2. Розгляньте яку-небудь гру двох осіб (наприклад, який-небудь нетривіальний варіант хрестиків-нуликів). Напишіть відношення, що задають правила цієї гри (дозволені ходи й термінальні позиції). Запропонуйте статичну оцінюючу функцію, придатну для використання в ігровій програмі, заснованій на альфа-бета алгоритмі.

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