Успехи и неудачи эвристических программ

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

Одним из наиболее известных критиков искусственного интеллекта, резко отрицавших возможность наделения цифровых компьютеров какими бы то ни было человеческими способностями, был философ, профессор Герберт Дрейфус. В своей обширной работе (1965 г.) с весьма показательным названием «Алхимия и искусственный интеллект» (выполненной им в корпорации «RAND») он, в частности, категорично заявлял, что компьютер обладает настолько ограниченными возможностями, что принципиально не сможет играть в шахматы даже на посредственном уровне. Вызов, брошенный Дрейфусом, был принят программистами из лаборатории искусственного интеллекта Массачусетсского технологического института, одним из основателей которой был Марвин Минский.

В 1969 году с Дрейфусом сыграла программа, написанная Ричардом Гринблаттом. Несмотря на уверенную игру профессора и то, что программа исполнялась на компьютере PDP-6 (с быстродействием примерно 0,25 млн операций в секунду), в результате ожесточенной битвы победа все же осталась за компьютером. Однако этот проигрыш не пошатнул уверенности Дрейфуса в ущербности компьютеров, который и спустя десятилетия продолжал говорить о том, что область ИИ претерпела предвиденную им неудачу. Стоит все же отметить, что критика Дрейфуса содержала не только ряд заблуждений, но и некоторые ценные идеи.

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

Сейчас можно уверенно утверждать, что компьютер способен выиграть в шахматы у чемпиона мира. В отдельных партиях компьютер брал верх уже в 1990-х года, а в 2006 году компьютер выиграл в серии партий у действующего чемпиона мира Владимира Крамника со счетом 2 : 4. Эта участь постигла шашки еще раньше. А в 2008 году на чемпионате по игре в покер (в один и его ограниченных вариантов) компьютер смог победить сильнейших игроков-людей, хотя еще в 2007 году он потерпел поражение. И даже в американской телевикторине «Jeopardy!» в 2011 году компьютер выиграл у сильнейших игроков-людей. И лишь в немногих играх, таких как го, по-прежнему сохраняется безоговорочное лидерство человека. Поклонники все еще не поддавшихся компьютеру игр уже реже говорят о том, что человек навсегда останется в них непобежденным, а чаще просто относят эту страшную дату на многие годы вперед. Стоит, правда, отметить, что прогресс в силе компьютерных игроков для этих игр может быть связан не с вполне классическим эвристическим программированием. К примеру, в го компьютер не так давно поднялся на следующую ступень мастерства благодаря объединению поиска по дереву вариантов с оцениванием по методу Монте-Карло (путем статистических испытаний).

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

Естественно, само умение играть в шахматы или другую игру заложено в компьютер человеком, и за хорошей игрой программы стоит интеллект разработчиков. Однако и человек не достигнет высокого уровня, не переняв огромный мировой опыт игры в шахматы, накопленный на протяжении многих веков. Без объяснений более опытных игроков или хотя бы просто игры с ними любой человек останется на весьма примитивном уровне игры. Хорошо, пусть человек опирается на чужой опыт, но этот опыт все же накоплен людьми. Пусть понемногу, но каждый хороший игрок привносит в эту мировую копилку опыта что-то свое. А компьютер? Он же «механически» выполняет заложенную в него программу, состоящую из строгих операций, которые кто угодно может воспроизвести.

Но ведь и сами шахматы — чисто дедуктивная игра. По теореме о минимаксе оптимальная стратегия игры в шахматы уже содержится в правилах этой игры, поэтому если нам эту стратегию сообщат, мы, согласно классической теории информации, новых сведений не получим. Когда кто-то говорит, что компьютер, выигрывая в шахматы, делает только то, что заложено в него человеком, он, по сути, мыслит в рамках этих классических представлений. Подобные представления берут свое начало в философии нового времени в споре последователей эмпиризма и рационализма о методах познания. При этом индуктивному методу Фрэнсиса Бэкона приписывается возможность получения новых, но обязательно недостоверных знаний, тогда как дедуктивному методу Рене Декарта — достоверных, но принципиально не обладающих новизной знаний. Таким образом, будучи последовательным, следовало бы сказать, что и гроссмейстер своей игрой не показывает ничего, что не было бы заложено в шахматы.

На примере шахмат видно, что этот традиционный взгляд, воплощенный и в современной теории информации, требует расширения. Еще более ярко это видно на примере великой теоремы Ферма, согласно которой уравнение a^n + b^n = c^n не имеет натуральных (положительных целочисленных) решений при целых значениях n > 2. На протяжении нескольких столетий ее пытались доказать многие математики. Порой даже думали, что построение доказательства (или опровержения) этой теоремы — неразрешимая задача («доказательство» этой теоремы среди любителей было настолько же популярным, как и «изобретение» вечного двигателя). Этот случай поучителен и для области искусственного интеллекта: часто говорят о том, что ИИ создать невозможно, поскольку этого не удалось сделать в течение уже более чем полувека, и также проводят аналогии ИИ с вечным двигателем или философским камнем. Однако на доказательство какой-то одной совершенно простой по своей формулировке теоремы Ферма ученые потратили гораздо больше времени, и они бы не достигли успеха, если бы думали о том, как долго ее не удается решить.

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

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

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

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

В похожей ситуации за белых было предложено сыграть компьютеру «Deep Thought», который до этого одержал несколько

formula_13

 

побед над гроссмейстерами. Компьютер сделал ход b4–a5, при котором пешка белых съедает ладью черных, приводит к скорому проигрышу белых. Для человека очевидна стратегия белых, которая позволяет вести игру до бесконечности, избегая поражения. При анализе этой ситуации человек, правда, использует понятие связанных областей, которое в шахматах обычно не нужно, т. е. человек и компьютер здесь поставлены не совсем в равные условия.

И все же данный пример показывает определенную ограниченность шахматной программы «Deep Thought». Сильнейшие шахматисты еще могут соперничать с машиной, создавая нестандартные ситуации, смысла которых компьютер не понимает. Для шашек это уже в принципе невозможно, поскольку для этой игры в 2007 году было получено слабое решение — алгоритм, гарантирующий идеальную игру, начиная с начальной, но не с любой произвольной, позиции. Отсюда видно, что программа может идеально играть и без «понимания» игры. Можно предположить, что глубина «понимания» игры связана со способом описания игровой ситуации, который находит отражение в оценивающей функции. Если, к примеру, в оценивающую функцию заложены силы фигур, можно считать, что программа «понимает» значимость той или иной фигуры. То же можно сказать и о позиционном преимуществе, складывающемся из каких-то свойств взаимного расположения фигур. Как уже отмечалось, улучшение оценивающей функции позволяет уменьшать глубину перебора при сохранении уровня игры. Понимание игры у существующих компьютерных программ находится на не слишком высоком уровне, что, однако, компенсируется глубоким перебором за счет существенных вычислительных ресурсов. Такой подход обычно называют методом «грубой силы».

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

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

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

И все же человек при решении задач проявляет ряд принципиальных свойств, которыми обладают и эвристические программы. Это и резкий рост времени нахождения точного решения при увеличении сложности задачи, и поиск приближенного решения для задач большой размерности. Интересно то, что часто отличие человека от компьютера видят в способности ошибаться. Однако очевидно, что при решении NP-полных задач большой размерности компьютеру свойственно ошибаться в не меньшей степени. Конечно, человек часто делает ошибки из-за невнимательности, которые компьютеру как будто не свойственны. Однако это связано с тем, что человек непрерывно решает NP-полную (а может, и неразрешимую) проблему огромной размерности, предоставляемую внешним миром в целом, т. е. живет. Партия в какую-либо игру — лишь маленькая часть этой проблемы, на которую выделяются ограниченные ресурсы мозга. Если бы компьютерная программа не просто играла в шахматы, но одновременно с этим решала множество иных задач, естественно, в некоторые моменты времени ей приходилось бы отвлекать на них значительные ресурсы, в результате чего глубина ее игры могла резко сокращаться, что выглядело бы, как банальная невнимательность.

Иногда, напротив, люди демонстрируют удивительные способности к решению вычислительно сложных задач. Один из наиболее интересных (в контексте нашего разговора) случаев приведен в книге нейропсихолога Оливера Сакса «Человек, который принял жену за шляпу». Сакс описывает свои наблюдения за двумя близнецами, с детства содержавшимися в лечебных учреждениях с диагнозами «аутизм» и «умственная отсталость». Он обратил внимание на игру, в которую близнецы играли друг с другом. В этой игре они по очереди называли шестизначные числа. Как оказалось, все называемые ими числа были простыми. Сакс, решив проверить, вспоминают ли они известные им числа или каждый раз называют новые, нашел в справочниках девятизначные простые числа и, выписав их, попытался принять участие в игре. Близнецы не только с радостью приняли его в игру, сумев удостовериться в простоте называемых им чисел, но стали постепенно увеличивать порядок чисел вплоть до двенадцатого, для которого простых чисел в справочниках того времени не оказалось.

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

Сакс делает вывод о том, что близнецы пользовались не вычислительными или алгоритмическими, а некими иконическими, или визуальными, приемами для поиска и проверки простых чисел. Действительно, способность близнецов в уме находить двенадцатизначные простые числа кажется поразительной, особенно с учетом того, что данная проблема является NP-полной. А ведь близнецы определенно не могли в уме проверять делимость некоторого числа на все возможные делители. Подумайте только: перед вами число из двенадцати цифр, и вам нужно проверить его делимость на множество других чисел. Сколько времени у вас это займет даже с использованием калькулятора?! Подобные истории хочется отбросить как миф, нелепицу, которая не может иметь места в действительности. Или следует признать, что в мозгу действуют какие-то хитрые неалгоритмические процессы, которые, если только удастся их задействовать, открывают поистине сказочные возможности? Попробуем все же не отмахиваться от фактов, но, в то же время, и не списывать их на необъясненные способности.
Во-первых, для проверки простоты некоторого числа достаточно проверить делимость на все простые числа от двух до корня из анализируемого числа. Для двенадцатизначного числа потребуется порядка миллиона операций без какой-либо дополнительной памяти. Во-вторых, близнецы называли по одному числу за раз, для чего не нужно применять алгоритмы типа решета Эратосфена, находящие все простые числа вплоть до заданного. Есть приемы, позволяющие получать числа, подозрительные на простоту. Такими числами, к примеру, являются числа вида 2^n – 1 (например, 7, 31 и др.). Можно придумать много других приемов, например произведения простых чисел, к которым прибавлена единица или суммы простых чисел также часто оказываются простыми (23 + 1 = 7, 235 + 1 = 31, 211 + 3 + 5 + 7 = 37 и т. д.). Естественно, близнецы не могли пользоваться на уровне сознания явным поиском делителей некоторого числа или решетом Эратосфена. Но здесь важно то, что для реализации их способностей принципиально хватает ресурсов мозга или компьютеров в рамках алгоритмических процессов. Важно также и то, что время поиска и проверки нового числа у близнецов существенно возросло при незначительном увеличении разрядности чисел. Вопрос состоит в том, какова может быть структура этих процессов поиска. Сакс же противопоставляет структуру процессов и их основу, т. е. путает уровни представления, причиной чего, видимо, является крайне узкое понимание им алгоритмов как непосредственных вычислений. «Иконические» (в его терминологии) процессы могут быть вполне алгоритмическими.

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

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

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

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

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