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

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

История создания

Разработка GPS началась в рамках исследовательского проекта в корпорации RAND (США) и была продолжена в Университете Карнеги-Меллона. Предшественником программы стала система «Логик-теоретик» (Logic Theorist), созданная теми же авторами в 1956 году, которая могла доказывать математические теоремы из «Principia Mathematica» Бертрана Рассела и Альфреда Норта Уайтхеда. Успех «Логик-теоретика» показал, что символьные методы могут имитировать логические рассуждения человека, однако программа была узкоспециализированной.

В 1957 году Ньюэлл, Шоу и Саймон поставили задачу создать более общий инструмент, который не зависел бы от конкретной предметной области. Идея заключалась в том, что любая задача может быть представлена как переход из начального состояния в целевое с помощью последовательности операций. Программа была реализована на языках IPL (Information Processing Language) — одном из первых символьных языков программирования, разработанном той же группой. Первая версия GPS была запущена в 1959 году на компьютере IBM 704.

Принцип работы

Представление задачи

GPS работает с формальным описанием задачи, которое включает три компонента:

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

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

Метод анализа целей и средств

Основной алгоритм GPS называется «анализ целей и средств» (англ. Means-Ends Analysis, MEA). Он работает следующим образом:

1. Программа сравнивает текущее состояние с целевым и выявляет различия.
2. Выбирается оператор, который уменьшает или устраняет одно из различий.
3. Если оператор применим к текущему состоянию, он выполняется, и программа переходит к новому состоянию.
4. Если оператор не применим, программа рекурсивно ставит подзадачу: изменить текущее состояние так, чтобы оператор стал применим.

Таким образом, GPS не просто перебирает все возможные ходы, а использует эвристику — приоритетное устранение наиболее значимых различий. Это делает поиск более направленным, чем слепой перебор (например, в алгоритме «в ширину»).

Планирование

В некоторых версиях GPS реализован механизм планирования. Программа может откладывать выполнение операторов, если они не могут быть применены немедленно, и строить последовательность шагов заранее. Например, в задаче «Волк, коза и капуста» GPS сначала планирует перевозку козы, а затем возврат лодки, чтобы избежать конфликта.

Примеры решаемых задач

GPS был успешно протестирован на нескольких классических задачах:

• Ханойская башня — перемещение дисков с одного стержня на другой с ограничением: нельзя класть больший диск на меньший.
• Задача о волке, козе и капусте — перевозка трёх объектов через реку с ограничениями на совместимость.
• Логические головоломки — например, задачи на перестановку символов или доказательство простых теорем.
• Задачи на манипуляцию с символами — например, преобразование одних строк в другие по заданным правилам.

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

Ограничения и критика

Несмотря на новаторство, GPS имел серьёзные ограничения:

• Узость области применения. Программа работала только с задачами, которые можно было полностью формализовать. Реальные проблемы (например, планирование маршрута в городе или медицинская диагностика) требовали гораздо более сложных описаний.
• Эффективность. В сложных задачах с большим количеством состояний GPS часто застревал в локальных оптимумах или требовал огромных вычислительных ресурсов. Например, для задачи с 10 дисками в ханойской башне количество шагов экспоненциально растёт.
• Отсутствие обучения. GPS не запоминал успешные стратегии и не улучшал свои результаты со временем.
• Психологическая неадекватность. Хотя авторы утверждали, что программа моделирует человеческое мышление, критики (например, Хьюберт Дрейфус) указывали, что люди решают задачи иначе — с помощью образов, интуиции и контекста, а не формальных правил.

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

Влияние на искусственный интеллект

GPS оказал значительное влияние на развитие ИИ:

• Эвристический поиск. Метод анализа целей и средств стал основой для многих алгоритмов планирования, например, в системах STRIPS (1971) и SOAR (1983).
• Символьная обработка. GPS подтвердил гипотезу Ньюэлла и Саймона о том, что интеллект можно реализовать через манипуляцию символами (физическая символьная система).
• Когнитивное моделирование. Программа использовалась как инструмент для проверки гипотез о человеческом мышлении. Например, Саймон и Ньюэлл утверждали, что GPS воспроизводит «протоколы мышления» — записи рассуждений людей при решении задач.

В современном ИИ идеи GPS применяются в автоматическом планировании (например, в робототехнике), а также в некоторых системах общего искусственного интеллекта (AGI). Однако большинство современных решателей задач (например, AlphaGo или GPT) используют другие подходы — глубокое обучение и нейронные сети, а не символьные правила.

Интересные факты

• Название «General Problem Solver» было выбрано, чтобы подчеркнуть универсальность, хотя на практике программа решала только простые головоломки.
• В 1960 году Саймон и Ньюэлл предсказали, что компьютер сможет обыграть чемпиона мира по шахматам в течение 10 лет. Это предсказание не сбылось — Deep Blue победил Гарри Каспарова только в 1997 году.
• GPS был реализован на IPL, который, в свою очередь, стал предшественником языка LISP (1958), одного из основных языков для ИИ.

Источники

• Newell, A., Shaw, J. C., & Simon, H. A. (1959). Report on a general problem-solving program. Proceedings of the International Conference on Information Processing.
• Simon, H. A. (1996). The Sciences of the Artificial (3rd ed.). MIT Press.
• Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
• Дрейфус, Х. (1972). Чего не могут вычислительные машины.