Intel_Nils (526801), страница 24
Текст из файла (страница 24)
Этот факт должен быть отмечен, чтобы в дальнейшем включить такой оператор в решающую последовательность.) Состоянием цели в пространстве состояний высшего уровня служит любое описание состояния с пустым списком задач. Читатель сможет много уяснить для себя, проследив решение задачи об обезьяне и бананах с использованием такого пространства состояний высшего уровня. 4Л2. ИГРЫ Подход, связанный с расчленением задачи на совокупность подзадач, может быть использован также для поиска игровых стратегий для некоторых типов игр. Мы будем рассматривать игры двух лнц с полной информацией.
В них играют два игрока, делающие свои ходы поочередно. Им полностью известно все, что было сделано и что может быть сделано в этой игре. Конкретнее, мы будем интересоваться играми, в которых один из двух игроков выигрывает (а другой проигрывает) или же результат получается ничейным. Некоторыми примерами игр такого типа служат шашки, тик-так-ту, шахматы, гоу и ним.
Мы не собираемся рассматривать здесь те игры, в которых результат зависит хотя бы частично от случая: так, мы исключаем игральные кости и большинство карточных игр. (Впрочем наш анализ можно было бы обобщить, включив в рассмотрение некоторые типы игр, содержащих случайный элемент.) В подходе, основанном на сведбнин задачи к совокупности подзадач, выигрышная стратегия ищется в процессе доказательства того, что эта игра может быть выиграна. Г!оэтому в описании задачи должно содержаться описание того состояния (или конфигурации) игры, про которое.утверждается, что из 4.»2. Игры шз него достижение выигрыша может быть гарантировано.
Например, в шахматах конфигурацией является полное описание положений всех фигур на доске и указание, кому принадлежит следующий ход. Пусть именами игроков будут ПЛЮС и МИНУС. Рассмотрим задачу нахождения игровой стратегии для игрока ПЛЮС, отправляясь от некоторой конфигурации Х'. Индекс г принимает значения + или †, причем Х+ представляет собой конфигурацию, в которой следующий ход принадлежит игроку ПЛЮС, а Х- — конфигурацию, в которой следующий ход за игроком МИНУС. Мы хотели бы иметь возможность доказать, что игрок ПЛЮС может выиграть, исходя из конфигурации Х', если же такого доказательства найти не удастся, то мы хотели бы иметь возможность доказать, что, исходя из конфигурации Х', игрок ПЛЮС может по крайней мере добиться ничьей.
Обозначим через Я»'(Х») задачу доказательства того, что ПЛЮС может выиграть, отправляясь от конфигурации Х'. Допустимые и этой игре ходы порождают схему сведения игровых задач к совокупности подзадач. Предположим, что очередь делать ход в конфигурации Х' за игроком ПЛЮС, и предположим, что имеется»т' допустимых ходов, приводящих к конфигурациям Х»», Х»', ..., Х»'". Тогда для доказательства %'(Х+) мы должны иметь возможность доказать ту или иную из )(7(Х,'») С другой стороны, если очередь делать ход в конфигурации Х- за игроком МИНУС и если имеется М допустимых ходов, приводящих к конфигурациям у',, у'», ..., у'„и, то для доказательства ЯУ(Х ) мы должны уметь доказывать каждую из задач (У»(У,*.»).
Конечно, подобное сведение к подзадачам применимо и и том случае, когда мы пытаемся доказать лишь, что возможны ничьи. Применение этих операторов сведйния задачи порождает структуру, которая часто называется деревом игры. Элементарные задачи даются правиламн окончания игры, а процесс доказательства продолжается до тех пор, пока не будет установлено, что решающее дерево оканчивается на элементарных задачах. (В большинстве игр, представляющих интерес, таких, как шахматы, гоу и шашки, построить полные решающие деревья не представляется возможным. В следующей главе мы рассмотрим некоторые специализированные методы перебора на игровых деревьях, в которых строятся частичные деревья.) Мы проиллюстрируем эти соображения на простом примере игры, называемой «игра Гранди», и применим методы сведения задачи к совокупности подзадач для поиска стратегии игрока ПЛЮС.
124 Гл. 4. Представления, допускающие сведение задач к подзадачам Правила игры Гранди таковы. Перед двумя играющими расположена единственная кучка предметов, например стопка монет. Первый игрок делит исходную стопку на две новые стопки, которые должны быть неравными. В дальнейшем каждый из игроков, когда приходит его очередь делать ход, делает то же самое с одной из стопок монет. Игра продолжается до тех пор, Рис.
4.15. «И/ИЛИ» граф длк кгрм Граали. пока все стопки 'не будут содержать по одной-две монеты, после чего игра заканчивается, посколькеу дальнейшее ее продолжение невозможно. Проигрывает тот из игроков, который первым окажется в положении, когда игра не может продолжаться, Начнем со стопки, содержащей семь монет, и пусть первым ,делает ход игрок МИНУС.
Конфигурацией в этой игре является последовательность чисел, отражающая числа монеток в различных стопках, плюс указание иа то, чей ход. Так, 7- — начальная конфигурация. В положении 7 у игрока МИНУС имеются три альтернатив- ных хода, приводящих к конфигурациям б,1н, 5,2Я или 4,3+. 4,1а Бибгиографические и исторические замечании 125 Имеются всего три конфигурации, в которых игрок, имеющий право на'следующий ход, проигрывает: 2„1, 1, 1, 1, 1+, 2, 2, 1, 1, 1, 2, 2, 2, 1+. Единственной элементарной задачей (означающей выигрыш для игрока ПЛЮС) является,' таким образом, 1й(2,2,1, 1,1-). Применив нашу процедуру сведения задачи к совокупности подзадач (отправляясь от задачи 1« (7-)), мы получаем «И/ИЛИ» граф, показанный из рис.
4.15. Жирными дугами на этом графе выделено решающее дерево, а в двойных прямоугольниках размещены элементарные задачи. Если мы изменим игру так, чтобы первым начинал игрок ПЛЮС (отправляясь от конфигурации 7+), то окажется, что мы не можем доказать йт(7+). (Второй игрок всегда может выиграть.) Пытаясь доказать )ут(7'), мы придем в конце концов к ситуации, когда невозможно будет построить новые вершины, и тогда можно было бы определить, что начальная вершина неразрешима. (Например, в соответствии с правилами игры у конфигурации 2, 2, 1, 1, 1+ нет следующих за ней конфигураций.) 4.13.
БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ Методы сведйиия задачи к подзадачам и «И/ИЛИ» графы В некоторых из самых первых работ по искусственному интеллекту для решения задач использовались методы сведйния задачи к совокупности подзадач (называемые также «рассуждением в обратном направлении»). Ньюэлл, Шоу и Саймон (1957) написали программу для логико-теоретической машины (ЛТ), которая доказывала теоремы исчисления предикатов, строя свою работу на рассуждении в обратном направлении от доказываемой теоремы.
В этой программе было использовано дерево подзадач, для того чтобы можно было просмотреть альтернативные цепочки рассуждений. Другой из первых программ, в которой были применены методы сведения задачи и деревья подзадач, была программа для символьного интегрирования (БА!)ч(Т) Слейджла (1963а). Слейджл первым назвал эти деревья деревьями типа «И/ИЛИ». В более поздней работе Слейджла и Бурского (!968) был использован термин «пропозициональное дерево>. Ригни и Таун (1969) предложили применить граф типа графов «И/ИЛИ» для анализа структуры последовательностей операций в промышленности.
Некоторые примеры представлений неявно заданных деревьев типа «И/ИЛИ» с помощью недетерминированных программ были даны Манна (1970). 126 Гл 4, Представления, допускающие сведение задач к подзадачам Примеры программ, использующих метод сведйиия задачи к подзадачам Наш пример символического интегрирования основан на программе Слейджла (1963а). Подробно эта программа описана в диссертации Слейджла (1961). Много более развитая система интегрирования (названная 81Х) была впоследствии запрограммирована Мозесом (1967). Она содержала так много специаль- ' ных критериев применимости различных операторов, что интегрирование по большей части производилось либо вовсе без перебора, либо после очень незначительного перебора ').
Риш (1969) разработал алгоритмические процедуры для интегрирования выражений различных типов (см. задачу 4.5). Примеры доказательства геометрических теорем были заимствованы из программы Гелернтнера и др. (1959, 1960). Некоторые элементы этой программы представляют собой важные и оригинальные нововведения. Понятия ключевых операторов и различий и их применение при решении задач связаны главным образом с именем Ньюэлла и его сотрудников по универсальному решателю задач ОРЗ (см. Эрнст н Ньюэлл, 1969). Можно было бы здесь упомянуть, что наше объяснение этих идей несколько отличается от того, что можно найти у Ньюэлла и др. Ньюэлл употреблял фразу «анализ цели-средства», когда говорил о процессе поиска различий и устранения этих различий с помощью подходящих операторов. Он различал также три типа целей в программе ОРЗ: преобразование объекта, уменьшение различия и применение оператора.
Из нашего описания не видна полезность такой классификации. Нас интересует программа ОРЯ постольку, поскольку она может быть использована в системе автоматического решения задач, а многих работавших над ОРЯ онэ интересовала также и как психологическая модель мыслительного процесса. Это различие в точках зрения, без сомнения, отразилось в какой-то мере и на способах описания программы. Особо интересуясь возможностями программы ОРБ для решения задач, Эрнст (1969) исследовал те условия, при которых ОРЗ гарантирует нахождение решения. Анализ Эрнста привел к формализации понятий различия и упорядочения различий, Игры н подход, связанный с разбиением задачи иа подзадачи Слейджл и его сотрудники подчеркнули существенную аналогию между «И/ИЛИ» деревьями и игровыми деревьями ') Можно было бы считать, что большая часть перебора, необходимого для проведения интегрирования, была произведена раз и навсегда самим.Мовесом прн разработке програымы.
Результатом такого перебора на стадии проектирования явились специальные правила, по которым во всех случаях применяются операторы. Задачи !27 (Слейджл, 1970, Слейджл и Бурский, !968). Эта аналогия в какой-то мере очевидна в простых играх, которые могут быть рассмотрены до конца, или в окончаниях более сложных игр, таких, как шахматы. Действительно, мы часто думаем о шахматных эндшпилях как о задачах на доказательство, а не как об играх, Наш пример игры Гранди взят из статьи О'Бирна (1961).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
