10.02.2014

Первая победа компьютера над чемпионом мира по шахматам

10 февраля 1996 года, 18 лет назад, как принято считать, завершилась история противостояния человека и компьютера как соперников за шахматной доской. В этот день компьютер Deep Blue (на фото внизу), созданный компанией IBM, впервые в истории одержал победу в шахматной партии над сильнейшим шахматистом мира Гарри Каспаровым.

Матч с призовым фондом $500 тыс. проводился в Филадельфии (США) и был организован международной Ассоциацией вычислительной техники (является одной из самых авторитетных организаций в мире; ежегодно она присуждает Премию Тьюринга и Премию имени Грейс Мюллей Хоппер за выдающийся вклад в информатику и вычислительную технику). Общая победа со счетом 4:2 в этом матче из 6 партий досталась Каспарову.

Матч-реванш с увеличенным более чем вдвое призовым фондом ($1,1 млн), организованный в следующем году, завершился уже победой компьютера со счетом 3,5:2,5. Не обошлось, как водится, без многочисленных обвинений со стороны Каспарова в адрес IBM, требований еще одного матч-реванша на условиях гроссмейстера, однако историческое значение этих турниров налицо: шахматы навсегда оказались вычеркнуты из перечня задач, в решении которых первенство человеческого интеллекта над машинным предполагалось само собой разумеющимся.

Гарри Каспаров еще раз садился играть с компьютером. Это было в 2003-м, а соперником его была программа Deep Junior. На этот раз матч был организован Международной шахматной федерацией FIDE, которая никогда до этого даже в теории не рассматривала возможности конкуренции компьютера и человека за шахматной доской. Хотя Каспаров к этому времени уступил мировую шахматную корону Владимиру Крамнику, тем не менее, с точки зрения FIDE, он являлся лучшим шахматистом за всю историю официальных игр.

Перед началом серии игр профессор Джонатан Шеффер, международный эксперт в области искусственного интеллекта и один из судей этого матча, говорил: «На сегодня Deep Junior является чемпионом среди шахматных программ и удерживает это звание третий год подряд. Она получила множество призов, а играет удивительно красиво. Нет сомнений, Каспаров стремится доказать, что 1997 год для компьютера оказался не более чем счастливой случайностью, а Deep Junior хочет убедить в обратном. В общем, есть все основания считать это классическим противостоянием». Матч завершился вничью. На заключительной пресс-конференции Шеффер выразил общее настроение собравшихся так: «Через сто лет идея, что люди могут по-прежнему побеждать компьютеры, будет казаться странной. Сегодня мы переживаем момент, когда человечество уступает компьютеру одну из своих самых заветных и, казалось бы, однозначно человеческих способностей».

После матчей Каспарова многие руководители FIDE неоднократно высказывали мысли о том, что проводить смешанные встречи (человек против компьютерной программы) по многим причинам нецелесообразно. Поддерживая эту позицию, Гарри Каспаров пояснял: «Да, компьютер не знает, что такое выигрыш или проигрыш. А как это для меня?.. Как я буду относиться к игре после бессонной ночи, после грубых ошибок в игре? Это все эмоции. Они ложатся огромным бременем на человека-игрока, и самое неприятное, что вы ведь понимаете: ваш оппонент не подвержен ни усталости, ни любым другим эмоциям».

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

Михаил Ботвинник. Интуиция vs. Brute force?

Умение играть в шахматы издавна было отнесено к стандартным тестовым задачам, демонстрирующим возможности искусственного интеллекта справляться с заданием не с позиций «грубой силы», что в данном контексте понимается как применение тотального перебора возможных ходов, а с помощью... «чего-то такого», как выразился однажды один из пионеров в области разработки шахматных программ Михаил Ботвинник. В свое время ему удалось «пробить» официальное финансирование работ над проектом «искусственного шахматного мастера» - программного комплекса «ПИОНЕР», который создавался под его руководством во Всесоюзном НИИ электроэнергетики. О возможностях применения базовых принципов «ПИОНЕРА» для решения задач оптимизации управления в народном хозяйстве Ботвинник неоднократно докладывал в президиум АН СССР.

Базовую идею, на которой основывал свою разработку экс-чемпион мира, он сам сформулировал в одном из своих интервью 1975 года: «Уже не один десяток лет я работаю над проблемой распознавания мышления шахматного мастера: как он находит ход без полного перебора? И сейчас можно утверждать, что этот метод в основном раскрыт... Три основных этапа создания программы: машина должна уметь находить траекторию передвижения фигуры, потом она должна «научиться» формировать зону игры, зону местного боя на шахматной доске и уметь формировать совокупность этих зон. Первая часть работы выполнена давно. Сейчас закончена подпрограмма формирования зоны. В ближайшие дни начнется ее отладка. Если она пройдет успешно, будет полная уверенность, что удастся и третий этап и машина начнет играть».

Увы. Проект «ПИОНЕР» остался незавершенным. Ботвинник работал над ним с 1958 по 1995 год - и за это время сумел построить алгоритмическую модель шахматной игры, основанную на поиске «дерева вариантов» и последовательного достижения «неточных целей», в качестве которых выступал выигрыш материала. Саму идею о том, что в игре гроссмейстера главное - борьба за материал, Ботвинник почерпнул в книгах Хосе Рауля Капабланки (на фото ниже).

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

Как спасти СССР от превентивного ядерного удара?

В 1978 году два немецких университета (в Дортмунде и Мангейме) и американская Control Data пригласили Михаила Ботвинника совместно довести проект «ПИОНЕР» до работоспособного состояния. Ехать за рубеж ему не разрешили, мотивируя тем, что вывоз за границу столь передового программного обеспечения может нанести ущерб государству. 15 декабря 1978 года Ботвинник пишет письмо секретарю ЦК КПСС М. В. Зимянину: «Сейчас программа "Пионер" написана и введена в ЭВМ. Для отладки программы и эксперимента необходима ЭВМ с быстродействием порядка 10-15 миллионов операций в секунду и объемом оперативной памяти около тысячи килобайт. Таких ЭВМ в СССР нет. <...> Нельзя не выразить недоумение по поводу того, что шахматная программа "Каисса" (без экспертизы ГКНТ) была вывезена за рубеж в 1977 году (и до сих пор там пребывает) - при этом никто не выказал опасений, что это может нанести ущерб СССР ("Каисса" была чемпионом мира в 1974 г. Как и нынешний чемпион "Чесс", она основана на полном переборе). Чем же это объясняется? Видимо тем, что "Каисса" обитает в одном из институтов ГКНТ, а "Пионер" - всего лишь во ВНИИЭ Минэнерго».

Внятного ответа «из верхов» Ботвинник так и не получил. Мы же, благодаря рассекреченному протоколу совещания, состоявшегося в феврале 1979 года в отделе науки и учебных заведений ЦК КПСС, сегодня имеем возможность ознакомиться с аргументацией, перечеркнувшей надежды экс-чемпиона мира на скорое завершение работ над своей программой, буквально нафаршированной обладавшими мировой новизной идеями. Итак...

«В. С. Семенихин, ученый в области автоматики и механики, академик, считает, что в СССР используются сильные алгоритмы для принятия стратегических решений. Он против вывоза "ПИОНЕРА", так как американцы убедятся в отставании советской вычислительной техники, и это спровоцирует превентивный термоядерный удар по СССР со стороны США.

М. М. Ботвинник спрашивает Семенихина, почему в 1977 году, когда "Каиссу" вывозили на отладку в Канаду на "IBM 370/168", все обошлось благополучно. И почему покупка производительной американской программы "Сайбр-176" для Гидрометслужбы не раскрыла отставания СССР и не вызвала превентивного удара...

В. Бурцев, ученый в области электронно-вычислительной техники, членкор АН СССР, согласен с Семенихиным. Считает, что методы игры в шахматы давно объяснены в шахматной литературе и Ботвинник ничего существенного не сделал...

А. Кириллин указал, что американцы запретили передачу шахматных программ в СССР, поэтому сотрудничество с ними и, т. о., вывоз "Пионера" исключается.

Замзав отделом науки и учебных заведений С. Г. Щербаков прекратил дискуссию. В составленной справке для руководства КПСС Щербаков написал, что Ботвинник согласился со всеми сделанными ему предложениями».

Каисса

Упомянутая только что «Каисса» - первая советская шахматная программа - была создана в Институте теоретической и экспериментальной физики (ИТЭФ). Начало работ над проектом, который тогда еще не имел никакого звучного названия, относится к 1963 году. В 1967-м прототип будущей «Каиссы» принял участие в первом международном матче шахматных программ, где играл против программы Стэнфордского университета (Калифорния, США). По правилам этого матча ходы передавались по телеграфу раз в неделю! Программы играли целый год и завершили матч из 4 партий со счетом 3:1 в пользу детища ИТЭФ.

В 1972 году по инициативе газеты «Комсомольская правда» был организован заочный шахматный матч программы с читателями. Под это мероприятие шахматный обозреватель газеты А. Хенкин и придумал название программы - «Каисса». За неделю делался один ход (из присланных читателями вариантов выбирался один - тот, который был в наибольшем числе писем). Матч, продлившийся 10 месяцев, «Каисса» проиграла со счетом 1,5:0,5.

Через два года «Каиссу» пригласили принять участие в ежегодном чемпионате Северной Америки среди шахматных программ, который организовывала АСМ (мы уже упоминали ее - Ассоциация вычислительной техники). В матче, проходившем в одном из отелей Стокгольма, приняли участие 16 компьютерных программ из стран Европы, США и Канады.

Как рассказывал один из авторов программы Михаил Донской (на фото он за столиком справа), наиболее сильным впечатлением оказался невероятный шум в зале: участники соревнования старались докричаться по телефону до операторов вычислительных центров, где стояли ЭВМ, участвующие в турнире. Вот фрагмент его воспоминаний: «Партии не откладывались, а игрались до конца (одна заняла не только вечер, но и всю ночь). Я был единственным участником, претендовавшим на второе место в чемпионате, все же остальные претендовали только на первое. В результате все обернулось наоборот, именно "Каисса" заняла первое место. Мне была вручена для "Каиссы" золотая (в смысле из чистого золота, 110 г.) медаль чемпиона мира среди шахматных программ, сданная потом на хранение в ИПУ.

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

Вместо заключения

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

Юрий Романов

Источники:

1. computerra.ru