Интеллектуальные игры и доказательства теорем

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

Оба подхода нашли свое отражение при создании программ, играющих в шашки и шахматы.

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

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

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

Первую программу для ЭВМ, использующую эвристические принципы, описали А. Ныоэлл, Дж. Шоу и Г. Саймон в работе "Динамические исследования машины "логик-теоретик". Пример изучения эвристик". Авторы так определили цель своей работы: "...разобраться в тех сложных процессах ("эвристиках"), которые сопровождают решение задач... мы не интересуемся методами, обеспечивающими решения задач, но требующими очень большого объема вычислений, а стремимся понять, каким образом, например, математик в состоянии доказать теорему, даже если он вначале не знает, как ему это сделать, и сможет ли он вообще ее доказать" [29].

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

В 1957 г. авторы "логика-теоретика" разработали новую программу General Problem Solving (GPS), т. е. "Решение общих задач", в которой сформулировали общие эвристические правила для решения широкого круга задач как математических, так и технических. Программа работает с различными объектами, образующими предметную среду (математические выражения, геометрические фигуры и т. п.).

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

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

Использовавшиеся эвристические приемы фактически не имеют психологического содержания и позволяют говорить только об аналогиях: "...мы используем термин "эвристический" при определении любого принципа или устройства, которые вносят вклад в уменьшение среднего числа проб при решении" [31, с. 514], - отмечали авторы эвристических программ. Более того, мыслящий человек рассматривается ими как система обработки информации: "...все люди представляют собой системы обработки информации и поэтому обладают рядом общих фундаментальных признаков. Эти общие свойства порождают одинаковые характеристики, свойственные поведению всех людей при решении задач" [30]. Упрощенное представление о мыслящем человеке не позволило авторам правильно определить границы применимости своего метода.

О необходимости проявлять осторожность при использовании термина "эвристический" говорил Ван Хао, успешно применивший алгоритмические (не эвристические) методы для решения задач, о которых говорилось выше: "Слово эвристический обычно понимается как синоним для искусства открытий, однако оно означает лишь частный метод, который не гарантирует общего решения данной проблемы. Эта двусмысленность наделяет слово эмоциональным оттенком, который может вводить в заблуждение при дальнейших научных изысканиях. Более знакомое и менее вдохновляющее слово "стратегия", по-видимому, является более подходящим" [31, с. 528].

Советский ученый В. Н. Пушкин [32] в работе "Психология и кибернетика" вскрыл ограничения эвристического подхода. Одно из них состоит в разделении материала задачи, ее условий и операций, которые приводят к ее решению. В мышлении человека процесс решения задачи всегда связан с ее условиями. Другое ограничение (не позволяющее, в частности, применять GPS для шахматной игры) - нечеткая формулировка целей и средств во многих научных и практических задачах, делающая неприемлемыми эвристические программы. Наконец, сам ход мышления человека, оценивающего ситуацию, совершенно отличен от перебора вариантов, сокращенного эвристическими правилами.

Несмотря на трудности и принципиальные ограничения эвристического программирования, в ряде случаев оно позволяет весьма успешно решать сложные задачи. Это относится, например, к шахматной игре. На состоявшемся в 1977 г. Втором чемпионате шахматных программ между советской программой "Каисса" и программой США "Чесс-4" обе программы играли на уровне второго разряда. В том же 1977 г. под руководством М. М. Ботвинника была разработана программа "Пионер", использующая эвристические приемы мастера шахматной игры.

С развитием методов программирования и усовершенствованием вычислительных машин происходит расширение возможностей интеллектуальных программ, приближение их к практическим задачам. Большие успехи достигнуты здесь советскими учеными. В Институте кибернетики АН УССР под руководством В. М. Глушкова разработаны программы, ориентированные, в отличие от программы GPS, на сложные проблемные среды. В программе APROS (Adaptive Problems Solver) база данных организована в семантическую сеть. Авторы отказались от старого принципа, согласно которому модель среды ("система знаний" машины) закладывается человеком. Программа является адаптивной в том смысле, что модель среды формируется в процессе работы с использованием так называемых растущих семантических сетей. При поиске стратегии решения задач используется эвристика. Программа способна к обучению, накоплению знаний при взаимодействии с внешним миром, что делает ее особенно эффективной в применении к роботам. Проведенные эксперименты подтвердили возможность применения программы для планирования действий роботов в реальных средах, в частности для перемещения объектов в среде с препятствиями и для сборки [33].