Общий решатель задач

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

Одна из первых и наиболее известных программ, в которой такой подход был реализован, — это «Общий решатель задач» (General Problem Solver — GPS). Первая версия GPS была разработана Гербертом Саймоном и Аланом Ньюэллом (при участии Кристофера Шоу) в 1957 году (развитие и исследование программы осуществлялось до 1969 года) на основе ранее разработанной ими программы «Логик-теоретик». Кроме того, разработка GPS тесно связана с теми исследованиями Саймона по процессам принятия решений в экономических организациях, за которые он получил Нобелевскую премию по экономике 1978 года. Таким образом, GPS рассматривался не просто как компьютерная программа, а как модель человеческих рассуждений. И по сей день упоминания о GPS можно встретить не только в книгах по искусственному интеллекту, но также и по когнитивной психологии. Кроме того, именно работа над GPS привела к формулировке Ньюэллом и Саймоном уже упоминавшейся гипотезы физической символьной системы о реализуемости мышления на произвольных физических носителях, выполняющих символьные вычисления.

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

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

Как видно, подход, использованный в GPS, полностью соответствует идее Торндайка о природе мышления животных как решения задач с использованием перебора имеющихся в распоряжении операций. Но мог ли GPS решать задачи, аналогичные тем, что Кёлер предъявлял обезьянам? Задача «обезьяна и банан» была одной из первых, на которой тестировался GPS.

В простейшем варианте этой задачи легко можно выделить несколько объектов: ОБЕЗЬЯНА, БАНАН, ЯЩИК, — каждый из которых может находиться в нескольких состояниях (положениях из множества «место-1», «место-2», «под бананом» для обезьяны и ящика и «на полке», «в руке» для банана). У обезьяны есть несколько операций: ИДТИ, ТОЛКАТЬ ЯЩИК, БРАТЬ БАНАН. Для каждого из действий описывается его эффект в зависимости от положений объектов. Условие задачи задается в виде начальных положений объектов и конечной цели, включающей только положение банана «в руке».

GPS легко находит цепочку операций, позволяющих обезьяне заполучить банан. Кстати, можно ли теперь на основе модели эвристического программирования дать хотя бы некоторые содержательные ответы на вопросы об особенностях решения задач обезьянами, поставленные выше, при обсуждении мышления животных? Понятно, что основные особенности процесса решения задач обезьянами связаны с комбинаторным взрывом и эвристиками, используемыми для его преодоления. При увеличении числа действий в цепочке, позволяющей решить задачу, происходит экспоненциальный рост пространства поиска, поэтому, начиная с некоторого момента, даже небольшое усложнение задачи делает ее непреодолимой для обезьяны. Однако если животное успело познакомиться с некоторыми промежуточными решениями, то решение целой задачи может быть описано более короткой цепочкой действий, и обезьяна с ней справится. При этом используются и общие эвристики, к примеру, в перебор не вовлекаются действия над объектами, находящимися вне поля зрения. Подобные эвристики очень эффективно отсекают неперспективные варианты, но не являются универсальными. Человек, в отличие от животных, может отказаться от подобных эвристик, хотя по умолчанию их использует. Нередко мы говорим: «не подумал», — когда какой-то из вариантов действий выпадает из нашего поля зрения. Решается ли проблема компромисса между вычислительными затратами и полнотой поиска в GPS?

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

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

Помимо задачи «обезьяна и банан» GPS был способен решать широкий круг задач. В частности, он успешно справлялся с задачами о Ханойских башнях и семи Кёнигсбергских мостах, а также более серьезными задачами, включающими аналитическое интегрирование, некоторые шахматные и геометрические задачи, задачи планирования и т. д. При этом «обучение» GPS решению задач нового типа можно считать заметно более легким, чем обучение ребенка решению этих же задач.

Вероятно, GPS мог бы быстро справиться и со многими тестами IQ, не требующими знаний о реальном мире (или при условии, что необходимые знания были бы даны в описании проблемной среды), и показал бы высокий уровень «интеллекта», что, однако, говорит не столько о широких возможностях GPS, сколько об ограниченности тестов IQ. Конечно, GPS решал только корректно поставленные задачи. Интересно, что значительная часть упоминавшейся выше книги Пойа «Математическое открытие» посвящена вопросу формализации задач: ведь школьники начинают свое обучение со словесных задач, в большинстве своем становящихся тривиальными после того, как для них удается найти четкую математическую формулировку.

Относительно алгоритмически неразрешимых проблем мы уже отмечали, что важность правильной постановки задачи сложно переоценить: правильно поставленный вопрос — это уже половина ответа. Этот вывод верен и для разрешимых, но сложных задач. Конечно, нельзя сказать, что правильные постановки могут полностью избавить нас от необходимости рассматривать NP-полные задачи, но отсутствие хорошей формулировки проблемы делает пространство вариантов крайне широким, а поиск в нем — чрезвычайно затруднительным. Это хорошо видно на примере творчества или изобретательства, где «лабиринт вариантов» столь разветвлен, что даже просто выявление всех возможных направлений «движения» невозможно. Здесь эти направления должны не просто перебираться, но генерироваться (и лишь потом отсекаться), за что вполне могут отвечать иные механизмы (и даже возможно, что за механизмы порождения и отсечения вариантов отвечают разные полушария мозга). Что уж говорить о проблеме выбора жизненного пути, где мы зачастую просто не рассматриваем никаких возможностей, выходящих за рамки наших случайных стереотипов? Эти стереотипы — эвристики, позволяющие беспощадно отсекать огромное количество неперспективных вариантов. Без них человеческий мозг потонул бы в море вариантов и не нашел бы никакого приемлемого решения. Но вместе с тем стереотипы приводят к пропуску неожиданных решений, которые могут оказаться гораздо более эффективными. И даже в науке большинство ученых сейчас занимается поиском в актуальных направлениях, определенных в текущей научной парадигме, а не открытием новых областей поиска. Конечно, этот подход является оправданным, но все же уж очень он напоминает перебор методом «грубой силы». Умение управлять эвристиками поиска сейчас является своего рода искусством, которому толком нигде не учат, а проявление этого умения рассматривается как признак одаренности (но именно обычные люди с «дефектом» отсутствия гениальности могут превратить ее из природного дара в доступный для каждого инструмент).

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

Вполне естественно, что вопрос о формализации задач был проигнорирован в начале исследований в области ИИ, поскольку к нему при имеющемся тогда уровне знаний было просто невозможно подступиться. Попробуйте представить, какой должна быть программа, способная решать такие простые задачи: «Один кран наполняет бочку за 10 минут, второй — за 12, третий — за 15. За какое время краны наполнят бочку, работая одновременно?» и «Есть три работника, каждый из которых по отдельности может справиться с некоторой работой за 10, 12 и 15 часов соответственно. Сколько времени им необходимо, чтобы выполнить ее вместе?» Совпадают ли эти задачи по содержанию? Какие упрощения нужно сделать, чтобы суметь их однозначно решить? Как до этих упрощений можно догадаться?

По сути, формализация задачи — это построение «лабиринта», который в эвристических программах считался четко заданным. GPS стал первой программой, в которой этот «лабиринт» задавался извне, а не кодировался в теле программы. GPS оказался заметно слабее, чем специализированные эвристические программы: для решения сложных задач ему не хватало сложных эвристик и оценивающих функций, которые можно было задать в виде программного кода, но которые не могли быть выражены на языке описания предметной среды. А без таких эвристик универсальные процедуры поиска оказывались бессильными перед задачами, в которых размеры деревьев вариантов неизмеримо превосходят возможности плохо направленного поиска. В частности, GPS не мог играть в шахматы, поскольку в них не удавалось разбить конечную цель (выигрыш в партии) на непосредственно достижимые подцели.

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