Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич - Страница 80

Быстрое развитие вычислительной техники в 1970-е гг. на фоне высокого интереса к шахматам привело к стремительному расцвету шахматного программирования. С 1970 г. стартовал ежегодный Северо-Американский чемпионат по шахматам среди компьютерных программ. В первом чемпионате приняли участие шесть программ, а в 1973 г. — уже 12. Четыре первых года чемпионом становится программа под незамысловатым названием Chess, созданная студентами Ларри Аткином и Дэвидом Слейтом из Северо-Западного университета (Northwestern University, штат Иллинойс, США). Разработка программы была начата в 1968 г. Первоначально в число разработчиков входил также Кейт Горлен, но в 1970 г. он покинул команду. Первые версии программы (включая 3.6 от 1972 г.) относились к шенноновскому типу B, как и программа Маккарти. Обаяние идей Шеннона, который рассматривал тип B в качестве более совершенного подхода, похоже, владело умами американских разработчиков, в то время как ранние советские программы относились к более прагматичному на тот момент типу A.

Впрочем, весной 1973 г. Аткин и Слейт решаются на смену парадигмы. «Версия 3.6 стала окончательным результатом серии эволюционных изменений оригинальной программы и содержала в себе большую часть недостатков её первоначального дизайна. Chess 3.6 была, как динозавр, представителем вымирающего вида, — писали авторы. — Являясь по своей сути программой Шеннона типа B, она была основана на переборе „в глубину“ с альфа-бета-отсечениями и рассматривала более-менее фиксированные по длине варианты. Примитивная функция оценки позиции использовалась для оценки терминальных узлов дерева и для выбора n лучших ходов для дальнейшего изучения. Элементарных оценки и перебора Chess 3.6 было достаточно для того, чтобы в большинстве случаев совершать ходы, выглядящие разумно, и не подставлять фигуры под одно-двухходовые угрозы. По всей видимости, этого хватало для того, чтобы играть в силу слабого третьего разряда [class C player] и какое-то время обыгрывать другие программы». Chess 4.0 и его наследники получили более простую модульную архитектуру и относились к шенноновскому типу A[718].

Матч 1967 г. и последующие публичные выступления советской шахматной программы подогревали желание организовать международные соревнования, и в августе 1974 г. Международная федерация по обработке информации (International Federation for Information Processing, IFIP) организовала первый чемпионат мира по шахматам среди компьютерных программ. Он состоялся в стокгольмском отеле «Биргер Ярл». Директором турнира был Дэвид Леви.

Из шестнадцати «приглашённых» программ за звание чемпиона мира в итоге сразилось тринадцать — четыре из США (Chess 4.0, CHAOS, Tech 2 и Ostrich), три из Великобритании (Master, Beal, A16chs) и по одной из СССР («Каисса»), Канады (Ribbit), Австрии (Frantz), Швейцарии (Tell), Норвегии (Freedom) и Венгрии (Papa).

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

Позже Донской вспоминал, что был единственным участником, претендовавшим на второе место в чемпионате (именно его он обещал тем, кто отправил его на соревнования), в то время как остальные претендовали только на первое. В результате всё обернулось ровным счётом наоборот: именно «Каисса» заняла первое место, выиграв все четыре турнирные партии (турнир проходил по швейцарской системе) и опередив на одно очко программы Chess 4.0, CHAOS и Ribbit. Поскольку «Каисса» и Chess 4.0 не пересеклись в ходе турнира, было решено организовать между ними отдельную игру, которая завершилась вничью. Донскому была вручена для «Каиссы» золотая медаль чемпиона мира среди шахматных программ, сданная потом на хранение в ИПУ. В годы перестройки её след затерялся в музеях шахматных клубов[719] (дорогой читатель или читательница, если вы случайно найдёте её, обязательно дайте нам об этом знать).

С чисто шахматной точки зрения первый чемпионат мира представлял не слишком впечатляющее зрелище — партии были полны ошибок, заметных даже шахматным любителям. В последнем туре «Каисса» встретилась с программой Ostrich. В ходе партии американская программа дважды упустила возможность выигрыша (в одном из вариантов она могла дать мат в шесть ходов) и в итоге потерпела поражение. В демонстрационной игре против Chess 4.0 «Каиссе» вновь повезло — противник также упустил победу[720].

Всё это было вполне ожидаемо: «Каисса» в ту пору играла, по оценке Донского, в силу слабого первого разряда[721]. Однако с научной точки зрения прогресс был огромным. Написанная на смеси фортрана и ассемблера «Каисса» была способна на своей машине просматривать лишь около 200 позиций в секунду (в миллион раз меньше, чем Deep Blue, созданный спустя 20 лет). Однако уже тогда её авторы смогли реализовать в ней алгоритмы, ставшие затем фундаментом шахматного программирования на многие десятилетия. «Каисса» была способна обдумывать ходы во время хода противника, рационально распределять время на обдумывание, использовала представление позиции на доске в виде набора 64-битных масок[722], использовала динамические эвристики для упорядочения ходов в дереве перебора (так называемая «служба лучших ходов» — прообраз современных методов сортировки вариантов), была оснащена дебютной библиотекой, в которой содержалось в общей сложности около 10 000 ходов для различных дебютных позиций, и использовала революционную технику сокращения числа перебираемых вариантов, получившую название «эвристика пустого хода»[723].

Суть этого метода заключается в следующем: если в некоторой позиции внутри дерева перебора передать очередь хода сопернику и проанализировать его ответы при помощи перебора с урезанной глубиной, то, если в результате обнаружится, что противник, несмотря на возможность выполнить ход дважды, всё-таки не смог найти ход-опровержение с достаточной оценкой, перебор в данной позиции можно завершить, вернув оценку, равную верхней границе. Конечно, в шахматах бывают ситуации, когда любой из возможных ходов хуже, чем отсутствие хода. Подобное положение называется цугцванг (от нем. Zugzwang — принуждение к ходу). Однако возникают они достаточно редко, и их возможное появление можно в ряде случаев предсказать при помощи дополнительных правил (например, не применять эвристику пустого хода в пешечных эндшпилях с блокированными пешками) или с использованием ещё одного «проверочного» шага перебора с ещё более урезанной глубиной рассмотрения вариантов.

Впрочем, сохранить лидерство в области компьютерных шахмат, как и в космической гонке, Советскому Союзу не удалось. В 1977 г. в Торонто Chess 4.6 берёт реванш и становится чемпионом мира. «Каисса» делит второе место с другой американской программой, уже знакомой нам Duchess из Университета Дьюка. В первом туре чемпионата в партии Duchess против «Каиссы» разыгралась настоящая драма: «Каисса» на ровном месте отдала ладью и проиграла, что многие зрители в зале посчитали проявлением ошибки в программе. Однако, когда после партии «Каиссе» предъявили позицию после ожидаемого от неё «правильного» хода, она продемонстрировала головокружительную комбинацию противника с жертвой ферзя, ведущую к неминуемому мату[724]. Ценой этого красивого поражения стала утрата чемпионского титула.