Шахматисты и компьютеры: история соперничества. Часть I
АрхивПлатформаПока что сражение проходит с переменным успехом. То человек окажется сильнее, то машина, а иногда матч заканчивается вничью, при том, что и с той, и с другой стороны выступают самые сильные и видные игроки.
Человек и компьютер - это не только очень неплохой "дуэт", способный решать массу нужных и ненужных задач. Человек и компьютер - это еще и непримиримые соперники.
Сами обратите внимание: все человеческое очень часто противопоставляют всему компьютерному. При этом область, в которой производится сравнение человека и машины, может быть едва ли не любой. Музыка? Пожалуйста: певец либо обладает простым, природным человеческим талантом, либо умеет спеть гамму, а остальную работу с помощью компьютера делает звукорежиссер. Кино? На экране либо живые люди, либо нарисованные, самые что ни на есть компьютерные спецэффекты.
Тест Тьюринга – помните? И помните кучу вытекающих из него попыток программистов "очеловечить" машину? Допустим, конкурс на самого человечного "железного" собеседника. Сидит независимое жюри, общается в чате и пытается понять, кто из собеседников - человек, а кто - машина.
Люди боятся, что компьютер научится общаться, вести себя, думать, как человек, и вообще, с каждым годом будет становиться все человечней и человечней.
Отдельная категория людей - шахматисты - боятся, что компьютер когда-нибудь станет играть в шахматы как человек. Машина уже сейчас играет если не сильнее, то практически на равных с сильными гроссмейстерами даже на не самых мощных домашних ПК. Но до сих пор игра кремниевых "друзей" от человеческой отличается довольно-таки сильно. Человек все же приучен к абстрактной, общей, оценке позиций на доске, в то время как компьютер обычно опирается на точный счет. Именно поэтому, кстати, очень часто в специализированной прессе используется термин "компьютерный ход" - то есть ход, возможно, и сильный, но не соответствующей человеческому понятию о шахматной логике.
Шахматы в сознании даже далеких от них людей - игра, требующая логики, интеллекта, интуиции, умения принимать решения. И когда речь идет о шахматных матчах "человек против компьютера", как правило, в очередной раз поднимается вопрос: "А будет ли компьютер умнее, логичней, интуитивней человека?"
Пока что соперничество проходит с переменным успехом. То человек окажется сильнее, то машина, а иногда матч заканчивается вничью. Правда, из-за того, что Гарри Каспаров совсем недавно принял решение уйти из большого спорта, в скором будущем статистика может подпортиться.
И с той, и с другой стороны, как правило, выступают самые сильные и видные представители. За "команду" людей играют шахматисты из первой десятки-двадцатки мирового рейтинга. Что же касается машин, то производители компьютерного "железа" и шахматного софта экипируют эту сторону по самым высоким стандартам.
Попробуем проследить историю противостояния, отметив самых видных представителей последнего лагеря. О шахматистах написаны многотомниики биографий, тысячи статей - а кто, кроме нас, обобщит вместе самую важную информацию о компьютерах?
Турецкое начало
(Поборол в себе желание дать подзаголовок "Турецкий гамбит" - свят-свят, маленькая радость для журналиста.)
Шахматное противостояние человека и машины началось задолго до появления компьютеров. Конкретнее - в конце 18 века. Венгерский дворянин Вольфганг фон Кемпелен присутствовал на представлении, организованном при императорском дворе. После мероприятия он подошел к тогдашней австровенгерской императрице Марии-Терезе, и заявил, что гостей развлекать при дворе совершенно не умеют, и даже он смог бы придумать что-то, способное уберечь публику от скуки. Императрице, конечно, такие речи не понравились, и она дала фон Кемпелену ровно полгода на поиск нового развлечения для тогдашней знати.
Как раз через полгода в императорской приемной появился "турок" - автомат, представляющий собой механического человека, сидящего за столом. На столе стояла шахматная доска, на доске - фигуры. Как заявлял изобретатель, машина могла играть в шахматы, и весьма неплохо. Турецкое название машина получила из-за восточных одежд, надетых на "робота".
Машина действительно отлично играла. Ей удалось обыграть многих сильных шахматистов того времени, а также некоторых известных исторических деятелей. Известно, что жертвой машины пал даже Наполеон Бонапарт.
Современному человеку очевидно, что изобретатель как-то жульничал. Самая распространенная точка зрения - внутри стола, под доской, сидел человек, который управлял работой "турка". Но никаких прямых доказательств тому не осталось, поэтому загадка жива до сих пор. Вопросу посвящены многочисленные исследования, художественные рассказы - недавно вышла даже целая книга ("The Turk", Tom Standage, ISBN: 0-8027-1391-2. Продается либо в бумажном варианте за $24 через интернет, либо в электронном - за $10 через него же. В России, судя по всему, найти невозможно, тем более в переводе на русский).
Многие до сих пор пытаются строить догадки. Самая популярная точка зрения, поддерживающая интригу, заключается в том, что размеры стола были весьма малы, и уместиться там мог либо карлик, либо ребенок. Причем, этот человек должен был быть весьма одаренным, и тогда возникает другой вопрос: почему шахматный гений не сумел "засветиться" в каких бы то ни было исторических источниках того периода?
В общем, налицо тот самый случай, когда здравый смысл вступает в противоречие с наблюдаемой реальностью. Как бы то ни было, "Турок" считается первым представителем команды машин в длящемся уже, получается, более двух веков противостоянии.
"Дочеловеческая" история
Компьютерные шахматы как таковые появились в 50-х годах прошлого века. Вернее нет, не то чтобы появились - начали появляться. Написать шахматную программу - задача нетривиальная. Можно научить её делать ходы, можно даже научить делать неслучайные ходы. Но вот как научить её понимать игру?
Началось все с того, что в 1945-1947 гг. Алан Тьюринг, упоминавшийся чуть выше, сначала привел игру в шахматы как пример того, что может делать компьютер. Затем он же провел параллель между умом машины и шахматами, и набросал примерный алгоритм шахматной программы. Ну а в 1950 году он же написал первую шахматную программу.
С тех пор началась довольно-таки серьезная работа в этой области. Появлялись научные статьи о шахматах и компьютерах, разрабатывались новые программы. Подробно на этом вряд ли стоит останавливаться - это тема, достойная отдельного разговора. А мы с вами сегодня о противостоянии "человек-машина". Если вдруг есть желание проследить вкратце, что и как происходило до первого человеко-компьютерного матча - см. здесь.
Глубокая мысль Гарри Каспарова
Первым "серьезным" компьютером, который бросил вызов человеку в отдельном матче, стал Deep Thought, созданный в 1989 году. Фенг-Сьюнг Су (Feng-Hsuing Hsu), аспирант одного из американских университетов, занимался подготовкой кандидатской диссертации о шахматном компьютере, играющем в силу реального гроссмейстера.
Фенг-Сьюнг Су
Судьба свела аспиранта с Шелби Лайманом (Shelby Lyman) – известным в шахматной Америке человеком. Последнему в голову и пришла идея свести в поединке самый сильный шахматный компьютер (созданный по случаю диссертации в качестве экспериментального образца) с самым сильным человеком-шахматистом.
Компьютер получил название Deep Thought. Те, кто читали "The hitchhiker’s guide to the galaxy" Дугласа Адамса наверняка знают, что так же назывался местный суперкомпьютер, долгое время думавший над ответом на главный вопрос всего сущего. (Ответ тогда, кстати, звучал так: "42". После его обнаружения компьютер тут же заставили думать, каким же, собственно, является главный вопрос всего сущего?)
Из названия первого настоящего шахматного компьютера и пошло, кстати, это известное в шахматной среде компьютерное слово “deep”, обозначающее мультипроцессорность. Пример из современности: среди многих профессиональных шахматных программ существуют, в частности, следующие четыре: Fritz, Junior, Deep Fritz, Deep Junior. Первые две отличаются от последних двух исключительно тем, что они предназначены для однопроцессорных машин, в отличие от deep-версий, работающих на компьютерах с двумя "камнями" и более. Сами же алгоритмы не отличаются ничем, дело только в распараллеливании вычислений.
Deep Thought работал на трех двупроцессорных системах под управлением рабочей станции Sun и использовал программное обеспечение, написанное другим аспирантом, Томасом Анантараманом (Thomas Anantharaman). Кстати, особо любопытные могут найти по этому адресу составленный Андреасом Новатчиком (Andreas Nowatzyk), одним из членов команды DT, документ, многое рассказывающий о функции оценки ходов.
Компьютер Каспарову проиграл. Матч состоял из двух партий. В первой Гарри Кимович играл черными, и весьма осторожно, пробуя машину "на зуб". Во второй, получив белый цвет и изрядно осмелев, чемпион мира среди живых буквально разгромил соперника. И это при том, что машина анализировала до 2 млн. позиций в секунду, а человек - лишь около трех. Не миллионов, конечно - просто трех позиций.
Не думайте только, что DT был создан эксперимента ради, и поэтому играл соответствующе. Может, Каспарова обыграть он не смог, зато жертвами этого агрегата пали такие известные гроссмейстеры, как Майлз, Ларсен и Бронштейн. Проследовав по этому адресу, можно ознакомиться с 24 партиями известной шахматной машины (учтите, что с 90-ого года тот же софт перебрался на более производительное железо - об этом см. далее).
Мысль номер два
Получивший определенную долю известности в результате нескольких громких побед и матча с Каспаровым, проект Deep Thought перешел под крыло большой и сильной (чуть было не написал "и синей" - Big Blue) IBM. Тут-то и началось самое интересное.
Получив в свое распоряжение суперкомпьютер IBM/6000, команда разработчиков увеличила скорость счета программы более чем в три раза - с 2 до 7 млн. позиций в секунду. Тут же последовали и очередные успехи - победа в чемпионате мира по шахматам среди компьютеров, несколько удачных игр с гроссмейстерами. В том числе и победа в 1993 году над Юдит Полгар, самой сильной шахматисткой - и тогда, и сейчас. Примерно в то же время системе присваивают гораздо более известное современному человеку название Deep Blue. Ну а создатель машины, Фенг Сьюнг-Су, переходит на постоянную работу в IBM.
Синие глубины
На самом деле переводить Deep Blue как "темно-синий" или "глубокая тоска", как это делали многие журналисты, немного неверно. Что такое "deep" применительно к шахматным программам - уже сказано выше. Ну а blue, по всей вероятности, - производное от также упомянутого ранее Big Blue ("голубого гиганта") - неформального "прозвища" IBM.
От Deep Blue, впрочем, на время отвлечемся. Поговорим о тех событиях, которые успели состояться до известных двух матчей с Каспаровым.
* * *
Примерно в это же время компьютер доказал свое превосходство над большинством сильнейших игроков в быстрых шахматах, в блице. Компания Intel в 1994 году провела Intel World Chess Express Challenge. В нем, помимо живых гроссмейстеров, участвовала программа Fritz на весьма неплохом "железе" - рабочей станции Olivetti с процессором Intel Pentium 90 МГц. Зря смеетесь – тогда таких процессоров было всего три штуки на всю Европу.
Обыграв нескольких гроссмейстеров, в том числе, индийского гения Вишванатана Ананда, машина поделила с Каспаровым первое место. Тут же был проведен дополнительный поединок для выявления единоличного победителя, и в нем Каспаров выиграл со счетом 4-1.
У человека, разбирающегося в шахматах, здесь может возникнуть вопрос. Как получается, что лучшие игроки десять лет назад проигрывали весьма среднему по современным меркам компьютеру, а сегодня даже многие мастера (а то и кандидаты - о гроссмейстерах же, вообще, речь не идет) способны обыграть того же Fritz’а на домашнем компьютере в быстрой игре.
Рискну связать это с изобретением впоследствии так называемых "антикомпьютерных шахмат", то есть, игре с прицелом на те позиции и планы, которые компьютер в силу своей специфики адекватно оценить не в состоянии. Вероятно, это тема для отдельной статьи. Впрочем, и по ходу этой я обязательно приведу ярчайший, относительно свежий, пример "антикомпьютерной" партии.
* * *
В 1995 году Каспаров сыграл еще два матча с компьютерами, и оба выиграл со счетом 1,5 на 1 очко. Первый - у Genius’а, второй - у Fritza. Ничего примечательного ни с исторической, ни с компьютерной точки зрения в них не было, поэтому подробно на них останавливаться не будем.
* * *
Перейдем лучше сразу к великому и ужасному Deep Blue. Точную дату его появления на свет затрудняется сообщить даже сама IBM. Цитата с официального сайта: "Проект IBM Deep Blue открылся в 1989 году. С тех пор IBM постоянно добавляла новое железо, программы в различные модификации машины. Нельзя назвать точный год, когда был создан компьютер Deep Blue ".
В конечном итоге, к 1996 году - к первому матчу с Каспаровым - Deep Blue представлял собой суперкомпьютер RS/6000, состоящий из 32 нодов, по 6 процессоров на нод. Система была способна обрабатывать (читай: оценивать) до 100 млн. шахматных позиций в секунду. Работало все это чудо под управлением операционной системы AIX UNIX.
Любопытна реализация алгоритма оценки позиций. Вернее, даже не сколько реализация, сколько сам её процесс. Алгоритм оценки был сначала написан в самом общем виде. Точные же коэффициенты, отвечающие за конкретные, абсолютные показатели (скажем, какова ценность пешки? А если пешка проходная? А если защищенная проходная? А если стоит на поле одного цвета с неприятельским слоном? – и так далее), долго подбирались одним из членов команды Deep Blue - Мюрреем Кэмпбеллом. Тот, по словам очевидцев, буквально обложился шахматной литературой, сборниками комментированных партий и засел за постижение шахматной грамоты. Его рейтинг Эло (используется для оценки силы шахматиста) составлял на тот момент 2150 пунктов (Вот ссылка на его "личное дело" на сайте ФИДЕ. Сейчас рейтинг еще и упал). Интересно, что этого рейтинга не хватает даже для получения звания мастера. Для сравнения: мастера ФИДЕ должны обладать рейтингом от 2300 пунктов, международные мастера - в районе 2400, гроссмейстеры (высший шахматный титул) - около 2500 и выше. Рейтинг Каспарова в то время превышал 2800. Вот и думайте, кто учил компьютер играть против чемпиона мира, и как компьютер смог выиграть.
Говоря о производительности суперкомпьютера, нельзя не отметить и существовавшие в алгоритме недостатки. Так, метод отбора ходов базировался, прежде всего, на старом-добром, дедовском методе "брутфорса". Проще говоря: компьютер тупо (зато быстро!) перебирал все варианты (ну, не совсем все, но все же среди них было множество абсолютно ненужных изначально - таких, которые человек не стал бы даже смотреть), и выбирал из них наилучший.
Лирическое отступление:
Это раньше шахматные компьютеры развивались "вширь" - сейчас разработчики делают основной акцент на оптимизации алгоритма, а не "железа". Главное - научить компьютер сразу отбрасывать "тупиковые" ветви поиска. Задача сложнее, чем может показаться. Конечно, относительно легко понять, какой ход лучше, а какой хуже, если смотреть на ход вперед. А если на двадцать? Представьте себе эффектную комбинацию с жертвой "половины комплекта". На первом ходу отдаем ферзя, на втором, ладью, на третьем " другую и так далее, и так далее, а последним скромным ходом пешкой - ставим мат. И как прикажете это оценивать?
С учетом того, что надо еще научить программу учитывать любые виды перевеса (скажем, что лучше в данном конкретном случае: отдать фигуру за две пешки и перевес в развитии или не отдавать? а за три пешки?), проблема значительно усложняется.
Проиграв первую партию, Каспаров выиграл вторую, затем сделал две ничьих и выиграл последние две партии. Итоговый результат: победа человека со счетом 4-2.
Как отметил победитель после игры, компьютер играл иногда очень сильно, но, в целом, был достаточно негибок, и до уровня чемпиона мира не дотягивал. "Похоже, что у меня есть еще несколько лет", - таковы были слова Каспарова.
Deep Blue возвращается
Нескольких лет в запасе у гроссмейстера не оказалось. Уже через год состоялся матч-реванш, победу в котором со счетом 3,5 на 2,5 одержала машина.
К тому времени в каждом из 32 нодов появилось еще по 2 процессора, а количество обсчитываемых в секунду позиций возросло до 200 миллионов - то есть, увеличилось в два раза. Сравните следующие цифры: за три минуты компьютер просчитывал до 200 млрд. ходов. Для сравнения, та же цифра для живого гроссмейстера - 500 ходов.
Как оказалось, даже при определенных недостатках алгоритма этих мощностей достаточно для победы над чемпионом мира.
Подробнее о ходе матча можно прочитать, например, здесь (на англ. языке).
* * *
Матч имел для истории шахмат, компьютеров и, вообще, человечества огромное значение: машина впервые стала сильнее человека. Многие даже заговорили о "человеческой логике" Deep Blue - произошло это после эффектной жертвы коня в последней партии. Раньше всем казалось, что так просто жертвовать материал за позиционные преимущества способен только человек. Сама команда Deep Blue всякие следы "человеческой логики" начисто отрицала: по их мнению, машина отлично считала, отлично анализировала, но интуиции ей явно не хватало, и мыслить "как живой" Deep Blue не научился. Многое об этом можно прочитать, например, в книге "Behind Deep Blue: Building the Computer that Defeated the World Chess Champion".
Но что-то у людей Deep Blue все же перенял. Что бы вы думали…? Умение "зевать"!
В принципе, шахматные "зевки" условно делятся на две категории. "Зевая" по первому принципу, вы думаете, что у вас чего-то нет, а оно - есть. Скажем, забываете о ладье на краю доски, и соперник её спокойно берет. Согласно второму принципу, вы думаете, что у вас что-то есть. А этого- нет. Речь идет, скажем, о связке фигуры: вы думаете, что конь соперника "связан" слоном и ходить не может. Потом соперник устраняет связку, а вы просто забываете об этом. И тут же "развязанный" конь, например, ставит мат. Или забирает материал.
Deep Blue "зевал" по второму методу. Да еще так "зевал", что мало не покажется! Машине почему-то периодически мерещились ферзи. В конце мая 1997 года в The New York Times появилась статья, в которой рассказывалось о любопытном баге программного обеспечения шахматного монстра. На устранение неполадки потратили две недели.
Это я, скорее, к вопросу о "человечности" программы. Человеку ферзи мерещатся максимум несколько раз в жизни, причем, нерегулярно.
Продолжая разговор о глюках. Фредерик Фридель (известный эксперт в области шахматного ПО, глава Chessbase – создателя Фритца, Джуниора, Шреддера и массы полезного шахматного софта) в одном из выпусков мультимедийного ChessBase Magazine приводит такую позицию и рассказывает:
"Вечером после первой игры мы собрались в отеле и запустили Фритца на ноутбуке. В указанной позиции компьютер пошел ладьей на d1 и на следующем же ходу сдался. Наиболее очевидное продолжение - ход ладьей на f5 - тоже проигрывало, но хотя бы не через ход.
…
В конечном итоге мы пришли к выводу, что Deep Blue видел все возможные продолжения и выбрал самое "приятное" со своей точки зрения продолжение из всех - всех проигрывающих. Человек бы, конечно, попытался запутать игру, создать максимальные сложности для оппонента, попробовать помешать ему реализовать преимущество".
Компьютер же вот так просто взял и проиграл. По сути, сдался в не до конца очевидной для человека позиции и поверг тем самым зрителей в недоумение.
Перенося то же самое на нешахматную обстановку, представьте: садитесь вы с утра в автомобиль, а он не едет и сообщает вам, что сегодня вам никуда ехать не стоит. У вас это вызывает недоумение, а авто анализирует ваше физическое, психологическое и прочее состояния, принимает в учет техническое состояние самого себя, погодные условия и пр. и рассчитывает, что у вас часам к 6 вечера есть 95-процентный шанс попасть в аварию. Примерно то же почувствовал Каспаров, когда увидел на доске, с человеческой точки зрения, худший ход оппонента.
Продолжение рассказа о шахматном противостоянии человека и компьютера читайте завтра.
