Текст книги "Романтика искусственного интеллекта"

Эвристические алгоритмы

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

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

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

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

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

Проблема в том, что этот алгоритм переборный. А количество всех возможных сочетаний из N элементов равно 2^N. То есть даже при очень небольшой исходной куче, например в 100 камней, общее количество сочетаний 2¹⁰⁰. И получается так, что решение есть и его как бы нет. Дождаться, когда компьютер его обнаружит, человеческой жизни не хватит. А теперь давайте откажемся от желания найти идеальное решение. Пусть нам будет достаточно решения хорошего. Тогда возможен такой алгоритм:

• Упорядочим исходную кучу камней в порядке убывания веса.

• Пока в исходной куче камней есть хотя бы один камень, делаем:

– берем очередной камень;

– если правая куча тяжелее левой, то кладем очередной камень в левую кучу, иначе кладем его в правую.

Проиллюстрируем алгоритм примером. Пусть исходная куча содержит такие камни: (9, 15, 1, 1, 7, 4).

После упорядочивания массив примет такой вид: 15, 9, 7, 4, 1, 1.

Шаг 1: Правая – 15; Левая – 0; Исходная 9, 7, 4, 1, 1.

Шаг 2: Правая – 15; Левая – 9; Исходная 7, 4, 1, 1.

Шаг 3: Правая – 15; Левая – 9 + 7 = 16; Исходная 4, 1, 1.

Шаг 4: Правая – 15 + 4 = 19; Левая – 9 + 7 = 16; Исходная 1, 1.

Шаг 5: Правая – 15 + 4 = 19; Левая – 9 + 7 + 1 = 17; Исходная 1.

Шаг 6: Правая – 15 + 4 = 19; Левая – 9 + 7 + 1 + 1 = 18; Исходная – Пусто.

Заметим, что за шесть шагов было найдено идеальное решение. А алгоритм полного перебора отработал бы 2⁶ = 64 варианта. Вот что такое эвристический алгоритм. Его суть в том, что принимается допущение, которое не обязательно верно во всех случаях жизни, но выглядит вполне правдоподобно. Например, рыбак, выбирая место для ловли, может рассуждать так: «Вон там я вижу омут. В омуте может водиться крупная рыба. Попробую я, однако, порыбачить там». Конечно, рыбак может и ошибаться. В этой реке вообще может рыбы не быть. Но предположение, что в омуте она есть, выглядит разумно, и это эвристическое допущение.

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

Эвристика все меняет радикально. Классический алгоритм принимает во внимание только входные данные, и если они такие же, как и в предыдущем запуске, то и ответ будет тем же. Эвристический алгоритм, кроме входных данных, имеет возможность оценивать опыт. В примере с рыбаком это работает так: «Я имею перед собой реку, в ней есть отмель и есть омут (это примерно так, как выглядит на рис. 1.6). Я уже десять раз встречал такую ситуацию и восемь раз из десяти был успешен, порыбачив в омуте. Значит, есть смысл попробовать еще раз».

Рис. 1.6. Эвристический рыбак

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

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

Эвристика позволяет менять стратегию. Рассмотрим это опять на примере с рыбаком. Допустим, у него поменялись интересы к видам рыб, и он перешел на рыбу, которая больше любит отмели, но рыбак пока этого не знает. Первые попытки ловли другой рыбы естественно пытаться реализовать в рамках отработанной стратегии омута. Тем более что стратегия основательно закреплена и доля сомнения очень низка. Но каждая неудача ловли на омуте будет увеличивать уровень сомнения. Введем понятие порога успешности. Назовем таким порогом величину сомнения, превышение которой означает признание провала стратегии. Пусть пороговым значением для рыбака будет половина неудачных попыток в их общем числе. Тогда если он закрепил стратегию 9 успешными попытками (на прежней рыбе) из десяти, то 8 неуспешных приведут его к пониманию непригодности старой стратегии в новых условиях.

А мы можем методику определения неуспешности эвристики усилить. Пусть, например, замечено, что ранее из трех попыток рыбачить в омуте две были железно успешными. Тогда три неудачи подряд (а не 8) могут быть поводом для переосмысления стратегии.

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

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

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

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

В заключение

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

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

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

Глава 2
Вся жизнь – игра

Есть один вид человеческой деятельности в высшей степени интеллектуальный, но тем не менее, как оказалось, легко поддающийся алгоритмизации. Я имею в виду игру. Первые программы, эффективно играющие против человека, появились еще на заре развития вычислительной техники. Что интересно, штурм игры искусственным интеллектом пришелся на шахматы, каковые следует признать одной из наиболее сложных игр. И успех пришел достаточно быстро. Начало шахматных разработок можно отсчитывать от статьи Клода Шеннона, опубликованной еще в 1949 году, в которой рассмотрены основные проблемы игровых моделей. Шеннон впервые представил игру в виде дерева позиций, ветви которого – это возможные ходы, а выбор хода – это выбор наилучшего продолжения из возможных. Процедура выбора получила название минимаксной. Ее название характеризует самую суть действия машины, и немного позже мы это обсудим.

Рис. 2.1. Клод Элвуд Шеннон

Клод Элвуд Шеннон (рис. 2.1) – американский инженер и математик, его работы являются синтезом математических идей с конкретным анализом чрезвычайно сложных проблем их технической реализации. Является основателем теории информации, нашедшей применение в современных высокотехнологичных системах связи. Шеннон внес огромный вклад в теорию вероятностных схем, теорию автоматов и теорию систем управления – области наук, входящие в понятие «кибернетика».

Первым проект Шеннона реализовал Тьюринг, но его программа, показав принципиальную приемлемость, тем не менее не смогла выиграть даже у слабого шахматиста. Первой если не сильной, то вполне играющей шахматной программой можно считать проект MANIAC–I, реализованный в 1956 году группой сотрудников Лос-Аламосской лаборатории. Эта программа наиболее точно соответствовала идее Шеннона, ей также не удалось показать выдающихся результатов, но одну из трех партий против слабого игрока она уже могла выиграть.

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

В 1996 году состоялся первый матч Deep Blue с Гарри Каспаровым, в котором чемпион мира одержал победу со счетом 4:2. Deep Blue – это 6-процессорный суперкомпьютер, способный просчитывать 100 млн позиций в секунду. Через год состоялся матч-реванш с модернизированным 8-процессорным Deep Blue, считающим вдвое быстрее. Компьютер впервые победил лучшего шахматиста планеты со счетом 3,5:2,5. Пока компьютер не умел оценивать позицию, как человек, рост силы игры достигался по большей части за счет увеличения мощности «железа». Даже в качестве алгоритма перебора все еще использовался «брутфорс» (грубая сила), перебиралось как можно больше вариантов, но очень быстро. В 2003 году состоялся еще один матч Каспарова против компьютера – Deep Junior, работавшего на 4-процессорной системе с процессорами Pentium IV 1,9 ГГц и 3 Гб оперативной памяти. Junior стал первой программой, демонстрирующей «человечную» игру и способной пойти на жертву ради инициативы. Матч закончился вничью.

Компьютер против человека. Как это выглядит в принципе?

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

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

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

Как эту работу выполняет человек

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

Рис. 2.2. Этюд мастера Рети

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

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

Даже на этом, довольно простом примере видно, что игрок – человек использует довольно сложный понятийный аппарат: перехват, зоны гарантированной поддержки, угроза, одновременная угроза. Вопрос здесь вот какой: а имеем ли мы техническое устройство, способное оперировать понятиями такого смыслового уровня? Если взглянуть на проблему глазами специалиста середины XX века, то ответ отрицательный. Современный уровень развития систем искусственного интеллекта, конечно, другой, и сейчас движение в сторону моделирования человеческого способа мышления уже не выглядит таким уж невероятным. Но дело в том, что в интеллектуальных играх техника повторила прецедент колеса. В то время когда интерес к моделированию шахмат был очень велик, ресурсы для реализации человекоподобного шахматиста можно сказать что отсутствовали, и теория искусственного интеллекта нашла возможность решить поставленную задачу совсем иным, но очень эффективным способом. Коротко этот способ можно обозначить двумя словосочетаниями: «дерево перебора» и «оценочная функция».

Первая базовая идея – дерево перебора

Допустим, шахматная ситуация допускает десять ходов игрока. Конечно, реально в шахматной партии, даже если осталась пара фигур, вариантов хода существенно больше, чем десять, но мы для упрощения анализа остановимся на числе в 10 продолжений. Тогда его противник тоже имеет выбор из 10 ходов. Таким образом, ход игрока и реакция его оппонента создадут 100 позиций. Еще пара ходов (игрок – противник), и конечных позиций уже 10 000. Простая арифметика дает астрономическое число. N ходов обоих игроков породят 10^N ситуаций. Таким образом, партия в 100 ходов даст 10¹⁰⁰ конечных позиций. А значит, даже если бы в каждой позиции действительно было бы возможно только 10 ходов, количество конечных ситуаций практически необозримо.

Есть, правда, вопрос: а зачем анализировать возможные продолжения от исходной позиции до конечной? Вопрос вполне правомерный. Люди-шахматисты, очевидно, не выполняют подобной работы, однако партии в исполнении людей выглядят вполне разумно. Есть, кстати, любопытная легенда об одном из величайших шахматистов всех времен и народов – Хозе Рауле Капабланке. Вроде бы его как-то спросили, как далеко он продумывает игру, на что Рауль ответил: на один ход. Значит, это возможно – не смотреть глубоко.

Вспомним, однако, что человек – довольно сложно устроенная машина. У нас такой нет. Мы не можем опираться на опыт, нет и возможности использовать развитую шахматную теорию, что, конечно, минус. Знание теории дает довольно много. Допустим, требуется выяснить, выдержит ли некая конструкция удар кувалдой. Знание теории сопротивления материалов позволяет провести расчет и дать ответ без кувалды. Если теория испытателю неизвестна, то остается только выполнить удар. Примерно такова же ситуация и в шахматах. Если мы знаем, что потеря центра в дебюте – это почти всегда плохо, и если мы видим, что такая угроза существует, то нет необходимости анализировать все продолжения, будет вполне достаточно сосредоточиться на угрозах центру. Если такой теоретический факт неизвестен, то придется провести анализ на некоторое количество ходов вперед, чтобы обнаружить то, о чем теория говорит сразу. Конечно, шахматная теория существует, но давайте пока осложним себе жизнь и положим, что она нам неизвестна. Итак, зафиксируйте свое внимание на проблеме. Обход дерева перебора необходим, но полный его обход невозможен. Продолжим анализ.

Чем меньше мы знаем, тем больше возможностей необходимо проверять

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

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

Рис. 2.3. Дерево перебора