Короли, Ферт и кремниевые чипы

Для шахматных чемпионов это была плохая неделя Когда Анатолий Карпов отставал на игру от Гари Каспарова на чемпионате мира по шахматам, проходившем к концертном зале Чайковского в Москве, в Редис сон Хол­ле в Денвере происходило другое расстрой­ство Шахматная машина мирового класса и стоимостью 14 миллионов долларов, супер­компьютер Cray X-MP/48 при запуске про­граммы под названием "Блиц" в Северо-аме риканском шахматном чемпионате проигры вал партию машине Hitech — сделанной на заказ стойке из кремниевых чипов, соеди­ненной с мини компьютером Sun ценой $20000

Если Карпов и Каспаров сидели лицом к лицу, то эти два компьютера разделяло 750 миль Cray находился в Мендота Хайте, штат Миннесота, a Sun — в университете Карне-ги-Меллона в Питтсбурге Ходы компьюте­ров посылались по телефонным линиям в Денвер и транслировались на стационарную шахматную доску Но расстояние не повре­дило игре Мастер по шахматам Дэвид Леви сказал "В первый раз программа играла как сильный игрок-человек"

Компьютеры стали сносно играть в шах маты с 1966 года, когда студент из МТИ Ри­чард Гринблат написал программу МакХэк, побившую Хуберта Дрейфуса, философа из Беркли, который настаивал, что ни один ком­пьютер никогда не превзойдет 10-летнего ре­бенка Современные шахматные машины по­беждают большинство случайных игроков, а лучшие программы могут постоять за себя против всех, кроме самых сильных мастеров¹³

Подход шахматных компьютеров обычно Заключается в грубой силе Они просчиты вают от 4 до 8 ходов вперед, изучают наибо­лее возможную игру и контригру и выбира­ют ход, минимизирующий выигрыш оппонен­та Компьютер Cray просчитывает 100000 ходов в секунду и обычно выходит победите­лем У Hitech'a не такая большая память, как у Cray, и не такие мощные процессоры, но он компенсирует это скоростью и более умной игрой Долговременная стратегия, например, управляется в нем программой "Оракул", созданной Хансом Берлинером,

экспертом по искусственному интеллекту и экс-чемпионом мира по шахматам по пере­писке

Выбрав линию атаки, Оракул передает управление отдельному блоку, названному "Искатель" Искатель разработан Карлом Эбелингом, выпускником университета Кар-неги-Меллон, и изготовлен за счет гранта, предоставленного Департаментом по Оборо­не Этот прибор размером с хлебницу содер­жит 64 микропроцессора специального на­значения, каждый из которых приписан к оп­ределенному квадрату шахматной доски Когда фигура ступает на отдельный квадрат, курирующий этот квадрат процессор опре­деляет вероятные исходы При работе с мак­симальной скоростью эти 64 чипа могут про­считать 175000 позиций в секунду или 30 миллионов позиций за 3 минуты, отводимых в турнире игре на каждый ход

Две недели назад в Питтсбурге Hitech пришел первым в турнире из десяти команд, где участвовали 4 шахматных мастера На прошлой неделе он быстро расправился с тре­мя более слабыми машинами, прежде чем пойти на Cray Через два часа игры в атаке Cray со стороны короля открылась брешь и миникомпьюьтер устремился внутрь на свою жертву Как выразился Роберт Хайэтт, глав­ный конструктор проигрывающей програм­мы - "Мы были отданы на его милость"

Готов ли новый чемпион сыграть с по­бедителем в матче Карпов-Каспаров? Не впол­не, считает Берлинер Он курирует Премию Фредкина — награда $100000 предлагается первой шахматной программе, которая побе­дит человека-чемпиона мира Как полагает Берлинер, шансы, что кто-нибудь ухватит этот приз к 1990 году, составляют примерно 50 на 50 Леви, который обыграл много шах­матных программ, соглашается "Раньше иг­роки в шахматы смеялись На следующий год они придут посмотреть А скоро они придут учиться"

— Philip Elmer-DeWitt Репортаж Robert С Wurmstedt/r Денвер — Журнал Time 28 октября 1985г

¹³В 1994г суперкомпьютер дважды обыграл чемпиона мира Г Каспарова - Прим ред

Искусственный интеллект 529

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

Насколько хорошо компьютер может играть в шахматы? Я сомнева­юсь, чтобы Фишеру или Спасскому стоило об этом беспокоиться, но се­годня есть сколько угодно компьютеров, которые могут обыграть всех, кроме самых сильных игроков. Что мы можем узнать, наблюдая за маши­ной, которая учится играть в шахматы? Из того, что мы можем узнать, основное это то, что при анализе паттернов машина может делать только грубые оценки существенности деталей. Однако, нехватка проницательно­сти у компьютера компенсируется его способностью к быстрому и обшир­ному математическому поиску и операциям сравнения. Способность чело­века выделять значимые признаки; из чрезвычайно сложного мира сенсор­ной информации, формировать из этих признаков абстракции, преобразо­вывать абстракции в более высокие ассоциативные структуры и разраба­тывать развитые когнитивные планы, Сохраняя в то же самое время эти внутренние операции в соответствии с внешней реальностью, можно по­вторить в компьютере пока еще только очень приблизительно.

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

(YP3)

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

Первую эвристическую программу, ставшую важным шагом для ИИ, разработали Ньюэлл, Саймон и Шоу (Newell and Simon, 1956; Newell, Simon, and Shaw, 1958¹⁴). Эта программа, названная "Логичный Теоре­тик" (The Logic Theorist) была разработана для доказательства теорем символической логики эвристическими средствами, а не с помощью грубо­го поиска с перебором всех возможных перестановок. Многие основные идеи Логичного Теоретика были расширены Ньюэллом и Саймоном (1964) в более поздней программе, упоминавшейся в Главе 14, которая называет­ся "Универсальный Решатель Задач" (УРЗ).

УРЗ — это эвристическая программа, которая моделирует общие стра­тегии, используемые людьми при решении задач. Она может использо­ваться для решения конкретной задачи (в шахматах, логике, доказатель-

^|4Самая первая статья была опубликована в 1956 году Ньюэллом и Саймоном в техническом журнале для радиоинженеров. Более поздняя версия общей "психологической" теории была опубликована в 1958 году в журнале Psyc­hological Review.

Мышление и интеллект - естественный и искусственный 530

r

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

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

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

CROSS (пересеченные)¹⁶ + ROADS___________(дороги)________

DANGER (опасность)

УРЗ постепенно был вытеснен более внушительными программами, но он признан за открытие области решения задач компьютерами путем раз­ложения сложной задачи на подзадачи, которые решить проще. Ховард Гарднер (Gardner, 1985) отдал дань проницательности Ньюэлл а и Саймо­на в своей книге по истории "когнитивной революции" в следующем абзаце:

"С их точки зрения, глубокое сходство между человеческим мозгом, занятым решением задачи, и компьютером, за-программированным на. решение этой же задачи, далеко превосходит различия в их устройстве (электронная машина и комок нервной ткани). И то, и другое — это просто системы, которые обрабатывают информацию во времени, действуя при этом более или менее логично. Более того, если этапы, отмеченные индивидуумом в процессе интроспекции, соответствуют строкам компьютерной программы, то мы уже не можем придерживаться мягкого подхода к ИИ: оказывается, что эту созданную человеком физическую символическую систему имеет смысл рассматривать как

^|5Более сложное описание модели Ньюэлла можно найти в статье "Artificial Intelligence and the Concept of Mind" в книге: R.Schank and K.Colby, eds., Computer Models of Thought and Language (1973).

¹⁶B русском языке "crossroads" (пересечение дорог) выражается словом "пе­рекресток".— Прим, перев.

Искусственный интеллект 531

Время _Отсчет

^Вскан^аиро-^И Да"**™" времени вания (сек) ^глаз (^сек'

Вербализация

Время внимания и сканиро­вания (сек)

глаз

^ВР(секГ ^ВеР^6а^изация

0.6

3.0

0.8

2.0

1.0

2.8

2.0

CROSS

ROADS

DANGER