Иван Братко - Программирование на языке Пролог для искусственного интеллекта
Завершите программирование нашей оболочки в части, касающейся неопределенной информации (процедура ответпольз и другие).
Рассмотрите перечисленные выше критические замечания, а также возможные расширения нашей экспертной системы. Разработайте и реализуйте соответствующие усовершенствования.
Резюме
• Обычно от экспертных систем требуют выполнения следующих функций:
решение задач в заданной предметной области,
объяснение процесса решения задач,
работа с неопределенной и неполной информацией.
• Удобно считать, что экспертная система со стоит из двух модулей: оболочки и базы знаний. Оболочка в свою очередь состоит из механизма логического вывода и интерфейса с пользователем.
• При создании экспертной системы необходимо принять решения о выборе формального языка представления знаний, механизма логического вывода, средств взаимодействия с пользователем и способа работы в условиях неопределенности.
• "Если-то"-правила, или продукции являются наиболее часто применяемой формой представления знаний в экспертных системах.
• Оболочка, разработанная в данной главе, интерпретирует "если-то"-правила, обеспечивает выдачу объяснений типа "как" и "почему" и запрашивает у пользователя необходимую информацию.
• Машина логического вывода была расширена для работы с неопределенной информацией.
• В данной главе были обсуждены следующие понятия:
экспертные системы
база знаний, оболочка,
машина логического вывода
"если-то"-правила, продукции
объяснения типа "как" и "почему"
категорические знания, неопределенные знания
сеть вывода,
распространение оценок достоверности по сети
ЛитератураКнига Michie (1979) - это сборник статей, относящихся к различным аспектам экспертных систем и инженерии знаний. Две ранние экспертные системы, оказавшие большое влияние на развитие этой области, MYCIN и Prospector, описаны в Shortliffe (1976) и Duda et al (1979). Книга Buchanan and Shortliffe (1984) является хорошим сборником статей, посвященных результатам экспериментов с системой MYCIN. Weiss and Kulikowski (1984) описывают свой практический опыт разработки экспертных систем. Вопрос о работе в условиях неопределенности еще нельзя считать вполне решенным: в статье Quinlan (1983) сравниваются различные подходы к этой проблеме. Способ разработки нашей экспертной системы до некоторой степени аналогичен описанному в Hammond (1984). Некоторые примеры, использовавшиеся в тексте, заимствованы из Winston (1984), Shortliffe (1976), Duda et al (1979), Bratko (1982) и Reiter (1980).
Bratko I. (1982). Knowledge-based problem-solving in AL3. In: Machine Intelligence 10 (J.E. Hayes, D. Michie, Y.H. Pao, eds.). Ellis Horwood.
Buchanan B.G. and Shortliffe E.H. (1984, eds.). Rule-based Expert Systems: The МYСIN Experiments of the Stanford Heuristic Programming Project. Addison-Wesley.
Duda R., Gasschnig J. and Hart P. (1979). Model design in the Prospector consultant system for mineral exploration. In: Expert Systems in the Microelectronic Age (D. Michie, ed.). Edinburgh University Press.
Hammond P. (1984). vMicro-PROLOG for Expert Systems. In: Micro-PROLOG: Programming in Logic (K.L. Clark, F.G. McCabe, eds.). Prentice-Hall.
Michie D. (1979, ed.). Expert Systems in the Microelectronic Age. Edinburgh University Press.
Quinlan J.R. (1983). Inferno: a cautious approach to uncertain reasoning. The Computer Journal 26: 255-270.
Reiter J. (1980). AL/X: An Expert System Using Plausible Inference. Oxford: Intelligent Terminals Ltd.
Shortliffe E. (1976). Computer-based Medical Consultations: MYCIN. Elsevier.
Weiss S.M. and Kulikowski CA. (1984). A Practical Guide to Designing Expert Systems. Chapman and Hall.
Winston P. H. (1984). Artificial Intelligence (second edition). Addison-Wesley. [Имеется перевод первого издания: Уинстон П. Искусственный интеллект. — М.: Мир, 1980.]
Глава 15
Игры
В этой главе мы рассмотрим методы программирования игр двух лиц с полной информацией (таких, как шахматы). Для игр, представляющих интерес, деревья возможных продолжений слишком велики, чтобы можно было говорить о полном переборе, поэтому необходимы какие-то другие подходы. Один из таких методов, основанный на минимаксном принципе, имеет эффективную реализацию, известную под названием "альфа-бета алгоритм". В дополнение к этому стандартному методу, мы разработаем в этой главе программу на основе Языка Советов (Advice Language), который дает возможность вносить в шахматную программу знания о типовых ситуациях. Этот довольно подробный пример может послужить еще одной иллюстрацией того, насколько хорошо Пролог приспособлен для реализации систем, основанных на знаниях.
15.1. Игры двух лиц с полной информацией
Игры, которые мы собираемся обсуждать в данной главе, относятся к классу так называемых игр двух лиц с полной информацией. Примерами таких игр могут служить шахматы, шашки и т.п. В игре участвуют два игрока, которые ходят по очереди, причем оба они обладают полной информацией о текущей игровой ситуации (это определение исключает большинство карточных игр). Игра считается оконченной, если достигнута позиция, являющаяся согласно правилам игры "терминальной" (конечной), например матовая позиция в шахматах. Правилами игры также устанавливается, каков исход игры в этой терминальной позиции.
Для игр такого рода возможно представление в виде дерева игры (или игрового дерева). Вершины этого дерева соответствуют ситуациям, а дуги — ходам. Начальная ситуация игры — это корневая вершина; листьями дерева представлены терминальные позиции.
В большинстве игр этого типа возможны следующие исходы: выигрыш, проигрыш и ничья. Мы будем рассматривать здесь игры, имеющие только два возможных исхода — выигрыш и проигрыш. Игры, в которых возможна ничья, можно упрощенно считать играми с двумя исходами — выигрыш и не-выигрыш. Двух участников игры мы будем называть "игроком" и "противником". "Игрок" может выиграть в некоторой нетерминальной позиции с ходом игрока ("позиции игрока"), если в ней существует какой-нибудь разрешенный ход, приводящий к выигрышу. С другой стороны, некоторая нетерминальная позиция с ходом противника ("позиция противника") является выигранной для игрока, если все разрешенные ходы из этой позиции ведут к позициям, в которых возможен выигрыш. Эти правила находятся в полном соответствии с представлением задач в форме И/ИЛИ-дерева, которое мы обсуждали в гл. 13. Между понятиями, относящимися к И/ИЛИ-деревьям, и понятиями, используемыми в играх, можно установить взаимное соответствие следующим образом:
позиции игры вершины, задачи терминальные позиции выигрыша целевые вершины, тривиально решаемые задачи терминальные позиции проигрыша задачи, не имеющие решения выигранные позиции задачи, имеющие решение позиции игрока ИЛИ-вершины позиции противника И-вершиныОчевидно, что аналогичным образом понятия, относящиеся к поиску в И/ИЛИ-деревьях, можно переосмыслить в терминах поиска в игровых деревьях.
Ниже приводится простая программа, которая определяет, является ли некоторая позиция игрока выигранной.
выигр( Поз) :-
терм_выигр( Поз).
% Терминальная выигранная позиция
выигр( Поз) :-
not терм_проигр( Поз),
ход( Поз, Поз1), % Разрешенный ход в Поз1
not ( ход( Поз1, Поз2),
not выигр( Поз2) ).
% Ни один из ходов противника не ведет к не-выигрышу
Здесь правила игры встроены в предикат ход( Поз, Поз1), который порождает все разрешенные ходы, а также в предикаты терм_выигр( Поз) и терм_проигр( Поз), которые распознают терминальные позиции, являющиеся, согласно правилам игры, выигранными или проигранными. В последнем из правил программы, содержащем двойное отрицание (not), говорится: не существует хода противника, ведущего к не выигранной позиции. Другими словами: все ходы противника приводят к позициям, выигранным с точки зрения игрока.
Рис. 15.1. Сложность игровых деревьев в шахматах. Оценки основаны на том, что в каждой шахматной позиции существуют приблизительно 30 разрешенных ходов я что терминальные позиции расположены на глубине 40 ходов. Один ход равен двум полуходам (по одному полуходу с каждой стороны).
Так же, как и аналогичная программа поиска в И/ИЛИ-графах, приведенная выше программа использует стратегию в глубину. Кроме того, в ней не исключается возможность зацикливания на одних и тех же позициях. Попытка устранить этот недостаток может привести к осложнениям, поскольку правила некоторых из игр допускают такое повторение позиций. Правда, разрешение повторять позиции часто носит условный характер, например по шахматным правилам после троекратного повторения позиции может быть объявлена ничья.
