Часть 3.

Трудности в передаче "глубоких" знаний предметной области. Системе MYCIN, к

примеру, не достает действительного знания человеческой физиологии. Она не

знает, какова функция кровеносной системы или спинного мозга. Ходит предание,

что однажды, подбирая лекарство для лечения менингита, MYCIN спросила, беремен ли пациент, хотя ей указали, что пациент мужского пола. Было это на самом

деле или нет, неизвестно, но это хорошая иллюстрация потенциальной ограниченности знаний экспертной системы.

Недостаток здравомыслия и гибкости. Если людей поставить перед задачей, которую они не в состоянии решить немедленно, то они обычно исследуют сперва основные принципы и вырабатывают какую-то стратегию для подхода к проблеме.

Экспертным системам этой способности не хватает.

Неспособность предоставлять осмысленные объяснения. Поскольку экспертные системы не владеют глубоким знанием своей предметной области, их пояснения обычно ог­раничиваются описанием шагов, которые система предприняла в поиске решения. Но они зачастую не могут пояснить, "почему" был выбран конкретный подход.

Трудности в тестировании. Хотя обоснование корректности любой большой компьютерной системы достаточно трудоемко, экспертные системы проверять осо­бенно тяжело. Это серьезная проблема, поскольку технологии экспертных систем

применяются для таких критичных задач, как управление воздушным движением,

ядерными реакторами и системами оружия.

Ограниченные возможности обучения на опыте. Сегодняшние экспертные системы

делаются "вручную"; производительность разработанной системы не будет

возрастать до следующего вмешательства программистов. Это заставляет серьезно

усомниться в разумности таких систем.

Несмотря на эти ограничения, экспертные системы доказали свою ценность во мно­гих важных приложениях. Будем надеяться, что недоработки сподвигнут студентов заняться этой важной отраслью компьютерных наук. Экспертные системы - одна из основных тем этой книги. Они подробно обсуждаются в главах 6 и 7.

1.2.4. Понимание естественных языков и семантическое моделирование

Одной из долгосрочных целей искусственного интеллекта является создание программ, способных понимать человеческий язык и строить фразы на нем. Способность применять и понимать естественный язык является фундаментальным аспектом челове­ческого интеллекта, а его успешная автоматизация привела бы к неизмеримой эффектив­ности самих компьютеров. Многие усилия были затрачены на написание программ, по­нимающих естественный язык. Хотя такие программы и достигли успеха в ограниченных контекстах, системы, использующие натуральные языки с гибкостью и общностью, ха­рактерной для человеческой речи, лежат за пределами сегодняшних методологий.

46

Понимание естественного языка включает куда больше, чем разбор предложений на индивидуальные части речи и поиск значений слов в словаре. Оно базируется на обширном фоновом знании о предмете беседы и идиомах, используемых в этой области, так же, как и на способности применять общее контекстуальное знание для понимания не­домолвок и неясностей, присущих естественной человеческой речи.

Представьте себе, к примеру, трудности в разговоре о футболе с человеком, который ничего не знает об игре, правилах, ее истории и игроках. Способен ли такой человек понять смысл фразы: "в центре Иванов перехватил верхнюю передачу- мяч полетел к штрафной соперника, там за него на "втором этаже" поборолись Петров и Сидоров, после чего был сделан пас на Васина в штрафную, который из-под защитника подъемом пробил точно в дальний угол"? Хотя каждое отдельное слово в этом предложении можно понять, фраза звучит совер­шенной тарабарщиной для любого нефаната, будь он хоть семи пядей во лбу.

Задача сбора и организации этого фонового знания, чтобы его можно было применить к осмыслению языка, составляет значительную проблему в автоматизации понима­ния естественного языка. Для ее решения исследователи разработали множество методов структурирования семантических значений, используемых повсеместно в искусственном интеллекте (см. главы 6, 7 и 13).

Из-за огромных объемов знаний, требуемых для понимания естественного языка, большая часть работы ведется в хорошо понимаемых, специализированных проблемных областях. Одной из первых программ, использовавших такую методику "микромира", была программа Винограда SHRDLU - система понимания естественного языка, которая могла "беседовать" о простом взаимном расположении блоков разных форм и цветов [Winograd, 1973]. Програм­ма SHRDLU могла отвечать на вопросы типа: "какого цвета блок на синем кубике?", а также планировать действия вроде "передвинь красную пирамидку на зеленый брусок". Задачи это­го рода, включая управление размещением блоков и их описание, на удивление часто всплы­вали в исследованиях ИИ и получили название проблем "мира блоков".

Несмотря на успехи программы SHRDLU в разговорах о расположении блоков, она была не способна абстрагироваться от мира блоков. Методики представления, использован­ные в программе, были слишком просты, чтобы передать семантическую организацию бо­лее богатых и сложных предметных областей. Основная часть текущих работ в области по­нимания естественных языков направлена на поиск формализмов представления, которые должны быть достаточно общими, чтобы применяться в широком круге приложений и уметь адаптироваться к специфичной структуре заданной области. Множество разнообраз­ных методик (большинство из которых являются развитием или модификацией семантиче­ских сетей) исследуются с этой целью и используются при разработке программ, способ­ных понимать естественный язык в ограниченных, но достаточно интересных предметных областях. Наконец, в текущих исследованиях [Marcus, 1980], [Manning и Schutze, 1999], [Jurafsky и Martin, 2000] стохастические модели, описывающие совместное использование слов в языке, применяются для характеристики как синтаксиса, так и семантики. Полное понимание языка на вычислительной основе все же остается далеко за пределами совре­менных возможностей.

1.2.5. Моделирование работы человеческого интеллекта

В большей части рассмотренного выше материала человеческий интеллект служит отправной точкой в создании искусственного, однако это не означает, что про­граммы должны формироваться по образу и подобию человеческого разума.

47

Действительно, многие программы ИИ создаются для решения каких-то насущных задач без учета человеческой ментальной архитектуры. Даже экспертные системы, заим­ствуя большую часть своего знания у экспертов-людей, не пытаются моделировать внутренние процессы человеческого ума. Если производительность системы - это единственный критерий ее качества, нет особых оснований имитировать человече­ские методы принятия решений. Программы, которые используют несвойственные людям подходы, зачастую более успешны, чем их человеческие соперники. Тем не менее конструирование систем, которые бы детально моделировали какой-либо ас­пект работы интеллекта человека, стало плодотворной областью исследований как в искусственном интеллекте, так и в психологии.

Моделирование работы человеческого разума помимо обеспечения ИИ его основной методологией оказалось мощным средством для формулирования и испытания теорий человеческого познания. Методологии принятия решений, разработанные теоретиками компьютерных наук, дали психологам новую отправную точку для исследования человеческого разума. Вместо того чтобы гадать о теориях познания на неясном языке ранних исследований или вообще оставить попытки описания внутренних механизмов человече­ского интеллекта (как предлагают специалисты по изучению поведения), многие психо­логи приспособили язык и теорию компьютерной науки для разработки моделей челове­ческого разума. Такие методы не только дают новую терминологию для характеристики человеческого интеллекта. Компьютерная реализация этих теорий предоставляет психо­логам возможность эмпирически тестировать, критиковать и уточнять их идеи [Luger, 1994]. Обсуждение отношений между ИИ и попытками понять человеческий ра­зум приводится ниже и резюмируется в главе 16.

1.2.6. Планирование и робототехника

Исследования в области планирования начались с попытки сконструировать роботов, которые бы выполняли свои задачи с некоторой степенью гибкости и способностью реагировать на окружающий мир. Планирование предполагает, что робот должен уметь вы­полнять некоторые элементарные действия. Он пытается найти последовательность та­ких действий, с помощью которой можно выполнить более сложную задачу, например, двигаться по комнате, заполненной препятствиями.

Планирование по ряду причин является сложной проблемой, не малую роль в этом играет размер пространства возможных последовательностей шагов. Даже очень простой робот способен породить огромное число различных комбинаций элементарных движений. Представьте себе, к примеру, робота, который может передвигаться вперед, назад, влево и вправо, и вообразите, сколькими различными пу­тями он может двигаться по комнате. Представьте также, что в комнате есть препят­ствия, и что робот должен выбирать путь вокруг них некоторым оптимальным обра­зом. Для написания программы, которая могла бы разумно определить лучший путь из всех вариантов, и не была бы при этом перегружена огромным их числом, потре­буются сложные методы для представления пространственного знания и управления перебором в пространстве альтернатив.

Одним из методов, применяемых человеческими существами при планировании, является иерархическая декомпозиция задачи (hierarchical problem decomposition). Плани­руя путешествие в Лондон, вы, скорее всего, займетесь отдельно проблемами организа­ции перелета, поездки до аэропорта, самого полета и поиска подходящего вида транспорта

48

в Лондоне, хотя все они являются частью большого общего плана. Каждая из этих задач может сама быть разбита на такие подзадачи, как, например, покупка карты горо­да, преодоление лабиринта линий метро и поиск подходящей пивной. Такой подход не только эффективно ограничивает размер пространства поиска, но и позволяет сохранять часто используемые маршруты для дальнейшего применения.

В то время как люди разрабатывают планы безо всяких усилий, создание компьютерной программы, которая бы занималась тем же - сложная проблема. Казалось бы, такая простая вещь, как разбиение задачи на независимые подзадачи, на самом деле требует изощренных эвристик и обширного знания об области планирования. Не менее сложная проблема - определить, какие планы следует сохранить, и как их обобщить для исполь­зования в будущем.

Робот, слепо выполняющий последовательности действий, не реагируя на изменения в своем окружении, или неспособный обнаруживать и исправлять ошибки в своем собственном плане, едва ли может считаться разумным. Зачастую от робота требуют сформи­ровать план, основанный на недостаточной информации, и откорректировать свое пове­дение по мере его выполнения. Робот может не располагать адекватными сенсорами для того, чтобы обнаружить все препятствия на проектируемом пути. Такой робот должен начать двигаться по комнате, основываясь на "воспринимаемых" им данных, и коррек­тировать свой путь по мере того, как выявляются другие препятствия. Организация пла­нов, позволяющая реагировать на изменение условий окружающей среды, - основная проблема планирования [Lewis и Luger, 2000].

Наконец, робототехника была одной из областей исследований ИИ, породившей множество концепций, лежащих в основе агентно-ориентированного принятия решений (см. подраздел 1.1.4). Исследователи, потерпевшие неудачу при решении проблем, связан­ных с большими пространствами представлений и разработкой алгоритмов поиска для тра­диционного планирования, переформулировали задачу в терминах взаимодействия полуав­тономных агентов [Agre и Chapman, 1987], [Brooks, 1991a]. Каждый агент отвечает за свою часть задания, и общее решение возникает в результате их скоординированных действий. Элементы алгоритмов планирования будут представлены в главах 6, 7 и 14.

Исследования в области планирования сегодня вышли за пределы робототехники, теперь они включают также координацию любых сложных систем задач и целей. Современные планировщики применяются в агентских средах [Nilsson, 1994], а также для управления ускорителями частиц [Klein и др., 1999, 2000].

1.2.7. Языки и среды ИИ

Одним из наиболее важных побочных продуктов исследований ИИ стали достижения в сфере языков программирования и средах разработки программного обеспечения. По множеству причин, включая размеры многих прикладных программ ИИ, важность методологии "создания прототипов", тенденцию алгоритмов поиска порождать чересчур большие пространства и трудности в предсказании поведения эвристических программ, программистам искусственного интеллекта пришлось разработать мощную систему ме­тодологий программирования.

Средства программирования включают такие методы структурирования знаний, как объектно-ориентированное программирование и каркасы экспертных систем (они обсуждаются в части III). Высокоуровневые языки, такие как LISP и PROLOG (см. часть IV), которые обеспечивают модульную разработку, помогают управиться с размерами и

49

сложностью программ. Пакеты средств трассировки позволяют программистам реконструировать выполнение сложного алгоритма и разобраться в сложных структурах эври­стического перебора. Без подобных инструментов и методик вряд ли удалось бы постро­ить многие известные системы ИИ.

Многие из этих методик сегодня являются стандартными методами разработки программного обеспечения и мало соотносятся с основами теории ИИ. Другие же, такие как объектно-ориентированное программирование, имеют значительный теоретический и практический интерес. Наконец, многие алгоритмы ИИ сейчас реализуются на таких традиционных для вычислительной техники языках, как C++ и Java.

Языки, разработанные для программирования ИИ, тесно связаны с теоретической структурой этой области. В данной книге рассматривается и LISP, и PROLOG, и мы старались удержаться от религиозных прений об их относительных достоинствах, склоня­ясь, скорее, к той точке зрения, что "хороший работник должен знать все инструменты". Главы, посвященные языкам программирования (14 и 15), рассматривают преимущества применения различных языков для решения конкретных задач.

1.2.8. Машинное обучение

Обучение остается "крепким орешком" искусственного интеллекта. Важность обучения, тем не менее, несомненна, поскольку эта способность является одной из главных составляющих разумного поведения. Экспертная система может выполнять долгие и трудоемкие вычисления для решения проблем. Но, в отличие от человеческих существ, если дать ей такую же или подобную проблему второй раз, она не "вспомнит" решение. Она каждый раз вновь будет выполнять те же вычисления - едва ли это похоже на ра­зумное поведение.

Большинство экспертных систем ограничены негибкостью их стратегий принятия решений и трудностью модификации больших объемов кода. Очевидное решение этих проблем - заставить программы учиться самим на опыте, аналогиях или примерах.

Хотя обучение является трудной областью, существуют некоторые программы, которые опровергают опасения о ее неприступности. Одной из таких программ является AM - Автоматизированный Математик, разработанный для открытия математических законов [Lenat, 1977, 1982]. Отталкиваясь от заложенных в него понятий и аксиом тео­рии множеств, Математику удалось вывести из них такие важные математические кон­цепции, как мощность множества, целочисленная арифметика и многие результаты тео­рии чисел. AM строил теоремы, модифицируя свою базу знаний, и использовал эвристи­ческие методы для поиска наилучших из множества возможных альтернативных теорем. Из недавних результатов можно отметить программу Коттона [Cotton и др., 2000], кото­рая изобретает "интересные" целочисленные последовательности.

К ранним трудам, оказавшим существенное влияние на эту область, относятся исследования Уинстона по выводу таких структурных понятий, как построение "арок" из на­боров "мира блоков" [Winston, 1975a]. Алгоритм ID3 проявил способности в выделении общих принципов из разных примеров [Quinlan, 1986a]. Система MetaDENDRAL выво­дит правила интерпретации спектрографических данных в органической химии на при­мерах информации о веществах с известной структурой. Система Teiresias - интеллек­туальный "интерфейс" для экспертных систем - преобразует сообщения на высоко­уровневом языке в новые правила своей базы знаний [Davis, 1982]. Программа Hacker строит планы для манипуляций в "мире блоков" посредством итеративного процесса

50

работки плана, его испытания и коррекции выявленных недостатков [Sussman, 1975]. Работа в сфере обучения, основанного на "пояснениях", продемонстрировала эффективность для обучения априорному знанию [Mitchell и др., 1986], [DeJong и Моопеу, 1986]. Сегодня известно также много важных биологических и социологических моделей обу­чения. Они будут рассмотрены в главах, посвященных коннекционистскому и эмерджентному обучению.

Успешность программ машинного обучения наводит на мысль о существовании универсальных принципов, открытие которых позволило бы конструировать программы, способные обучаться в реальных проблемных областях. Некоторые подходы к обучению будут представлены в главах 9-11.

1.2.9. Альтернативные представления: нейронные сети и генетические алгоритмы

В большей части методик, представленных в этой книге, для реализации интеллекта используются явные представления знаний и тщательно спроектированные алгоритмы перебора. Совершенно отличный подход состоит в построении интеллектуальных программ с использованием моделей, имитирующих структуры нейронов в человеческом мозге или эволюцию разных альтернативных конфигураций, как это делается в генетиче­ских алгоритмах и искусственной жизни.

Схематическое представление нейрона (рис. 1.2) состоит из клетки, которая имеет множество разветвленных отростков, называемых дендритами, и одну ветвь - аксон. Дендриты принимают сигналы от других нейронов. Когда сумма этих импульсов превышает некоторую границу, нейрон сам возбуждается, и импульс, или "сигнал", проходит по аксону. Разветвления на конце аксона образуют синапсы с дендритами других нейро­нов. Синапс - это точка контакта между нейронами. Синапсы могут быть возбуждаю­щими (excitatory) или тормозящими (inhibitory), в зависимости от того, увеличивают ли они результирующий сигнал.

Такое описание нейрона необычайно просто, но оно передает основные черты, существенные в нейронных вычислительных моделях. В частности, каждый вычислительный элемент подсчитывает значение некоторой функции своих входов и передает результат к присоединенным к нему элементам сети. Конечные результаты являются следствием па­раллельной и распределенной обработки в сети, образованной нейронными соединения­ми и пороговыми значениями.

Нейронные архитектуры привлекательны как средства реализации интеллекта по многим причинам. Традиционные программы ИИ могут быть слишком неустойчивы и чувствительны к шуму. Человеческий интеллект куда более гибок при обработке такой

51

зашумленной информации, как лицо в затемненной комнате или разговор на шумной вечеринке. Нейронные архитектуры, похоже, более пригодны для сопоставления зашумленных и недостаточных данных, поскольку они хранят знания в виде большого числа мелких элементов, распределенных по сети.

С помощью генетических алгоритмов и методик искусственной жизни мы вырабатываем новые решения проблем из компонентов предыдущих решений. Генетические операторы, такие как скрещивание или мутация, подобно своим эквивалентам в реальном мире, вырабаты­вают с каждым поколением все лучшие решения. В искусственной жизни новые поколения создаются на основе функции "качества" соседних элементов в прежних поколениях.

И нейронные архитектуры, и генетические алгоритмы дают естественные модели параллельной обработки данных, поскольку каждый нейрон или сегмент решения представляет собой независимый элемент. Гиллис [Hillis, 1985] отметил, что люди быстрее справляются с задачами, когда получают больше информации, в то время как компьюте­ры, наоборот, замедляют работу. Это замедление происходит за счет увеличения време­ни последовательного поиска в базе знаний. Архитектура с массовым параллелизмом, например человеческий мозг, не страдает таким недостатком. Наконец, есть нечто очень привлекательное в подходе к проблемам интеллекта с позиций нервной системы или ге­нетики. В конце концов, мозг есть результат эволюции, он проявляет разумное поведе­ние и делает это посредством нейронной архитектуры. Нейронные сети, генетические алгоритмы и искусственная жизнь рассматриваются в главах 10 и 11.

1.2.10. Искусственный интеллект и философия

В разделе 1.1 мы представили философские, математические и социологические ис­токи искусственного интеллекта. Важно осознавать, что современный ИИ не только на­следует эту богатую интеллектуальную традицию, но и делает свой вклад в нее.

Например, поставленный Тьюрингом вопрос о разумности программ отражает наше понимание самой концепции разумности. Что такое разумность, как ее описать? Какова природа знания? Можно ли его представить в устройствах? Что такое навыки? Может ли знание в прикладной области соотносится с навыком принятия решений в этой среде? Как знание о том, что есть истина (аристотелевская "теория"), соотносится со знанием, как это сделать ("практика")?

Ответы на эти вопросы составляют важную часть работы исследователей и разработчиков ИИ. В научном смысле программы ИИ можно рассматривать как эксперименты. Проект имеет конкретную реализацию в виде программы, и программа выполняется как эксперимент. Разработчики программы изучают результаты, а затем перестраивают про­граммы и вновь ставят эксперимент. Таким образом возможно определить, являются ли наши представления и алгоритмы достаточно хорошими моделями разумного поведения. Ньюэлл и Саймон [Newell и Simon, 1976] предложили этот подход к научному познанию в своей тьюринговской лекции 1976 г.

Ньюэлл и Саймон также предложили более сильную модель интеллекта в своей гипотезе о физической символьной системе: физическая система проявляет разумное поведение тогда и только тогда, когда она является физической символьной системой. В главе 16 подробно рассматривается практический смысл этой теории, а также критические замечания в ее адрес.

Многие применения ИИ подняли глубокие философские вопросы. В каком смысле можно заявить, что компьютер "понимает" фразы естественного языка? Продуцирование и понимание языка требует толкования символов. Недостаточно правильно сформировать строку символов.

52

Механизм понимания должен уметь приписывать им смысл или интерпретировать символы в зависимости от контекста. Что такое смысл? Что такое интерпретация?

Подобные философские вопросы встают во многих областях применения ИИ, будь то построение экспертных систем или разработка алгоритмов машинного обучения. Эти вопросы будут рассмотрены в данной книге по мере их появления. Философские аспекты ИИ обсуждаются также в главе 16.

1.3. Искусственный интеллект - заключительные замечания

Мы попытались дать определение искусственному интеллекту путем рассмотрения основных областей его исследования и применения. Этот обзор обнаружил молодую и многообе­щающую область науки, основная цель которой - найти эффективный способ понимания и применения интеллектуального решения проблем, планирования и навыков общения к широ­кому кругу практических задач. Несмотря на разнообразие проблем, затрагиваемых исследо­ваниями ИИ, во всех отраслях этой сферы наблюдаются некоторые общие черты.

Использование компьютеров для доказательства теорем, распознавания образов,

обучения и других форм рассуждений.

Внимание к проблемам, не поддающимся алгоритмическим решениям. Отсюда -

эвристический поиск как основа методики решения задач в ИИ.

Принятие решений на основе неточной, недостаточной или плохо определенной

информации и применение формализмов представлений, помогающих программисту справляться с этими недостатками.

Выделение значительных качественных характеристик ситуации.

Попытка решить вопросы семантического смысла, равно как и синтаксической формы.

Ответы, которые нельзя отнести к точным или оптимальным, но которые в каком

то смысле "достаточно хороши". Это результат применения эвристических методов в ситуациях, когда получение оптимальных или точных ответов слишком тру­доемко или невозможно вовсе.

Использование большого количества специфичных знаний в принятии решений.

Это основа экспертных систем.

Использование знаний метауровня для более совершенного управления стратегия­

ми принятия решений. Хотя это очень сложная проблема, затронутая лишь не­

сколькими современными системами, она постепенно становится важной областью

исследований.

Надеемся, что это введение даст некоторое понятие об общей структуре и значимости искусственного интеллекта. Предполагаем, что краткое обсуждение таких технических вопросов, как перебор и представления, не были излишне поверхностными и неясными, детальнее они будут рассмотрены впоследствии. Здесь они приведены для демонстрации их значимости в общей организации этой области.

Как мы отмечали при обсуждении агентского решения проблем, объекты приобретают смысл при взаимоотношении с другими объектами. Это не менее справедливо в отношении фактов, теорий и методов, образующих любую научную область. Мы

53

попытались дать понятие таких взаимосвязей, так что, когда будут представлены отдель­ные технические аспекты искусственного интеллекта, они займут свое место в посте­пенном понимании общей сущности и направлений этой сферы. Мы руководствуемся наблюдением, принадлежащим психологу и системному теоретику Грегори Бэйтсону [Bateson, 1979]:

"Разрушьте структуру, объединяющую предметы изучения, и вы неизбежно разрушите все его качество".

1.4. Резюме и дополнительная литература

Перспективная область ИИ отражает некоторые из древнейших вопросов, занимавших западную мысль, в свете современного вычислительного моделирования. Понятия рациональности, представления и мышления сейчас находятся, вероятно, под более при­стальным рассмотрением, чем во все былые времена, поскольку компьютерная наука требует их алгоритмического понимания! В то же время политические, экономические и этические рамки мира людей заставляют нас помнить об ответственности за последствия наших творений. Надеемся, последующие главы помогут вам лучше понять современные методики ИИ и извечность проблем этой области.

Отличными источниками по вопросам, поднятым в этой главе, являются труды [Haugeland, 1997, 1985], [Dennett, 1978, 1984, 1991, 1995]. Использованы такие первоисточники, как "Физика", "Метафизика" и "Логика" Аристотеля; работы Фреге; труды Бэб-биджа, Буля, Рассела и Уайтхеда. Весьма интересны работы Тьюринга, особенно его представления о природе интеллекта и возможности разработки интеллектуальных про­грамм [Turing, 1950]. Биография Тьюринга [Hodges, 1983] представляет собой отличное чтение. Критика теста Тьюринга может быть найдена в [Ford и Hayes, 1995].

Работы [Weizenbaum, 1976] и [Winograd и Flores, 1986] дают трезвую оценку ограничениям и этическим аспектам ИИ. Саймон [Simon, 1981] положительно высказывается об осуществимости искусственного интеллекта и его роли в обществе.

Упомянутые в разделе 1.2 применения ИИ призваны показать широту интересов исследователей ИИ и сформулировать многие изучаемые ныне вопросы. Учебник [Вагг и Feigenbaum, 1989] содержит введение в эти области. Кроме того, рекомендуем книги [Nilsson, 1998] и [Pearl, 1984]. В них подробно рассмотрены вопросы ведения игр, которые затронуты в главах 2-5. В главах 2, 3 и 12 обсуждается проблема автоматических рассуждений. Некоторая избранная литература по этой теме включает труды [Wos и др., 1984], [Bledsoe, 1977], [Boyer и Moore, 1979], [Veroff, 1977].

Прочитав главы 6 и 7, читатель может получить хорошее представление об экспертных системах из книг [Harmon и King, 1985], [Hayes-Roth и др., 1984], [Waterman, 1986] и [Durkin, 1994].

Понимание естественных языков - область непрекращающегося изучения, некоторые важные взгляды на нее выражены в [Allen, 1995], [Winograd, 1983], [Schank и Colby, 1973], [Wilks, 1972], [Lakoff и Johnson, 1999], [Jurafsky и Martin, 2000]; введение в эту область представлено в главах 6 и 13 этой книги.

Использование компьютеров для моделирования работы человеческого разума, кратко описанное в главе 16, более подробно обсуждается в [Newell и Simon, 1972], [Pylyshyn, 1984], [Anderson, 1978] и [Luger, 1994]. Планирование и робототехника (см. главы 7 и 14) представлены в т. 3 книги [Вагг и Feigenbaum, 1981], [Brooks, 1991а] и [Lewis и Luger, 2000].

54

ИИ-ориентированные языки и среды разработки рассматриваются в главах 14 и 15 этой книги, а также в [Forbus и de Kleer, 1993]. Машинное обучение обсуждается в главах 9-11; многотомном издании [Michalski и др., 1983,1986], [Kondratoff и Michalski, 1990]; журналы Journal of Artificial Intelligence и Journal of Machine Learning также являются важными источниками информации по этой теме.

Главы 10 и 11 представляют взгляд на интеллект с упором на модульность структуры и адаптацию в социальном и природном контексте. Работа [Minsky, 1985] - одна из наиболее ранних и побуждающих к размышлению работ, отстаивающих эту точку зрения (см. также [Ford и др., 1995] и [Langton, 1995]).

Книга [Shapiro, 1992] дает ясное и всестороннее описание области искусственного интеллекта. Эта энциклопедия также проводит детальный анализ многих разных подходов и противоречий, образующих Текущее состояние этой дисциплины.

1.5. Упражнения

Предложите и аргументируйте собственное определение искусственного интеллекта.

Приведите несколько дополнительных примеров аристотелевского различия между

"материей" и "формой". Можете ли вы показать, как ваши примеры вписываются в

теорию абстракции?

Западная философская традиция во многом выросла из проблемы взаимоотношения

разума и тела. По вашему мнению:

а) разум и тело - сущности разной природы, каким-то образом взаимодействующие;

б) разум - всего лишь результат "физических процессов";

в) тело - лишь иллюзия мысли?

Обсудите ваши мысли по поводу проблемы разума и тела и ее важность для теории искусственного интеллекта.

Приведите критические замечания по поводу тьюринговского критерия

"разумности" компьютерной программы.

Сформулируйте ваш собственный критерий "разумности" компьютерной программы.

Хотя вычислительная техника - относительно молодая дисциплина, философы и

математики размышляли о вопросах, существенных для автоматического решения

задач, на протяжении тысяч лет. Каково ваше мнение о существенности этих философских вопросов по отношению к проектированию устройств интеллектуального

решения проблем? Аргументируйте свой ответ.

Рассмотрев различия между архитектурами современных компьютеров и человеческого мозга, поясните, какое значение имеет исследование физиологической структуры и функции биологических систем для разработки программ ИИ? Аргументи­руйте свой ответ.

Выберите проблемную область, в которой, как вы считаете, затраты на разработку

экспертной системы были бы оправданы. Разъясните в общих чертах суть проблемы.

На основании своей интуиции скажите: какие аспекты принятия решений будет наиболее сложно автоматизировать?

55

9. Найдите еще два преимущества экспертных систем, кроме уже перечисленных в тек­сте. Обсудите их с точки зрения интеллектуальных, социальных или экономических результатов.

Поясните, почему вы считаете такой сложной проблему машинного обучения.

Считаете ли вы возможным для компьютера понимать и использовать естественный

(человеческий) язык?

Выявите и поясните два потенциально негативных последствия развития искусственного интеллекта для общества.

56

Часть II

Искусственный интеллект как представление и поиск

Все науки описывают основные характеристики систем, изучаемых ими. Эти ха­рактеристики неизменно являются качественными по своей природе, поскольку они задают термины, оперируя которыми, можно развить данную область науки

более детально...

Изучение логики и компьютеров показало, что интеллект присущ физическим символьным системам. В качественной структуре заключается основной принцип теории вычислительных систем. Символьные системы - это наборы комбинаций символов (шаблонов) и способов их обработки (процессов), которые в то же время описывают способы создания, разрушения и изменения символов. Наиболее важное свойство наборов символов заключается в том, что с их помощью можно определять объекты, процессы или другие наборы символов. Процессы при этом могут

быть интерпретированы...

Второй принцип качественной структуры искусственного интеллекта заключается в

том, что символьные системы решают задачи путем генерации возможных решений, а

затем проверяют их в процессе поиска (или перебора вариантов). Для решения задачи

обычно создаются символьные выражения, а затем они последовательно

модифицируются до тех пор, пока не будут достигнуты условия решения.

- Ньюэлл (Newell) и Саймон (Simon), лекция по случаю вручения премии Тьюринга в Ассоциации специалистов по компьютерной технике, 1976

Введение в представление знаний

В вышеупомянутой лекции Ньюэлл и Саймон доказывают, что интеллектуальная деятельность как человека, так и машины, осуществляется с использованием следующих средств.

Символьные шаблоны (комбинации символов), предназначенные для описания

важнейших аспектов области определения задачи.

Операции с этими шаблонами, позволяющие генерировать потенциальные решения проблем.

Поиск с целью выбора решения из числа всех возможных.

Описанные предположения формируют базис гипотезы о физической символьной системе (physical symbol system hypothesis) (раздел 16.1). Эта гипотеза лежит в основе наших попыток создания умных машин и делает очевидными основные предположения в иссле­довании искусственного интеллекта. Гипотеза о физической символьной системе неявно различает понятия шаблонов (patterns), сформированных путем упорядочения символов, и среды (medium), в которой они реализованы. Если уровень интеллекта определяется ис­ключительно структурой системы символов, то любая среда, которая успешно реализует правильные шаблоны и процессы, достигнет этого уровня интеллекта, независимо от того, составлена она из нейронов, логических цепей, или это просто механическая игрушка. Возможность построения машины, которая бы прошла тест Тьюринга, зависит от выше­упомянутого разграничения. Согласно тезису Черча о вычислимости по Тьюрингу [Machtey и Young, 1979] компьютеры способны осуществить любой эффективно описанный процесс обработки символьной информации. Разве из этого не следует, что должным образом за­программированный цифровой компьютер обладает интеллектом?

Гипотеза о физической символьной системе также вкратце описывает главные вопросы исследования в области искусственного интеллекта и разработки его приложений. К ним относится определение структур символов и операций, необходимых для интеллектуального решения задачи, а также разработка стратегий для эффективного и правильного поиска потенциальных решений, сгенерированных этими структурами и операциями. Эти взаимо­связанные проблемы представления знания и поиска (knowledge representation and search) лежат в основе современных исследований в области искусственного интеллекта.

Гипотеза физической символьной системы оспаривается критиками, которые утверждают, что интеллект является наследственно биологическим и экзистенциальным и не может быть зафиксирован с помощью символов [Searle, 1980], [Winograd и Flores, 1986]. Эти суждения относятся к господствующему направлению исследований в области ис­кусственного интеллекта. Они определяют такие направления исследований, как разви­тие теории нейронных сетей, генетических алгоритмов и агентно-ориентированных ме­тодов (подход "агент-действие"). Несмотря на вышеуказанные возражения, предположе­ния гипотезы физической символьной системы лежат в основе почти всех практических и теоретических работ в экспертных системах, в планировании и понимании естествен­ного языка. Эти проблемы будут рассмотрены в главе 16.

Задача любой схемы представления заключается в том, чтобы зафиксировать специфику области определения задачи и сделать эту информацию доступной для механизма реше­ния проблемы. Очевидно, что язык представления должен позволять программисту выра­жать знания, необходимые для решения задачи. Абстракция (abstraction), т.е. представле­ние только той информации, которая необходима для достижения заданной цели, является

58

необходимым средством управления сложными процессами. Кроме того, конечные программы должны быть рациональными в вычислительном отношении. Выразительность и эффективность являются взаимосвязанными характеристиками оценки языков представ­ления знаний. Многие достаточно выразительные средства представления в одних задачах совсем неэффективны в других классах задач. Иногда выразительностью можно пожертво­вать в пользу эффективности. В то же время нельзя ограничивать возможности такого ото­бражения, позволяющего фиксировать существенные знания, что приводит к эффективно­му решению конкретной задачи. Разумный компромисс между эффективностью и вырази­тельностью - нетривиальная задача для разработчиков интеллектуальных систем.

Языки представления знаний являются средством, позволяющим решать задачи. По существу, способ представления знания должен обеспечить естественную структуру выражения знания, позволяющую решить проблему. Способ представления должен сделать это знание доступным компьютеру и помочь программисту описать его структуру.

Эти взаимные компромиссы в выборе способа представления знания можно показать на примере представления чисел с плавающей точкой в компьютере (рис. П.1). Вообще, для полного описания вещественного числа требуется бесконечный ряд цифр, что не может быть выполнено на конечном устройстве, т.е. на машине с конечным числом состояний. Единственное решение этой дилеммы - представление числа в виде двух частей: его значащих цифр и положения десятичной точки в пределах этих цифр. Несмотря на то что ве­щественное число без искажения нельзя хранить в компьютере, можно создать его представление, адекватно функционирующее в большинстве практических приложений.

Вещественное число: я

Десятичный эквивалент: 3,1415927 . . .

Представление с плавающей точкой: | 31416 | 1 |

Экспонента Мантисса

Представление в памяти компьютера: 11100010

Рис. II.1. Различные представления вещественного числа п

Представление числа с плавающей точкой уступает в выразительности, но выигрывает в эффективности. Такое представление позволяет выполнять многократные арифме­тические операции, обеспечивает эффективность их выполнения, не ограниченную точ­ностью вычислений с предельной ошибкой округления при любой предварительно за­данной погрешности. Представление числа с плавающей точкой также позволяет анализировать ошибки округления. Подобно всем представлениям, это лишь абстракция, символьный шаблон, определяющий желаемый логический объект, но не сам объект не­посредственно.

Массив - еще одно представление, принятое в теории вычислительных систем. Для многих задач оно более естественно и эффективно, чем архитектура памяти, реализованная в аппаратных средствах. Это представление во многих задачах оказывается естест­венным и эффективным, уступая при этом в выразительности, что наглядно показано на следующем примере обработки изображений. На рис. П.2 дано оцифрованное изображе­ние хромосом человека на стадии метафазы. В процессе обработки изображения опреде­ляются номер и структура хромосомы, обнаруживаются разрывы, отсутствующие фраг­менты и другие аномалии.

59

Визуальная сцена состоит из точек изображения. Каждая точка, или пиксель, характеризуется расположением и числовым значением, представляющим уровень се­рого цвета. Поэтому всю сцену вполне естественно представить в виде двухмерного массива, где номер строки и столбца элемента массива определяет место располо­жения пикселя (координаты X и У), а сам элемент массива - уровень серого цвета в этой точке. Для обработки подобного изображения необходимо реализовать такие операции, как поиск изолированных точек для удаления шума из образа, нахождение пороговых уровней для распознаваемых объектов и их границ, суммирование непре­рывных элементов для определения размеров и плотности образов. Затем получен­ные данные, описывающие изображения, могут быть преобразованы. Этот алгоритм удобно программировать на языке FORTRAN, в котором непосредственно реализо­ваны операции с массивами. Однако программа была бы слишком громоздкой, если бы в ней использовались такие средства, как исчисление предикатов, записи или ас­семблерный код, потому что они не обеспечивают естественного представления данного материала.

Представляя изображение в виде массива пикселей, мы жертвуем разрешением (сравните фотографию в газете с исходным изображением). Кроме того, массивы пикселей не могут достаточно точно отображать семантическую организацию образа. Напри­мер, массив пикселей не может представить организацию хромосом в отдельном ядре клетки, их генетическую функцию или роль метафазы в делении клетки. Эти знания лег­че фиксировать, используя такие понятия, как исчисление предикатов (глава 2) или се­мантические сети (глава 6).

Схема представления знания должна удовлетворять следующим условиям.

60

Адекватно выражать всю необходимую информацию.

Поддерживать эффективное выполнение конечного кода.

Обеспечивать естественный способ выражения необходимых знаний.

Мак-Дермотт (McDermott) и его последователи утверждают, что секрет написа­ния хорошей программы, основанной на знаниях, заключается в выборе подходящих средств представления. Программисты, специализирующиеся на языках низкого уровня (Basic, FORTRAN, С и т.д.), порой строят неудачные экспертные системы только потому, что эти языки не обладают достаточной выразительностью и не обеспечивают модульность, необходимую для программирования на основе знаний [McDermott, 1981].

Вообще говоря, задачи ИИ не решают путем их упрощения и "подгонки" к уже имеющимся понятиям, предлагаемым традиционными формальными системами, на­пример массивам. Эти задачи связаны скорее с качественными, а не количествен­ными проблемами, с аргументацией, а не вычислениями, с организацией больших объемов знаний, а не реализацией отдельного четкого алгоритма. Чтобы удовлетво­рять этим требованиям, язык представлений искусственного интеллекта должен об­ладать следующими свойствами.

Обрабатывать знания, выраженные в качественной форме.

Получать новые знания из набора фактов и правил.

Отображать общие принципы и конкретные ситуации.

Передавать сложные семантические значения.

Обеспечивать рассуждения на метауровне.

Рассмотрим этот перечень более подробно.

Обработка знаний, выраженных в качественной форме

Программирование искусственного интеллекта требует средств фиксации (выражения) и рассуждений о качественных аспектах задачи. Рассмотрим простой при­мер - размещение блоков на столе (рис. П.З).

Рис. 11.3. Мир блоков

Для представления расположения блоков можно использовать декартову систему координат, где значения X и V задают координаты каждой вершины блока. Хотя этот подход описывает мир блоков и является, несомненно, правильным представлением для многих задач, в данном случае он неудачен, поскольку не позволяет непосредст­венно зафиксировать свойства и отношения, необходимые для качественных выво­дов. Это выводы о том, какие из блоков уложены друг на друга и какие имеют

61

открытый верх, чтобы их можно было взять и поднять. Исчисление предикатов (predicate calculus) непосредственно фиксирует эту наглядную информацию. В исчислении предикатов мир блоков может быть описан логическими утверждениями:

clear(c)

clear(a)

ontable(a)

ontable(b)

on{c, b)

cutoe(b)

cube(a)

pyramid(c)

Первое слово каждого выражения (on, clear и т.д.) - предикат (predicate), обозначающий некоторое свойство или соотношение его параметров, приведенных в круглых скобках. Параметры - это символы, обозначающие объекты (блоки) в предметной облас­ти. Совокупность логических предложений описывает важные свойства и соотношения ми­ра блоков. Исчисление предикатов предоставляет программистам задач искусственного ин­теллекта четкий язык описания и способ рассуждений относительно качественных аспектов системы. Исчисление предикатов не единственный способ представления, но этот подход, вероятно, наиболее понятен для многих задач. Кроме того, он является достаточно общим, чтобы служить основой для других формальных моделей представления знания. Исчисле­ние предикатов подробно рассматривается в главе 2.

Вышеупомянутый пример иллюстрирует точное представление блоков на рис. П.З. Это явное представление, поскольку очевидна связь между его элементами и нашим собственным пониманием "мира" блоков. Знание можно также представлять неявно. Например, с помощью нейронной сети (глава 10) можно представить эту конфигурацию блоков в виде шаблонов взаимодействия между искусственными нейронами. Соотношения между этими шаблонами и элементами мира блоков не очевидны. В большинстве случаев единственный способ понять, какие знания содержатся в сети, - это рассмот­реть ее работу на примерах. Тем не менее возникает вопрос о соответствии неявных представлений их явным эквивалентам: способна ли данная модель нейронной сети пе­редать все знания, которые необходимы в задаче? Сможет ли компьютер получать дос­туп и эффективно управлять этими знаниями? Можно ли гарантировать правильность логических выводов, сделанных нейронной сетью?

Логическое получение новых знаний из набора фактов и правил

Любой интеллектуальный объект должен обладать способностью логически получать дополнительные знания из имеющегося описания реального мира. Люди, например, не запоминают точное описание каждой пережитой ситуации (да это и невозможно). Скорее, мы способны рассуждать об абстрактных описаниях классов объектов и состояний. И язык представления знаний должен обеспечить эту возможность.

В примере из мира блоков можно определить тест, устанавливающий, является ли блок открытым, т.е. не располагается ли на его верхней грани другой объект. Это важный вопрос для робототехнической системы, в которой рука робота должна поднимать блоки или укладывать их друг на друга. Это свойство не обязательно явно приписывать каждому блоку. Можно определить общее правило, которое позволяет системе делать

62

логические выводы из имеющихся фактов. В исчислении предикатов это правило может выглядеть так.

Оно означает следующее: для любого элементах элемент X является открытым, если не существует такого У, что Y находится на X. Это правило может применяться в различных ситуациях при замене значений X и У. Позволяя программисту формулировать обобщенные правила вывода, исчисление предикатов предоставляет большие удобства в выражении знания. Кроме того, исчисление предикатов дает возможность проектировать гибкие и достаточно общие системы, умеющие действовать разумно в различных ситуациях.

Нейронные сети тоже выводят новые знания из имеющихся фактов, хотя правила, используемые ими, скрыты. Классификация - это общепринятая форма логического вы­вода, выполняемого такими системами. Например, нейронную сеть можно обучить узна­вать все конфигурации блоков, в которых пирамида располагается поверх блока, имею­щего форму куба.

Отображение общих принципов наряду с конкретными ситуациями

В предыдущем разделе было продемонстрировано применение логических правил для вывода дополнительных знаний из основных фактов. Кроме того, на примере с блоками было показано, как использовать переменные в исчислении предикатов. Поскольку интеллектуальная система должна быть максимально общей, любой хороший язык представле­ния нуждается в переменных. Необходимость качественных рассуждений делает использо­вание и реализацию переменных чрезвычайно сложной и тонкой задачей по сравнению с их трактовкой в традиционных языках программирования. Значения, типы и правила обра­ботки данных в языках программирования, ориентированных на вычисления, чрезвычайно ограничены и не годятся для реализации интеллектуальных систем. Для обработки связан­ных переменных и объектов существуют специальные языки представления знаний (главы 2, 14, и 15). Высокая способность обобщения- это ключевое свойство нейронных сетей, систем обучения и других адаптивных систем. Эффективное обучение системы-агента заключается в том, чтобы научиться обобщать данные, полученные в процессе тако­го обучения, а затем правильно применить полученные знания в новых ситуациях.

Передача сложных семантических значений

Во многих областях искусственного интеллекта решение задачи требует использования высокоструктурированных взаимосвязанных знаний. Например, чтобы описать автомобиль, недостаточно перечислить его составные части. Адекватное описание должно учитывать также способ соединения и взаимодействия этих частей. Структурное представление необходимо во многих задачах, начиная с таких таксономических систем, как система классификации рас­тений по видам и родам, и заканчивая средствами описания таких сложных объектов, как ди­зельный двигатель или человеческое тело в терминах составляющих их частей. В примере блоков основой полного описания расположения были взаимодействия предикатов.

Семантические отношения также необходимы для описания причинных связей между событиями. Они позволяют понять простые рассказы, например, детские сказки, или представить план действий робота как последовательность элементарных действий, которые должны быть выполнены в определенном порядке.

63

Хотя все эти ситуации могут быть представлены в виде совокупности предикатов или адекватных им формализмов, для программиста, имеющего дело со сложными понятия­ми и стремящегося дать устойчивое описание процессов в программе, необходимо неко­торое высокоуровневое представление структуры процесса.

Например, канарейку можно описать так. Канарейка- это маленькая желтенькая птичка, а птичка- это крылатое летающее позвоночное животное. Эта формулировка может быть представлена в виде набора логических предикатов:

hassize{canary, small) hascovering(bird, feathers) hascolor{canary, yellow) hasproperty(bird, flies) isa(canary, bird) isa{bird, vertebrate)

Предикатное описание можно представить графически, используя для отображения предикатов, определяющих отношения, дуги (arc) или связи (link) графа (рис. П.4). Такое описание, называемое семантической сетью (semantic network), является фундаментальной методикой представления семантического значения. Поскольку отношения явно выражены связями графа, алгоритм рассуждений о предметной области может строить соответст­вующие ассоциации, просто следуя по связям. В примере с канарейкой системе нужно про­следовать только по двум дугам, чтобы решить, что канарейка - это позвоночное живот­ное. Это значительно эффективнее, чем утомительный исчерпывающий поиск в базе дан­ных, содержащей описания на языке исчисления предикатов вида isa(X, V).

Кроме того, знания могут быть организованы так, чтобы отражать естественную структуру экземпляра класса из данной предметной области. Некоторые связи, напри­мер, связи isa на рис. П.4, указывают на принадлежность к классу и задают свойства, ха­рактерные для описания данного класса, которые наследуют все члены класса. Этот ме­ханизм наследования встроен в язык непосредственно и позволяет сохранять знания на самом высоком уровне абстракции. Наследование - инструмент представления таксо­номической (классифицированной) структурированной информации, который гаранти­рует, что все члены класса обладают общими свойствами.

Теория графов эффективно и естественно выражает сложные семантические знания. Кроме того, она позволяет описывать структурную организацию базы знаний. Семанти­ческие сети - это достойная альтернатива исчислению предикатов.

64

Возможно, наиболее важное свойство семантических сетей - это способность описывать семантические значения для систем понимания естественного языка. Например, если необходимо понять детскую сказку, журнальную статью или содержание Web-страницы, то в соответствующей прикладной программе следует закодировать семанти­ческую информацию и отношения, отражающие знания. Семантические сети - подхо­дящий для этого механизм. Они обсуждаются в главе 6, а их применение для описания задач понимания естественного языка - в главе 13.

Рассуждения на метауровне

Интеллектуальная система должна не только знать предмет, но также знать о том, что она знает этот предмет. Она должна быть способна решать задачи и объяснять эти решения. Система должна описывать свои знания как в конкретных, так и в обобщенных тер­минах, узнавать их ограничения и учиться в процессе взаимодействия с миром. Эта "осведомленность о своих знаниях" составляет более высокий уровень знаний, называе­мых метазнаниями, необходимых для проектирования и адекватного описания интел­лектуальных систем.

Проблему формализации метазнаний впервые исследовал Бертран Рассел (Russell) в своей теории логических типов. Кратко ее можно описать так: если множества могут быть членами других множеств (ситуация, аналогичная обладанию знанием о знании), то могут существовать множества, которые являются членами самих себя. Согласно теории Рассела это ведет к неразрешимым парадоксам. Рассел отверг эти парадоксы, классифицируя множества как относящиеся к различным типам, в зависимости от того, содержат они отдель­ные элементы или множества элементов и т.д. Множества не могут быть членами мно­жеств, относящихся к типу меньшего или равного значения. Это соответствует различиям между знаниями и метазнаниями. Но при попытке формально описать эти рассуждения Рассел столкнулся с многочисленными трудностями [Whitehead и Russell, 1950].

Способность обучаться на примерах, опыте или понимать инструкции высокого уровня (в отличие от жесткого программирования) зависит от применения метазнаний. Методы представления знаний, разработанные для программирования задач искусственного интеллекта, обеспечивают возможность адаптации и модификации, так необ­ходимую для обучающихся систем, и формируют основу для дальнейших исследова­ний (главы 9-11).

Чтобы удовлетворять требованиям символьных вычислений, искусственный интеллект должен обладать такими средствами, как языки представления, например, исчисле­ние предикатов, семантические сети, фреймы и объекты (главы 2 и 6). LISP и PROLOG - языки для реализации этих и других представлений. Все эти инструменталь­ные средства подробно рассматриваются в книге.

Как следует из приведенных выше рассуждений о необходимых свойствах языка представления знаний, решение задачи искусственного интеллекта можно свести к выбору представления среди возможных альтернатив. Выбор подходящего представления весьма важен для разработчиков компьютерных программ, обеспечивающих решение задач искусственного интеллекта. Несмотря на большое разнообразие языков представ­ления, используемых в искусственном интеллекте, все они должны удовлетворять общим требованиям выразительности, эффективности и правильности дедуктивных выводов. Выбор и оценка языков представлений - весьма важная задача как для исследователей, так и для программистов.

65

Решение задачи методом поиска

Вторым аспектом гипотезы о символьной системе Ньюэлла и Саймона является поиск решения задачи среди альтернативных вариантов. С точки зрения простого здравого смысла это выглядит разумно, поскольку именно так задачи решает человек. Рассматривая ряд альтернативных вариантов, мы пытаемся решить проблему. Шахматист обычно изучает возможные ходы и выбирает оптимальные согласно та­ким критериям, как вероятные ответы противника или некоторая глобальная страте­гия, поддерживаемая на каждом этапе игры. Игрок также рассматривает преимуще­ства в краткосрочных стратегиях (например, взятие ферзя противника), возможно­сти пожертвовать фигуру за позиционное преимущество или строит предположения относительно психологического состояния противника, его опыта и умения. Мате­матик при доказательстве трудной теоремы выбирает свою линию среди большого набора сложных стратегий. Врач может систематично рассматривать ряд возможных диагнозов и т.д. Такое интеллектуальное поведение лежит в основе методики поиска решения в пространстве состояний.

В качестве простого примера рассмотрим игру "крестики-нолики". Для любой заданной ситуации всегда существует только конечное число допустимых ходов игрока. Первый игрок может разместить крестик в любой из девяти клеточек пустой игровой доски. Каждый из таких шагов порождает различные варианты заполнения игровой доски, которые позволяют противнику сделать восемь возможных ответных ходов и т.д. Эту совокупность (в зависимости от возможной конфигурации игровой доски) можно представить в виде вершин графа. Дуги графа представляют разрешенные ходы, приводящие от одной конфигурации игровой доски к другой. Узлы этого графа соответствуют различным состояниям игрового поля. Результирующая структура называется графом пространства состояний.

Можно построить граф пространства состояний для игры "крестики-нолики" (рис. II.5). Корневая вершина этого графа будет соответствовать пустой игровой доске, указывающей на начало игры. Каждый следующий узел графа будет представлять состояние игровой доски, возникающее в процессе игры в результате до­пустимых ходов, а дуги между ними - связи между вершинами. Значение этого графа состоит в том, что он дает возможность проследить последовательность шагов в любой игре. Проход начинается с вершины, представляющей пустую игровую доску, а перемещения по дугам приводят к вершинам-состояниям, представляющим или очередной ход, или победу. Представление в пространстве состояний, таким обра­зом, позволяет рассматривать все возможные варианты игры "крестики-нолики" как различные пути на графе пространства состояний.

Описав игру таким образом, можно с помощью поиска на графе найти эффективную игровую стратегию. Иными словами, определить все пути, ведущие к наиболь­шему числу побед и наименьшему числу поражений, и выбрать такую игру, которая всегда будет вынуждать противника идти по одному из оптимальных для нас путей. Возможность выбора эффективной стратегии - это не единственное преимущество графа. Регулярность и точность представления пространства состояний позволяют непосредственно реализовать игру на компьютере.

66