3.5.3 Алекс Бернстайн и первая полноценная шахматная программа

В 1951 г. ещё один коллега Тьюринга, Дитрих Принц, создал первую программу для Ferranti Mark I, способную решать задачки типа «мат в два хода». Было ясно, что созданию полноценной шахматной программы мешает недостаточный объём памяти машины.

Манчестерская команда не была единственной группой программистов, работавших над созданием шахматных программ в 1950-е. За океаном собственную разработку вели физики-атомщики из Лос-Аламоса под руководством самого фон Неймана.

Шахматная программа для компьютера MANIAC I (Mathematical Analyzer, Numerical Integrator, and Computer или Mathematical Analyzer, Numerator, Integrator, and Computer, «Математический анализатор, числовой интегратор и компьютер» или «Математический анализатор, счётчик, интегратор и компьютер»), спроектированного и построенного командой из Лос-Аламоса, была готова к 1956 г. и умела играть в так называемые антиклерикальные шахматы — вариант шахмат на доске 6 × 6 и без слонов (дело в том, что эта фигура в английском языке называется словом bishop — епископ). Также в антиклерикальных шахматах не было рокировки и ходов пешек через одно поле.

Позже эта программа получила название Los Alamos Chess.

Рис. 66. Учёные из Лос-Аламоса Пол Штейн (слева) и Ник Метрополис (справа) играют в шахматы с MANIAC I (на заднем плане)

Интерес к шахматному программированию проявляли и исследователи социалистических стран. В 1953 г. в ГДР в журнале Funk und Ton (Радио и звук) была опубликована работа Гюнтера Шлибса с описанием алгоритма работы шахматной программы. Идеи Шлибса в целом повторяли идеи Шеннона и Тьюринга: он воспроизводит в своей работе оценочную функцию из статьи Шеннона, включающую оценку материала (девять единиц за ферзя, пять — за ладью, по три — за коня и слона), наличие отсталых, изолированных и сдвоенных (штраф по 0,5 балла) пешек, а также мобильности (по 0,1 балла за каждое поле). Перебор в программе Шлибса, как и в программе Шеннона, должен был осуществляться на фиксированное число полуходов в глубину, а оценка — производиться только в стабильных позициях. В общем, Шлибс почти полностью воспроизводит в своей работе статью Шеннона, внося ряд замечаний и уточнений.

Работа Шлибса не упоминается в современной западной литературе, но была хорошо известна советским исследователям. Краткий пересказ идей Шеннона и Шлибса мы впервые находим в книге «Электронные цифровые машины» Анатолия Ивановича Китова — руководителя головного вычислительного центра Министерства обороны СССР. Эта книга стала первой «открытой» книгой по вычислительной технике в Союзе, была позднее переведена на ряд иностранных языков и опубликована в Китае, Польше, Чехословакии. Пересказывая идеи Шлибса и Шеннона, Китов не удержался от того, чтобы скорректировать величину штрафа за изолированную и сдвоенную пешку: в его книге они составляют 0,4 и 0,3 балла соответственно (вместо 0,5 за оба дефекта у Шеннона и Шлибса).

Два года спустя увидела свет новая книга Китова, написанная в соавторстве с Николаем Криницким, — «Электронные вычислительные машины» (в этой книге, вышедшей в «тёплые ламповые времена», слово «алгоритм» пока ещё пишется через Ф — «алгорифм»), в которой уже упоминаются первые проекты советских программистов. Например, созданная В. М. Курочкиным программа, способная решать шахматные задачи, а также созданная В. Д. Кукушкиным программа, способная ставить мат одинокому королю двумя разнопольными слонами^, . Откровенно говоря, первой моей мыслью, когда я увидел эти фамилии в книге Китова, было то, что за птичьими псевдонимами в данном случае скрывались засекреченные сотрудники ИТМиВТ, во главе которого стоял ещё один, уже известный нам исследователь с «крылатой» фамилией — Сергей Алексеевич Лебедев. В мемуарах его коллег упоминается программа для БЭСМ, которая решала двух- и трёхходовые задачи намного быстрее, чем лучшие шахматисты института. Но красивая версия не выдержала проверки: по крайней мере Владимир Михайлович Курочкин — вполне реальный человек, известный российский учёный в области информатики, стоявший у истоков отечественного программирования. С 1950 по 1955 г. Курочкин работал под началом Лебедева в ИТМиВТ, а затем возглавил отдел систем математического обеспечения Вычислительного центра РАН.

Несмотря на все усилия исследователей, первая полноценная шахматная программа появилась только в 1957 г. Её создала команда под руководством сотрудника компании IBM Алекса Бернстайна.

Написание шахматной программы в конце 1950-х гг. было сложной задачей. Во-первых, языки программирования находились в зачаточном состоянии. Язык программирования фортран (FORTRAN) был огромным шагом вперёд по сравнению с машинным кодом, но первые компиляторы имели ограниченный набор функций, глючили и генерировали неоптимальный код. Во-вторых, у машин было мало памяти. Машина со 100 000 байтов памяти была большой редкостью, при этом значительная часть этого драгоценного ресурса была отдана операционной системе и программному коду. В-третьих, инструментов отладки не существовало. Если что-то пошло не так или вы подозревали, что что-то не так, арсенал средств поиска проблемы был крайне ограничен. Наконец, компьютеры стоили дорого и доступ к ним был сложен. Большая часть ранних работ в области шахматного программирования сильно страдала из-за сложностей в получении доступа к дорогостоящему компьютерному оборудованию. В этих сложных условиях прогресс в разработке сильных шахматных программ был ожидаемо медленным.

Неудивительно, что большую часть пионерских проектов в области компьютерных шахмат осуществили люди, которые либо были сотрудниками компаний, производящих компьютерное оборудование, либо работали в университетах. И у тех и у других был пусть и ограниченный, но всё-таки какой-никакой доступ к драгоценному компьютерному времени (особенно посреди ночи). IBM была компанией, обладавшей ключевым ресурсом для создания шахматной программы: современными компьютерами. Однако одних только машин было недостаточно: чтобы создавать программы, нужны ещё и программисты, а людей с необходимыми навыками было в то время трудно найти (как, впрочем, нередко бывает и сейчас). На что были похожи практики поиска сотрудников в ИТ в 1950-е?

В декабре 1956 г. IBM разместила объявление в журнале Scientific American и в газетах New York Herald Tribune и Los Angeles Times, в котором сообщала, что ищет тех, кто интересуется программированием компьютеров. В рекламе использовалось изображение чёрного шахматного коня и говорилось, что «эта работа понравится тем, кто любит играть в шахматы или разгадывать головоломки».

В ответ на объявление компания получила ровно семь ответов, и этот результат был сочтён отличным. Пятеро из откликнувшихся были опытными программистами, работавшими у конкурентов, — кадровое браконьерство всегда было в той или иной мере свойственно компьютерной индустрии. Двое других были новичками, и только один из них оказался полезным в долгосрочной перспективе. Первым был шахматист, который «интересовался только игрой в шахматы», и вскоре IBM «позволила ему вернуться к своей доске». Второй «почти ничего не знал о вычислительной технике», но, как утверждалось, его IQ равнялся 172 баллам, и, по словам сотрудника компании, ответственного за наём программистов, кандидат «обладал тем типом ума, который нам нравился… [Он] научился играть на пианино, когда ему было десять лет, пребывая в уверенности, что нота фа в действительности является нотой ми. Так он и играл в течение многих лет. Бог знает, через что прошли его соседи. Однако, следует отметить, эта история показала наличие прекрасного независимого таланта к систематической работе по преобразованию значений». В конце концов первоначальная рекламная кампания и её последующее продолжение в еженедельнике The New Yorker привели к появлению многообещающих «джуниоров». В их число входили кристаллограф, получивший образование в Оксфорде, доктор философии в области английского языка из Колумбийского университета, экс-модель из модной индустрии, протохиппи и многочисленные шахматисты.

Одним из откликнувшихся на объявление стал победитель чемпионата США (U. S. Open) по шахматам Артур Бисгайер. Также среди связавшихся с компанией были Алекс Бернстайн, бывший капитан шахматной команды Высшей научной школы Бронкса (The Bronx High School of Science, среднее учебное заведение с высоким уровнем преподавания), Дон Шульц, который позднее стал президентом Шахматной федерации США, а также Сид Нобл, самопровозглашённый «чемпион по шахматам Французской Ривьеры». Единственное, что объединяло этих начинающих программистов, — это, пожалуй, только их выдающиеся результаты в серии тестов, основанных на интеллектуальных головоломках, да достаточная самоуверенность для того, чтобы откликнуться на расплывчатые, но интригующие объявления IBM^, .

Долгое время о биографии Алекса Бернстайна, несмотря на его весомый вклад в историю развития шахматного программирования, было известно немного. Некоторые подробности удалось установить в результате переписки с его ныне здравствующими родственниками. Отец Бернстайна — математик Владимир Бернштейн, уроженец Санкт-Петербурга, был учеником профессора Якова Успенского. В 1919 г. Владимир решает покинуть разорённую Гражданской войной Советскую Россию. Во время пересечения советско-финской границы в районе Выборга он получил серьёзное пулевое ранение, которое стоило ему потери лёгкого. В эмиграции Владимир Бернштейн сменил несколько стран пребывания. Какое-то время он жил в Лондоне, а в середине 1920-х перебрался во Францию, где поступил в Сорбонну и в 1930-м защитил докторскую диссертацию, посвящённую проблеме единственности для рядов Дирихле. Опубликованная в 1933 г. монография Бернштейна, посвящённая этим рядам, получила очень высокую оценку от знаменитого французского математика Жака Адамара. В 1931 г. Бернштейн получил итальянское гражданство и преподавал аналитическую геометрию в Павии и математический анализ в Милане. Именно в Милане и родился Алекс Бернстайн. К сожалению, здоровье Владимира было серьёзно подорвано из-за ранения, и в 1936 г. он скоропостижно скончался в Милане от пневмонии, не дожив до своего 36-летия. Примерно в 1940 г. юный Алекс с матерью и её вторым мужем перебираются в Нью-Йорк. Здесь он окончил школу, колледж, а затем Колумбийский университет, где изучал математику и средневековую французскую литературу^, . Во время Корейской войны его призывают в армию. Благодаря познаниям в области математики он попадает в специальное техническое подразделение, где получает первые знания в области компьютерной техники. Сын Алекса, Макс Бернстайн, так описывает историю знакомства своего отца с компьютерами: «Когда его призвали в армию (это была война в Корее), он упомянул свои познания в области математики, и его пригласила на собеседование женщина, которая создавала специальное техническое подразделение и искала новобранцев, хорошо разбирающихся в математике. Сама она была русской и когда увидела его фамилию, то спросила: „Бернштейн? Вы случайно не в родстве с Владимиром Бернштейном?“ Когда он сказал, что является сыном Владимира, она ответила: „Пойдём, я научу тебя компьютеру“. Таким образом, именно армия дала ему образование в области компьютеров. Я не знаю подробностей его работы в армии, но она была весьма разнообразной, мне смутно помнится, как он рассказывал о попытках оптимизировать оборонительные позиции США на континенте (в случае авианалётов? ракетных атак?) и про использование полиномов Чебышёва для чего-то связанного с кораблями для военно-морского флота».

Идея создания шахматной программы принадлежала изначально товарищу Алекса Бернстайна Хэлу Джадду и была поддержана Чарльзом ДеКарло — главой отдела прикладной науки компании. Бернстайн в итоге возглавил команду по созданию шахматной программы, в которую помимо него вошли Майкл де Ван Робертс, Тимоти Арбакл и Мартин Бельски. Артур Бисгайер стал шахматным советником проекта. Разработанная программа относилась к типу B по терминологии Шеннона, выполняя перебор на четыре полухода в глубину и рассматривая по семь наиболее перспективных альтернатив на каждом уровне дерева перебора.

Эти ограничения были связаны со временем, необходимым для выбора хода: обычно машина затрачивала на принятие решения около восьми минут, а если на каждом уровне дерева перебора анализировалось не семь, а восемь вариантов, то этот интервал возрастал бы до 15 минут. При этом увеличение глубины перебора на один полуход приводило бы к увеличению времени расчёта до шести с половиной часов. Современному компьютеру на те же вычисления потребовались бы доли секунды^, .

Несмотря на то что команда Бернстайна получила уникальные результаты, знаем мы о ней сегодня очень мало. Биографические данные участников команды крайне скудны, неизвестны даже годы жизни авторов первой в мире шахматной программы. О самом Бернстайне известно, что он научился играть в шахматы в девять или десять лет. Он не проиграл ни одной партии своей программе, но, отзываясь о её игре, однажды заметил, что «один или два раза она сыграла так хорошо, что это вызвало у меня волненье». Многие источники по истории программирования сообщают, что Бернстайн был межуниверситетским чемпионом страны, но в шахматных источниках отсутствуют подтверждения этого факта. Хотя Бернстайн начал работу над шахматной программой только в 1956 г., он успел поучаствовать в знаменитой Дартмутской конференции, куда прибыл вместе со своими коллегами по IBM — уже знакомым нам Артуром Сэмюэлом и Эдвардом Муром. «Алекс Бернстайн, приехавший из Нью-Йорка, чтобы поговорить о шахматной программе, сразился в шахматы с Маккарти, что эквивалентно индивидуальному поединку (mano-a-mano) в мире науки. Бернстайн победил, несмотря на то, что предоставил противнику фору, играя вслепую. После этого, по возвращении в Нью-Йорк, он создал программу, чтобы окончательно победить Маккарти. Поскольку его визит в Дартмут не совпал с визитом Ньюэлла и Саймона, Бернстайн лишь позже узнал о том, что они независимо пришли к некоторым идеям в отношении одной и той же задачи», — пишет упоминавшаяся нами в первой части писательница и специалистка по истории ИИ Памела Маккордак. Сам Маккарти в своих воспоминаниях немного более скуп: «Алекс Бернстайн из IBM представил свою шахматную программу на стадии разработки. Моей реакцией было изобрести и порекомендовать ему альфа-бета-отсечение. Его это не убедило». Работа Бернстайна так и не получила продолжения, и эстафета перешла к другим командам. Шахматный проект изначально развивался по остаточному принципу, во всяком случае в интервью The New Yorker Бернстайн сетовал на занятость в других проектах IBM. Изначальным или по крайней мере официальным оправданием менеджеров IBM, позволивших Бернстайну использовать первые IBM 704 для столь несерьёзной вещи, как программирование шахмат, была надежда на то, что в случае успеха это послужит демонстрацией того, что компьютеры могут решать задачи, сопоставимые по сложности с теми, с которыми сталкивается бизнес. Однако акционеры не оценили достижения Бернстайна и Сэмюэла и были не в восторге от того, что ресурсы фирмы тратились на игры.

В наследие от Бернстайна нам осталось несколько статей, фотографий и даже короткое видео, демонстрирующее игру Бернстайна со своим детищем.

Рис. 67. Алекс Бернстайн демонстрирует, как компьютер IBM 704 играет в шахматы

‎

Loading comments...