Что такое Универсальный решатель проблем — программа из 1955 года

Когда Герберт Саймон и Алан Ньюэлл в 1955 году начали придумывать Logic Theorist, понятия «искусственный интеллект» ещё не существовало.

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

А потом они решили сделать ещё более крутую штуку — программу, которая сможет решить любую проблему, поставленную перед людьми. Они назвали её GPS — General Problem Solver. По идее, у них должен был получиться разумный электронный советчик, который точно знает, как лучше всего поступить в сложной ситуации из серии «аккумулятор на машине разрядился, а вам срочно нужно отвезти ребёнка в детский сад». Ну или дать ответ на главный вопрос жизни, Вселенной и всего такого.

Но вот получилось вообще не то.

«Ты только посмотри, что GPS предлагает нам сделать! ^[1]»

Герберт Саймон — вообще-то политолог. Он изучал, как устроены человеческие мозги ^[2] и принимаются решения, как работает бюрократия. Вот тут ^[3] можно почитать о нём подробнее. Алан Ньюэлл же был программистом, работал в RAND Corporation ^[4] и изучал логистику вместе с теорией организации. К идее о создании мыслящего компьютера они пришли примерно одновременно под влиянием работ о связи, кодировании и компьютерах Гёделя ^[5], Тьюринга ^[6] и Шеннона ^[7], а также статей о нейропсихологии и психических процессах Маккалока и Питтса ^[8].

Великие умы, как говорится, мыслят одинаково.

А потом они встретились и достаточно оперативно придумали, как это сделать.

Так появилась программа Logic Theorist ^[9]

Она рассуждала о заданных вещах и умела доказывать логические теоремы примерно на уровне студента-второкурсника. В качестве экзамена LT предложили доказать 52 теоремы символической логики из второй главы трёхтомного опуса магнума Альфреда Уайтхеда и Бертрана Рассела Principia Mathematica. С 38 из них программа справилась играючи, причём для некоторых даже сформулировала доказательства изящнее, чем те, что были приведены в книге (этим она порадовала Рассела). Кстати, в большинстве случаев программа сразу находила прямой путь к решению задачи и вообще не использовала метод проб и ошибок в отличие от студентов-второкурсников.

Напоминаю: компьютеры тогда выглядели примерно вот так. И этот ещё не самый большой.

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

Как была устроена Logic Theorist

Основные термины, которые нужны для понимания её работы, таковы:

• Мышление ^[2] — то есть превращение одних абстрактных символов в другие в кратковременной и долговременной памяти компьютера.
• Символы — то, что несёт в себе определённые знания, воздействует на информационные процессы, изменяет поведение программы и запускает новые процессы в работу.
• Эвристики — то есть совокупность методов и логических приёмов, которые приводят к решению сложных задач. Правда, у эвристик есть одно любопытное свойство: с одной стороны, они весьма эффективны, но с другой — не всемогущи. То есть решения проблемы они не гарантируют.

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

Потенциал эвристики они обнаружили, когда описывали собственные когнитивные усилия во время доказательства теорем. В итоге к концу 1955 года они реализовали несколько весьма многообещающих эвристик и вручную смоделировали работу программы LT. То есть попросту написали всю программу на карточках и раздали их своим аспирантам, а также жене и детям Саймона: проиграли работу программы «вживую».

Написать код, чтобы утрамбовать эту программу в компьютер (и вообще придумать язык для обработки списков), Ньюэлл попросил помочь Клиффорда Шоу — программиста, который тоже работал в RAND.

В августе 1956 года Саймон, Ньюэлл и Шоу выкатили Logic Theorist в продакшен на компьютере JOHNNIAC в головном офисе RAND в Санта-Монике.

Тот самый JOHNNIAC, к слову, выглядел вот так ^[10]

У Logic Theorist было два вида памяти: рабочая, куда информация попадает на время, и долгосрочная, которая запоминает данные навсегда. В ней хранятся аксиомы и теоремы, которые программа уже доказала. В одной ячейке рабочей памяти хранятся один элемент и все его атрибуты, которые нужны при решении одной задачи. Как правило, на каждую задачу нужны три ячейки рабочей памяти, каждая из которых хранит один элемент вместе с атрибутами.

LT состояла из двух блоков: первый анализировал задачи и создавал в случае необходимости подзадачи, а второй применял правила исчисления высказываний.

Теоремы эта программа доказывала в обратном направлении: стартовала в точке «вот высказывание, которое надо доказать» и дальше с помощью тех самых эвристик последовательно делала выводы до тех пор, пока не утыкалась в аксиому, которая не требует доказательств, или теорему, которая уже была доказана чуть раньше.

При этом LT реализовывала четыре вида процессов:

1. Инструкции. Могут выполнять примитивные операции над выражением в рабочей памяти или переход к другой инструкции.

2. Элементарные процессы. Последовательность инструкций, которые можно вызвать для решения этой задачи.

3. Методы. Это последовательность элементарных процессов. Вариантов может быть четыре:

• Подстановка — заданное выражение пытается преобразоваться в доказанную теорему или аксиому путём замены переменных и логических связок.
• Отстранённость — заданное выражение пытается найти доказанную теорему или аксиому формы 𝐴→𝐵', где B' получается из 𝐵 после подстановки, а затем пытается доказать 𝐴 путём подстановки.
• Переход по цепочке — заданное выражение 𝐴→𝐶 пытается найти доказанную теорему или аксиому формы 𝐴→𝐵, а затем пытается доказать 𝐵→𝐶 путём подстановки.
• Обратная цепочка — заданное выражение 𝐴→𝐶 пытается найти доказанную теорему или аксиому формы 𝐵→𝐶, а затем пытается доказать 𝐴→𝐵 путём подстановки.

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

Трагически недооценённая Logic Theorist

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

Ньюэлл, Саймон и Шоу представили ^[11] Logic Theorist на Втором Симпозиуме ^[12] по теории информации — на той же самой конференции, где Маккарти сформулировал понятие «искусственный интеллект».

То есть что такое искусственный интеллект ^[12], эти учёные мужи поняли, а на программу, которая посматривала в его сторону, большого внимания не обратили

А потом с LT произошла ещё одна очень обидная вещь. Учёные попытались опубликовать в журнале The Journal of Symbolic Logic новое изящное доказательство одной из теорем Уайтхеда и Рассела, придуманное машиной. Но в журнале тоже не поняли, в чём прикол, и в публикации отказали со словами: «Новое доказательство элементарной теоремы — это слишком просто и никого не заинтересует». А то, что в соавторы статьи затесался компьютер, — ну какая разница, в конце концов!

Следующий проект — Универсальный решатель проблем

General Problem Solver, или GPS, должен был моделировать ^[13] решение проблем человеком и уметь выпутываться из разных сложных ситуаций. Идейной основой этой программы стало сочетание вычислительной науки и психологии. GPS должен был стать логическим обобщением программ, предназначенных для решения задач в самых разных областях — от исчисления высказываний до планиметрии.

В отличие от Logic Theorist GPS работал с анализом средств и целей и был реализован на языке программирования третьего порядка IPL. Главное новшество было в том, что блоки анализа задач и создания подзадач в нём были отделены от методов их решения как логически, так и в программной реализации. Та часть программы, которая искала решение задачи, не имела никакой информации о том, с каким типом задачи она работает. Специфичные для каждой задачи знания организовывались в отдельные структуры: объекты и операторы — для их преобразования, а GPS должен был составить пары из начального и конечного объектов.

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

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

По идее, GPS должен был уметь решать любые проблемы, которые можно было бы выразить с помощью формул (WFF) или предложений Хорна ^[14].

Работало это так:

1. Пользователь определяет объекты и операции, которые можно выполнять с объектами.
2. GPS генерирует эвристику посредством анализа средств и целей для решения проблем. Он сосредотачивается на операциях, которые доступны прямо сейчас, выясняет, какие входные данные приемлемы и какие результаты должны быть получены.
3. Затем создаёт подцели и придумывает, как к ним приблизиться. И самым первым делом проверяет наиболее перспективные ветви поиска. Сначала он находит разницу между текущим объектом и конечным заданным, потом классифицирует её, сопоставляет набор действий, которые могли бы уменьшить различие между текущим и целевым объектами.
4. На каждом шагу поиска GPS ищет эти различия и подбирает подходящую последовательность операторов в глубину до тех пор, пока вообще получается их применять, а ветвь поиска выглядит перспективной. Как только она перестаёт быть таковой, он откатывается назад и начинает поиск сначала.

В общем, придумано всё было очень хорошо, но что-то пошло не так.

Универсальный решатель проблем оказался не совсем универсальным

То есть загадку про кувшины ^[15] с водой или Ханойскую башню ^[16] он решить мог. С задачками по шахматам справлялся, а с реальным миром, анализировать который было интереснее всего, не получалось. Внезапно выяснилось, что пространство вариантов и вероятностей настолько велико, что оперативно обыскать его в поисках решения просто невозможно.

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

Но зато из него выросла когнитивная архитектура Soar

И не только она — ещё и GOMS ^[17], ACT-R ^[18] и EPIC ^[19]. Но Soar, пожалуй, — самая известная из них (и Алан Ньюэлл тоже приложил руку к её разработке).

Если вкратце, то Soar умеет кодировать, использовать и изучать все типы знаний для реализации широкого спектра когнитивных способностей человека. С её помощью было создано огромное количество моделей самых разных аспектов человеческого поведения. Soar принимала решения, выбирая различных операторов, умела учиться и активно взаимодействовала с внешними языковыми средами, в том числе — с C++, Java, Tcl и Python, через язык разметки Soar (SML).

Soar до сих пор используют:

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

Несмотря на то, что сами программы LT и GPS «не взлетели», их появление — важная веха в развитии программирования

Ещё в 1957 году Саймон заявил, что машина, обученная играть в шахматы, превзойдёт навыки людей через десять лет. И в принципе так в итоге и случилось, но на тридцать лет ^[20] позже, чем он запланировал, — в 1997-м. А в го ^[21] и покер ^[22] — ещё позже: в 2016 году и начале 2017-го.

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

А началось всё с создания программы, которая сумела доказать несколько логических теорем на уровне второкурсника технического вуза и продемонстрировала, что машина может выполнять задачи, которые до сих пор считались доступными только человеческому разуму.

Помимо создания первого LT и GPS, один из его «отцов» (Герберт Саймон) вместе с Эдвардом Фейгенбаумом разработал EPAM — одну из первых теорий обучения в виде компьютерной программы. А следом за ней — компьютерную модель CHREST ^[23], которая занимается тем, что объясняет, как из элементарных отрывков информации образуются строительные блоки для более сложных структур.

И работы эти, кстати, оказали огромное влияние не только на кибернетику и представления об ИИ, но и внезапно на когнитивную психологию ^[24] — тоже.