Есть ли у них ног-
ти? Сколько? Чтобы "разумная" машина понимала язык, она должна уметь
при обработке языка делать разумные выводы, как это делают обычные
люди. Основная идея Шенка близка принципу обработки "сверху-вниз",
широко обсуждающемуся в этой книге.
Одной из трудностей, встретившихся при разработке программы обра-
ботки языка, была неоднозначность естественных языков. Шенк (Schank,
1981) приводит следующий пример:
Я ударил Фреда в нос.
Я ударил Фреда в парке.
Чтобы правильно проанализировать эти предложения, нужно знать гораз-
до больше, чем только синтаксические и семантические правила. Чита-
тель должен что-то знать о том, где может находиться человек, а также
другую концептуальную информацию о человеческом поведении и общую
информацию о мире.
Разработанная Шенком программа содержит много систем и подсис-
тем, из которых мы рассмотрим здесь только наиболее существенные.
Сердце программы составляет система умозаключений, скриптов, планов,
тем и целей, считающихся неотъемлемой частью человеческого понима-
ния языка. Мы рассмотрим каждую из них.
Умозаключения. При обработке естественного языка мы обычно от-
слеживаем, где расположены люди и объекты, что они ощущают, в каком
состоянии они находятся, что они знают, каковы их убеждения.
Искусственный интеллект
525
Скрипты2. Скрипт - это "общепринятая" последовательность причин-
ных связей. В естественном языке мы не проговариваем детально и точно
последовательность причинных событий, но (обычно) даем достаточно де-
талей, так чтобы другой человек со сходным жизненным опытом мог по-
нять последовательность событий. В случае с Джоном из вышеприведен-
ного эпизода в ресторане говорящие предполагают, что собеседник выве-
дет связь между событиями (в данном случае - чаевые, еда и плата),
даже если конкретная причинная связь не представлена.
Планы. Чтобы понять большинство событий, важно знать мотивы и на-
мерения участвующих людей. Для этого нужно знать виды их характеров.
Цели. Цели - это довольно специализированные планы, в которых пре-
следуется определенный результат или исход. Планы могут включать воп-
росы о причине выбора конкретной цели, о том, с чем она может конфлик-
товать, и о том, при каких обстоятельствах от нее придется отказаться.
Над целями доминируют структуры более высокого порядка, которые на-
зываются темы.
Темы. Умозаключения, основанные на темах, направлены на выяснение
вопросов:
Какие цели вероятнее всего преследует данное действующее
лицо?
Какие темы вероятнее всего сосуществуют с данной?
Существуют ли противоречия в темах?
Сколько из обнаруженных противоречий можно разрешить?
Откуда происходит данная тема?
Взято из: Schank (1981).
Вначале Шенк и его коллеги стремились только к программе, которая
бы читала, понимала и могла отвечать на несколько вопросов о простом
сюжете - в общем, умела бы то, что умеет делать маленький ребенок. Но
то, что начиналось как элементарный поиск, вылилось в огромный слож-
ный лабиринт взаимосвязанных систем, анализ функциональных свойств
языка, теорию памяти, рассмотрение структуры знания и философское
высказывание о природе мысли. В своей статье, посвященной ИИ. мышле-
нию и самопониманию, Шенк заключает:
"Искусственный интеллект является частью общего стремления
понять мышление. Мы считаем, что он вносит важный вклад в
эти усилия и что они и есть цель нашей науки. Программы,
которые мы пишем,- это эксперимент, а не результат. Наш
интерес - это интеллект, а не артефакт. По мере нашего прогресса
полученные результаты откроют путь ав-томатическим
партнерам, которые, возможно, станут необходимой частью
повседневной жизни. Однако это не будет нашим настоящим
Иначе - стереотипы, штампы поведения.- Прим. ред.
Мышление и интеллект - естественный и искусственный
526
результатом. Настоящим результатом будет новое понимание
нас самих, понимание, которое в конечном счете гораздо более
ценно, чем любая, программа" (Schank, 1985, р.155).
Важность этой работы в том, что она способствует созданию специфи-
кации правил языковой структуры так, чтобы их можно было искусствен-
но смоделировать с высокой степенью верности. Если система ИИ терпит
неудачу, значит мы не смогли понять свойства языка.
Решение задач и искусственный интеллект
Литература по решению задач в рамках ИИ возможно более обширна, чем
по любому другому психологическому процессу. Одна из причин, почему
многие специалисты по ИИ интересуются решением задач, состоит в том,
что этот термин, грубо говоря, синонимичен мышлению, которое в его
сложном виде является исключительно человеческим атрибутом. Этот факт,
а также то, что машины с ИИ вообще способны выполнять процедуры
решения задач, привело к широкому развитию методов и теории в этой
области.
Вычисления были одним из первых примеров использования машин
для решения задач. В 1642 году Паскаль (тогда ему было 19) продемонст-
рировал, что при помощи изобретенного им механического вычислители
некоторые математические задачи можно решать точнее и быстрее, чем
люди делают вручную. В контексте современного ИИ решение заоач очн;!-
чает гораздо больше, чем математические вычисления; оно охватывает
широкий диапазон от решения сложных головоломок до доказатгльстия
теорем, заучивания успешных операций и различных игр.
В основе многих работ в сфере ИИ лежит важное различение между
двумя методами решения задач. Один метод называется алгоритмическим,
а другой - эвристическим. Алгоритмы обычно определяются как проце-
дуры, гарантирующие решение задач данного типа; эвристика есть набор
эмпирических правил или стратегий, которые в итоге действуют подобно
правилу большого пальца. Различие между этими методами можно проил-
люстрировать на примере шахматной задачи. Шахматы для компьюте-
ра - это игра, в которой во всякий данный момент существует ограничен-
ное количество ходов для каждого игрока. И на каждый из возможных
ходов противник может ответить также ограниченным набором ходов. Для
практических целей количество этих перестановок конечно - т.е. игра
должна закончиться выигрышем (поражением) или вничью. На Рис. 15.12
показана часть еще более разветвленного дерева ходов, возможных в шах-
матной партии. Конечно, нельзя изобразить возможные ходы для всей
партии, ибо такая диаграмма содержит около 1020 различных путей. Что-
бы представить себе это огромное число возможных ходов в шахматной
игре, вообразите пространство, необходимое для отображения всех этих
перестановок. Если все возможные пути закодировать в виде мельчайших
точек, они бы многократно заполнили все библиотеки мира! Тем не менее,
алгоритмический поиск, при котором исследуются все варианты, неизбеж-
но привел бы к ряду вариантов игры с выигрышем, проигрышем или ничь-
ей. Не только люди, но даже и самые сложные компьютеры из всех, кото-
рые только можно вообразить, неспособны воспользоваться этим мето-
Искусственный интеллект
527
дом. Вместо него и люди, и компьютеры используют эвристические мето-
ды поиска, при которых становится важной стратегия игры - например,
атака на ферзя, контроль за центром доски, блокирование главных фигур
противника, обмен с получением преимущества в позиции или фигурах и
т.д. К обсуждению алгоритмического и эвристического поиска мы вернем-
ся при рассмотрении универсального решателя задач, но сначала пого-
ворим еще о компьютерных шахматах.
Компьютер- Выше мы описывали, как при помощи оптимального сканера, работающе-
ные шахма- г(э с компьютером, можно было бы разобрать смысл простого паттерна
гы методом сравнения матриц (с. 506). Обсуждая анализ паттернов, мы выяс-
нили, что паттерны сложны и что модель распознавания паттернов чело-
веком, основанная только на сопоставлении матриц, не способна имитиро-
вать разнообразие, сложность и экономичность, характерные для челове-
ческой способности к распознаванию паттернов при кратком предъявле-
нии.
Если бы для распознавания каждого из разнообразных паттернов, встре-
чающихся в повседневной жизни, нужно было иметь по отдельной матри-
це. они переполнили бы емкость хранения даже самого большого компью-
тера. Но давайте выберем для сопоставления матриц умеренно простой
паттерн - что-нибудь среднее между опознанием вашей бабушки и счи-
тыванием стоимости фунта масла (код напечатан на упаковке). В шахма-
тах мы имеем как раз такие паттерны: простая сетка 8х8 попеременно
окрашенных клеток; ходы четко определяются (например, ладья может
ходить на любое количество клеток по вертикали или горизонтали при
условии, что на ее пути нет других фигур, пешка может ходить на одно
тле вперед, за исключением... и т.д.); ходы можно выбирать путем грубо-
го поиска, а количество перестановок конечно, хотя и огромно. При усло-
вии очень большого объема хранения и такого же запаса времени можно
для каждого хода определить вероятность, с которой он приближает вы-
Рис. 15.12. Часть дерева
вероятных ходов в шахмат-
ной партии.
Возмажныв
начальные
ходы Белых
Возможные
ответные
ходы Черных
Возможные
последующие
ответные
ходы Белых
.\1Ы1илсние и. интеллект - естественный и искусственный
528
Короли, Ферзи и кремниевые чипы
Для шахматных чемпионов это была плохая
неделя. Когда Анатолий Карпов отставал па
игру от Гари Каспарова на чемпионате мира
по шахматам, проходившем к концертном
зале Чайковского в Москве, в Редиссон Хол-
ле в Денвере происходило другое расстрой-
ство. Шахматная машина мирового класса и
стоимостью 14 миллионов долларов, супер-
компьютер Cray X-MP/48 при запуске про-
граммы под названием "Блиц" в Северо-аме-
риканском шахматном чемпионате проигры-
вал партию машине Hitech - сделанной на
заказ стойке из кремниевых чипов, соеди-
ненной с мини-компьютером Sun ценой
20000.
Если Карпов и Каспаров сидели лицом к
лицу. то эти два компьютера разделяло 750
миль: Cray находился в Мендота Хайте, штат
Миннесота, a Sun - в университете Карне-
ги-Меллона в Питтсбурге. Ходы компьюте-
ров посылались по телефонным линиям в
Денвер и транслировались на стационарную
шахматную доску. Но расстояние не повре-
дило игре. Мастер по шахматам Дэвид Леви
сказал: "В первый раз программа играла как
сильный игрок-человек".
Компьютеры стали сносно играть в шах-
маты с 1966 года, когда студент из МТИ Ри-
чард Гринблат написал программу МакХэк,
побившую Хуберта Дрейфуса, философа из
Беркли, который настаивал, что ни один ком-
пьютер никогда не. превзойдет 10-летнего ре-
бенка. Современные шахматные машины по-
беждают большинство случайных игроков, а
лучшие программы могут постоять за себя
против всех, кроме самых сильных мастеров13.
Подход шахматных компьютеров обычно
заключается ь грубой силе. Они просчиты-
вают от 4 до 8 ходов вперед, изучают наибо-
лее возможную игру и контригру и выбира-
ют ход, минимизирующий выигрыш оппонен-
та. Компьютер Cray просчитывает 100000
ходов в секунду и обычно выходит победите-
лем. У Hitectia не такая большая память,
как у Cray, и не такие мощные процессоры,
но он компенсирует это скоростью и более
умной игрой. Долговременная стратегия,
например, управляется в нем программой
"Оракул", созданной Хансом Берлинером,
экспертом по искусстиенному интеллекту и
экс-чемпионом мира по шахматам по пере
писке.
Выбрав линию атаки, Оракул передает
управление отдельному блоку, па шаппому
"Искатель". Искатель разработан Карлом
Эбелингом, выпускником универсше i.i Кар-
неги-Меллон, и изготовлен за счет гранта.
предоставленного Департаментом по Оборо-
не. Этот прибор размером с хлебницу содер-
жит 64 микропроцессора специальною на-
значения, каждый из когорых приписан к оп-
ределенному квадрату шахматной доски
Когда фигура ступает па отдельный квадрат.
курирукяций этот квадрат процессор опре
деляст вероятные исходы. При работе с мак-
симальной скоростью эти (i4 чина могут про-
считать 175000 позиций и секунду или :i()
миллионов позиций за ,i минуты, отводимых
в турнире игре на каждый ход
Две недели назад в Питтсбурге IIilecli
пришел первым в турнире из десяти команд,
где участвовали 4 шахматных мастера Па
прошлой неделе он быстро расправился с тре-
мя более слабыми машинами, прежде чем
пойти па Cray. Через дна часа игры в атаке
Cray со стороны короля открылась брешь и
миникомпьюьтср устремился внутрь па спою
жертву. Как выразился Роберт Хайэтт, глав-
ный конструктор проигрывающей програм-
мы - "Мы были отданы на его милость".
Готов ли новый чемпион сыграть с по-
бедителем в матче Карпов-Каспаров Не впол-
не, считает Берлине? Он курирует Премию
Фредкина - награда 100000 предлагается
первой шахматной программе, которая побе-
дит человека-чемпиона мира. Как полагает
Берлииер, шансы, что кто-пибуд!, ухватит
этот приз к 1990 году, составляют примерно
50 на 50. Леви. который обыграл много шах-
матных программ, соглашается: "Раньше иг-
роки в шахматы смеялись. На следующий год
они придут посмотреть. Л скоро они придут
учиться".
- Philip Elmer-DeWill Репортаж Robert
С.Wurrnstedt/r.Денвер - Журнал Time. 28
октября 1985г.
1} 1994г. суперкомпьютер дважды обыграл чемпиона мира Г.Каспарока. - Прим. ред.
Искусстненный интеллект
529
игрыш. Компьютеры изучают потрясающее количество возможных ходов,
однако модель, которая будет просчитывать все ходы, построить техничес-
ки невозможно: кроме того, это не говорит ничего о том, как играют в
шахматы люди и, что более важно, насколько сложные паттерны при этом
воспринимаются, кодируются, преобразуются и приводятся в действие.
Из экспериментов Чейза и Де Грота мы знаем, что даже начинающие
игроки в шахматы выделяют информацию о положении конкретных фигур
и затем сосредотачиваются на разработке стратегии вокруг ключевых фигур
и ходов. Поэтому чтобы шахматная машина могла играть в шахматы как
человек, она должна уметь анализировать паттерн и быстро абстрагиро-
вать из фигур и их позиций информацию об относительной важности бо-
лее крупных единиц информации.
Насколько хорошо компьютер может играть в шахматы? Я сомнева-
юсь, чтобы Фишеру или Спасскому стоило об этом беспокоиться, но се-
годня есть сколько угодно компьютеров, которые могут обыграть всех,
кроме самых сильных игроков. Что мы можем узнать, наблюдая за маши-
ной, которая учится играть в шахматы? Из того, что мы можем узнать,
основное это то, что при анализе паттернов машина может делать только
грубые оценки существенности деталей. Однако, нехватка проницательно-
сти у компьютера компенсируется его способностью к быстрому и обшир-
ному математическому поиску и операциям сравнения. Способность чело-
века выделять значимые признаки из чрезвычайно сложного мира сенсор-
ной информации, формировать из этих признаков абстракции, преобразо-
вывать абстракции в более высокие ассоциативные структуры и разраба-
тывать развитые когнитивные планы, сохраняя в то же самое время эти
внутренние операции в соответствии с внешней реальностью, можно по-
вторить в компьютере пока еще только очень приблизительно.
Универсаль-
ный реша-
тель задач
(УРЗ)
В работе над ИИ эвристика используется потому, что (1)ее можно исполь-
зовать там, где алгоритм (формальная последовательность шагов, ведущая
к решению) неизвестен, (2)она позволяет избежать большого количества
иногда ненужных вычислений и (З)она лучше отражает процедуры реше-
ния задач человеком, чем алгоритмы.
Первую эвристическую программу, ставшую важным шагом для ИИ,
разработали Ньюэлл, Саймон и Шоу (Newell and Simon, 1956; Newell,
Simon, and Shaw, 19584). Эта программа, названная "Логичный Теоре-
тик" (The Logic Theorist) была разработана для доказательства теорем
символической логики эвристическими средствами, а не с помощью грубо-
го поиска с перебором всех возможных перестановок. Многие основные
идеи Логичного Теоретика были расширены Ньюэллом и Саймоном (1964)
в более поздней программе, упоминавшейся в Главе 14, которая называет-
ся "Универсальный Решатель Задач" (УРЗ).
УРЗ - это эвристическая программа, которая моделирует общие стра-
тегии, используемые людьми при решении задач. Она может использо-
ваться для решения конкретной задачи (в шахматах, логике, доказатель-
Самая первая статья была опубликована в 1956 году Ньюэллом и Саймоном
в техническом журнале для радиоинженеров. Более поздняя версия общей
"психологической" теории была опубликована в 1958 году в журнале Psyc-
hological Review.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
ти? Сколько? Чтобы "разумная" машина понимала язык, она должна уметь
при обработке языка делать разумные выводы, как это делают обычные
люди. Основная идея Шенка близка принципу обработки "сверху-вниз",
широко обсуждающемуся в этой книге.
Одной из трудностей, встретившихся при разработке программы обра-
ботки языка, была неоднозначность естественных языков. Шенк (Schank,
1981) приводит следующий пример:
Я ударил Фреда в нос.
Я ударил Фреда в парке.
Чтобы правильно проанализировать эти предложения, нужно знать гораз-
до больше, чем только синтаксические и семантические правила. Чита-
тель должен что-то знать о том, где может находиться человек, а также
другую концептуальную информацию о человеческом поведении и общую
информацию о мире.
Разработанная Шенком программа содержит много систем и подсис-
тем, из которых мы рассмотрим здесь только наиболее существенные.
Сердце программы составляет система умозаключений, скриптов, планов,
тем и целей, считающихся неотъемлемой частью человеческого понима-
ния языка. Мы рассмотрим каждую из них.
Умозаключения. При обработке естественного языка мы обычно от-
слеживаем, где расположены люди и объекты, что они ощущают, в каком
состоянии они находятся, что они знают, каковы их убеждения.
Искусственный интеллект
525
Скрипты2. Скрипт - это "общепринятая" последовательность причин-
ных связей. В естественном языке мы не проговариваем детально и точно
последовательность причинных событий, но (обычно) даем достаточно де-
талей, так чтобы другой человек со сходным жизненным опытом мог по-
нять последовательность событий. В случае с Джоном из вышеприведен-
ного эпизода в ресторане говорящие предполагают, что собеседник выве-
дет связь между событиями (в данном случае - чаевые, еда и плата),
даже если конкретная причинная связь не представлена.
Планы. Чтобы понять большинство событий, важно знать мотивы и на-
мерения участвующих людей. Для этого нужно знать виды их характеров.
Цели. Цели - это довольно специализированные планы, в которых пре-
следуется определенный результат или исход. Планы могут включать воп-
росы о причине выбора конкретной цели, о том, с чем она может конфлик-
товать, и о том, при каких обстоятельствах от нее придется отказаться.
Над целями доминируют структуры более высокого порядка, которые на-
зываются темы.
Темы. Умозаключения, основанные на темах, направлены на выяснение
вопросов:
Какие цели вероятнее всего преследует данное действующее
лицо?
Какие темы вероятнее всего сосуществуют с данной?
Существуют ли противоречия в темах?
Сколько из обнаруженных противоречий можно разрешить?
Откуда происходит данная тема?
Взято из: Schank (1981).
Вначале Шенк и его коллеги стремились только к программе, которая
бы читала, понимала и могла отвечать на несколько вопросов о простом
сюжете - в общем, умела бы то, что умеет делать маленький ребенок. Но
то, что начиналось как элементарный поиск, вылилось в огромный слож-
ный лабиринт взаимосвязанных систем, анализ функциональных свойств
языка, теорию памяти, рассмотрение структуры знания и философское
высказывание о природе мысли. В своей статье, посвященной ИИ. мышле-
нию и самопониманию, Шенк заключает:
"Искусственный интеллект является частью общего стремления
понять мышление. Мы считаем, что он вносит важный вклад в
эти усилия и что они и есть цель нашей науки. Программы,
которые мы пишем,- это эксперимент, а не результат. Наш
интерес - это интеллект, а не артефакт. По мере нашего прогресса
полученные результаты откроют путь ав-томатическим
партнерам, которые, возможно, станут необходимой частью
повседневной жизни. Однако это не будет нашим настоящим
Иначе - стереотипы, штампы поведения.- Прим. ред.
Мышление и интеллект - естественный и искусственный
526
результатом. Настоящим результатом будет новое понимание
нас самих, понимание, которое в конечном счете гораздо более
ценно, чем любая, программа" (Schank, 1985, р.155).
Важность этой работы в том, что она способствует созданию специфи-
кации правил языковой структуры так, чтобы их можно было искусствен-
но смоделировать с высокой степенью верности. Если система ИИ терпит
неудачу, значит мы не смогли понять свойства языка.
Решение задач и искусственный интеллект
Литература по решению задач в рамках ИИ возможно более обширна, чем
по любому другому психологическому процессу. Одна из причин, почему
многие специалисты по ИИ интересуются решением задач, состоит в том,
что этот термин, грубо говоря, синонимичен мышлению, которое в его
сложном виде является исключительно человеческим атрибутом. Этот факт,
а также то, что машины с ИИ вообще способны выполнять процедуры
решения задач, привело к широкому развитию методов и теории в этой
области.
Вычисления были одним из первых примеров использования машин
для решения задач. В 1642 году Паскаль (тогда ему было 19) продемонст-
рировал, что при помощи изобретенного им механического вычислители
некоторые математические задачи можно решать точнее и быстрее, чем
люди делают вручную. В контексте современного ИИ решение заоач очн;!-
чает гораздо больше, чем математические вычисления; оно охватывает
широкий диапазон от решения сложных головоломок до доказатгльстия
теорем, заучивания успешных операций и различных игр.
В основе многих работ в сфере ИИ лежит важное различение между
двумя методами решения задач. Один метод называется алгоритмическим,
а другой - эвристическим. Алгоритмы обычно определяются как проце-
дуры, гарантирующие решение задач данного типа; эвристика есть набор
эмпирических правил или стратегий, которые в итоге действуют подобно
правилу большого пальца. Различие между этими методами можно проил-
люстрировать на примере шахматной задачи. Шахматы для компьюте-
ра - это игра, в которой во всякий данный момент существует ограничен-
ное количество ходов для каждого игрока. И на каждый из возможных
ходов противник может ответить также ограниченным набором ходов. Для
практических целей количество этих перестановок конечно - т.е. игра
должна закончиться выигрышем (поражением) или вничью. На Рис. 15.12
показана часть еще более разветвленного дерева ходов, возможных в шах-
матной партии. Конечно, нельзя изобразить возможные ходы для всей
партии, ибо такая диаграмма содержит около 1020 различных путей. Что-
бы представить себе это огромное число возможных ходов в шахматной
игре, вообразите пространство, необходимое для отображения всех этих
перестановок. Если все возможные пути закодировать в виде мельчайших
точек, они бы многократно заполнили все библиотеки мира! Тем не менее,
алгоритмический поиск, при котором исследуются все варианты, неизбеж-
но привел бы к ряду вариантов игры с выигрышем, проигрышем или ничь-
ей. Не только люди, но даже и самые сложные компьютеры из всех, кото-
рые только можно вообразить, неспособны воспользоваться этим мето-
Искусственный интеллект
527
дом. Вместо него и люди, и компьютеры используют эвристические мето-
ды поиска, при которых становится важной стратегия игры - например,
атака на ферзя, контроль за центром доски, блокирование главных фигур
противника, обмен с получением преимущества в позиции или фигурах и
т.д. К обсуждению алгоритмического и эвристического поиска мы вернем-
ся при рассмотрении универсального решателя задач, но сначала пого-
ворим еще о компьютерных шахматах.
Компьютер- Выше мы описывали, как при помощи оптимального сканера, работающе-
ные шахма- г(э с компьютером, можно было бы разобрать смысл простого паттерна
гы методом сравнения матриц (с. 506). Обсуждая анализ паттернов, мы выяс-
нили, что паттерны сложны и что модель распознавания паттернов чело-
веком, основанная только на сопоставлении матриц, не способна имитиро-
вать разнообразие, сложность и экономичность, характерные для челове-
ческой способности к распознаванию паттернов при кратком предъявле-
нии.
Если бы для распознавания каждого из разнообразных паттернов, встре-
чающихся в повседневной жизни, нужно было иметь по отдельной матри-
це. они переполнили бы емкость хранения даже самого большого компью-
тера. Но давайте выберем для сопоставления матриц умеренно простой
паттерн - что-нибудь среднее между опознанием вашей бабушки и счи-
тыванием стоимости фунта масла (код напечатан на упаковке). В шахма-
тах мы имеем как раз такие паттерны: простая сетка 8х8 попеременно
окрашенных клеток; ходы четко определяются (например, ладья может
ходить на любое количество клеток по вертикали или горизонтали при
условии, что на ее пути нет других фигур, пешка может ходить на одно
тле вперед, за исключением... и т.д.); ходы можно выбирать путем грубо-
го поиска, а количество перестановок конечно, хотя и огромно. При усло-
вии очень большого объема хранения и такого же запаса времени можно
для каждого хода определить вероятность, с которой он приближает вы-
Рис. 15.12. Часть дерева
вероятных ходов в шахмат-
ной партии.
Возмажныв
начальные
ходы Белых
Возможные
ответные
ходы Черных
Возможные
последующие
ответные
ходы Белых
.\1Ы1илсние и. интеллект - естественный и искусственный
528
Короли, Ферзи и кремниевые чипы
Для шахматных чемпионов это была плохая
неделя. Когда Анатолий Карпов отставал па
игру от Гари Каспарова на чемпионате мира
по шахматам, проходившем к концертном
зале Чайковского в Москве, в Редиссон Хол-
ле в Денвере происходило другое расстрой-
ство. Шахматная машина мирового класса и
стоимостью 14 миллионов долларов, супер-
компьютер Cray X-MP/48 при запуске про-
граммы под названием "Блиц" в Северо-аме-
риканском шахматном чемпионате проигры-
вал партию машине Hitech - сделанной на
заказ стойке из кремниевых чипов, соеди-
ненной с мини-компьютером Sun ценой
20000.
Если Карпов и Каспаров сидели лицом к
лицу. то эти два компьютера разделяло 750
миль: Cray находился в Мендота Хайте, штат
Миннесота, a Sun - в университете Карне-
ги-Меллона в Питтсбурге. Ходы компьюте-
ров посылались по телефонным линиям в
Денвер и транслировались на стационарную
шахматную доску. Но расстояние не повре-
дило игре. Мастер по шахматам Дэвид Леви
сказал: "В первый раз программа играла как
сильный игрок-человек".
Компьютеры стали сносно играть в шах-
маты с 1966 года, когда студент из МТИ Ри-
чард Гринблат написал программу МакХэк,
побившую Хуберта Дрейфуса, философа из
Беркли, который настаивал, что ни один ком-
пьютер никогда не. превзойдет 10-летнего ре-
бенка. Современные шахматные машины по-
беждают большинство случайных игроков, а
лучшие программы могут постоять за себя
против всех, кроме самых сильных мастеров13.
Подход шахматных компьютеров обычно
заключается ь грубой силе. Они просчиты-
вают от 4 до 8 ходов вперед, изучают наибо-
лее возможную игру и контригру и выбира-
ют ход, минимизирующий выигрыш оппонен-
та. Компьютер Cray просчитывает 100000
ходов в секунду и обычно выходит победите-
лем. У Hitectia не такая большая память,
как у Cray, и не такие мощные процессоры,
но он компенсирует это скоростью и более
умной игрой. Долговременная стратегия,
например, управляется в нем программой
"Оракул", созданной Хансом Берлинером,
экспертом по искусстиенному интеллекту и
экс-чемпионом мира по шахматам по пере
писке.
Выбрав линию атаки, Оракул передает
управление отдельному блоку, па шаппому
"Искатель". Искатель разработан Карлом
Эбелингом, выпускником универсше i.i Кар-
неги-Меллон, и изготовлен за счет гранта.
предоставленного Департаментом по Оборо-
не. Этот прибор размером с хлебницу содер-
жит 64 микропроцессора специальною на-
значения, каждый из когорых приписан к оп-
ределенному квадрату шахматной доски
Когда фигура ступает па отдельный квадрат.
курирукяций этот квадрат процессор опре
деляст вероятные исходы. При работе с мак-
симальной скоростью эти (i4 чина могут про-
считать 175000 позиций и секунду или :i()
миллионов позиций за ,i минуты, отводимых
в турнире игре на каждый ход
Две недели назад в Питтсбурге IIilecli
пришел первым в турнире из десяти команд,
где участвовали 4 шахматных мастера Па
прошлой неделе он быстро расправился с тре-
мя более слабыми машинами, прежде чем
пойти па Cray. Через дна часа игры в атаке
Cray со стороны короля открылась брешь и
миникомпьюьтср устремился внутрь па спою
жертву. Как выразился Роберт Хайэтт, глав-
ный конструктор проигрывающей програм-
мы - "Мы были отданы на его милость".
Готов ли новый чемпион сыграть с по-
бедителем в матче Карпов-Каспаров Не впол-
не, считает Берлине? Он курирует Премию
Фредкина - награда 100000 предлагается
первой шахматной программе, которая побе-
дит человека-чемпиона мира. Как полагает
Берлииер, шансы, что кто-пибуд!, ухватит
этот приз к 1990 году, составляют примерно
50 на 50. Леви. который обыграл много шах-
матных программ, соглашается: "Раньше иг-
роки в шахматы смеялись. На следующий год
они придут посмотреть. Л скоро они придут
учиться".
- Philip Elmer-DeWill Репортаж Robert
С.Wurrnstedt/r.Денвер - Журнал Time. 28
октября 1985г.
1} 1994г. суперкомпьютер дважды обыграл чемпиона мира Г.Каспарока. - Прим. ред.
Искусстненный интеллект
529
игрыш. Компьютеры изучают потрясающее количество возможных ходов,
однако модель, которая будет просчитывать все ходы, построить техничес-
ки невозможно: кроме того, это не говорит ничего о том, как играют в
шахматы люди и, что более важно, насколько сложные паттерны при этом
воспринимаются, кодируются, преобразуются и приводятся в действие.
Из экспериментов Чейза и Де Грота мы знаем, что даже начинающие
игроки в шахматы выделяют информацию о положении конкретных фигур
и затем сосредотачиваются на разработке стратегии вокруг ключевых фигур
и ходов. Поэтому чтобы шахматная машина могла играть в шахматы как
человек, она должна уметь анализировать паттерн и быстро абстрагиро-
вать из фигур и их позиций информацию об относительной важности бо-
лее крупных единиц информации.
Насколько хорошо компьютер может играть в шахматы? Я сомнева-
юсь, чтобы Фишеру или Спасскому стоило об этом беспокоиться, но се-
годня есть сколько угодно компьютеров, которые могут обыграть всех,
кроме самых сильных игроков. Что мы можем узнать, наблюдая за маши-
ной, которая учится играть в шахматы? Из того, что мы можем узнать,
основное это то, что при анализе паттернов машина может делать только
грубые оценки существенности деталей. Однако, нехватка проницательно-
сти у компьютера компенсируется его способностью к быстрому и обшир-
ному математическому поиску и операциям сравнения. Способность чело-
века выделять значимые признаки из чрезвычайно сложного мира сенсор-
ной информации, формировать из этих признаков абстракции, преобразо-
вывать абстракции в более высокие ассоциативные структуры и разраба-
тывать развитые когнитивные планы, сохраняя в то же самое время эти
внутренние операции в соответствии с внешней реальностью, можно по-
вторить в компьютере пока еще только очень приблизительно.
Универсаль-
ный реша-
тель задач
(УРЗ)
В работе над ИИ эвристика используется потому, что (1)ее можно исполь-
зовать там, где алгоритм (формальная последовательность шагов, ведущая
к решению) неизвестен, (2)она позволяет избежать большого количества
иногда ненужных вычислений и (З)она лучше отражает процедуры реше-
ния задач человеком, чем алгоритмы.
Первую эвристическую программу, ставшую важным шагом для ИИ,
разработали Ньюэлл, Саймон и Шоу (Newell and Simon, 1956; Newell,
Simon, and Shaw, 19584). Эта программа, названная "Логичный Теоре-
тик" (The Logic Theorist) была разработана для доказательства теорем
символической логики эвристическими средствами, а не с помощью грубо-
го поиска с перебором всех возможных перестановок. Многие основные
идеи Логичного Теоретика были расширены Ньюэллом и Саймоном (1964)
в более поздней программе, упоминавшейся в Главе 14, которая называет-
ся "Универсальный Решатель Задач" (УРЗ).
УРЗ - это эвристическая программа, которая моделирует общие стра-
тегии, используемые людьми при решении задач. Она может использо-
ваться для решения конкретной задачи (в шахматах, логике, доказатель-
Самая первая статья была опубликована в 1956 году Ньюэллом и Саймоном
в техническом журнале для радиоинженеров. Более поздняя версия общей
"психологической" теории была опубликована в 1958 году в журнале Psyc-
hological Review.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81