Технология разработки нерекурсивных правил Задание
 Скачать 0.5 Mb.
|
|
Технология разработки нерекурсивных правил Задание: Шахматы. Варианты взятия фигуры ладьей по горизонтали. Исходные данные: коды всех фигур, их цвет и координаты (поле 1-8 на A-H), код ходящей ладьи, её цвет и её исходные координаты (поле 1-8 на A-H). Результат: код ходящей ладьи, ее цвет и её новые координаты (поле 1-8 на A-H), код взятой фигуры. Интерпретация задачи По условиям задачи разработку программы будем проводить, используя схему шахматной доски с расстановкой фигур, представленной на рисунке. Предположим, что на n-м ходу игры возникла следующая ситуация.  Наименования фигур могут быть следующими: пешка, ферзь, король, конь, ладья, слон (согласно правилам шахмат). Идентифицировать каждую фигуру будем по ее уникальному обозначению. Количество элементов в схеме не регламентируем.  Формирование и тестирование исходных данных Совокупность аргументов каждого элемента объединим в один терм пользовательской структуры с именем фигура. Опишем эту пользовательскую структуру в области предикатов с указанием типов всех её аргументов. Опишем фигуры. Каждая из них характеризуется своим набором аргументов: наименованием, обозначением, цветом, координатой по горизонтали (1-8) и координатой по вертикали (1-8). Например, факт 1 (рис.2) читается так, поле содержит фигуру с наименованием пешка, обозначением п1, цветом черный, координатой по горизонтали 6 и координатой по вертикали 6. В базе фактов и правил запишем все 14 фактов, соответствующих введенному пользовательскому предикату и описывающих каждую из фигур. Последовательность записи аргументов в пользовательской структуре фигура строго соответствует типу аргумента, указанному в области предикатов. Последовательность записи фактов в базе фактов и правил произвольна. PREDICATES nondeterm фигура (symbol, symbol, symbol, integer, integer) CLAUSES % фигуры фигура (пешка, п1, черный, 6, 6). %факт 1 фигура (пешка, п2, черный, 4, 5). %факт 2 фигура (пешка, п3, белый, 8, 4). %факт 3 фигура (пешка, п4, белый, 3, 3). %факт 4 фигура (конь, кн1, черный, 1, 7). %факт 5 фигура (конь, кн2, белый, 2, 6). %факт 6 фигура (слон, с1, черный, 5, 7). %факт 7 фигура (слон, с2, белый, 6, 4). %факт 8 фигура (ладья, л1, белый, 8, 5). %факт 9 фигура (ладья, л2, черный, 3, 4). %факт 10 фигура (ладья, л3, белый, 4, 1). %факт 11 фигура (ферзь, ф1, черный, 4, 8). %факт 12 фигура (король, кр1, черный, 6, 8). %факт 13 фигура (король, кр2, белый, 5, 1). %факт 14 GOAL фигура (пешка, п1, черный, 6, 6). %запрос 1 Сформируем различные виды запросов к программе:
По количеству целей запросы делят на простые запросы, состоящие из одной цели (запросы 1, 2, 5, 6, 7) и запросы составные, которые содержат две цели или более (запросы 3, 4, 8). По наличию в целях именованных переменных классифицируют запросы, на не содержащие именованные переменные - могут иметь решения или истина, или ложь (запросы 1-4), и запросы с именованными переменными - указываются конкретизации именованных переменных (запросы 5-8). Результаты выполнения запросов к программе:
Проанализируем пошаговое выполнение программы для нескольких запросов. Запрос 1 является простым запросом, так как состоит из одной цели. Для проверки цели на истинность необходимо сопоставить ее с утверждениями базы фактов и правил. В программе содержится всего 14 утверждений. Шаг 1-й. Сопоставим цель с фактом 1. Цель содержит структуру с именем фигура. Первый факт также содержит структуру. Сопоставляем их по правилу сопоставления структур. Сопоставляем имена структур (функторы) по правилу сопоставления констант. Имена у структур тождественны, поэтому результат сопоставления имен – истина. Проверяем арность структур, то есть количество аргументов у каждой из них. Число аргументов у структур – 5. Результат проверки по арности – истина. Сопоставляем соответствующие аргументы структур. Аргументы сопоставляемых структур – константы, поэтому используем правило сопоставления констант. Атом пешка цели сопоставляем с атомом пешка утверждения. Результат сопоставления – истина. Атом п1 цели сопоставляем с атомом п1 утверждения. Результат – также истина. Атом цели черный сопоставляем с атомом утверждения черный. Результат – истина. Сопоставляем числа 6 и 6 цели с числами 6 и 6 утверждения соответственно. Сопоставляемые константы тождественны. Результат сопоставления всех аргументов – истина. Сопоставили цель с утверждением факта 1. Получили результат - истина. Дальнейший перебор утверждений прекращается, так как уже достигли положительного результата. Выполнение программы прекращается. Последующие шаги не выполняются. Ответ – yes. Запрос 6 является простым запросом с именованной переменной в качестве аргумента структуры. Шаг 1-й. Сопоставляем цель с фактом 1. Сопоставляем структуру цели со структурой утверждения по правилу сопоставления структур. Имена структур тождественны (фигура ≡ фигура). Арности сопоставляемых структур равны. Первый аргумент структуры цели не тождественен первому аргументу структуры утверждения (ладья ≠ пешка). Получили результат – ложь. Прекращаем дальнейшее сравнение. Шаг 2-й. Сопоставляем цель с фактом 2. Получили результат – ложь (по аналогии с шагом 1). Тот же самый результат будет для фактов 3-8 (шаги 3-8). Шаг 9-й. Сопоставим цель с фактом 9. Сопоставляем структуру цели со структурой утверждения по правилу сопоставления структур. Имена структур тождественны (фигура ≡ фигура). Арности сопоставляемых структур равны. Первый аргумент структуры цели тождественен первому аргументу структуры утверждения (ладья ≡ ладья). Второй аргумент структуры цели с именем Обозначение (переменная в неконкретизированном состоянии) сопоставляем с соответствующим аргументом утверждения – с атомом л1 по правилу сопоставления именованных переменных в неконкретизированном состоянии. Результат сопоставления – истина, при этом происходит конкретизация переменной Обозначение, которая приобретает значение равное л1. Третий аргумент структуры цели тождественен третьему аргументу структуры утверждения (белый ≡ белый). Четвертый и пятый аргументы структур сопоставляем по правилу сопоставления анонимных переменных. Результат сопоставления – истина. Анонимные переменные цели на момент сопоставления конкретизируются соответственно числами 8 и 5, но теряют эти конкретизации при переходе к следующему терму. Результат сопоставления на первом шаге – истина при этом переменная Обозначение получает конкретизацию л1. Это первое решение программы. В программе осталось необработанными еще 5 утверждений, поэтому конкретизация переменной сохраняется в стеке. Переменная Обозначение переходит в неконкретизированное состояние, продолжается перебор утверждений и сопоставления. Шаг 10-й. Сопоставляем цель с фактом 10. Имена структур цели и утверждения тождественны. Арности сопоставляемых структур равны. Первый аргумент структуры цели тождественен первому аргументу структуры утверждения. Второй аргумент структуры цели с именем Обозначение сопоставляем с соответствующим аргументом утверждения. Результат сопоставления – истина, при этом происходит конкретизация переменной Обозначение. Четвертый аргумент структуры цели не тождественен первому аргументу структуры утверждения (белый ≠ черный). Получили результат – ложь. Прекращаем дальнейшее сравнение. Переменная Обозначение переходит в неконкретизированное состояние, продолжается перебор утверждений и сопоставления. Шаг 11-й. Сопоставляем цель с фактом 11. Процедура сопоставления аналогична процедуре на шаге 10, за исключением конкретизации переменной Обозначение. На 11-м шаге переменная получает значение равное л3. Шаги с 12-го по 14-й также выполняются программой, но результат выполнения в этом случае отрицательный. Причина этого – отрицательный результат сопоставления атома ладья с соответствующими аргументами, стоящими на первом месте в структурах соответствующих фактов. Итоговый результат выполнения запроса 6 – истина. При этом получаем два решения с соответствующими конкретизациями переменной Обозначение. Определения очередности разработки правил По правилам игры ладья может осуществлять взятие фигур по вертикали и по горизонтали. Задача подразумевает определение вариантов взятия фигур ладьей только по горизонтали. Требуется разработать правило, отвечающее за атаку. Разработка логической модели правила Сформируем логическую модель атаки ладьей л1 фигуры п2. PREDICATES nondeterm фигура (symbol, symbol, symbol, integer, integer) nondeterm атака (symbol, symbol, symbol, integer, integer, symbol, symbol, integer, integer) CLAUSES % фигуры фигура (пешка, п1, черный, 6, 6). %факт 1 фигура (пешка, п2, черный, 4, 5). %факт 2 фигура (пешка, п3, белый, 8, 4). %факт 3 фигура (пешка, п4, белый, 3, 3). %факт 4 фигура (конь, кн1, черный, 1, 7). %факт 5 фигура (конь, кн2, белый, 2, 6). %факт 6 фигура (слон, с1, черный, 5, 7). %факт 7 фигура (слон, с2, белый, 6, 4). %факт 8 фигура (ладья, л1, белый, 8, 5). %факт 9 фигура (ладья, л2, черный, 3, 4). %факт 10 фигура (ладья, л3, белый, 4, 1). %факт 11 фигура (ферзь, ф1, черный, 4, 8). %факт 12 фигура (король, кр1, черный, 6, 8). %факт 13 фигура (король, кр2, белый, 5, 1). %факт 14 % атака атака (ладья, л1, белый, 8, 5, п2, черный, 4, 5). %факт 15 GOAL атака (ладья, л1, белый, 8, 5, п2, черный, 4, 5). %запрос 9 Ладья с обозначением л1 белого цвета, стоящая в поле с координатами 8-5, может взять фигуру с обозначением п2 черного цвета, стоящую на поле с координатами 4-5. Разработка и тестирование варианта программы с безусловными утверждениями (фактами) Для реализации разработанной логической модели необходимо ввести пользовательскую структуру, содержащую аргументы: название атакующей фигуры – ладья, ее обозначение, цвет и координаты, обозначение второй фигуры, ее цвет и координаты. Присвоим этой структуре имя атака, определим её и тип её аргументов в области предикатов. Дополним базу фактов и правил 15-м фактом, определяющим атаку ладьей л1 фигуры п2.
Результат выполнения запроса к программе:
Выполнение запроса 9 в программе контролирует правильность функционирования левой части правила логической модели, то есть контролирует утверждение. Запрос 10 проверяет работоспособность правой части правила логической модели, то есть контролирует условие. Разработка и тестирование варианта с частными правилами (правила с константами) В программе перейдем от факта 15 и запросов 9-10 к соответствующему частному правилу 1. PREDICATES nondeterm фигура (symbol, symbol, symbol, integer, integer) nondeterm атака (symbol, symbol, symbol, integer, integer, symbol, symbol, integer, integer) CLAUSES % фигуры фигура (пешка, п1, черный, 6, 6). %факт 1 фигура (пешка, п2, черный, 4, 5). %факт 2 фигура (пешка, п3, белый, 8, 4). %факт 3 фигура (пешка, п4, белый, 3, 3). %факт 4 фигура (конь, кн1, черный, 1, 7). %факт 5 фигура (конь, кн2, белый, 2, 6). %факт 6 фигура (слон, с1, черный, 5, 7). %факт 7 фигура (слон, с2, белый, 6, 4). %факт 8 фигура (ладья, л1, белый, 8, 5). %факт 9 фигура (ладья, л2, черный, 3, 4). %факт 10 фигура (ладья, л3, белый, 4, 1). %факт 11 фигура (ферзь, ф1, черный, 4, 8). %факт 12 фигура (король, кр1, черный, 6, 8). %факт 13 фигура (король, кр2, белый, 5, 1). %факт 14 % атака атака (ладья, л1, белый, 8, 5, п2, черный, 4, 5) :- фигура (ладья, л1, белый, 8, 5), фигура (пешка, п2, черный, 4, 5). % правило 1 GOAL атака (ладья, л1, белый, 8, 5, п2, черный, 4, 5). %запрос 11 По критерию наличие или отсутствие переменных в качестве аргументов в правилах их можно классифицировать на три группы. Правила, не содержащие переменных в качестве аргументов структур. Аргументами в них могут быть константы (атомы и числа), списки с константами, вложенные структуры без переменных. Назовем эти правила частными. Правила, содержащие одновременно как переменные, так и константы, списки с константами, вложенные структуры без переменных. Правила, содержащие в качестве аргументов лишь переменные. В этих правилах отсутствуют константы, списки с константами, вложенные структуры без переменных. Назовем эти правила универсальными. Результаты выполнения запросов к программе:
Анализ результатов выполнения запросов 11-12 показывает, что частные правила обеспечивают правильное функционирование лишь в частных случаях, соответствующих этим правилам. Правильное функционирование программы для всех вариантов требует перехода к универсальным правилам, то есть необходима замена констант в правилах на переменные. Разработка и тестирование варианта с универсальными правилами Заменим атомы с обозначением фигур, их цветов и координат на соответствующие именованные переменные. Введем новую пользовательскую структуру для проверки возможности хода и назовем ее ход, которая в качестве аргументов будет содержать координаты атакующей ладьи и атакованной фигур. Определим ее и тип аргументов в области предикатов. Также введем пользовательскую структуру проверка_беспрепятственной_атаки для проверки на то, что между атакующей ладьей и атакованной фигурой нет других фигур (по правилам шахмат). Добавим в правила условия для устранения избыточности. PREDICATES nondeterm фигура (symbol, symbol, symbol, integer, integer) nondeterm атака (symbol, symbol, symbol, integer, integer, symbol, symbol, integer, integer) nondeterm ход (integer, integer, integer, integer) nondeterm проверка_беспрепятственной_атаки (integer, integer, integer, integer) CLAUSES % фигуры фигура (пешка, п1, черный, 6, 6). %факт 1 фигура (пешка, п2, черный, 4, 5). %факт 2 фигура (пешка, п3, белый, 8, 4). %факт 3 фигура (пешка, п4, белый, 3, 3). %факт 4 фигура (конь, кн1, черный, 1, 7). %факт 5 фигура (конь, кн2, белый, 2, 6). %факт 6 фигура (слон, с1, черный, 5, 7). %факт 7 фигура (слон, с2, белый, 6, 4). %факт 8 фигура (ладья, л1, белый, 8, 5). %факт 9 фигура (ладья, л2, черный, 3, 4). %факт 10 фигура (ладья, л3, белый, 4, 1). %факт 11 фигура (ферзь, ф1, черный, 4, 8). %факт 12 фигура (король, кр1, черный, 6, 8). %факт 13 фигура (король, кр2, белый, 5, 1). %факт 14 % атака атака (ладья, Л1, Цвет1, X1, Y1, Ф, Цвет2, X2, Y2) :- фигура (ладья, Л1, Цвет1, X1, Y1), фигура ( _, Ф, Цвет2, X2, Y2), Цвет1<>Цвет2, ход (X1, Y1, X2, Y2). %правило 1 % ход ход (X0, Y0, X, Y) :- Y=Y0, X0<>X, not(проверка_беспрепятственной_атаки (X0, Y0, X, Y)). %правило 2 % проверка на отсутствие других фигур между атакующей и взятой фигурой проверка_беспрепятственной_атаки (X0, Y0, X, Y) :- фигура (_, _, _, Xf, Yf), Yf=Y0, Yf=Y, Xf>X0, Xf фигура (_, _, _, Xf, Yf), Yf=Y0, Yf=Y, Xf GOAL атака (ладья, Л, Цвет, _, _, Ф, _, X2, Y2). %запрос 13 Результаты выполнения запроса 13 к программе:
|