Просмотр кода страницы 3.5.7 Прогресс в компьютерных шахматах в конце XX века

<span id="прогресс-в-компьютерных-шахматах-в-конце-xx-века"></span>

Меж тем прогресс в компьютерных шахматах не стоял на месте — в начале 1980-x гг. программы достигли уровня игры профессионалов.

В 1981 г. программа Cray Blitz для суперкомпьютера Cray, созданная Робертом Хайаттом, Гарри Нельсоном и Альбертом Гоуэром, набрала пять из пяти очков в чемпионате штата Миссисипи. В четвёртом туре программа победила бывшего чемпиона штата мастера Джозефа Сентефа, что стало первой в истории победой компьютера над мастером по шахматам в турнирной игре.

Хотя в некоторых источниках Сентеф упоминается как международный мастер, в действительности он имел лишь звание национального мастера<ref><sup>**</sup> Сила игры международного мастера соответствует 2400–2500 пунктов Эло, к 1981 г. звание «международный мастер» было присвоено 897 шахматистам.</ref>. На момент игры с Cray Blitz сила игры Сентефа, по всей видимости, соответствовала 2160–2180 пунктам. Сегодня доктор Сентеф, уважаемый специалист в области медицины, так вспоминает своё поражение: «''Не лучший момент моей жизни. Я несколько раз обыгрывал Cray Blitz, но [в этот раз] в цейтноте допустил ошибку. Мне не нравится быть печально известным — и всего по одной игре''»<ref>Lopez R., Sentef J. (2017). Comments / Marginal Revolution // https://marginalrevolution.com/marginalrevolution/2017/03/new-george-steiner-book.html</ref>.

Семь лет спустя предшественник Deep Blue, шахматный компьютер Deep Thought, одержал первую турнирную победу над международным гроссмейстером<ref><sup>***</sup> Рейтинг Эло свыше 2500, в 1988 г. в мире было 338 международных гроссмейстеров.</ref> — роль жертвы была уготована Бенту Ларсену.

Конец 1980-х — начало 1990-х гг. были ознаменованы ростом интереса к шахматным программам в среде профессиональных шахматистов. Машины наконец-то стали интересными соперниками. Впервые в истории людям удалось взглянуть на древнюю игру совершенно новым взглядом — с позиции интеллекта, существенно отличающегося от человеческого. И хотя в отношении игры машин часто звучали обвинения в «чрезмерном материализме», «отсутствии стратегического мышления», шахматисты не переставали удивляться тактическим способностям электронных игроков и их уникальной способности защищать, казалось бы, безнадёжные позиции.

На первый взгляд казалось, что программы конца 1990-х мало чем отличались от программ 1970–1980-х. Когда я впервые в 1999 г. погрузился в чтение исходных кодов программы Crafty — наследницы Cray Blitz, созданной Робертом Хайаттом, — я узнал в ней по сути всё ту же «Каиссу» — по крайней мере тогда я не увидел в алгоритмах никаких революционных нововведений. Конечно, за два десятилетия программы научились весьма эффективно использовать многопроцессорные машины и увеличившиеся объёмы оперативной памяти, некоторые ранние идеи оформились в виде общепринятых методов, но в целом казалось, что развитие теории шахматного программирования забуксовало.

Разгадка состоит в том, что в 1970-е сообщество разработчиков шахматных программ на волне всеобщего энтузиазма наработало множество продуктивных идей, на долгие годы вперёд обеспечив потомков материалом для дальнейшего развития.

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

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

Одновременно с развитием программ продолжалось совершенствование микропроцессорной техники. Закономерным продуктом симбиоза программных и аппаратных технологий 1990-х стал амбициозный проект компании IBM — шахматный суперкомпьютер Deep Blue.

История Deep Blue началась в 1985 г. с конфликта, возникшего между Хансом Берлинером и строптивым аспирантом по имени Фэнсюн Сюй по прозвищу Си-Би (англ. CB, сокращение от Crazy Bird — сумасшедшая птица)<ref>Lieserson C., Newborn M. (2013). Deep Blue: An Artificial Intelligence Milestone. Springer New York // https://books.google.ru/books?id=rWPgBwAAQBAJ</ref>. Казалось бы, что за пустяк? У кого только не было проблем с Берлинером? Даже президент Кеннеди пострадал от него: в своей знаменитой речи 26 июня 1963 г. он, произнеся по-немецки фразу «Я — берлинец» [Ich bin ein Berliner], якобы вставил в неё ненужный в данном случае артикль ein, тем самым превратив её в заявление «Я — берлинский пончик». Жаль, что это всего лишь городская легенда. А деятельного Ханса Берлинера уж точно никто не назвал бы пончиком. Этот человек сделал для компьютерных шахмат очень много.

Берлинер родился в 1929 г. в Берлине в еврейской семье. После прихода Гитлера к власти семья была вынуждена бежать из страны и переселиться в Вашингтон (Федеральный округ Колумбия, США). Проявивший незаурядный талант к шахматам, Ханс в 20 лет стал чемпионом округа, а спустя три года выиграл в чемпионате штата Нью-Йорк. В 1965 г. Берлинер победил в V Всемирном чемпионате по шахматам по переписке. В 1974 г. Ханс защитил диссертацию по информатике в Университете Карнеги — Меллона под руководством Аллена Ньюэлла (одного из создателей шахматной программы NSS). Диссертация была посвящена шахматному программированию и озаглавлена «Шахматы как решение проблем: разработка тактического анализатора».

Главным шахматным детищем Берлинера была программа HiTech<ref><sup>*</sup> По неведомым причинам в советских научно-популярных изданиях её именовали на славянский манер — «Хитеч».</ref>. Берлинер занимался шахматным программированием с начала 1960-х гг., когда работал в IBM, и, оказавшись в стенах университета, предложил проект по созданию новой продвинутой шахматной программы.

Первая версия программы демонстрировала неплохой уровень игры, однако испытывала трудности в момент перехода игры из одной стадии в другую (например, из миттельшпиля<ref><sup>*</sup> Миттельшпиль (от нем. ''Mittelspiel'' — середина игры) — следующая за дебютом стадия шахматной партии, в которой обычно происходят основные события.</ref> в эндшпиль<ref><sup>**</sup> Эндшпиль (от нем. ''Endspiel'' — «заключительная игра») — заключительная часть шахматной партии, после размена большинства фигур.</ref>). Это привело Берлинера к выводу, что слабость HiTech заключалась в недостаточной гладкости оценочной функции. Например, в миттельшпиле плохо защищённый король в центре доски — существенная слабость позиции, в то время как в эндшпиле централизованный король обычно является преимуществом. Но где проходит граница между миттельшпилем и эндшпилем? Программа, играющая за сторону, король которой хорошо защищён, в отличие от короля противника, будет стараться максимально оттянуть размен фигур, формально определяющий переход в эндшпиль, и тем самым может критически ухудшить свою позицию. Это было похоже на уже упоминавшийся нами «эффект горизонта» (этот термин, кстати говоря, ввёл Берлинер).

Берлинер уже применял идею повышения гладкости оценочной функции при создании программы для другой игры — нардов. Коэффициент ветвления игрового дерева в нардах существенно выше, чем в шахматах: в каждом из его узлов существует порядка восьми сотен альтернатив<ref>Berliner H. J. (1977). Experiences in Evaluation with BKG, a Program That Plays Backgammon / Proceedings of IJCAI, 1977 (1979), pp. 428–433 // http://www.bkgm.com/articles/Berliner/ExperiencesInEvaluationWithBKG/index.html</ref>, причём многие из них равнозначны, так как связаны с различными равновероятными вариантами выпадения игральных костей. При таком обилии вариантов их перебор не может заметно улучшить качество выбора ходов программой, поэтому наличие эффективной оценочной функции является одним из ключевых факторов успеха. Программа для игры в нарды, созданная Берлинером в конце 1970-х, предназначалась для компьютера DEC PDP-10 и получила название BKG. Ранние версии BKG (вплоть до 8.0) играли в целом довольно неплохо, но всё же не могли соперничать с сильнейшими игроками-людьми. В очередной версии Берлинер решил применить новый подход, использующий нечёткую логику для определения фаз игры. Этот подход получил название SNAC (Smoothness, Nonlinearity, and Application Coefficients — «Гладкость, нелинейность и коэффициенты применения»). Использование этого подхода усилило программу в достаточной мере, чтобы Берлинер смог бросить перчатку действующему чемпиону мира по нардам Луиджи Вилле.

[[File:image126.jpeg|600x404px]]

Рис. 72. Ханс Берлинер (на переднем плане) и Карл Эбелинг, разработчики программы HiTech, 1985 г.

В состоявшемся в 1979 г. матче BKG 9.8 выиграла у Виллы со счётом 7 : 1, став первой компьютерной программой, победившей чемпиона мира в какой-либо игре. Впрочем, Берлинер позже утверждал, что победа была в значительной степени обусловлена случаем, поскольку машине больше везло с выпадениями костей. По крайней мере, более поздний анализ показал, что игра Виллы была практически безупречной, в то время как программа в ряде случаев допускала ошибки (которыми Вилле не посчастливилось воспользоваться)<ref>Berliner H. J. (1980). Backgammon Computer Program Beats World Champion / Artificial Intelligence, vol. 14 (1980), pp. 205—220 // http://www.bkgm.com/articles/Berliner/BackgammonProgramBeatsWorldChamp/</ref>.

В середине 1980-х Берлинер пребывал в расцвете своего творческого периода. В конце 1985 г. его программа HiTech заняла первое место на Шестнадцатом Северо-Американском чемпионате по шахматам среди компьютерных программ, в 1986 г. победила со счётом 2 : 0 международного гроссмейстера по шахматам среди женщин Яну Майлс, а двумя годами позже одержала победу в товарищеском матче со счётом 3,5 : 0,5 над 74-летним гроссмейстером Арнольдом Денкером.

Так какие проблемы могли возникнуть у всемирно известного специалиста с простым тайваньским аспирантом?..

В начале 1985 г. профессор Кунг, куратор (faculty advisor) Фэнсюна Сюя, попросил юношу помочь Берлинеру с одной из технических проблем. Обсуждаемое решение не нравилось ни Берлинеру, ни самому Сюю, который после некоторых раздумий пришёл к выводу, что корень проблемы кроется в самом подходе Берлинера. Фэнсюн предложил радикально новую конструкцию, основанную отчасти на идеях конкурентов мэтра, однако последний отверг подобную новацию. В ответ Фэнсюн Сюй в недипломатичной форме раскритиковал подход Берлинера и заявил, что утратил интерес к проекту. Мудрый Кунг постарался вразумить юношу, объяснив, что ему следовало бы проявить побольше такта. С учётом предшествующих проступков академическая карьера Фэнсюна Сюя была под угрозой, и Кунг настоял на том, чтобы Сюй подготовил детальное обоснование своей идеи в виде технического отчёта и устроил по нему презентацию. Так Фэнсюн Сюй очутился в дивном новом мире компьютерных шахмат<ref>Hsu F. (2004). Behind Deep Blue: Building the Computer that Defeated the World Chess Champion. Princeton University Press // https://books.google.ru/books?id=WOk9DwAAQBAJ</ref>.
<references />
‎<comments />