Deep Blue

Deep Blue — шахматный суперкомпьютер[1][2], разработанный компанией IBM, который 11 мая 1997 года выиграл матч из 6 партий у чемпиона мира по шахматам Гарри Каспарова.

Одна из двух стоек Deep Blue в Музее компьютерной истории

В названии «Deep Blue» (дословно — «тёмно-синий» или, в литературном переводе, «глубокая печаль») сочетается название проекта «Deep Thought» (букв. — «глубокая мысль») и прозвище, которое дали IBМ: «Big Blue» (в русском передаётся как «Голубой гигант»).

История создания

Прямым предшественником Deep Blue была шахматная машина Deep Thought[3], которая, в свою очередь, была создана на основе машины ChipTest[4].

Шахматная машина ChipTest была спроектирована и изготовлена группой аспирантов университета Карнеги-Меллон. У истоков создания машины ChipTest стоял Фэн Сюн Сю, который занимался ею в рамках своего диссертационного проекта на соискание научной степени PhD по информатике. Диссертация была посвящена разработке специализированных шахматных СБИС. Впоследствии эти СБИС использовались в составе аппаратной части шахматных машин ChipTest и Deep Thought. Позднее к проекту присоединились аспиранты Томас Анансараман (программная часть) и Мюррей Кэмпбелл (программная часть, шахматная подготовка). Также заметный вклад в осуществление проектов ChipTest и Deep Thought внесли Андреас Новатчук, Майкл Браун, Питер Янсен и др.

В процессе выбора хода ChipTest в основном использовал типовые методы поиска по шахматному дереву, применявшиеся в большинстве шахматных программ — минимаксный алгоритм поиска с альфа-бета-отсечениями и оценочную функцию, дававшую оценку конечным позициям. Аналогичный принцип работы впоследствии использовали Deep Thought и Deep Blue[1].

Разработка ChipTest началась в 1985 году. Финансирование проекта осуществлялось по линии диссертационных расходов Фэн Сюн Сю. К концу 1986 года создание ChipTest было в основном закончено. В 1987 году ChipTest выигрывает 18-й Северо-Американский чемпионат по шахматам среди компьютерных программ. Незадолго до этого авторы ChipTest начали создание следующей шахматной машины — Deep Thought.

В Deep Thought оценочная функция стала сложнее и учитывала больше позиционных факторов. Для некоторых факторов впервые использовалась автоматическая настройка[5]. Аппаратная оценочная функция была переведена на FPGA. Количество специализированных шахматных процессоров было увеличено сначала до 2-х, а впоследствии и до 24-х (в Deep Thought II). Создание Deep Thought было в основном завершено в 1988 году.

В 1988 году Deep Thought принял участие в шахматном турнире, проходившем в Лонг-Бич (США), где поделил первое-второе место вместе с гроссмейстером Энтони Майлсом. В турнире он опередил нескольких гроссмейстеров, в том числе экс-чемпиона мира Михаила Таля.

В 1989 году Deep Thought выигрывает 6-й Чемпионат мира по шахматам среди компьютерных программ, проводившийся в Эдмонтоне (Канада).

В 1989—90 годах Deep Thought проигрывает двум сильнейшим на тот момент шахматистам в мире, сначала Гарри Каспарову в матче со счётом 0 : 2, а затем Анатолию Карпову 0 : 1. К этому времени рейтинг Deep Thought достиг уровня в 2552 пункта[6] по шкале USCF. В соревнованиях Deep Thought играл в различных конфигурациях — количество шахматных процессоров варьировалось от двух до шести, а общая скорость перебора от 700 тыс. до 2 млн шахматных позиций в секунду[7]. В качестве головной машины, к которой подключались внешние шахматные процессоры, использовались рабочие станции университета Карнеги-Меллон. В частности, в играх с Каспаровым использовались три рабочие станции Sun-4, соединённые по сети, и 6 шахматных процессоров.

В 1989 году корпорацией IBM принято решение начать проект по созданию шахматной машины, для осуществления которого нанимаются разработчики Deep Thought[8]. В течение 1989—90 годов, по мере окончания обучения в университете, Томас Анансараман, Фэн Сюн Сю и Мюррей Кэмпбелл переходят на работу в IBM. Фэн Сюн Сю начинает разработку специализированного шахматного микропроцессора, целиком помещающегося на одном кристалле кремния, который предполагается использовать в качестве основы новой шахматной машины — Deep Blue.

В 1991—92 годах закончено создание машины Deep Thought II, которая представляет собой усиленный вариант Deep Thought, с дополнительными шахматными процессорами. Томас Анансараман покидает проект. Его место занимает сотрудник IBM, Джозеф Хоэн.

В 1995 году разработка шахматного микропроцессора закончена. В сентябре того же года, на основе двух шахматных микропроцессоров, была получена первая работоспособная версия Deep Blue I[9]. Корпорация IBM нанимает гроссмейстера Джоэла Бенджамина для работы над шахматной подготовкой Deep Blue I. В феврале 1996 года, в Филадельфии, Deep Blue I проигрывает матч Гарри Каспарову со счётом 2 : 4.

После матча, в течение 1996 года, Фэн Сюн Сю вносит значительные изменения в конструкцию шахматного микропроцессора. В декабре 1996 года, по заказу IBM, сторонними поставщиками начато изготовление новых шахматных процессоров. В начале 1997 года изготовленные процессоры начинают поступать в IBM. Джозеф Хоэн адаптирует программное обеспечение под новые аппаратные возможности машины. Мюррей Кэмпбелл и Джозеф Хоэн активируют и настраивают новые позиционные факторы оценочной функции. Часть факторов выставляется программой автоматической настройки[10]. Джоэл Бенджамин осуществляет игровое тестирование новой версии Deep Blue (сначала на 24-процессорной, а перед матчем на полной, 480-процессорной версии машины). По его замечаниям Джозеф Хоэн и Мюррей Кэмпбелл производят корректировку коэффициентов позиционных факторов в оценочной функции. За несколько месяцев до начала нового матча группа гроссмейстеров в лице Джоэла Бенджамина и подключившихся впоследствии Ника де Фирмиана, Джона Федоровича и Мигеля Ильескаса начинает подготовку дебютной книги Deep Blue. Незадолго до начала матча производится сборка новой машины — Deep Blue II — на основе нового, более производительного сервера IBM[11]. В мае 1997 года Deep Blue II выигрывает матч у Гарри Каспарова со счётом 3½ : 2½.

Результаты в соревнованиях
№Участник123456 +−=Очки
1Каспаров, Гарри01½½11 3124
2Deep Blue10½½00 1322


№Участник123456 +−=Очки
1Каспаров, Гарри10½½½0 1232½
2Deep Blue01½½½1 2133½

Устройство Deep Blue

Deep Blue II представлял собой суперкомпьютерный кластер RS/6000 SP (от англ. Scalable Powerparallel) компании IBM. Он состоял из двух стоек с размещёнными в них 30 узлами, построенными на базе рабочих станций RS/6000. На каждом узле был установлен процессор P2SC (одномикросхемное исполнение процессора POWER2) и две платы[13] расширения с 8 специализированными шахматными процессорами на каждой плате под шину MCA. Таким образом всего использовалось 480[11] шахматных процессоров и 30 процессоров P2SC. Два узла использовали процессоры P2SC с тактовой частотой 135 МГц, а остальные 28 узлов — процессоры P2SC с тактовой частотой 120 МГц. На каждом узле были установлены 1 ГБ ОЗУ и 4 ГБ дисковой памяти. Узлы обменивались данными между собой по высокоскоростной сети. Один из процессоров P2SC был назначен главным, а остальные — вспомогательными. В свою очередь, каждый специализированный шахматный процессор работал на частоте 24 МГц[14] и перебирал от 2 до 2,5 миллионов шахматных позиций в секунду, что примерно в сто раз больше, чем у аналогичных по частоте универсальных процессоров[2]. Шахматные процессоры были изготовлены по 0,6-микронной КМОП-технологии и содержали около 1,5 миллиона транзисторов каждый[15]. Программное обеспечение Deep Blue II было написано на языке С и работало под управлением операционной системы AIX 4.2[1][16].

Структурно Deep Blue состоял из двух частей:

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

Такая структура позволяла, с одной стороны, использовать сложную и относительно просто изменяемую шахматную программу на универсальном компьютере, а с другой стороны, использовать высокую скорость специализированных шахматных микропроцессоров. Для увеличения гибкости аппаратной части машины в конструкцию шахматных микропроцессоров Deep Blue II была опционально добавлена поддержка возможности подключения внешних FPGA, корректирующих аппаратный поиск и оценку. Теоретически, это позволило бы приблизить аппаратный поиск по сложности и гибкости к программному поиску. Из-за нехватки времени к началу матча 1997 года эта возможность не была реализована и потому никогда не использовалась[17].

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

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

В процессе поиска по дереву шахматных ходов Deep Blue использовал стандартные методы организации перебора, известные в то время: NegaScout (одна из модификаций альфа-бета-отсечений), форсированный вариант, итеративное углубление, таблицы перестановок и др.[18][19] Использовался также разработанный авторами метод продления единственных ходов (Singular extensions).

Deep Blue II использовал две дебютные книги. Одна из них, подготовленная вручную, использовалась в течение первых нескольких ходов в партии, до начала расчётов. После того, как позиция на доске выходила за рамки первой книги и компьютер начинал расчёт вариантов, подключалась вторая (расширенная) книга, созданная на основе базы данных игр гроссмейстеров. Эта книга, на основании результатов использования рассматриваемой позиции в ранее состоявшихся партиях, вводила некоторую поправку к расчётной оценке позиции. В некоторых случаях, если у одного из возможных ходов поправка была положительной и намного превышала таковую у других ходов, Deep Blue мог сделать ход сразу, без дополнительного перебора[20].

Общая скорость системы варьировалась в широких пределах, в зависимости от свойств рассматриваемых позиций. В ходе матча 1997 года общая средняя скорость системы составляла 126 миллионов позиций в секунду. Максимальная установившаяся скорость, наблюдавшаяся в матче, составляла 330 миллионов позиций в секунду[1]. Стоимость Deep Blue составила около 10 млн долл США[21].

Матчи против Каспарова

Первый матч

Первый матч Deep Blue c Каспаровым состоялся в Филадельфии (США) с 10 по 17 февраля 1996 года. Призовой фонд матча составлял 500 000 долларов, из которых 400 000 получал победитель, а 100 000 проигравший. Матч проводился в Конференц-центре Филадельфии и состоял из 6 партий. Организацией матча занималась АСМ.

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

Каспаров — Deep Blue
6-я партия, 1996 год
abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Заключительная позиция 6-й партии. После хода Каспарова 43.Лb4 Deep Blue сдался.

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

Вторую партию матча выиграл Каспаров.

После ничьих в третьей и четвёртой партиях в матче сохранялся равный счёт, 2 : 2.

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

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

Окончательный счёт матча — 4 : 2 в пользу Каспарова.

После матча Гарри Каспаров посетил исследовательский центр IBM, где вместе с разработчиками проанализировал на Deep Blue некоторые заинтересовавшие его ходы из недавнего матча[22][23].

Второй матч

Второй матч проходил в Нью-Йорке с 3 по 11 мая 1997 года и состоял из 6 партий. Призовой фонд матча составлял 1 100 000 долларов, из которых 700 000 получал победитель, а 400 000 проигравший. Партии проводились на 35-м этаже небоскрёба Equitable Building. В игровом помещении была выделена игровая зона, зона отдыха Каспарова и несколько мест для зрителей, среди которых могли присутствовать только официальные лица матча и приглашённые гости (представители IBM, команды Каспарова, АСМ и др.). Deep Blue перевезли из лаборатории IBM и разместили на том же этаже, в отдельном помещении.

Функции оператора машины поочередно выполняли разработчики Deep Blue, сменяя друг друга после каждой партии. Судьёй матча была назначена Кэрол Джареки, ранее уже судившая матч Каспарова с Анандом в 1995 году. Апелляционный комитет матча состоял из Кена Томпсона, Майкла Вэльво и представителя ACM Монти Ньюборна. Кен Томпсон осуществлял контроль над работой Deep Blue из операционного зала машины[24]. На 49-м этаже Equitable Building был оборудован пресс-центр. Впоследствии, из-за малой вместимости, он был перенесён в другое помещение, на 50-м этаже. На одном из подземных этажей здания размещался зрительный зал на 480 мест.

Каспаров — Deep Blue
5-я партия, 1997 год
abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
47... Крb6! Король Deep Blue идёт в лагерь противника, чтобы помочь своим фигурам организовать вечный шах королю Каспарова, пока тот не успел провести пешку g5 в ферзи[25].

Первая партия матча завершилась победой Каспарова.

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

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

На пресс-конференции после третьей партии Каспаров выступил с резкой критикой корпорации IBM. Он заявил, что не понимает принцип выбора машиной некоторых ходов во второй партии, высказал сомнение в том, что эти ходы могли быть сделаны машиной, и потребовал объяснить, почему машина приняла те или иные решения[27][28][29].

В концовке пятой партии, в казалось бы проигранной для Deep Blue позиции[30], компьютер серией точных ходов инициировал вечный шах, и таким образом была зафиксирована ничья. После партии Каспаров потребовал, чтобы log-файлы Deep Blue из пятой и предыдущих партий были распечатаны, помещены в конверты, опечатаны и переданы на хранение судье матча. IBM удовлетворила эти требования[31][32].

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

Окончательный счёт матча — 3½ : 2½ в пользу Deep Blue.

После матча

После матча Каспаров высказал претензии к корпорации IBM, обвиняя её в создании нездоровой напряжённости вокруг матча, неравных условиях и нечестной игре. Каспаров также потребовал у IBM провести новый матч на определённых им условиях[33][34][35][36].

После матча Каспаров получил распечатки log-файлов для отдельных (запрошенных им) ходов[35][37]. Впоследствии IBM разместила log-файлы Deep Blue на своём сайте в свободном доступе[38].

После матча с Каспаровым Deep Blue больше никогда публично не играл в шахматы в своём полноразмерном варианте[39] (но сыграл несколько выставочных партий в усечённом варианте, в рамках послематчевого турне[40][41]). По состоянию на 2011 год, одна стойка Deep Blue хранится в Музее компьютерной истории в Калифорнии, вторая — в Национальном музее Американской истории в Вашингтоне. Большая часть шахматных плат хранится в исследовательском центре IBM Research[42].

В 2003 году вышел фильм «Game Over: Kasparov and the Machine», посвящённый матчам Каспарова с Deep Blue. В фильме, в целом, поддерживалась точка зрения Каспарова в его споре c IBM[43].

В 2010 году состоялся релиз третьего студийного альбома канадской группы Arcade Fire The Suburbs, двенадцатый трек которого носит название "Deep Blue". В тексте песни есть строчка "Kasparov, Deep Blue, 1996", подчёркивающая, учитывая "литературное" имя компьютера - "глубокая печаль", общий посыл трека - упадок человеческого творчества и потенциала во все более механизированном мире, и сожаление по поводу того, как технологии захватывают наши жизни.

В 2013 году в Манчестере и Нью-Йорке состоялись театральные постановки пьесы Мэтью Чармана «The Machine», посвящённой матчам Каспарова с Deep Blue. В том же году компания Дисней приобрела права на экранизацию пьесы[44].

Поражение Каспарова вдохновило создание игры Аримаа, которая была задумана как более сложная для искусственного интеллекта[45].

См. также

Примечания
  1. Campbell, 2002, p. 60.
  2. Sedatchess
  3. Deep Thought
  4. ChipTest (недоступная ссылка). Дата обращения: 21 октября 2013. Архивировано 5 декабря 2013 года.
  5. Код
  6. Hsu, 1990, p. 6.
  7. Campbell, 2002, p. 82.
  8. Hsu, 2004, pp. 92—95.
  9. Hsu, 2004, p. 157.
  10. Campbell, 2002, p. 76.
  11. Hsu, 2004, p. 214.
  12. WCCC 1995
  13. Фото платы (недоступная ссылка). Дата обращения: 22 октября 2013. Архивировано 23 октября 2013 года.
  14. Newborn, 2003, p. 121.
  15. Hsu, 1999, pp. 75—76.
  16. IBM Research | Deep Blue | Overview
  17. Campbell, 2002, p. 64.
  18. Алгоритмы
  19. Алгоритмы
  20. Campbell, 2002, pp. 76—78.
  21. Каспаров, 2018, с. 8.
  22. Hsu, 2004, p. 180.
  23. Ein Gegner mit Elo 2200 bis 3000 // Соmputerschach und Spiele. — 1996. — № 3. — P. 47—48.
  24. Hsu, 2004, p. 215.
  25. Кряквин. «До и после Houdini»
  26. Макарычев С. Матч Каспаров — «Дип Блю» // Наука и жизнь. — 1997. — № 7. — С. 114.
  27. Newborn, 2003, p. 174.
  28. Hsu, 2004, pp. 240—241.
  29. Benjamin, 2008, pp. 192—193.
  30. 64 — Шахматное обозрение, 1997, с. 10.
  31. 64 — Шахматное обозрение, 1997, с. 11.
  32. Hsu, 2004, p. 252.
  33. Видео с пресс-конференции
  34. Стенограмма пресс-конференции
  35. Шахматы в России, 1997, с. 6—9.
  36. 64 — Шахматное обозрение, 1997, с. 14—15.
  37. Соmputerschach und Spiele, 1997, p. 17.
  38. log-файлы
  39. Hsu, 2004, pp. 265—266.
  40. Все известные партии Deep Blue и Deep Thought
  41. Andy Soltis, GM beats Deep Blue Junior // Selective Search. — 1997. — № 71. — P. 7—8.
  42. Newborn, 2011, p. 4.
  43. Benjamin, 2008, p. 198.
  44. Про матч Каспарова и Deep Blue снимут фильм. Lenta.ru (27 сентября 2013). Дата обращения: 24 ноября 2014.
  45. Syed, Omar; Syed, Aamir. Arimaa – a New Game Designed to be Difficult for Computers (англ.) // International Computer Games Association Journal : journal. — 2003. — Vol. 26. — P. 138—139.

Литература
Книги
Статьи
  • Фэн-Сюн Сюй и др. Шахматная машина — гроссмейстер = A Grandmaster Chess Machine, October 1990, Scientific American, pp. 44—50. // В мире науки. — 1990. — № 12. — С. 6—13.
  • Wie Deep Blue den Zug fand // Соmputerschach und Spiele. — 1997. — № 3. — P. 17. (нем.) — разбор 36-го хода из второй партии матча 1997 года, на основании распечаток отдельных ходов из log-файлов Deep Blue, полученных Каспаровым.
  • Каспаров Г. Война объявлена! // Шахматы в России. — 1997. — № 5. — С. 6—9. (рус.) — интервью с Каспаровым после матча 1997 года, с замечаниями к некоторым ходам Deep Blue
  • Каминский В. В зыбкой тени «темно-синего» шкафа // 64 — Шахматное обозрение. — 1997. — № 5. — С. 5—12. (рус.) — шахматные комментарии с места событий
  • Hamilton S., Garber L. Синергия программного и аппаратного обеспечения Deep Blue // СomputerWeekly. — 1998. — № 5. — С. 34—37, 45. (рус.) — краткое описание Deep Blue
  • Feng-Hsiung Hsu. IBM’s Deep Blue chess grandmaster chips // IEEE Micro. — 1999. — Vol. 19, № 2. — P. 70—81. — doi:10.1109/40.755469. (англ.) — описание физической структуры шахматного процессора
  • Campbell M., Hoane A. J. Jr., Feng-Hsiung Hsu. Deep Blue // Artificial Intelligence. — 2002. — Vol. 134, № 1. — P. 57—83. — doi:10.1016/S0004-3702(01)00129-1. (англ.)

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.