Каспаров и компьютер

Ход игры

  • Белые: Deep Blue
  • Чёрные: Гарри Каспаров
  • Дебют: Защита Каро — Канн, система Петросяна-Смыслова (вариация Стейница)
a b c d e f g h
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h

Позиция после 5.Кg5

a b c d e f g h
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h

Позиция после 7…h6?

a b c d e f g h
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h

Позиция после 11.Сf4

a b c d e f g h
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h

Последний ход 19.c4, после которого Каспаров сдаётся

1. e4 c6

Для Каспарова применение защиты Каро — Канн было несвойственным. Впоследствии в матчах против других компьютеров он выбирал либо классический ход 1…e5, либо Сицилианскую защиту 1…c5 (последняя была характерна для его игры с обычными шахматистами).

2. d4 d5 3. Кc3 dxe4 4. Кxe4 Кd7 5. Кg5 (см. диаграмму)

Негласное правило шахматных дебютов «не трогай фигуру дважды в дебюте» нарушено, однако давление на поле f7 усиливается.

5… Кgf6

Каспаров избегает ошибки 5…h6?, которая привела бы к мату: 6.Кe6! fxe6?? 7.Фh5+ g6 8.Фxg6#, или большому преимуществу белых: 6…Фb6 7.Кxf8 Кxf8 8.c3 Сf5 9.Кge2 Кf6 10.a4 К8d7 11.Кg3 Сg6 12.Сd3

6. Сd3 e6 7. К1f3 h6? (см. диаграмму)

Каспаров, один из самых сильных игроков в шахматной истории, допустил грубую ошибку, сдвинув пешку на h6 слишком рано. Обычно он делал это на 8-м ходу (вариант 7…Сd6 8.Фe2 h6 9.Кe4 Кxe4 10.Фxe4 встретился в его партиях против Гаты Камского в 1994 и Владимира Епишина в 1995). Опасность последовавшей жертвы белых Каспаров должен был прекрасно понимать. Объективно ход Каспарова не худший, однако вести оборону чёрным становится трудно. Позднее Васик Райлих показал, что решающая ошибка, возможно, была сделана на 11-м ходу.

8. Кxe6!

Подобные жертвы ранее встречались неоднократно и приносили белым перевес.

8… Фe7

Каспаров не побил коня сразу, а «связал» его ходом ферзя, чтобы освободить королю поле d8. Однако многие эксперты высказали мнение, что чёрные должны были брать коня немедленно. Хотя королю пришлось бы встать на e7 (8…fxe6 9. Сg6+ Крe7), у чёрного ферзя оставалось более удобное поле c7.

9. 0-0

Рокировка лишает чёрных возможности побить коня ферзём: 9…Фxe6?? 10.Лe1 ведёт к потере ферзя из-за связки. Теперь Каспаров вынужден принять жертву белых, чтобы не остаться без пешки.

9… fxe6 10. Сg6+ Крd8 11. Сf4 (см. диаграмму)

Если бы слон чёрных уже был выведен на d6 (см. примечание к 7-му ходу), жертва коня была бы невозможна. Теперь же белые в обмен на принесённого в жертву коня занимают слоном выгодную позицию и усиливают давление на позицию чёрных. Каспаров потерял возможность рокировки, ферзь мешает развитию чернопольного слона, а преимущество в коня использовать невозможно.

11… b5?

Игра перешла из дебюта в миттельшпиль, и теперь компьютер должен действовать самостоятельно, без дебютных баз. Каспаров пытается освободить пространство на ферзёвом фланге и предотвратить ход 12. c4. Однако аргентинский гроссмейстер Аарон Шварцман считает этот ход ошибкой. Аналогичное мнение высказали Яссер Сейраван и Васик Райлих: ослабление пешечной структуры на ферзевом фланге увеличивает преимущество белым, давая им возможность вскрытия новых вертикалей.

12. a4 Сb7

Типичное в подобных ситуациях 12…b4 (чтобы оставить вертикаль закрытой), по мнению Реймонда Кина, было обязательным ходом, однако и в этом случае 13. c4 могло привести к разгрому чёрных.

13. Лe1 Кd5 14. Сg3 Крc8 15. axb5 cxb5 16. Фd3 Сc6? 17. Сf5

Белые усиливают давление на пешку на e6 и планируют подключить к атаке ладьи. Лишняя фигура чёрных совсем не чувствуется, и Каспаров вынужден отдать ферзя на ладью и слона.

17… exf5 18. Лxe7 Сxe7 19. c4

Чёрным грозит разгром: ферзь займёт поле c4 или f5, и после хода ладьи на e1 позиция белых становится выигранной. Например: 19…bxc4 20.Фxc4 Кb4 (20…Крb7 21.Фa6#) 21.Лe1 Крd8 22.Лxe7 Крxe7 23.Фxb4+. Каспаров сдался. В его карьере это было одно из самых быстрых поражений.

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

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

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

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

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

В Deep Thought оценочная функция стала сложнее и учитывала больше позиционных факторов. Для некоторых факторов впервые использовалась автоматическая настройка. Аппаратная оценочная функция была переведена на 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 пунктов по шкале USCF. В соревнованиях Deep Thought играл в различных конфигурациях — количество шахматных процессоров варьировалось от двух до шести, а общая скорость перебора от 700 тыс. до 2 млн шахматных позиций в секунду. В качестве головной машины, к которой подключались внешние шахматные процессоры, использовались рабочие станции университета Карнеги-Меллон. В частности, в играх с Каспаровым использовались три рабочие станции Sun-4, соединённые по сети, и 6 шахматных процессоров.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первый матч

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

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

Каспаров — Deep Blue
6-я партия, 1996 год

a b c d e f g h
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h

Заключительная позиция 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 некоторые заинтересовавшие его ходы из недавнего матча.

Второй матч

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

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

Каспаров — Deep Blue
5-я партия, 1997 год

a b c d e f g h
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h

47… Крb6! Король Deep Blue идёт в лагерь противника, чтобы помочь своим фигурам организовать вечный шах королю Каспарова, пока тот не успел провести пешку g5 в ферзи.

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

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

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

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

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

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

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

После матча

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

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

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

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

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

> См. также

  • Компьютерные шахматы
  • Искусственный интеллект
  • Fritz (программа)
  • IBM Watson
  • AlphaGo

Эта машина умнее меня В каких играх человек уже никогда не победит компьютер

Фото: Pendzich / REX / Vida Press

В конце 2015-го — начале 2016-го компьютерные программы оказались способнее людей в игре го и в скорости собирания кубика Рубика. По просьбе «Медузы» журналист Владислав Воронин рассказывает, в каких играх человек уже никогда не сможет выиграть у компьютера.

Отелло (реверси)

Игра «Отелло» стала популярной в начале 1970-х. Правила простые: два игрока свободно размещают фишки разных цветов на площадке из 64 клеток (8×8). Задача — закрыть с двух сторон сплошные ряды соперника (горизонтальные, вертикальные и диагональные) своими фишками. Как только ряд оказывается заблокированным, все фишки в нем переходят оппоненту и меняют цвет. Выигрывает тот, кто к концу партии занял большую территорию.

Во время первого поединка человека с компьютером в 1980 году уверенно победил действующий чемпион мира по «Отелло» Хироси Иноуе: из шести партий он уступил программе Moor только одну (5:1). Всего через девять лет компьютеры взяли реванш в командном турнире в Лондоне. Пять программ обыграли пятерых профессиональных игроков (трое из них входили в мировой топ-4) со скромным счетом 12:8.

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

Уже в 1997 году стало ясно, что даже сильнейшим игрокам бессмысленно тягаться с компьютерами: чемпион мира Такеси Мураками проиграл программе Logistello с унизительным счетом 0:6.

Нарды

Компьютеры научились играть в нарды еще в 1970-е, но этого бы точно не произошло без влияния шахмат. Для разработчиков суперкомпьютеров, способных бороться с шахматными гроссмейстерами, эта игра оказалась небольшим промежуточным этапом. Например, чемпион мира по шахматам по переписке Ханс Берлинер с помощью нард придумал алгоритм оценки ситуации на игровой доске (компьютер анализирует текущую ситуацию на доске и просматривает древо игры на несколько ходов вперед, чтобы выбрать оптимальное продолжение); позже это помогло ему написать шахматную программу HiTech, которая в 1988-м одолела гроссмейстера Арнольда Денкера.

Для нард Берлинер разработал программу BKG 9.8, в 1979-м она обыграла действующего чемпиона мира Луиджи Виллу со счетом 7:1. Победа была крайне неожиданной, даже создатель компьютера признал, что человек действовал талантливее и стабильнее — система восемь раз выбирала не лучшие варианты продолжения игры. Но, во-первых, BKG 9.8 несколько раз повезло с числами, выпавшими на костях, во-вторых, программа очень успешно делала выбор в пользу удвоения ставок (каждая игра начинается со ставкой в одно очко; при желании во время игры каждый участник может удвоить ставку — второй должен либо принять это удвоение, либо сдаться и проиграть одно очко, не рискуя двумя).

Позже метод Берлинера (анализ ситуации на игровом поле) был усовершенствован. Работа швейцарской программы Snowy и финской Jellyfish основывается на искусственных нейронных сетях, которые запоминают ходы лучших игроков и применяют их в случае необходимости. Правда, после поражения Виллы никто из чемпионов не решился сразиться с компьютером.

Шахматы

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

Тот матч из шести партий Каспаров выиграл (3 победы, 2 ничьи, 1 поражение), он был уверен, что эпоха машин наступит нескоро: «Хотя я и видел некоторые признаки интеллекта, у компьютера все-таки была неэффективная и негибкая манера игры. Это позволяет мне думать, что у меня есть несколько лет в запасе», — писал он в журнале Time.

Матч-реванш между Гарри Каспаровым и Deep Blue. 5 мая 1997 года Фото: Najlah Feanny / Corbis SABA / Vida Press

Однако Каспаров ошибался. Разработчики быстро увеличили мощность системы — теперь она могла оценивать 200 миллионов позиций в секунду. В 1997-м Deep Blue победил в матче-реванше (2 победы, 3 ничьих, 1 поражение) и стал первым компьютером, одолевшим сильнейшего шахматиста мира. Отыграться Каспаров уже не смог, потому что IBM отказалась от дальнейших соревнований, посчитав миссию выполненной.

С тех пор компьютеры становились только сильнее. Рейтинг Эло (метод расчета относительной силы игроков в играх для двоих) самой сильной шахматной программы Stockfish составляет 3341 пункт. Показатели людей существенно ниже: у Каспарова на пике был 2851 пункт, у нынешнего лидера Магнуса Карлсена — 2850,6.

Го

Древняя игра, придуманная в Китае более двух с половиной тысяч лет назад, казалась для компьютеров непреодолимым препятствием, пока за разработку не взялся Google. На первый взгляд, в го нет ничего особенно сложного: два игрока по очереди расставляют на площадке (19×19) белые и черные камни; побеждает тот, кто захватит большую территорию. В конце считаются камни, составляющие границу одного цвета, и свободные клетки за «стеной», куда можно беспрепятственно добавить другие камни. У кого сумма больше, тот выиграл.

Сложности в разнообразии вариантов. Например, в шахматах у каждого игрока есть 20 способов начать партию, а после первого хода на доске может быть 400 различных позиций. В го — 361 вариант стартового хода и 129 960 возможных комбинаций только после первого раунда. Это невероятно затрудняет работу систем искусственного интеллекта, которые опираются на стандартные алгоритмы и базы данных.

Поэтому система AlphaGo, разработанная под контролем Google, сочетает два подхода — так называемое «дерево вариантов» и глубокие нейронные сети, которые натренированы 30 миллионами ходов самых сильных игроков в го и тысячами партий внутри системы. Сейчас AlphaGo в 57% случаев предсказывает действия человека.

При тестировании AlphaGo уничтожила самые прогрессивные компьютерные го-системы, выиграв у них 499 партий из 500. Потом наступило время встретиться с человеком, и в октябре 2015-го AlphaGo разгромила трехкратного чемпиона Европы Фань Хуэя со счетом 5:0. Это первая победа компьютера над профессиональным игроком в го — до этого ни одна программа не поднималась выше любительского уровня.

Чтобы окончательно покорить го, AlphaGo осталось доказать силу в матче с сильнейшим игроком мира Ли Седолем. Встреча назначена на март.

Кубик Рубика

В январе изобретатели Джей Флэтлэнд и Пол Роуз представили робота, который может собрать кубик Рубика всего за секунду. Это космический уровень даже для компьютерных систем — раньше ни одной из них не удавалось справиться с головоломкой менее чем за 3,253 секунды. Лучший результат Флэтлэнда и Роуза — 1,047 секунды.

Машина работает с немного модифицированным кубиком Рубика: на каждой грани в центре высверлены дырки, за которые держатся шаговые электродвигатели. При помощи четырех веб-камер компьютер оценивает текущую раскладку кубика и определяет оптимальную последовательность действий на основе алгоритма Коцембы (решение не более чем за 20 ходов).

Лучший результат среди людей в ноябре 2015-го показал 14-летний американец Лукас Эттер — 4,904 секунды.

Шашки

Сказочная история американца Мариона Тинсли, который проиграл соперникам в чекерс (разновидность шашек) всего пять партий, завершилась встречей с компьютером. Он был чемпионом мира на протяжении всей карьеры с 1955-го по 1991-й; с перерывом на 17 лет, когда пропускал все турниры.

Систему для игры в чекерс разработали в канадском Альбертском университете. Машина весила около 540 килограмм и за минуту могла обработать 12 миллионов различных игровых вариантов. В 1992 году Chinook заслужила встречу с Тинсли, но матч остался за человеком: 4 поражения программы, 2 победы, 33 ничьих. Интересно, что один раз программа проиграла только из-за технических проблем — компьютер просто завис, и разработчикам пришлось сдаться.

Уже в 1994-м состоялся матч-реванш. В первых шести партиях были сплошные ничьи, а потом Тинсли снялся из-за проблем со здоровьем — победа автоматически досталась компьютеру. Через неделю у чемпиона нашли рак; менее чем через год он умер.

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

Скрэббл

Скрэббл, известный в России как «Эрудит», был покорен компьютером с первой попытки. В 2006 году в Торонто робот Quackle обыграл чемпиона мира Дэвида Бойса.

В двух стартовых партиях программа уступила — чтобы обыграть человека, потребовалось брать три следующие, используя необычные слова вроде «кади» (судья, рассматривающий дела на основе шариата) и «анурия» (отсутствие поступления мочи в мочевой пузырь).

Прежде чем сразиться с компьютером, Бойс в специальном турнире обошел 100 других желающих. Уступив роботу, он с расстройством отметил, что «по-прежнему лучше быть человеком, чем компьютером».

Quackle доступна в интернете, так что вы тоже можете посоревноваться.

Телевикторина

Компания IBM, которая разработала суперкомпьютер, обыгравший Гарри Каспарова, в 2011 году снова удивила человечество — на этот раз в интеллектуальной телевикторине Jeopardy! (российский аналог — «Своя игра»). Робот Watson не оставил никаких шансов двум рекордсменам: Кену Дженнингсу, который в свое время не проигрывал на протяжении 74 выпусков передачи, и Брэду Руттеру, получившему самый большой выигрыш в истории шоу — 4,45 миллиона долларов.

Кен Дженнингс, робот Watson и Брэд Руттер на телевикторине Jeopardy! 13 января 2011 года Фото: Seth Wenig / AP / Scanpix

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

По сумме двух игр Watson правильными ответами заработал 77 тысяч долларов, более чем втрое обогнав каждого соперника — 24 тысячи у Дженнингса и 21 600 — у Руттера.

В результате IBM выиграла миллион долларов. Все деньги были направлены на благотворительность.

Владислав Воронин

Москва

  • 367
  • 185
  • 3
  • Напишите нам

Deep Blue против Каспарова: двадцать лет революции больших данных

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

Это была не обычная игра в шахматы. Нередко побежденный игрок может обвинить своего оппонента в нечестной игре, но в этом случае проигравшим был тогдашний чемпион мира по шахматам Гарри Каспаров. Победитель был еще более необычным: суперкомпьютер IBM Deep Blue.

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

Эхом припоминая уловки шахматных автоматов 18 и 19 веков, Каспаров заявил, что компьютером управлял настоящий гроссмейстер. Он и его сторонники полагали, что игра Deep Blue была слишком человечной, чтобы принадлежать машине. Между тем для многих убежденных в производительности компьютера стало очевидно, что искусственный интеллект достиг той стадии, когда может превзойти человечество — по крайней мере в игре, которая долгое время считалась слишком сложной для машины.

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

Тот матч стал сигналом к социальному сдвигу, который набирает скорость по сей день. Глубокая обработка данных, на которую опирался Deep Blue, сегодня присутствует почти во всех уголках нашей жизни — от финансовых систем, которые доминируют в экономике, до сервисов онлайн-знакомств, которые пытаются найти нам идеального партнера. То, что начиналось как студенческий проект, помогло вступить в эпоху больших данных (big data).

Ошибка человека

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

Но следующий ход Deep Blue удивил Каспарова. Каспаров назвал его «человекоподобным». Джон Нанн, английский гроссмейстер, описал его как «удивительный» и «выдающийся». Этот ход разбил план Каспарова и перевернул его стратегию. Он так переволновался, что не смог вернуться в игру и отдал ее. Что еще хуже, он так и не оправился, сыграл вничью три следующих игры и допустил роковую ошибку, которая привела к поражению в последней игре.

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

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

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

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

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

Ему удалось выиграть игру, и ко второму раунду ошибка была исправлена. Но чемпион мира был, похоже, настолько потрясен превосходным интеллектом машины, что не смог восстановить свое самообладание и заиграл слишком осторожно. Он даже упустил шанс выйти из тактики открытой линии, когда Deep Blue допустил «ужасную ошибку».

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

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

Шахматная гонка

Когда Фэн-Сюн Сю прибыл в США с Тайваня в 1982 году, он и представить не мог, что станет частью интенсивного соперничества между двумя командами, которые почти десять лет пытались создать лучший шахматный компьютер в мире. Сю прибыл в Университет Карнеги — Меллон в Пенсильвании, чтобы изучать дизайн интегральных схем, из которых делают микрочипы, но также давно интересовался компьютерными шахматами. На него обратили внимание разработчики Hitech, компьютера, который в 1988 году первым обыграл гроссмейстера, и попросили помочь с разработкой аппаратного обеспечения.

Вскоре Сю рассорился с командой Hitech, когда увидел архитектурный косяк в предложенном ими дизайне. Вместе с другими аспирантами он начал разработку собственного компьютера ChipTest, опираясь на архитектуру шахматной машины Bell Laboratory. Собственная технология ChipTest использовала «очень широкомасштабную интеграцию», чтобы сочетать тысячи транзисторов на одном чипе и позволить компьютеры находить 500 000 шахматных ходов ежесекундно.

Хотя команда Hitech стартовала раньше, Сю и его коллеги скоро догнали ее с преемником ChipTest. Deep Thought — названный в честь компьютера из книги Дугласа Адамса «Автостопом по галактике» — объединил два специализированных процессора Сю и научился анализировать 720 000 ходов в секунду. В 1989 году он выиграл World Computer Chess Championship, не проиграв ни одной игры.

Но в том же году Deep Thought проиграл Гарри Каспарову, действующему чемпиону мира по шахматам. Чтобы обыграть лучшего гроссмейстера мира, Сю и его команда должны были зайти намного дальше. Но теперь у них была поддержка компьютерного гиганта IBM.

Шахматные компьютеры работают, присоединяя числовое значение к положению каждой фигуры на доске, используя формулу «функции оценки». Эти значения затем можно обрабатывать и перебирать в поисках лучшего хода. Первые шахматные компьютеры, такие как Belle и Hitech, использовали несколько кастомных чипов для выполнения оценочных функций и затем комбинировали результаты.

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

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

К февралю 1996 года команда IBM снова вызвала Каспарова на бой, в этот раз с Deep Blue. Хотя машина впервые обыграла чемпиона мира в обычном временном режиме, общий матч Deep Blue проиграл со счетом 4:2. Его 100 000 000 ходов в секунду было недостаточно, чтобы обыграть способность человека к выработке стратегии.

Чтобы увеличить число ходов, команда начала модернизацию машины, исследуя, как бы оптимизировать большое количество процессоров, работающих параллельно. Наконец, образовалась машина с 30 процессорами, которые, что очень важно, контролировали 480 кастомных интегральных схем, созданных специально для игры в шахматы. Этот кастомный дизайн позволил команде мощно оптимизировать параллельные вычисления между чипами. Результатом стала новая версия Deep Blue (Deeper Blue), способная находить 200 000 000 ходов в секунду. На каждую возможную стратегию машина могла просчитывать до 40 ходов наперед.

Параллельная революция

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

Сегодня сложные компьютерные модели используются для поддержки банковских финансовых систем, разработки более совершенных автомобилей и самолетов и для испытания новых лекарств. Системы, которые штудируют большие массивы данных (часто их называют большими данными, или big data), ищут значимые паттерны в планировании общественных услуг, транспорте и здравоохранении и позволяют компаниям ориентировать рекламу на определенные группы людей.

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

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

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

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

Между тем мир шахматных игровых автоматов существенно развился со времен победы Deep Blue. Несмотря на свой опыт работы с Deep Blue, в 2003 году Каспаров согласился сразиться с двумя самыми известными шахматными машинами — Deep Fritz и Deep Junior. Оба раза ему удалось избежать поражения, хотя он все так же делал ошибки, которые приводили к ничьей. И все же обе машины обыграли своих оппонентов в 2004 и 2005 годах.

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

Несмотря на этот прорыв, у нас все еще нет шахматных машин, которые напоминали бы человеческий интеллект в процессе игры — да им и не нужно. Люди совершают ошибки, потому что они эмоциональны и боятся за свою репутацию. Машины, с другой стороны, беспощадно используют логические расчеты в процессе игры. Однажды у нас могут появиться компьютеры, которые действительно думают по-человечески, но история последних 20 лет привела к развитию систем, которые точны в высокой степени исключительно потому, что являются машинными.