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

       

Проект



Проект

Напишите программу для какой-нибудь простой игры (такой, как ним), использующую упрощенный алгоритм войска в И / ИЛИ-дереве.



Проект

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





Проект

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

line();

% Библиотека предикатов для окончания
% "король и ладья против короля"

% Позиция представлена стуктурой:
% ЧейХод..Бх : Бу..Лх : Лу..Чх : Чу..Глуб
% ЧейХод - с чьей стороны ход в этой позиции ('б' или 'ч')
% Бх, Бу - координаты белого короля
% Лх, Лу - координаты белой ладьи
% Чх, Чу - координаты черного короля
% Глуб - глубина, на которой находится эта позиция в дереве
% поиска

% Отношения выбора элементов позиции

чей_ход( ЧейХод.._, ЧейХод).
        бк( _..БК.._, БК).
                                        % Белый король
        бл( _.._..БЛ.._, БЛ).                                     % Белая ладья
        чк( _.._.._..ЧК.._, ЧК).                                % Черный король
        глуб( _.._.._.._..Глуб, Глуб).

        восст_глуб( ЧХ..Б..Л..Ч..Г, ЧХ..Б..Л..Ч..0).
                                           % Формируется копия позиции, глубина устанавливается в 0

% Некоторые отношения между клетками доски

        сосед_чсл( N, N1) :-             % Соседнее число "в пределах доски"
                ( N1 is N + 1;
                  N1 is N - 1 ),
                внутри( N1).

        внутри( N) :-
                N > 0, N < 9.

        сосед_диаг( X : Y, X1 : Y1) :-
                                    % Соседние клетки по диагонали
                сосед_чсл( X, X1 ), сосед_чсл( Y, Y1).

        сосед_верт( X : Y, X : Y1) :-
                                    % Соседние клетки по вертикали
                сосед_чсл( Y, Y1).

        сосед_гор( X : Y, X1 : Y) :-
                                    % Соседние клетки по горизонтали
                сосед_чсл( X, X1).

        сосед( S, S1) :-
                                    % Соседние клетки (предпочтение - диагонали)
                сосед_диаг( S, S1);
                сосед_гор( S, S1);
                сосед_верт( S, S1).

        конец_игры( Поз) :-
                мат( Поз).

% Предикаты, ограничивающие ходы
% Специализированное генераторы ходов вида:
% ход( Ограничение, Поз, Ход, Поз1)

        ход( глубина < Макс, Поз, Ход, Поз1) :-
                глуб( Поз, Г),
                Г < Макс,  !.

        ход( глубина = Г, Поз, Ход, Поз1) :-
                глуб( Поз, Г),  !.

        ход( сначала диаг, б..Б..Л..Ч..Г, Б-Б1,
                                            ч..Б1..Л..Ч..Г1) :-
                Г1 is Г + l,
                сосед( Б, Б1),

                                    % "сосед" порождает сначала диагональные ходы
                not сосед( Б1, Ч),                                 % Не попасть под шах
                Б1 \== Л.                                               % Не столкнуться с ладьей

        ход( ход ладьей, б..Б..Лх : Лу..Ч..Г, Лх : Лу-Л,
                                                                ч..Б..Л..Ч..Г1) :-
                Г1 is Г + 1,
                коорд( I),
                                              % Число между 1 и 8
                ( Л = Лх : I; Л = I : Лу),
                                    % По горизонтали или по вертикали
                Л \== Лх : Лу,                                      % Обязательно двигаться
                not мешает( Лх : Лу, Б, Л).                % Мешает белый король

        ход( ход_шах, Поз, Л-Лх : Лу, Поз1) :-
                бл( Поз, Л),
                чк( Поз, Чх : Чу),
                ( Лх = Чх; Лу = Чу),

                                    % Ладья и черный король на одной линии
                ход( ход_ладьей, Поз, Л-Лх : Лу, Поз1).

        ход( разреш, б..П, М, П1) :-
                ( Огр = сначала_диаг; Огр = ход ладьей),
                ход( Огр, б..П, М, П1).

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

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

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

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

        мешает( 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 разрход( Поз, _, _ ).

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

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

        ближе_к_клетке( Поз, КорнПоз) :-
                расст_до_клетки( Поз, Р1),
                расст_до_клетки( КорнПоз, Р2),
                Р1 < Р2.

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

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

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

        не дальше_от_ладьи( _..Б..Л.._, _..Б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 сосед( Б, Л).              % Белый король не защищает ладью

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

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

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

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

                абс_разн( 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.

line();





Содержание раздела