Материал: Волченков Логическое программирование язык пролог 2015
Лекция 9 Пролог и системы искусственного интеллекта
В данной и следующей лекции обсуждается возможность использования Пролога для решения задач, которые традиционно принято относить к искусственному интеллекту (ИИ), другими словами, таких задач, решение которых условно содержит «творческий» элемент. Плохо формализуемое понятие ИИ лучше растолковать простым перечислением задач, решение которых в недавнем прошлом считалось прерогативой человека, но теперь успешно доверяется компьютеру. Такое перечисление заняло бы слишком много времени, поэтому ограничимся лишь несколькими примерами. В частности, в данной лекции рассматривается ряд задач, так или иначе относящихся к программированию логических игр. Первая из них – это интерпретация редукционной модели ИИ в контексте игры двух лиц с полной информацией, вторая – непосредственно связана с эвристическим поиском на игровых деревьях. Все задачи данной и следующей лекций будут решаться с помощью Пролога. Тем самым автор постарается убедить слушателей и читателей в том, что парадигма логического программирования является достаточно естественным и эффективным инструментом для решения задач ИИ, по крайней мере некоторых из них.
1. Интерпретация редукционной модели на Прологе
Редукция в ИИ – это сведение сложной задачи к иерархии более простых задач, или, в общем случае, преобразование сложной структуры данных в иерархию более простых структур. Разумеется, как задачи, так и структуры данных должны иметь чёткую смысловую интерпретацию, чтобы разговор о редукции был предметным и понятным.
Для наглядной интерпретации редукции в теории ИИ используется понятие И/ИЛИ-графа. Это ориентированный граф. Вершины графа обозначают задачи (в общем случае, структуры данных) и подзадачи (подструктуры). Дуги графа соединяют родительские вершины с дочерними вершинами (задачи – с их подзадачами, структуры – с их подструктурами).
Все дочерние вершины одной родительской вершины должны быть либо только конъюнктивными, либо только дизъюнктивными
121
вершинами. В первом случае (рис. 9.1, а) это означает, что решение задачи может быть заменено последовательностью (грубо – конъюнкцией) решений более простых подзадач. Иными словами – структура данных может быть заменена совокупностью более простых структур. Во втором случае (рис. 9.1, б) это означает, что решение задачи может быть заменено решением одной из альтернативных подзадач. Иными словами – структура данных может быть заменена одной из альтернативных структур.
|
a |
|
|
b |
|
b1 |
b2 |
bn |
c1 |
c2 … |
cm |
|
а) |
|
|
б) |
|
Рис 9.1. Конъюнктивные и дизъюнктивные вершины И/ИЛИ-графа
Дочерние вершины могут, в свою очередь, являться родительскими вершинами для других вершин. Если у вершины нет дочерних вершин, то это элементарная подзадача (подструктура). Она принадлежит к одному из двух классов: заведомо разрешимых и заведомо неразрешимых подзадач (допустимых и недопустимых
подструктур).
Родительская вершина называется разрешимой (допустимой), если все её конъюнктивные дочерние вершины разрешимы (допустимы) или если хотя бы одна из её дизъюнктивных дочерних вершин разрешима (допустима).
Интерпретация редукционной модели обычно заключается в доказательстве разрешимости (допустимости) корневой вершины И/ИЛИ-графа, а также в выделении решающего подграфа, состоящего только из разрешимых (допустимых) вершин.
Связь между представленной редукционной моделью и Прологом достаточно очевидна. Действительно, легко заметить, что факты и правила любой базы данных Пролога представляют не что иное, как иную форму записи некоторого И/ИЛИ-графа.
122
В частности, «кусту» на рис. 9.1,а соответствует единственное правило Пролога:
a :- b1, b2, …, bn.
А «кусту» на рис. 9.1,б соответствуют несколько правил с одинаковыми левыми частями:
b :- c1. b :- c2.
…
b :- cm.
Пример 9.1. На рис. 9.2,а показан И/ИЛИ-граф, у которого «висячие» вершины f3, f4, f6 заведомо разрешимые, а вершины f1, f2, f5 – заведомо неразрешимые. На рис. 9.2,б показан решающий подграф этого графа.
|
a |
|
|
a |
|
|
|
|
|
|
|
|
b |
c |
f1 |
c |
|
d |
f2 |
e |
f3 |
e |
f3 |
|
|
|
|
|
|
f4 |
f5 |
f6 |
|
f6 |
|
|
а) |
|
|
б) |
|
Рис. 9.2. Пример И/ИЛИ-графа и решающий подграф этого графа
Заведомо разрешимым подзадачам соответствуют факты, заведомо неразрешимым – отсутствие фактов в базе данных.
Так, И/ИЛИ-графу примера 9.1 соответствует следующая база данных (код 9.1):
123
Код 9.1
Для доказательства разрешимости исходной задачи интерпретатору Пролога достаточно задать целевое утверждение ?- a.
Для построения решающего подграфа каждому предикату представленной базы данных достаточно добавить единственный аргумент
(код 9.2).
a:- b.
a:- c.
a:- f1.
b:- d, f2,
c:- e, f3.
d:- f4.
d:- f5.
e:- f6, f3. f3.
f4.
Код 9.2
a(a(X)) :- b(X). a(a(X)) :- c(X). a(a(X)) :- f1(X).
b(b(X, Y, Z)) :- d(X), f2(Y), e(Z). c(c(X, Y)) :- e(X), f3(Y). d(d(X)) :- f4(X).
d(d(X)) :- f5(X).
e(e(X, Y)) :- f6(X), f3(Y). f3(f3).
f4(f4). f6(f6).
Целевое утверждение ?- a(X). возвратит следующее значение:
X = a(c(e(f6, f3), f3)).
2.Анализ игры двух лиц с полной информацией исчерпывающим перебором
К сожалению, в реальности И/ИЛИ-граф бывает изначально не задан: его приходится строить в процессе решения задачи. Другими словами, чаще всего приходится располагать не самими «кустами», показанными на рис. 9.1, а только правилами построения таких «кустов».
124
Рассмотрим так называемую игру двух лиц с полной информаци-
ей, когда противники ходят по очереди, меняя каждым своим ходом позицию игры. Эта позиция всегда «видна» каждому игроку. (В этом смысле игра и является «информационно полной».)
Для простоты будем считать, что:
исход игры двузначен: выигрыш или проигрыш каждого игрока;
каждому игроку известен алгоритм построения всех ходов (порождения всех позиций Q1, Q2, …, Qn из любой позиции
P);
позиция для данного игрока является проигрышной, если данный игрок не может сделать из неё ни одного хода.
Покажем, что для анализа игры указанного типа естественно использовать И/ИЛИ-граф, если под анализом понимать доказательство того факта, что игрок, начинающий игру из некоторой позиции, выигрывает (или, что он проигрывает).
Вершина И/ИЛИ-графа – это позиция игры. Заметим, что если доказывается выигрыш игрока, то своими возможными ходами он порождает дизъюнктивные вершины графа (хотя бы один ход должен быть выигрывающим). Если же доказывается проигрыш игрока, то он порождает конъюнктивные вершины (все возможные ходы проигрывающие).
Игрока, выигрыш которого мы пытаемся доказать, будем называть игроком ПЛЮС, а игрока, проигрыш которого мы пытаемся доказать, – игроком МИНУС. Очевидно, что если из данной позиции нет хода для игрока ПЛЮС, то это заведомо неразрешимая вершина графа, а если нет хода для игрока МИНУС, то это заведомо разрешимая вершина.
Пример 9.2. Рассмотрим игру Гранди, которую также называют «игрой английских моряков».
Имеется кучка предметов (чаще всего, монет), которые выставлены «на кон» двумя игроками. Число монет N «видно» каждому игроку.
Ходят по очереди. Первый ход – разделение исходной кучки на две так, чтобы число монет в новых кучках (N1 и N2) было различ-
ным:
N1 + N2 = N, N1 N2.
125