Компьютерные программы, как конец спортивных шахмат
Хорошо известно, что для компьютера написаны сильные шахматные программы. Пять лет назад Deep Blue обыграла в матче чемпиона мира Гарри Каспарова. Гораздо менее известно, что в силу гроссмейстера играют совсем небольшие программы, которые помещаются на гибкую трех с половиной дюймовую дискету. Более того, всем кто знаком с проблемой, очевидно, что благодаря компьютерам в ближайшие годы придет конец спортивным шахматам.
Долгое время казалось, что именно шахматы - символ высокого человеческого мышления. Пионерами кибернетики Клодом Шенноном, Аланом Тьюрингом, Джоном Маккарти программирование шахмат было выделено в приоритетную область искусственного интеллекта.
Сегодня мы будем говорить о крушении великого шахматного мифа, и о том, какая игра может занять вакантное место шахмат.
Мои собеседники - генеральный директор компании Disco http://www.disco.ru/russian/ Михаил Донской и Александр Битман, математик-программист и мастер спорта по шахматам. Они, одни из авторов знаменитой советской "Каиссы" - первого чемпиона мира среди шахматных компьютерных программ.
Рассказывает Михаил Донской:
Михаил Донской:
Компьютерные шахматы начались с Клода Шенона, который в 1948 году обозначил общую схему, как компьютер мог бы играть в шахматы. И эта схема оказалась настолько удачной, что и по сей день, грубо говоря, нет программы, которая бы играла по другой схеме.
Александр Костинский:
Клод Шенон - создатель теории информации.
Михаил Донской:
Создатель теории информации и человек, делавший историю во многих областях. Первые шахматные программы появились в конце пятидесятых, сначала они были игрушечными. Играли на доске 6х6. Программы, играющие в нормальные шахматы, появились где-то в 1965 году. Первый международный матч шахматных программ был в 67 году, когда программа Института теоретической и экспериментальной физики (группа под руководством Александра Кронрода: Владимир Арлазаров, Георгий Адельсон-Вельский, Александр Битман, Анатолий Усков, Александр Животовский сделали первую программу, предтечу Каиссы) играла с программой Стэнфордского университета, созданной под руководством Джона Маккарти. Кстати, при проведении этого матча возникла проблема:
Александр Костинский:
Джон Маккартни тоже крупный кибернетик?
Михаил Донской:
Да, это автор LISP (язык программирования - А.К.). Это человек, который с Аланом Тьюрингом придумал термин искусственный интеллект. В качестве забавной черты. Можете себе представить на секундочку, что институт делал тогда атомную бомбу. И вот когда из этого института передавали в Америку по телеграфу шахматные ходы, то КГБ вообще-то стоял на ушах. В конце 60-х все шахматные программы делались в крупных физических центрах, и это не удивительно. Все мощные компьютеры стояли там.
Александр Костинский:
Вы говорите об Институте теоретической и экспериментальной физики под руководством Алиханяна?
Михаил Донской:
Алиханова. Было два брата. Один Алиханов, другой Алиханян. Потом история приобрела политическую окраску, когда Адельсон-Вельский и Кронрод подписали письмо в защиту Есенина-Вольпина, и их выгнали из этого института. Адельсона и Арлазарова взяли на работу в ИПУ (Институт проблем управления АН СССР), куда пришел и я, и в ИПУ мы сделали то, что журналист "Комсомольской правды" Хенкин назвал Каиссой. Мы-то работали без названия, без плановой темы, подпольно.
Александр Костинский:
Наверное, все-таки в рамках каких-то научных программ, или просто из интереса к теме?
Михаил Донской:
Нет, это был просто интерес. Рабочее название программы, КВО, придумала Марианна Розенфельд. КВО значит - программа, которая всех обыгрывает. Мне были интересны две вещи. Хакерское программирование в кодах, чтобы программа быстро перебирала позиции и делала ходы. Саша Битман делал всю шахматную начинку, оценочную функцию, дебютную, справочную часть. А потом мой интерес сместился в сторону математики. Мы ввели понятие подобия деревьев. Ввели довольно тяжелую геометрию на шахматных деревьях и достигли очень интересных результатов, что и сказалось потом. В 1974 году Каисса стала первым чемпионом мира среди шахматных программ. И немного в сторону. Удивительная вещь была только у нас. Половина кода Каиссы была программа, которая докладывала, как машина перебирает глубокие варианты. Во время матча с читателями "Комсомольской правды" в 1972 году, который Каисса закончила с довольно почетным счетом 1,5:0,5 очка, наша работа заключалась в том, чтобы читать каждую неделю огромные листинги переборных вариантов, и надо было быть идиотом, чтобы не заметить, что важно отсекать не плохие, а повторяющиеся ходы. И это было нашей философией, приведшей к революции. А потом это подхватили другие, так как алгоритм мы опубликовали. В 74 году вышла книга на русском языке, в 78 она была переведена Springer-Verlag. Наши алгоритмы стали общественным достоянием. И в 80-м году, играя в Австрии на чемпионате мира, мы поняли, что все наши идеи уже знают, все их у себя реализовали:
Александр Битман
Шайба была нами вброшена, техника у них была более мощной. Им и карты в руки. И дальше все пошло по нарастающей.
Михаил Донской:
В качестве примера. Нам дали месяц, спасибо советской власти, на то, чтобы подготовиться к чемпионату мира в Канаде. Мы месяц проработали на крупном вычислительном центре в Канаде - Canada System Group. И там за месяц мы провели больше экспериментов, попробовали больше вариантов алгоритмов, чем за предыдущие шесть месяцев в Москве. Все-таки это экспериментальная математика. Надо придумать алгоритм, надо его попробовать, надо получить обратную связь. Цикл экспериментов, то, что физикам хорошо понятно, для нас тоже играл большую роль. Я подчеркиваю, не так важно, на каком компьютере играешь в турнире. Очень важно, на каком компьютере проводишь эксперименты. Турнир это - выступление на защите диссертации, но диссертацию еще нужно придумать, написать, доказать все теоремы. Вот эта, экспериментальная часть работы была просто непосильна на тех компьютерах, которые мы имели, и пришлось остановить работу по совершенствованию Каиссы.
Александр Костинский:
Какого успеха добились компьютерные программы в последние двадцать лет?
Михаил Донской:
Людей, которые реально продвигают эту науку, не так много. Один из них - Ганс Берлинер очень яркая личность, профессор университета Карнеги-Меллон в Питсбурге. Он собрал очень мощную группу аспирантов, которые сделали феноменальные алгоритмы, направленные не как наши, на отсечение перебора, а, наоборот, на надежность перебора. На то, в каких позициях надо углубляться дальше, чтобы убедиться, что оценка правильная. Они внесли огромный теоретический вклад и потом, когда защитили диссертации, ушли от Берлинера в IBM и сделали программу Deep Blue. И все сегодняшние разговоры дилетантов о грубом переборе, о том, что решает мощность машины, это просто от незнания. Потому что вклад именно в теорию шахматного программирования этой группы очень велик. Они тоже открыли новое направление. Если мы ушли от общих потуг сокращать плохие ходы к сокращению похожих, одинаковых, то они - от сокращения перебора к углублению перебора в нужных местах. Они сменили парадигму, и это не замедлило сказаться на силе программы. Поэтому мне всегда очень обидно, когда говорят - мощная машина, мощная машина: Мощная машина теперь есть в доступе почти у каждого. Попробуйте сделать такую программу. А о спортивном качестве матча Каспаров - Deep Blue я, мягко говоря, небольшого мнения. Я думаю, что одна сторона играла этот матч как коммерческий, а другая как рекламный. Я не думаю, что результат этого матча означает победу искусственного разума над естественным.
Александр Костинский:
Такое впечатление, что компьютеры уже превратили на каком-то уровне шахматы в крестики-нолики.
Михаил Донской:
Все гораздо хуже. В 98 году в Линаресе как всегда был крупный турнир, а рядом с ним было много побочных. Главным из побочных турниров была "швейцарка" (проведение турнира по швейцарской системе - А.К.), куда допускались все игроки, заплатившие крупный денежный взнос. В основном в турнире играли гроссмейстеры, надеясь выиграть крупный приз. Приз выиграл человек, который до этого был известен силой игры на уровне второго или может быть первого разряда. Всех изумляло, почему в Линаресе в июне, жара, человек все время ходит в галстуке, костюме, очках. Он обыгрывал всех гроссмейстеров.
Александр Костинский:
В 98 году?
Михаил Донской:
В 98 году. За все пять партий, которые он сыграл, он сделал одну ошибку, а именно: вместо слон h2 сыграл слон g2, что злые языки относят к тому, что он не расслышал ход, который был ему передан в наушники в очках. Он не пришел на награждение, потому что к этому моменту все его ходы были повторены программой. Нашли программу, которая повторяла все эти ходы. И это практически является доказательством того, что ему помогала шахматная программа. Играя решающую партию, вместо того, чтобы в один ход взять ферзя, он наоборот пожертвовал ладью для форсированного мата в пять ходов. Это типичная компьютерная игра. Люди так принципиально не играют. А вдруг, просчитался?
Александр Костинский:
Взял ферзя и спокоен.
Михаил Донской:
Взял ферзя и как-нибудь довезу. А здесь, наоборот, имея такую возможность, он пожертвовал ладью. Это событие в Линаресе вызвало широкий резонанс, потому что стало ясно, что если не блокировать помощь компьютера, то относительно слабый игрок может выиграть денежный приз у довольно сильных игроков. Тут же в начале 99 года был проведен матч Ананд-Карпов, в правила которого была включена легальная помощь компьютера.
Александр Костинский:
То есть, можно было прямо во время партии пользоваться компьютером?
Михаил Донской:
Компьютер просто стоял на турнирном столике рядом с шахматной доской. После этого матча Карпов получил психологический удар, после которого не поднялся. Я видел видеозапись матча. Если Ананд все время смотрел в компьютер, то Карпов все время смотрел на доску. Карпов играл сам, а Ананд с помощью компьютера. Ананд выиграл этот матч 5:1, без разговоров. Просто без разговоров. Возник вопрос: можно ли вообще блокировать компьютер? Ясно стало, что помощь компьютера даже на уровне ведущих гроссмейстеров - это 700-800 очков Эло.
Александр Костинский:
Это решающее преимущество.
Михаил Донской:
Абсолютно решающее.
Александр Битман
Полная страховка от грубых ошибок, что очень важно. Надежная тактика на 5-7 ходов. Компьютер не допускает тактических ошибок.
Михаил Донской:
Человек может сосредоточиться на стратегии, а компьютер подчистит все огрехи. О зевках нет речи. Если есть какой-то тонкий тактический вариант, он безусловно будет найден.
Тогда, насколько я знаю, Каспаров провел во Франкфурте совещание с экспертами по безопасности, можно ли блокировать игроков от помощи компьютера. Выяснилось, что можно, если играть в закрытом помещении в голом виде. Если шахматы выживут, как спорт, то они с необходимостью придут к такой организации соревнований.
Александр Битман
В закрытом, то есть, в специальном бункере, изолированном от внешних воздействий.
Александр Костинский:
Шахматисты должны играть за очень мелкой металлической сеткой, чтобы до них не доходили электромагнитные волны.
Михаил Донской:
И голые, чтобы нельзя было спрятать компьютер на себе.
Александр Битман
Но, опять же, как в технике много раз бывало, если сейчас проблема безопасности решена, то мы не можем гарантировать, что через пять лет ее не преодолеют.
Михаил Донской:
А потом, чисто по-человечески много занимаясь шахматами, я не понимаю, почему умение двигать фигурки по квадратному полю означает, что человек уже умнее всех. Я видел не у одного человека на свете такую странную веру. Шахматы и шахматы, игра есть игра. Я всю жизнь играл в бридж - гораздо более сложную игру, но я не думал, что от того, что я умею кидать карты на стол, я уже умнее всех на свете. Ну и бог с ними с шахматами. Мало ли видов спорта. Посмотрите на олимпийские игры. Одни виды спорта уходят, другие приходят. Какие-то скелетоны, лыжные спринты приходят, гонки патрулей уходят. Нормальный принцип. Шахматы пришли и ушли. Ничего страшного.
Александр Костинский:
Уход шахмат, это как уход футбола. Шахматы - часть культуры.
Михаил Донской:
Не хочу вдаваться в политику, но, конечно, в тюремной камере шахматная доска - очень полезная вещь, это правда. Но давайте понимать, что тот взгляд, который мы имели весь этот век - это взгляд наружу из очень узкого пространства.
Александр Битман
Я хотел бы прокомментировать эту длинную Мишину тираду. Со многим я согласен, но у меня на что-то есть и свои взгляды. То, что сказал Миша про достижения создателей Deep Blue, конечно, справедливо. Но Deep Blue - суперпрограмма, которая изначально предназначалась для борьбы с чемпионом мира. Тем не менее, прогресс в электронной технике позволил создать очень сильные программы, на уровне гроссмейстеров. То, что Ботвинник называл brute force - грубой силой. Эти программы берут за счет глубины расчета и за счет феноменальной скорости. Это, тем не менее, факт, поскольку, кроме Deep Blue, существует масса совсем миниатюрных шахматных программ. Программа Geneus-3 помещается буквально на обычной дискете в 3,5 дюйма. Ее можно подарить, передать, и она запросто бьет гроссмейстеров, по крайней мере, в относительно быстрых партиях, 5, 10, 15 минут на партию. Причем, чем меньше времени, тем меньше шансов у человека. Гроссмейстер проигрывает этой программе на домашнем компьютере, и в ней нет каких-то суперсложных алгоритмов, даже судя по ее объему.
Тем самым шахматы оказались не точно такими как крестики-нолики, но в некоторой степени подобными им. Достаточно было компьютерной технике развиться до определенного уровня, и компьютер пересчитал человека.
Изначально задача программирования шахмат ставилась как задача искусственного интеллекта. Цель работы над такого рода программами - понять механизмы мышления человека. Тем не менее, очень быстро все свелось к спортивному моменту. Программисты поняли, что вместо того, чтобы решать эти глобальные трудные проблемы, проще заняться чисто техническими вопросами убыстрения программ и так далее. И они в реальных партиях оказывались победителями, и это было мерилом и критерием их успеха. Тем не менее, некоторый прогресс в этой области был достигнут. То, что Миша кратко упомянул, в частности его работа по исследованию подобных деревьев, которые возникают в процессе перебора. Получилось огромное ускорение путем отбрасывания повторных, мусорных вариантов. И это привело к несколько печальной констатации факта, что компьютер, конечно, не постиг шахматы абсолютно, не играет в каждой позиции как Бог, но играет так, что этой силы достаточно, чтобы побеждать даже чемпионов мира.
То, что я сказал, что компьютер не играет как Бог, не совсем верно. Оказалось, что иногда он может играть как Бог. Первые программы такого рода тоже были сделаны под руководством Арлазарова в том же коллективе, который создавал Каиссу. А именно, были получены абсолютно точные оценки всех ходов и вариантов, которые возникают в малофигурных эндшпилях. В той стадии партии, когда фигур остается мало, буквально 4, 5, 6 фигур. Известным математиком Александром Львовичем Брудно, много сделавшим в области шахматного программирования, был разработан специальный алгоритм так называемого ранжирования. Оказалась, что все позиции, возникающие в малофигурных эндшпилях, можно разложить по полочкам и снабдить биркой, что эта позиция выиграна за 45 ходов, эта позиция ничейная и так далее. Компьютер, единожды проведя такой расчет, дальше держит в своей памяти на дисках всю эту базу данных и играет абсолютно оптимально. Мы сделали несколько эндшпилей: ладья с пешкой против ладьи и ферзь с единственной фиксированной пешкой g7 против ферзя. Это была сложная работа благодаря тому, что компьютеры еще не были на том уровне развития, как сейчас. И помню, как машина считала буквально сутками, но зато, единожды посчитав, эти результаты оставались и могли работать на все времена.
Эти результаты понравились многим шахматистам, поскольку это - элемент чистого знания. Их можно было использовать и в шахматных программах, и сами по себе. На этом пути были сделаны многие интересные чисто шахматные открытия.
Михаил Донской:
Машина просто изменила шахматные правила, например, правило пятидесяти ходов (ранее, если в партии в течение 50 ходов не была побита ни одна фигура и не сдвинулась с места ни одна пешка, то фиксировалась ничья - А.К.) было отменено вследствие этих эндшпильных программ.
Александр Битман
Это в частности. Но машина сделала то, чего человек не мог сделать в принципе. Потому что это исключительно сложные вещи. Это то, что может Бог. Так и есть. На сайте Кена Томпсона http://cm.bell-labs.com/who/ken/ (создателя UNIX) есть рубрика - "Игра в шахматы с Богом". Он выложил на сайте образцы своих отранжированных баз, и каждый может туда войти и буквально ход за ходом разыграть эти позиции в абсолютно оптимальном режиме. Он уже все шестифигурные позиции без пешки отранжировал. Причем перебрал самые экзотические сочетания. На этом пути были достигнуты интересные результаты. Оказалось, что эндшпиль ладья с конем против двух коней выигран, и на сайте приводится вариант партии-монстра мат в 262 хода.
Александр Костинский:
И это точно посчитано.
Александр Битман
Это абсолютно точно. Интерес в чем состоит? Эндшпиль ладья против коня является теоретически ничейным, там есть отдельные выигранные позиции, как исключение. В целом он ничейный. Получается, если мы добавили по коню каждой стороне, то позиция стала выигранной.
Все шахматы устроены таким образом. Их можно отранжировать, поднимаясь снизу вверх.
Михаил Донской:
Каждые 20 лет по одной фигуре добавлять. Когда-нибудь дойдут до 32-х.
Александр Битман
Шахматы, как игра, предопределена как ничейная. Это означает, что при абсолютно правильной игре, с точки зрения Бога, любая партия при правильной игре должна закончиться вничью. А то, что у шахматистов бывают победы и поражения всего лишь означает, что в процессе игры были допущены ошибки. Причем достаточно грубые. Потому что еще один минус шахмат - ничейная зона у них довольно большая. Скажем, один партнер может играть явно лучше, в течение партии выиграть пешку, а, тем не менее, большая ничейная зона позволяет противнику остаться в зоне безопасности. Ничья.
Михаил Донской:
Точно - крестики-нолики.
Александр Битман
Капабланка когда-то предсказывал ничейную смерть шахмат, отчасти это верно и все это видят. В турнирах очень высокого уровня, если люди не рискуют и пытаются играть аккуратно, правильно, грамотно, без приключений, более половины партий заканчиваются вничью.
Но, конечно, для любителей, которые играют на лавочке, простор для творчества. Они могут резвиться, играть, зевать, радоваться, испытывать эмоции и так далее. Общая картина тем не менее такая.
Михаил Донской:
А я хотел бы вернуться к философии. Заодно упомянем фамилию, которую в этом контексте нельзя не упомянуть. Вообще в искусственном интеллекте с самого начала были два течения. Если есть сложная задача, которую мы признаем задачей искусственного интеллекта (вначале это были шахматы, распознавание образов, сейчас это распознавание речи или еще что-то), то есть два философских подхода. Один - решить задачу и черт с ним как, а второй подход - попытаться понять, как ее делает человек и повторить алгоритм решения человека. Можно сказать, компьютероморфный и антропоморфный подходы. Мы, конечно, шли по первому пути. Главное, чтобы программа играла в шахматы. А как, черт с ним. Яркий образец другого подхода к шахматам - это Михаил Моисеевич Ботвинник.
Александр Костинский:
Чемпион мира.
Михаил Донской:
Чемпион мира. И он поставил перед собой задачу отрефлексировать свой собственный шахматный опыт, понять, как играет шахматный мастер, и воткнуть в программу этот алгоритм шахматного мастера. Я добавлю в скобках, как он его понимал. Ботвинник был не единственным на этом пути. Но, что характерно для меня (я не знаю относиться к этому, с позитивной или с негативной точки зрения), что ни одного успеха, ни только в шахматах, но и в искусственном интеллекте вообще, на антропоморфном пути не было достигнуто. Рано или поздно любая проблема, по спортивному ли признаку или по чисто прагматическому, сворачивала на то, что задачу нужно решать. Искусственный интеллект, не искусственный интеллект, ну его к черту. Надо решить задачу. Само-то понятие искусственного интеллекта в каком-то смысле "пиарное", а не содержательное. Тем не менее, очень интересно, что попытки повторять как делает человек ни разу не привели к успеху. И очень обидно, что Ботвинник так и не закончил свою программу. Она у него уже делала отдельные ходы, но по настоящему шахматная программа проверяется в турнирах, и этой проверки не было.
Александр Костинский:
Программа Ботвинника называлась "Пионер"?
Михаил Донской:
Да это была программа "Пионер".
Александр Битман
Некоторые считают, что была создана такая программа "Пионер", которая была в этой области чуть ли не пионером. Тем не менее, хорошо известно, что эта программа не сыграла ни одной шахматной партии, хотя, насколько я помню, разрабатывалась больше 20 лет. Так как она не могла продемонстрировать каких-то успехов, при всем уважении к Михаилу Моисеевичу, он, конечно, человек великий, но мне казалось, что эти годы он потратил как-то не совсем плодотворно. Жалко, что он преждевременно ушел из шахмат и занялся областью, которая была далека от него. Он был специалистом в электротехнике. В какой-то момент он попал в ловушку. Ему показалось, что он может передать свои знания машине, как он их чувствует.
Александр Костинский:
Считается, что Гете называл шахматы пробным камнем интеллекта. Он ошибся. Большие шахматы уходят, и место интеллектуальной спортивной игры освобождается. Многие специалисты говорят о том, что начинается новая эпоха. Эпоха еще более древней игры - го. В Корее ее называют "бадук", в Китае - "вейчи". Любопытно, что в отличие от шахмат, попытки написать сильную компьютерную программу для Го пока не увенчались успехом. Об этом говорит Александр Битман
Александр Битман
Возраст игры го оценивается примерно в 4-5 тысяч лет. Считается, что она зародилась в Китае. Потом в средние века она просочилась в Японию, и там ее стали культивировать в буддийских монастырях. Го считалось лучшим способом для воспитания интеллектуальных способностей детей. Научиться играть в го очень легко, легче, чем в шахматы, но трудно научиться играть хорошо. В го есть игроки, которые могут дать другому игроку крупную фору вроде ферзя в шахматах и выиграть, а ему более сильный игрок может дать в свою очередь такую же фору, и тоже выиграет. В шахматах такое представить невозможно. В Японии есть свои шахматы, которые называются "сёги". Существует такая пословица. В го играют боги, в сёги - герои, в рендзю - простые смертные. Игра в го - многоплановая, многостадийная как будто играются несколько шахматных партий. Борьба полыхает по всей доске, происходят жуткие катаклизмы. Когда человек приходит в себя после закончившейся партии он, не знает на какой планете он находится и в каком времени. Настолько все захватывающе и эмоционально.
Александр Костинский:
Что происходит с программированием Го?
Александр Битман
История программирования Го столь же длинная, как и у шахмат. Помню, когда Миша Донской ездил в свое время на конгрессы по искусственному интеллекту, он привозил оттуда толстый талмуд, в котором наряду с шахматным программированием обсуждались и проблемы го-программ. Нельзя сказать, что этим совсем не занимались. Просто создание качественной программы для го требует больших усилий, начиная с гораздо большей размерности и кончая тем, что там трудно формализовать чисто специфические понятия го, которые формулируются в терминах узнавания, похожести. Кроме того, в го - более тонкая, изощренная логика, которая подчас не раскладывается на рациональные элементы. Го ближе к искусству. Недаром в Японии эту игру называют: го - искусство гармонии. Поэтому, когда шахматы в некотором смысле исчерпали себя в качестве модели искусственного интеллекта, то вполне не грех научным организациям и коллективам программистов более плотно заняться проблемой сильной го-программы. Потому что те программы, которые существуют сейчас, их силу можно оценить примерно так, сравнивая с шахматами. Они играют в силу 4-5 шахматного разряда. Работы по созданию программ для игры в Го возможно дадут новый импульс теории создания искусственного интеллекта.
По оценкам некоторых американских специалистов не ранее, чем через 20-30 лет будут созданы программы, которые смогут реально служить спарринг-партнером человеку и в этом направлении будет какой-то реальный прогресс.
Александр Костинский:
Начать знакомство с го можно в Интернете на сайте go.hobby.ru.
Все ссылки в тексте программ ведут на страницы лиц и организаций, не связанных с радио "Свобода"; редакция не несет ответственности за содержание этих страниц.