‘‘Это - война!” - заявил Гарри Каспаров после окончания матча с компьютером Deep Blue (DB). Каспаров, как известно, потерпел поражение со счетом 2,5:3,5. Свой проигрыш он объяснил отсутствием качественной подготовки к матчу и короткой дистанцией состязания (6 партий). Теперь Гарри готов поставить на кон свой титул чемпиона мира, но требует, чтобы будущий матч проходил под эгидой не IBM, а одной из официальных шахматных организаций (по-видимому, Профессиональной шахматной ассоциации, ПША), и был бы более продолжительным.
Deep Blue представляет собой компьютер, основанный на технологии IBM RS/6000 SP. Он состоит из 16 узлов, каждый из которых содержит два процессора P2SC (усовершенствованные PowerPC). Дополнительно к компьютерному блоку подсоединено несколько сотен специализированных микропроцессорных наборов для быстрой генерации ходов и оценки позиции. Игровая программа написана на Си и работает под управлением ОС AIX. DB в секунду анализирует 200 млн. позиций (узлов дерева перебора).
На фоне громкой рекламной шумихи по поводу “победы Компьютера над Человеком” остался открытым главный вопрос - а так ли уж сильно играет DB? Прежде всего, сам Каспаров играл откровенно плохо, пунктов на 200 ниже своего рейтинга. Он объяснил это желанием выбить компьютер с наигранных путей. Такая странная стратегия и привела Гарри к поражению. Исходя из рекомендаций компьютерных специалистов (интересно, что московские специалисты по компьютерным шахматам в один голос высказались против его стремления взять программу на понт), Гарри посчитал, что компьютер не должен жертвовать материал за атаку, и пошел в решающей партии на теоретически проигрышный вариант. Увы! Гарри был прав в одном - программы не любят жертвовать, если думают сами. Однако фатальный для Каспарова ход 8. К:e6 был сделан DB “не думая”, за 10 секунд, простым запросом к справочной базе. Из дебюта программа вышла только на 11-м ходу, потратив на самостоятельный анализ позиции 2 минуты 59 секунд.
Иногда DB играла действительно странно. В Сети даже обсуждался вопрос “а не подсказывал ли кто программе?”, и некоторые подозрения просто не могли не зародиться из-за излишней закрытости IBM’овской стороны. Что происходило за пультом компьютера, знает только команда DB. Нельзя также не учитывать, что предыдущая встреча DB с Каспаровым принесла IBM, благодаря увеличению объемов продаж, дополнительный доход около 200 млн. долл. Победа в этом году принесет еще больше. Конечно, человек машине не подсказывал - по словам Карпова, он тогда сам бы сел играть с Гарри, но изменить параметры программы во время партии принципиально вполне возможно. Зачем? Причин много. Например, для шахматных программ актуальна проблема определения “активных” позиций, когда надо посчитать варианты поглубже, чтобы найти выигрыш. Недаром Каспаров требовал от команды DB, в состав которой входит сильный гроссмейстер Бенджамин, ответа (но так и не получил его), почему над ключевым ходом одной из партий программа думала целых 15 минут, хотя обычно она тратила ровно 3 минуты на ход. Масла в огонь подлил руководитель проекта DB профессор Тан, заявив, что в последний год они усиливали программу по трем направлениям: увеличивали счетные возможности машины, закладывали в нее шахматные знания и создавали инструментарий для динамической настройки параметров программы. Тан не скрывал, что они готовили DB к матчу с конкретным игроком - Каспаровым и меняли ее параметры в промежутках между партиями, что разрешалось регламентом. А сам Каспаров умышленно был лишен возможности “познакомиться” с DB, потому что сыграй он с ней предварительно несколько десятков тренировочных партий - и в матче “вычесал” бы программу на ноль.
Предложение повторить некоторые партии, чтобы проверить, сделает ли компьютер те же ходы, команда DB отвергла. Разработчики сослались на существенный стохастический элемент в игре машины. Дело в том, что на ускорение расчета влияет не только быстродействие процессора, но и объем памяти. При переборе вариантов машина много времени тратит на просмотр ранее исследованных позиций, которые возникают в результате сделанных ходов. Для решения этой проблемы используется хэш-таблица просмотренных позиций, и программа постоянно заглядывает в нее, проверяя, не встречалась ли новая позиция ранее. Правда, нередко разные позиции попадают в одну и ту же ячейку - возникает коллизия. Для ее разрешения применяются различные алгоритмы, но наиболее эффективный способ - просто увеличить размер таблицы. DB использует несколько распределенных параллельных массивов памяти для хэш-таблицы. Информация в них синхронизируется в моменты случайных прерываний, например по таймеру, поэтому точно смоделировать работу хэш-алгоритмов действительно невозможно.
Конечно, скорее всего, DB играла сама. Я, например, в этом уверен. Другое дело, что вольно или невольно, но команда DB подставила сама себя, проведя матч в закрытой атмосфере и дав пищу многочисленным слухам. Хотя не исключено, что это просто маркетинговый ход.
Мнения сильнейших шахматистов по поводу игры компьютера единодушны. DB играет на уровне среднего гроссмейстера, не более того. Считает, конечно, хорошо, но позиционно слабовата. В том, что она когда-либо дорастет до чемпионского уровня, многие сомневаются.
Лет пять назад сила игры шахматных программ напрямую зависела от глубины расчета. Увеличился расчет на один полуход (п/х, ход белых или черных) - программа усилилась на один разряд. Однако когда программы стали играть на гроссмейстерском уровне, то оказалось, что сама “гроссмейстерская зона” делится на множество рубежей. Темпы перехода количества (скорость анализа позиций) в качество игры существенно замедлились. За прошедший год быстродействие DB выросло в два раза, но это не дало существенного увеличения глубины перебора. Как считала программа в предыдущем матче на 12 п/х, так считает и сегодня. Для увеличения глубины расчета на один п/х необходимо повысить быстродействие компьютера в число раз, равное квадратному корню из среднего числа ходов в позиции, т. е. примерно в 5 - 7. Однако это справедливо для сильно упорядоченного дерева, а для реальной игры более подходит оценка Ботвинника, считавшего, что точнее брать корень кубический из числа ходов в квадрате. Получается, что для расчета на 13 п/х необходимо ускорить работу компьютера как минимум в десять раз. Неясно, достижим ли этот рубеж вообще. Команда DB последнее время работает преимущественно над увеличением объема дебютной справочной (заложены уже терабайты информации), добавляет базы данных по типовым окончаниям, совершенствует позиционную оценку. Но это чисто техническая работа - ничего принципиально нового команда DB предложить не смогла.
Поэтому перспективы DB выглядят не очень радужными. При более серьезном отношении к матчу Каспаров наверняка победит машину. Может быть, появятся оригинальные шахматные программы, способные эффективно работать на тысячах процессоров (хотя для этого требуются десятки лет теоретических исследований), может быть, будут реализованы более интеллектуальные алгоритмы наподобие разрабатывавшегося Ботвинником, но слабо изменившаяся с прошлого года игра DB показывает бесперспективность метода простого перебора для достижения чемпионского уровня игры. Ведь человек анализирует позиции в 200 млн. раз медленнее компьютера!
Поэтому в серьезном официальном матче между Человеком и Компьютером у последнего шансов пока очень мало. А решая, за кого болеть в следующем матче (он, учитывая характер Каспарова, обязательно состоится), не забудем надпись на одном из зарубежных Web-узлов: “Deep Blue (USA) - Kasparov (Russia)”.
Сергей Бобровский
К Сергею Бобровскому можно обратиться по адресу: softart@postman.ru.
