Когда созданный специалистами корпорации IBM суперкомпьютер Deep Blue обыграл Гарри Каспарова в матче с нормальным регламентом, шахматный мир был потрясен, однако многие приписали это одной лишь грубой его аппаратной мощи. Способность этой машины просчитывать по 200 млн вариантов ходов в секунду позволила Тому Хафхиллу (Tom Halfhill) выдвинуть свой известный провокационный аргумент относительно того, что Deep Blue просто обманул шахматные часы, прессуя 380 лет человеческих размышлений в три минуты своей игры.

Усовершенствование аппаратных средств, несомненно, сыграло свою роль: каждый дополнительный уровень прогноза (шахматный ход), за исключением завершающей части поиска решения, когда отдача от дополнительных вычислений начинает уменьшаться, добавляет к игровому рейтингу компьютера добрых 200 пунктов. (Рейтинги присваивает ФИДЕ; так, рейтинг Каспарова равен 2 тыс. 820 пунктам.) Однако метод грубой силы требует колоссальных вычислительных затрат. Проиллюстрируем это примером: известно, что игрок каждый раз может выбирать в среднем приблизительно из 30 возможных вариантов очередного хода. Столько же вариантов ответа имеется и у его противника. Таким образом, на один ход рассматривается около 900 вероятных позиций. Дерево позиций для игры стандартной продолжительности состоит из 10 125 узлов. Компьютеру, просчитывающему по миллиарду вариантов хода в секунду, на анализ этого дерева потребовалось бы 10 108 лет.

Итак, одной скоростью счета в поиске выигрышных шахматных комбинаций не обойтись. Deep Blue использует оптимизированное дерево выбора вариантов, настроенное с привлечением экспертных знаний. Создатели машины реализовали алгоритм обработки этого дерева аппаратно: наиболее вычислительно сложные операции возложены на специализированные микросхемы (ASIC), встроенные в процессорные узлы многопроцессорной машины.

В 1987 г. автор замысла и главный конструктор Deep Blue Фенг-Синг Су (Feng-Hsiung Hsu) писал: "Один из способов повышения скорости обработки на несколько порядков заключается в распараллеливании фундаментального для шахматных программ алгоритма альфа-бета-отсечения. Еще один путь увеличения производительности на порядки величины, аналогичный первому по своей природе, состоит в повышении уровня интеграции микросхем без снижения скорости работы отдельных их элементов. Синергетический эффект от совершенствования алгоритма и специализации аппаратуры сделал сегодня решаемой задачу создания шахматной машины с полным набором функций на небольшой номенклатуре микросхем".

Синергетический эффект - вот как называется то, чего сумели добиться Су и его соратники Джоэл Бенджамин (Joel Benjamin), Джерри Броуди (Jerry Brody), Мюррей Кэмпбелл (Murray Campbell), Джо Хоан (Joe Hoane) и Чанг-Джен Тан (Chung-Jen Tan) - команда, создавшая Deep Blue. Этот самый синергетический эффект и стал ключом к победе над Каспаровым.

Деревья выбора

Deep Blue использует вариант алгоритма альфа-бета-отсечения, называемый NegaScout и отличающийся от стандартного углубленным анализом особых ветвей. Семейство таких алгоритмов было предложено в 80-х группой аспирантов Университета Карнеги - Меллона. Некоторые из них впоследствии приняли участие и в создании Deep Blue. Обычный альфа-бета-алгоритм подразумевает поиск и оценку всех возможных вариантов на фиксированную глубину - 8, 9 или 10 полуходов. На горизонте - так называется последний уровень, до которого добирается программа с фиксированной глубиной просмотра, - производится поиск стабильной позиции, т. е. позиции, не являющейся промежуточным этапом в процессе размена. Иными словами, на этом этапе компьютером может быть принято решение в пользу позиции с очевидным материальным преимуществом, которое на следующем же ходу обернется более значительной потерей - так называемый эффект горизонта. Уточняющий поиск стабильных позиций ограничен учетом форсированных ходов, таких как взятие фигуры или шах, с тем чтобы его чрезмерно не усложнять

Однако анализ гроссмейстерских партий показал, что игроки данного класса просчитывают варианты на гораздо большее число уровней, чем это достижимо в программе с фиксированной глубиной просмотра. Так, первая группа, сформировавшаяся в Университете Карнеги - Меллона, пришла к идее использования алгоритмов, в которых по ходу основного поиска осуществляется выявление наиболее интересных и, возможно, форсированных комбинаций. Варианты развития подобных комбинаций анализируются затем на значительно большую глубину, до 30 - 40 уровней. Это новшество стало крупным прорывом в направлении повышения тактических способностей компьютеров.

Обычно форсированные ходы просчитываются на базе существующих специальных знаний, которые трудно собрать воедино и которые не охватывают всех динамических аспектов шахматных позиций. Углубленный просмотр особых ветвей не зависит от знания конкретной предметной области и основывается на идеях, общих для игр многих типов. Ход считается особым, если значение оценочной функции оказывается для него существенно выше соответствующих значений для альтернативных ходов; последствия такого хода подвергаются анализу на большее число уровней.

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

Более обобщенный вариант алгоритма углубленного просмотра особых ветвей - просмотра с выходом за границы основного русла - предусматривает анализ обычно отбрасываемых вариантов. В традиционном алгоритме альфа-бета-отсечения основным руслом называется множество путей, ограниченное заданными обязательными величинами функций эффективности хода и ответного хода. Эти две границы и именуются "альфа" и "бета". Выходящие за рамки основного русла ответвления отсекаются, что позволяет сократить размеры дерева. Разработчики шахматного компьютера Deep Thought (предшественника Deep Blue) реализовали углубленный просмотр особых ветвей с выходом за границы основного русла, дающий возможность исследовать варианты, не умещающиеся в альфа-бета-коридор, но все-таки имеющие некоторые перспективы. В Deep Blue данная стратегия получила дальнейшее развитие - эта машина на анализ таких вариантов отводит даже большую долю ресурсов, чем Deep Thought.

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

Оценка позиции

Deep Blue не использует ни БД известных из истории вариантов, ни методов искусственного интеллекта, таких как распознавание образов. Его создатели исследовали возможности адаптации разработанной в IBM технологии распознавания образов Flash и по-прежнему рассматривают это направление как перспективное, но на его реализацию у них просто не было времени. Вместо этого Deep Blue оценивает (аппаратно) приблизительно 6 тыс. специфических для шахмат показателей.

Люди, играя в шахматы, определяют свою позицию материальным перевесом ("Я проигрываю пешку") или степенью контроля над игровым полем ("Я контролирую центр"). Критерии этого рода используются и компьютерами. Клод Шэннон (Claude Shannon) в своей первой статье, посвященной компьютерным шахматам, предложил функцию оценивания, которая зависела в основном от трех факторов: материального перевеса, расположения пешек (далеко продвинутые, изолированные и неразвитые пешки) и мобильности фигур (количества разрешенных для них ходов). Количественная оценка качества позиции вычислялась по формуле

Качество (Позиция) = 200(Кр - Кр') + 9(Ф - Ф') + 5(Л - Л') + 3(С - С' + К - К') + (П - П') - 0,5(ПП - ПП' + ИП - ИП'+ НП - НП') + 0,1(Х - Х').

Здесь переменные без штриха относятся к фигурам одного игрока, а с символом ' - к фигурам другого. Х обозначает число разрешенных ходов. Остальные буквы соответствуют количеству остающихся на доске фигур: Кр - король, Ф - ферзь, Л - ладья, С - слон, К - конь, П - пешка. Среди пешек далее выделяются категории продвинутых (ПП), изолированных (ИП) и неразвитых (НП).

С ростом вычислительной мощности компьютеров функции оценивания стали намного сложнее. Значения, соответствующие каждому показателю, хранятся в таблицах размером 8х8 (по одной ячейке на каждую клетку шахматной доски). На рис. 1 представлена такая таблица для учета степени контроля коня над центром доски. Цифры соответствуют ценности положения коня на соответствующем поле. Например, если сейчас ваш ход и ваш конь занимает пятую позицию на королевской вертикали (выделенная клетка), то вы создали серьезную угрозу своему оппоненту. Ценность этой позиции приравнена к 10 - высшему из возможных значений. Аналогично первый ход коня с выходом на вертикаль королевского слона (F3) оценен выше (5), чем на вертикаль королевской ладьи (-7). Для коней, как и для большинства других фигур, выше оцениваются позиции, занимаемые ближе к центру доски. Как можно проследить по цепочкам отрицательных значений таблицы, наименее эффективны кони, располагающиеся на ладейных вертикалях (правый и левый края рисунка), а также на задних линиях (верхний и нижний края). Нахождение на исходной позиции любой из ладей своего цвета оценено в -10; конь, загнанный в эту позицию, в сущности, оказывается вне игры.

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

Наконец, любой показатель может иметь больший или меньший вес в зависимости от фазы игры, а ценность фигуры сильно зависит от ее позиции. Например, чернопольный слон потенциально менее полезен по сравнению с конем, если все фигуры противника размещаются на белых полях. Сходным образом ладья, занимающая свободную вертикаль, в определенных ситуациях может иметь меньшую тактическую ценность. В тестовых играх, проводившихся между матчами 1996 и 1997 гг., Deep Blue проявил склонность слишком охотно жертвовать пешки на ранних этапах игры, чтобы получить открытую вертикаль для ладьи. К матчу 1997 г. его разработчики скорректировали реализованную в специализированной микросхеме оценочную функцию, повысив тем самым порог открытия вертикали для ладьи. Это изменение проявило свою стратегическую важность во второй игре.

Между первым и вторым матчами с Каспаровым команда разработчиков Deep Blue трудилась не покладая рук, с тем чтобы реализовать в оценочной функции более полный учет контекста. Сильная позиционная игра Deep Blue на протяжении всего матча была обеспечена его способностью оценивать текущую ситуацию на доске и вносить соответствующие коррективы в веса оцениваемых показателей, которые затем записывались в регистры аппаратуры

Подстройка

Сильная позиционная игра Deep Blue против Каспарова стала возможной благодаря способности машины назначать веса показателям оценки в зависимости от значений других показателей. Таким образом компьютеру удавалось получить практически правильную оценку любой конкретной шахматной позиции. Соответствующая задача оптимизации очень сложна: количество измерений исчисляется тысячами.

Автоматическая подстройка. Автоматическая подстройка оценочной функции впервые была применена еще в проекте Deep Thought. Основная идея состояла в том, что, если компьютер будет чаще делать гроссмейстерские ходы, это повысит общий уровень его игры. Для обучения использовалась БД из 900 гроссмейстерских матчей.

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

Этот метод оказался чрезвычайно вычислительно емким (на счет уходили недели), так что впоследствии его стали использовать только для особо сложных позиций. В остальных случаях разработчики Deep Thought прибегали к методу наименьших квадратов для одновременного изменения весов сразу всех параметров. Автоматическая подстройка применяется и сейчас, наряду с некоторыми другими методами, такими, например, как предлагаемые в системе Neurogammon Джеральда Тезауро (Gerald Tesauro).

Стратегия подстройки Deep Blue. Даже при значительно возросшей вычислительной мощности, обеспечиваемой машиной RS6000 SP, для оптимизации весов около 10 тыс. параметров оценки (против 120 для Deep Thought) примерно по 5 тыс. эталонных позиций потребовалась бы неделя или две. Таким образом, автоматическая подстройка и в этом случае оказалась недопустимо дорогим занятием. По этой причине корректировка оценочной функции для Deep Blue осуществляется в основном вручную - примерно на 98%. (Deep Thought использовал методы поиска экстремума в некоторых сложных ситуациях, что дало значительный эффект в матче с Каспаровым.)

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

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

Распараллеливание поиска

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

Архитектура Deep Blue

Сегодня Deep Blue работает на мультикомпьютерной системе RS6000 SP, состоящей из 32 узлов. В ней применена схема с распределенной памятью (одновременно обрабатывается несколько потоков команд и несколько потоков данных); взаимодействие между потоками осуществляется путем обмена сообщениями. Каждый узел содержит процессор Power2 Super Chip (P2SC) производства IBM, способный выполнять до шести инструкций за один такт. Система состоит из двух узлов на базе 135-МГц процессоров P2SC, обеспечивающих высокую пропускную способность канала доступа к данным, и тридцати 120-МГц узлов, сконфигурированных для вычислительной обработки. Один из 135-МГц узлов управляет всей системой и служит резервным процессором ввода/вывода для 64-Гбайт диска с архитектурой SSA (serial-storage architecture). Пространство этого диска поделено между БД дебютов и эндшпилей (32 Гбайт) и разделом для резервного копирования. Второй 135-МГц узел обеспечивает в первую очередь ввод/вывод для SSA-диска, а кроме того, на этапе обработки выполняет функции одного из 31 ведомого процессора. В состав каждого узла, помимо основного универсального процессора, входит по две платы с восьмью специализированными шахматными чипами на каждой - итого 16 на узел и 512 на компьютер.

Шахматные кристаллы

Deep Blue черпает свою мощь в 512 специализированных микросхемах, аппаратно реализующих функции генерации и оценки вариантов ходов. В программных реализациях алгоритмов игры в шахматы генерация вариантов отнимает значительную часть процессорного времени (40 - 50%). Поэтому в новейших шахматных компьютерах, в частности (что представляет для нас наибольший интерес) в Deep Blue, для этого применяется специализированная аппаратура. Аппаратные реализации никоим образом не могут считаться новшеством: еще в компьютере ChipTest, предшественнике Deep Thought, Су использовал разработанные Кеном Томпсоном (Ken Thompson) аппаратные средства генерации вариантов. В Deep Thought были аппаратно реализованы функции генерации и оценки вариантов, предназначенные для ранжирования ходов, которое применяется в алгоритмах альфа-бета-отсечения.

Ранняя версия специализированной микросхемы (использовавшаяся в Deep Thought) содержала массив специализированных цепей просчета комбинаций размерности 8х8. Каждая такая цепь состояла из передатчика и приемника. На рис. 2 представлена схема приемной половины. Принимаются и передаются сигналы нападения соседних фигур друг на друга. Используя эвристику "наиболее ценная фигура под боем/наименее ценная нападающая фигура", специализированная микросхема выполняет две операции - "поиск жертвы" и "поиск агрессора". В цикле поиска жертвы кристалл упорядочивает возможные ходы таким образом, что первыми идут взятия наиболее ценных фигур, осуществляемые предпочтительно фигурами наименьшей ценности. Эти сгруппированные по типам сигналы атаки направляются в логическую цепь "приемника", где вычисляется приоритет каждого из них в зависимости от типов атакующих и атакуемых фигур, а также от очередности хода.

Первоначально специализированные микросхемы содержали 35925 транзисторов и производились по 3-мкм КМОП-технологии. Их производительность составляла 700 тыс. вариантов ходов в секунду. Со временем количество транзисторов выросло до 1,7 млн, а технологическая база была доведена до 0,6 мкм. В результате производительность увеличилась до двух-трех миллионов вариантов ходов в секунду.

Оценочные функции

У ChipTest настоящей функции оценки не было - этот компьютер полагался на простой подсчет материального преимущества. Функция оценки Deep Thought включает инкрементный и долговременный компоненты. Инкрементная часть имеет определенное значение для расположения каждой из фигур на каждой из 64 клеток доски. Применяемая эвристика учитывает материальную ценность фигуры, близость ее расположения к центру, развитие пешек и т. д.

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

При оценке каждого хода Deep Thought обходился менее чем 10 таблицами, а Deep Blue использует уже около 50. Каждая таблица обеспечивает расчет некоторого подмножества показателей: для позиции коня, слона, пешки и т. д. Специализированная аппаратура Deep Blue представляет собой функционально полный шахматный автомат, обеспечивающий генерацию вариантов ходов, простой поиск, а также более сложный уточняющий поиск.

В результате логика функции оценки занимает теперь около двух третей общей площади кристалла.

Еще одно новшество этой машины - логика эндшпиля и небольшая БД шахматных окончаний помещены фактически прямо на чипе. Кроме того, теперь микросхема обнаруживает повторение позиций или близкие к нему ситуации, т. е. обеспечивает выявление ничейных вариантов этого типа. Указанная функция компенсирует отсутствие на кристалле специальной таблицы сопоставления позиций, применяемой иногда для подобных целей. Обнаружение ничейных ситуаций заметно улучшило игру машины в эндшпиле. Способность Deep Blue учитывать мобильность фигур позволяет ему в зависимости от расположения пешек оценивать степень контроля над пространством доски.

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

Матч

Deep Blue победил Каспарова со счетом 3,5:2,5 - две победы, одно поражение и три ничьих. Каспаров, играя белыми, сравнительно легко одержал победу в первой игре. Вторая, по-видимому, оказалась переломной: Каспаров признал поражение на 45-м ходу и лишь на следующий день обнаружил, что сдал ничейную партию. Следующие три партии чемпион мира свел вничью, имея хорошие позиции, но пребывая в жестоком цейтноте, что, похоже, его добило. Он уступил решающую партию менее чем в 20 ходов, попавшись на 7-м ходу в известную ловушку, хотя и играл хорошо знакомый ему вариант защиты.

Победа Deep Blue во второй партии потрясла Каспарова. Чемпионка мира среди женщин Жужа Полгар заявила: "Компьютер играл по-чемпионски, по-карповски. Deep Blue продемонстрировал множество ходов, основанных на понимании ситуации, на чувстве позиции".

У разработчиков Deep Blue взгляд на эту игру несколько иной. Они выделяют удачную модификацию оценочной функции для ладейных пешек. На 19-м ходу Deep Blue сыграл такой пешкой, что сделало возможным ее размен и открыло ладейную вертикаль. Но сам размен машина отложила до 35-го хода, когда открыла вертикаль для сдвоенных ладей. Дальнейшее развитие этой комбинации привело к разрушению обороны Каспарова на ферзевом фланге. Для разработчиков подобное самоограничение Deep Blue стало кульминацией матча.

Будущее

Представители IBM не устают повторять, что разработка Deep Blue не являлась просто рекламной акцией и не преследовала цель создать компьютер, способный победить чемпиона мира по шахматам. Они уверены, что результаты исследований, проведенных в ходе осуществления этого проекта, будут иметь многочисленные практически важные приложения. "Шахматы - лишь одно из них, - заявил Тан. - Для нас главным стало понимание того, каким образом компьютеры могут решать сложные задачи и как можем использовать этот инструмент мы, люди. Истинная ценность проведенного эксперимента заключается для нас в опробовании различных инструментов в роли средства решения проблем, т. е. не просто для быстрого счета, а для проведения исследований во многих областях".

"Мы извлекли из построения этой системы множество полезных уроков и некоторые из них уже применили при решении других сложных задач, требующих огромной вычислительной мощности, - заявил Кэмпбелл. - Deep Blue способен выполнять неимоверные объемы вычислений в поисках хорошего шахматного хода. Конечной целью создания систем, подобных нашей, является применение выработанных принципов для построения инструментов, ориентированных на решение других задач".

Оценка финансовых рисков

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

"Некоторые из ключевых проблем, на решение которых мы нацеливались, относятся к оценке финансовых рисков и интеллектуальному анализу данных", - сказал Кэмпбелл. Он пояснил, что при решении задач с использованием технологий Deep Blue "основная идея состоит в том, чтобы определить аспекты вычислений, являющиеся хорошими кандидатами на ускорение. В случае оценки финансовых рисков, например, ускорение расчетов по тем или иным алгоритмам в десятки или сотни раз могло бы существенно повысить ценность получаемых результатов.Скорость здесь - все. На Уолл-стрит, как известно, получение нужной информации раньше конкурентов приносит огромные деньги". Одно из основных направлений исследований, проводимых командой разработчиков Deep Blue, - использование накопленного опыта в моделировании методом Монте-Карло. Они уже провели переговоры с несколькими финансовыми организациями, заинтересованными в более эффективном применении многопроцессорной технологии IBM.

Проект MD Grape

В прошлом специализированные суперкомпьютеры использовались в первую очередь учеными для решения вычислительно сложных задач. Например, в Токийском университете была создана система Grape-4 (GravityPipe No. 4 - гравитационная труба ь 4) с 1692 специализированными процессорами совокупной производительностью 1,08 Тфлоп. Этот компьютер, стоивший 1,5 млн дол., производил один-единственный расчет - определял силу притяжения между двумя небесными телами. Еще одна группа исследователей из IBM разработала в сотрудничестве с создателями Grape-4 новую версию этой системы, MD Grape, предназначенную для имитационного моделирования в области молекулярной динамики. В ней нашли применение некоторые из найденных в ходе выполнения проекта Deep Blue стратегий совместного использования специальных процессоров универсального процессора RS6000 для достижения максимальной вычислительной мощности и одновременно гибкости.

Реализация на базе перепрограммируемых логических матриц

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

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

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

Каспаров, возможно, дал наилучшую формулировку, когда сказал, что Deep Blue делал человеческие ходы. Это наблюдение подчеркивает важность роли программного обеспечения, воплощающего человеческий опыт и направляющего мощь аппаратных средств в правильное русло, - весьма многообещающая тенденция для будущего вычислительной техники. Уроки разработки Deep Blue не являются чисто специфическими для компьютерных шахмат, они могут найти применение и в других предметных областях.

Computer

Сложные проблемы - потенциальные приложения?

Задачи, решаемые Deep Blue с помощью специальных методов оценки, средств визуализации и аппаратуры, имеют важное значение для науки и, возможно, для производства. Вот некоторые потенциальные применения.

Молекулярная динамика

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

Фармацевтическое моделирование

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

Биомолекулы

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

Большое время счета даже по современным моделям относительно небольшой размерности затрудняет проведение исследований. Проблема, по мнению профессора Университета Дьюка Джона Борда-мл. (John Board jr) и его коллег, усугубляется "нехваткой интерактивных программ, которые позволяли бы ученому направлять процесс". Они убеждены, что для успешного решения этой проблемы необходимы "значительно более высокие скорости счета, достичь которых можно за счет более совершенных алгоритмов и с использованием параллельной обработки на множестве процессоров". Возможно, здесь окажется полезен опыт Deep Blue в части подстройки алгоритмов и ограничения дерева поиска.

Распространение трещин

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

В одном из исследований по теории распространения трещин, проведенном в Лос-Аламосской национальной лаборатории, использовалась имитационная модель 38 млн атомов, образующих тонкую пластину. По словам Нильса Гронбека-Дженсена (Niels Gronbech-Jensen) и его коллег, на каждом шаге расчета имитационной модели значительную часть времени (около 15%) занимал обмен сообщениями между параллельными узлами. Примененная в Deep Blue стратегия неодинаковых подходов к коммуникации на последовательных уровнях обработки дерева просмотра позиций может быть использована и для сокращения вычислительных затрат на коммуникационные процедуры при имитации процессов распространения трещин.

Интеллектуальный анализ данных

Различные формы интеллектуального анализа данных потенциально чрезвычайно важны для таких приложений, как оценка финансовых рисков и поддержка принятия деловых решений. Технология Deep Blue может найти применение в каждой из названных областей.

Оценка финансовых рисков

Существует потребность в правильном и рациональном оценивании рыночной стоимости таких ценных бумаг, как акции, облигации и опционы, и прогнозировании ее возможного изменения. Корпорации с Уолл-стрит для решения подобных задач все активнее начинают обращаться к областям знаний, долгое время остававшимся уделом инженеров и ученых. Например, для анализа опционов применяется уравнение в частных производных Блэка - Шоля (Black-Scholes), имеющее точное решение при следующих трех упрощающих допущениях:

- операции с опционами ведутся непрерывно, и накладные расходы на осуществление транзакций равны нулю;

- отсутствуют риски;

- цены изменяются по логарифмическому закону.

Однако для лучшего предсказания поведения реальных опционов необходимо учитывать в этих уравнениях, скажем, накладные расходы на осуществление транзакции. Отказ от этого упрощения приводит к нелинейной форме уравнения Блэка - Шоля, не имеющей замкнутого решения. Традиционно вычислительная наука предлагает решать такие задачи приближенными методами, такими как метод конечных разностей. Применяется и моделирование методом Монте-Карло, дополнительная привлекательность которого состоит в возможности использования сразу многих параллельно и независимо работающих компьютеров. Между тем, как указывают исследователи Эмилио Баруччи (Emilio Barucci), Леонардо Ланди (Leonardo Landi) и Умберто Керубини (Umberto Cherubini): "Основной недостаток... состоит в том, что все эти методы зависят от вида распределения..."

Чидананд Апте (Chidanand Aptе) из исследовательского центра Т. Дж. Уотсона корпорации IBM придерживается того же мнения: "Важная тенденция в развитии парадигмы моделирования... заключается в движении в сторону непараметрических методов... в которых не используются никакие допущения относительно распределения значений данных". Далее он говорит о возможности применения таких технологий, как нейронные сети, деревья решений и правила принятия решений. Если окажется, что деревья принятия решений действительно подходят для подобных вычислений, методы оптимизации поиска по таким деревьям, разработанные для Deep Blue, могут найти еще одно практическое применение.

Поддержка принятия деловых решений

Поддержка принятия деловых решений требует осуществления поиска и организации данных, на основании которых такие решения принимаются. Процедуры подстройки, разработанные для Deep Blue, могут быть экстраполированы для использования в алгоритмах, обеспечивающих "просеивание" данных и извлечение из них полезной информации. Апте указывает также на то, что уже после выполнения процедур интеллектуального анализа данных приходится решать очень сложную проблему визуализации, без чего пользователи не смогут осмыслить полученные результаты. Хотя и существует несколько средств визуализации универсального типа (созданных для статистических программ и пакетов трехмерного моделирования), их могло бы быть значительно больше. И тут, в частности, могут пригодиться уроки, извлеченные из разработки средств визуализации для проекта Deep Blue.

Janet Wilson

S.Hamilton, L.Garber

СomputerWeekly, N5, 1998, c.34-37,45