Универсальный решатель задач

Разработка Универсального решателя задач началась в контексте «когнитивной революции» в психологии и формирования искусственного интеллекта как науки после Дартмутского семинара 1956 года^[3][4]. Его основой послужила теоретическая работа Саймона и Ньюэлла по «логическим машинам»^[5]. Непосредственным предшественником Универсального решателя задач стала программа «Логик-теоретик» (англ. Logic Theorist), созданная в 1955—1956 годах^[6][7].

Любая задача, которую можно выразить в виде набора корректных формул (WFFs) или клауз Хорна, и которая образует ориентированный граф с одним или несколькими источниками (то есть гипотезами) и стоками (то есть желаемыми заключениями), принципиально может быть решена Универсальным решателем задач. Архитектура системы является историческим примером разделения декларативных и процедурных знаний^[8]: Универсальный решатель задач стал первой компьютерной программой, разделявшей свои знания о задаче (правила, представленные во входных данных) и стратегию решения (универсальный модуль решения задач). Программа была реализована с использованием языка третьего поколения IPL (англ. Information Processing Language)^[9], который позволил реализовать критически важные для неё обработку списков и рекурсию^[10].

Пользователь определял объекты и действия, которые можно производить над этими объектами, а Универсальный решатель задач генерировал эвристики с помощью анализа средств и целей^[11]. Фокус был на имеющихся операциях: программа определяла допустимые входные данные и получаемые выходы, затем формировала подцели для поэтапного приближения к основной цели. В основе метода анализа целей и средств лежит представление задачи в виде пространства состояний, которое включает начальное состояние (исходные условия), целевое состояние (желаемый результат) и набор операторов (действий, преобразующих одно состояние в другое). Алгоритм работает рекурсивно: он сравнивает текущее состояние с целевым, выявляет различия и выбирает оператор, способный их уменьшить. Если условия для применения выбранного оператора не выполнены, система создаёт новую подцель — достижение промежуточного состояния, в котором этот оператор станет доступен^[12].

Доказательства в пространствах задач предикатной логики и евклидовой геометрии являются примерами применения Универсального решателя задач. Программа также успешно применялась для решения криптарифметических и логических головоломок^[13].

Хотя Универсальный решатель задач успешно решал простые задачи, такие как Башни Ханоя (при условии, что задача достаточно формализована), он не был способен справиться со сложными реальными задачами. Главной причиной этого стал комбинаторный взрыв: при увеличении сложности проблемы количество возможных шагов и промежуточных состояний росло экспоненциально, из-за чего процесс поиска быстро терялся, а количество «путей» в графе вывода становилось вычислительно непреодолимым^[14]. (На практике даже простые задачи поиска в пространстве состояний, например «Башни Ханоя», могут оказаться вычислительно сложными, хотя такие методы искусственного интеллекта, как A* и IDA*, позволяют эффективно сокращать пространство состояний.)

Другим фундаментальным ограничением было требование строгой формализации. Программа требовала, чтобы проблема была чётко представлена в виде объектов, начального и целевого состояний, а также операторов, что крайне затруднительно для плохо структурированных задач реального мира^[12]. Кроме того, Универсальный решатель задач не обладал здравым смыслом и знаниями о предметной области^[15][12]. Пытаясь решить любую задачу с помощью общего метода, программа была лишена контекстуальных знаний, которые позволяют избегать перебора заведомо неверных путей.

Впоследствии парадигма Универсального решателя задач послужила основой для архитектуры Soar в области искусственного интеллекта.

Программа сыграла ключевую роль в становлении когнитивной психологии, предложив компьютерную симуляцию процессов человеческого мышления^[16]. Благодаря стремлению к универсальности она считается одним из прообразов искусственного общего интеллекта (AGI)^[2]. Впоследствии парадигма Универсального решателя задач послужила основой для архитектуры Soar в области искусственного интеллекта^[17]. Первоначальные амбиции создателей по универсальному решению задач находят частичное воплощение в современных системах (например, AlphaProof Nexus 2026 года), которые, в отличие от символьного подхода программы, используют гибридные методы^[18].