Программирование на языке пролог
Шрифт:
Предполагается, что программа действует за игрока, делающего свои ходы ноликами. Предикат вынужденный_ход используется для ответа на вопрос: «Нужно ли делать вынужденный ход в конкретной позиции?» Такая ситуация имеет место, если игрок 0 (игрок, делающий ходы ноликами, т. е. программа) не может выиграть немедленно (мы не будем рассматривать этот слу- случай), но есть угроза того, что игрок Xможет выиграть следую- следующим ходом. Например, в позиции
Игрок вынужден поставить в 4-й квадрат, так как если он не сделает этого, то его противник будет иметь возможность на следующем ходу заполнить линию 1-4-7.
линия(Клетки)
служит «генератором» возможных линий. Эта цель может быть согласована с базой данных несколькими способами, в частности, присваиванием в качестве значения переменной Клетки одного из возможных списков номеров клеток, находящихся на одной линии. Выбрав линию, необходимо проверить, существует ли угроза со стороны противника на этой линии. Это составляет задачу целевого утверждения, выполняющего функции «контролера»:
угроза(Клетки,Доска,К)
В этом целевом утверждении переменная Доскаиспользуется для представления текущей позиции на доске (т. е. какие клетки заняты и какими символами), а переменная К получает в качестве значения номер клетки, в которой игрок 0 должен поставить нолик (при условии что доказательство этой цели завершается успешно).
Основная идея программы очень проста – предикат линиявыдает линию, а затем предикат угрозапроверяет, имеется ли на этой линии угроза. Если это так, то доказательство согласованности исходного целевого утверждения вынужденный_ходзаканчивается успешно. Иначе инициируется возврат, и предикат линияпредполагает другую возможную линию. Эта линия также подвергается проверке, и, возможно, снова произойдет возврат. Если мы окажемся в ситуации, когда предикат линияне может более порождать линии, то доказательство согласованности целевого утверждения вынужденный_ходзакончится неудачей (вынужденных ходов нет).
Теперь рассмотрим, что происходит, если эта программа, являясь частью некоторой большей системы, успешно находит вынужденный ход. Переменная К получит в качестве значения номер клетки, в которой должен быть сделан ход, и эта информация будет использована где нибудь в другом месте в программе. Предположим, что в дальнейшем где-то в программе имеет место неудача при доказательстве согласованности некоторого утверждения и что Пролог в конце концов пытается вновь согласовать целевое утверждение вынужденный_ход.Тогда предикат линияначнет порождение новых возможных линий, которые должны быть проверены. Это бессмысленно, так как нет никакой пользы в том, чтобы искать альтернативный вынужденный ход. Если найден один из таких ходов, то мы не можем сделать ничего лучше, чем сделать этот ход – неудача при его осуществлении гарантировала бы проигрыш игры. В большинстве случаев, однако, альтернативных вынужденных ходов не будет, и при поиске сопоставления для цели вынужденный_ходбудут бесполезно просматриваться все неопробованные линии, прежде чем попытка доказать согласованность цели не закончится неудачей. Однако в случае альтернативных ходов известно, что даже если имеется другое решение, оно не может быть использовано без возникновения проблем с использованием первого решения Мы можем предотвратить потерю времени Прологом на поиск различных вынужденных ходов, поместив отсечение в конце соответствующего утверждения. Это приведет к замораживанию последнего успешного решения для предиката линия.Введение отсечения равносильно следующему заявлению: «если ищутся вынужденные ходы, то важно найти только первое решение».
Чтобы понять такое использование отсечения, необходимо лишь рассмотреть общую структуру этой программы. Однако некоторые из деталей также представляют интерес. В программе предполагается, что игровую доску можно описать с помощью структуры, состоящей из девяти компонент. Каждая компонента представляет содержимое клетки с соответствующим номером. Таким образом, в любой момент времени содержимое четвертой клетки доски может быть получено путем выборки четвертого аргумента структуры, представляющей текущую позицию на доске (для этого мы используем встроенный предикат arg). Если клетка ничем не заполнена, то переменная будет неконкретизи-рованной; иначе ее значение равно одному из атомов Оили X. Мы используем предикаты varи nonvarдля того, чтобы
Давайте рассмотрим другой пример программы, работающей по методу «порождения и проверки». Вернемся к вопросу о делении целых чисел, рассмотренному в разд. 2.5. Большинство Пролог-систем обеспечивают эту возможность автоматически, но здесь представлена программа для целочисленного деления, которая использует лишь операции сложения и умножения.
разделить(N1,N2,Результат):-
целое_число(Результат), Произведение_1 is Результат*N2, Произведение_2 is (Результат + 1)*N2, Произведение_1 =‹ N1, Произведение_2›N1,!.
Это правило использует предикат целое_число(как он определен ранее) для порождения числа Результат,которое является результатом «деления» N1на N2. Так, например, результат деления 27на 6равен 4, так как 4x6меньше или равно 27, а 5x6больше чем 27.
Приведенное правило использует предикат целое_числокак «генератор», а остальные целевые утверждения выполняют функцию соответствующего «контролера». Мы заранее знаем, что если заданы конкретные значения N1и N2, то предикат разделить(N1, N2, Результат)может иметь значение «истина» лишь для одного возможного значения Результат.Несмотря на то что целое_числоможет породить бесконечное множество кандидатов, лишь для одного из них будут выполняться последние тесты. Мы можем явно выразить это наше знание, вставив отсечение в конце правила. Словами это можно сказать так: «если нам удалось породить число Результаттакое, что оно успешно проходит тесты для числа, являющегося результатом деления, то нет надобности пытаться получить другое решение». В частности, нет необходимости пересматривать какой-либо из выборов, которые были сделаны при поиске правил для разделить, целое_числои так далее. Мы нашли единственное решение, и нет оснований искать другое. Если бы мы "не" добавили отсечение, то любой возврат в конце концов снова инициировал бы поиск альтернатив для целое_число.Так что продолжилось бы порождение значений для переменной Результат.Ни одно из новых значений не было бы правильным результатом деления, и, таким образом, генерация целых чисел продолжалась бы до бесконечности.
4.4. Проблемы, связанные с использованием отсечения
Мы уже убедились в том, что иногда необходимо учитывать стратегию, используемую в Прологе для поиска в базе данных, и что порядок записи утверждений в программе на Прологе влияет на результат доказательства согласованности целевых утверждений. Проблема, связанная с введением отсечений, заключается в том, что мы должны еще более детально знать, как именно будут использоваться правила программы. Ибо, когда правило используется одним способом, отсечение может быть безвредным или даже полезным, в то время как при другом способе употребления правила отсечение может привести к непредвиденному результату. Рассмотрим измененное определение предиката присоединить,приведенное в предыдущем разделе:
присоединить([],Х,Х):-!.
присоединить[А|В],С,[А|D]:- присоединить(В,С,D).
Когда мы имеем дело с целевыми утверждениями, подобными
присоединить([а,b,с],[d,е],Х)
и
присоединить([а,b,с],Х,Y)
то использование отсечения вполне уместно. Если первый аргумент такого целевого утверждения уже имеет некоторое значение, то единственный смысл отсечения – это подтверждение того, что когда значение первого аргумента есть [], то только первое правило применимо. Однако рассмотрим, что произойдет, если мы имеем целевое утверждение
присоединить(Х,Y,[а,b,с]).
Это целевое утверждение будет сопоставлено с заголовком первого правила, что даст
X = [], Y = [a,b,c]
но затем встретится отсечение. Это приведет к тому, что будет заморожен сделанный нами выбор правила, и как следствие в случае если мы обратимся за новым решением, ответ будет «нет», даже если в действительности для данного запроса имеются другие решения.
Приведем другой интересный пример того, что может произойти, если правило, содержащее отсечение, используется незапланированным способом. Давайте определим предикат число_родителей,который дает информацию о том, сколько родителей имеет человек. Мы можем определить его следующим образом: