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

Третье и последнее выступление «Каиссы» на чемпионате мира состоялось в 1980 г., где она поделила 6–11-е места. Примечательно, что первое место в чемпионате досталось не Chess 4.9, которая была, наряду с «Каиссой», одной из двух главных претенденток на победу, а программе Кена Томпсона — Belle. Из 18 участников III чемпионата восемь были из США, трое из Великобритании и трое из Канады. Социалистический лагерь был представлен одной лишь «Каиссой» [725]^, [726].

В 1990 г. команда из девяти программистов, возглавляемая Донским, выпустила новую версию «Каиссы», написанную на языке Си для операционной системы MS-DOS. Обновлённая программа участвовала во Второй компьютерной олимпиаде, разделив 4–6-е места (из 11 участников) [727]^, [728].

Сегодня сложно дать однозначный ответ на вопрос о том, почему «Каисса» не смогла сохранить лидерство. Сами авторы считали, что дело было в отставании аппаратной базы: машина, которую использовала «Каисса», была медленнее, чем у конкурентов [729]. Кроме того, команда «Каиссы» щедро делилась алгоритмическими находками с сообществом шахматных программистов — принципы работы программы были детально описаны в ряде статей [730]^,  [731]^,  [732]^, [733]^, [734], а затем и в книге [735], посвящённой методам шахматного программирования. Нельзя исключать и влияние субъективных факторов: интересы разработчиков со временем меняются, на смену творческим подъёмам приходят творческие кризисы, разработчики могут свернуть на неправильный путь, теряя время на попытки развития непродуктивных идей, в конце концов, люди стареют и утрачивают энергию и задор, поэтому смену лидеров в том или ином направлении можно считать во многом естественным процессом.

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

4.5.6 Рассуждения о теоретической основе шахматного программирования и идеи Ботвинника

С 1970-х гг. создатели шахматных программ постепенно отходят от парадигмы, предложенной Шенноном. Можно ли сказать, что «Каисса» была программой шенноновского типа A, как её предшественница из ИТЭФ, или же она относилась к типу B? Ответ на этот вопрос не так прост.

С одной стороны, благодаря эвристике пустого хода или «модели активной игры», при использовании которой в некоторых узлах дерева перебора анализировались только «активные» ходы, программа исключала часть ветвей дерева из рассмотрения. В принципе, исключение ветвей происходит и при альфа-бета-отсечении, но оно, в отличие от упомянутых ранее эвристик, является «безопасным», то есть не может изменить оценку программой позиции по сравнению с полным перебором вариантов. Казалось бы, в силу селективности перебора «Каиссы» её следовало бы отнести к типу B, однако использование метода «итеративного углубления» приводит к тому, что ходы, отброшенные при анализе позиции на n-й итерации, могут быть изучены на (n+1)-й. В зависимости от особенностей реализации эвристика пустого хода может исключить некоторые ходы из перебора «безвозвратно», но это происходит не всегда. Словом, программы второго поколения, такие как «Каисса», активно использовали подход, при котором более перспективные варианты рассматривались более глубоко. Целый сонм правил управлял в таких программах принятием решений о сокращении или же, наоборот, продлении перебора для тех или иных ходов. Например, шахи, ходы пешек на предпоследнюю горизонталь, размены, взятия, приводившие к переходу в пешечный эндшпиль, иногда даже просто взятия могли увеличивать глубину перебора на один полуход или даже на нецелое количество полуходов, скажем на ½ полухода (к примеру, два взятия приводят к продлению перебора на один полуход). С другой стороны, для бесперспективных ходов глубина рассмотрения уменьшалась — под «сокращение» могли попадать «тихие» ходы в позициях с нехваткой материала (обычно трудно отыграть материал, совершая пассивные ходы — не совершая взятий, шахов или ходов проходных пешек), просто предположительно слабые ходы (например, помещённые в конец списка ходов эвристиками, отвечающими за упорядочивание ходов на основе статистических данных о том, как часто те или иные ходы становились лучшими в процессе перебора) и так далее. Второе поколение шахматных программ стало золотым веком изобретателей эвристических правил. Их создание часто ограничивалось только полётом фантазии: творческое озарение, поспешная реализация, несколько десятков (в лучшем случае) тестовых партий — и вот уже программа оснащена новым, доселе невиданным знанием. Этот подход не был уникальной чертой шахматного программирования — он был распространён в самых разных областях ИИ вплоть до конца 1980-х или даже до 1990-х. Сегодня мы часто называем этот период временем GOFAI — Good Old-Fashioned Artificial Intelligence (Старого доброго искусственного интеллекта). Этот термин был предложен профессором Джоном Хогландом в книге «Символьные вычисления. Искусственный интеллект: сама идея» (Symbolic Computation. Artificial Intelligence: The Very Idea, 1985) для обозначения символьного подхода в ИИ, доминировавшего в эти годы [736]. Сторонники этого подхода стремились изложить человеческие знания в виде наборов правил и алгоритмов.

На заре шахматного программирования бытовало забавное заблуждение о том, что программист не может создать программу, которая будет играть в шахматы сильнее своего создателя. Тьюринг сравнивал это с утверждением, что ни одно животное не может проглотить животное тяжелее себя [737]. Возражения Тьюринга, в его время разумеется, могли носить только теоретический характер — на протяжении многих десятилетий машины играли в шахматы на любительском уровне, выполняя для шахматных экспертов роль безропотных учеников, в точности следующих рекомендациям учителей. Проблема, как и в случае процесса обучения людей, заключается в том, что рассказ эксперта о своём методе вовсе не равен самому методу. Обычно человек способен отличить на картинке хрен от пальца, но стоит вам попросить его объяснить, как именно он это делает, а потом начать следовать описанному способу, как вы немедленно запутаетесь и в хрене, и в пальцах.

Однако вплоть до 1990-х гг. преимущество «человеческого» способа игры в шахматы было очевидным, а возможность изобретения принципиально иного подхода — нет. Именно поэтому, создавая шахматные программы, их авторы в той или иной мере пытались подражать в них игре людей. Шахматный мастер тоже просчитывает варианты, оценивает позиции. Более того, люди попытались разложить эту оценку на отдельные элементы задолго до появления даже проектов первых шахматных программ. Уже в XVII–XVIII вв. в работах мастеров итальянской шахматной школы, таких как Пьетро Каррера [738] и Джамбаттиста Лолли [739], мы встречаем попытки численной оценки относительной силы шахматных фигур. Задачу формализации оценки позиции и способа отбора вариантов для анализа нужно было выполнить для того, чтобы обучать начинающих шахматистов, и неудивительно, что наработанные методы легли в основу алгоритмов первых шахматных программ. Однако пионеры шахматного программирования немедленно столкнулись с тем, что многие, казалось бы, самоочевидные для людей понятия были определены недостаточно строго. Если с материалом всё было более-менее ясно, то понятия слабого поля, слабой пешки, защищённости короля, активности фигур было непросто переложить на язык строгой математической логики. Ещё хуже дело обстояло с отбором перспективных вариантов для анализа. Как выяснилось, этот процесс шахматные мастера осознают весьма слабо — выбор основывается на интуиции, являющейся порождением опыта, и эта самая интуиция оказалась совершенно неуловимой и каждый раз, подобно солнечному зайчику, ускользала от попыток описания на не терпящем неоднозначностей и сомнений языке математических формул. Впрочем, в те годы никто не знал наперёд, что эти отважные донкихотские попытки обречены на неудачу. Тем более что во главе этого направления стоял один из патриархов советской шахматной школы — Михаил Ботвинник, шестой чемпион мира по шахматам.