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

Резюме

Абс_разн(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),
расст_до_клетки(КорнПоз, Р2),
Р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. % Тура і чорний король на одній лінії

кк(_..Б..Лх: Лу.. Чх: Чу.._, Кх: Ку):-
% Критична клітка
(Чх < Лх,!, Кх 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мови порад

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

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

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

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

Дата добавления: 2014-01-04