К достижению цели

После работы фотографа прощаемся и летим назад, в Скопле...

Кажич просит выступить с сеансами в трех македонских городах, один из них — у греческой границы.

Гонорар — стиральный автомат для жены! Божо — добрый и симпатичный друг... С законченной работой направляюсь в обратный путь, в аэропорту Скопле неожиданная встреча — Л. Коган! Он тоже летит в Белград. Впервые я увидел Леонида Борисовича треть века назад, когда 16-летний Леня выступал на ежегодном празднике в «Артеке».

Мило беседуем, Коган рассказывает, как несколько дней назад он забыл перед посадкой в самолет указать свои чемоданы (это правило введено для того, чтобы не был погружен багаж, если пассажир уклонился от поездки, — борьба с терроризмом!) и прилетел в Любляну без вещей... В Белграде мы расстаемся.

За мое отсутствие настроение у Бори Штильмана улучшилось, он вполне оценил задачу и своей судьбой доволен. «Один мой товарищ, — с хитрой улыбкой говорит Боря, — уже в аспирантуре, встретил и удивляется, что я на семинар кафедры не прихожу...» ФОРТРАН освоен, подпрограмма получения траекторий выполняется. У Саши Юдина с библиотекой дебютов также дело двигается. Как и предполагалось, М. Лозинский и Л. Полтавец консультируют молодых программистов.

Криницкий тоже доволен: «Работа будет успешно закончена», — несколько неожиданно заявляет он.

«Почему?»

«У вас нет чувства стадности», — объясняет свою уверенность Николай Андреевич. Да, это чувство должно отсутствовать у каждого большого шахматиста, ибо он привык за доской опираться только на свои расчеты и полагаться лишь на свои силы...

Летом 1973 года в издании Совета по кибернетике Академии наук вышел новый препринт «О кибернетической цели шахматной игры». Саша работу над библиотекой дебютов закончил и начал составлять библиотеку эндшпилей. Но с Борей начались осложнения.

В алгоритме были неясности, недостаточно доказанным была необходимость формирования зоны игры, неясна была и динамика изменения зон, то есть динамика всего математического отображения позиции. Боря доказывал, что зона не нужна; на споры уходило время, а я столько сил и времени тратил на электротехнику, что работа над программой застопорилась. Наконец зимой 1974 года вопрос о зоне был согласован, а с формированием новых зон, динамикой математического отображения неясность сохранялась. И стал я подумывать: а не отказаться ли мне от электротехники, как я уже сделал это с турнирными выступлениями, ради более важной задачи?

За последние несколько лет дальнейшая разработка теории и внедрение управляемой машины существенно продвинулись. Совместно с одним харьковским заводом была полностью отработана система управления для двигателя 1000 кВт, получен патент за рубежом и поставлен опытный образец АС-двигателя на цементный завод. Аналогичная задача совместно с заводом «Электросила» была подготовлена для экспериментальной Кислогубской приливной станции. На гидростанции на Кольском полуострове были проведены все необходимые исправления в схеме АС-генератора, и в 1972 году была проведена опытная эксплуатация в течение требуемых 72 часов. Однако вопросы дальнейшего выпуска опытных образцов и выпуска серии АС-машин застопорились. Люди суть люди; как и в шахматах, когда я трудился на благо шахмат вообще и советских, в частности, встречал неизбежное сопротивление, так и в электротехнике сопротивление становилось все сильнее, чем ближе было завершение работ по проблеме «Управляемая машина переменного тока». Пожалуй, в шахматах было даже легче; добился проведения соревнования — играй и демонстрируй, на что способен. В электротехнике, если завод не сделает, то и ты ничего не сделаешь...

Да и в лаборатории положение было неспокойным, моим сотрудникам время от времени казалось, что без меня им будет лучше! В интересах работы я терпел и относился к этому снисходительно, но когда 19 июня 1974 года было очередное «восстание», то колебаний у меня не возникло — шахматная программа превыше всего!

24 июня была достигнута договоренность с руководством института, что с сего числа я занимаюсь только программой для ЭВМ. Нелегким было это решение: 19 лет посвятил я проблеме управляемой машины, да и научные исследования не удалось завершить полностью — работа машины в динамическом режиме продолжала оставаться неисследованной. И хотя здесь не только идеи, но и план работы был ясен, и в успехе поиска не было сомнений — динамическая устойчивость машины может быть обеспечена так же, как и статическая, — решил я распроститься с электротехникой...

К осени 1974 года алгоритм был приведен в порядок, Штильман заработал с полной нагрузкой. В чем же вкратце суть работы, почему она столь важна?

Когда я впервые прочел работы Клода Шеннона, то не оценил их в полной мере. Меня тогда интересовало лишь то, что Шеннон предлагал по формализации игры: 1) полный перебор всех ходов в пределах усеченного дерева и 2) выборочный перебор по аналогии с игрой шахматного мастера.

Первый метод — американские математики образно назвали его «брут форс» («грубая сила», грубая в том смысле, что грубая сила животного противопоставляется изощренным человеческим приемам) — меня, конечно, устроить не мог (правда, тогда еще не был известен метод ветвей и границ, метод, который позволяет сократить объем дерева перебора, но и это не может спасти метод полного перебора от критики). Второй метод, разумеется, вполне подходил в принципе, но никаких ясных рекомендаций по применению этого метода дано не было. Да это и понятно — Шеннон познакомился с шахматами слишком поздно, шахматным специалистом он не был. И все же в статье содержится ясное указание на то, как мастер использует свою библиотеку позиций, использует опыт прошлого, партии, сыгранные ранее. Тогда на это указание я не обратил внимания, я продолжал работать лишь над поиском хода в оригинальной позиции, когда опыт прошлого не помогает...

Впоследствии я понял значение этой работы Клода Шеннона. Он поставил весьма важную проблему в кибернетике — как улучшить управление, как усовершенствовать принятие решений. Шеннон предложил формализовать и программировать шахматы для того, чтобы использовать шахматный компьютер как модель, для решения аналогичных задач управления. Авторитет Шеннона (автора теории информации) столь велик, что его статья незамедлительно положила начало новому научному направлению.

Математики считают, что полное дерево перебора в шахматах, хотя и является конечным, содержит примерно 1О¹²⁰ позиций! И если партия продолжается 100 ходов, то среднюю ширину дерева составляют Ю¹¹⁸ позиций. Получается, что это дерево — тончайший блин...

Не только изучить, но и сформировать такое сверхгигантское дерево перебора нет возможности. Как же быть? Нет никакого другого выхода, как срезать верхушку, то есть формировать и анализировать усеченное дерево перебора, где длина вариантов сравнительно невелика.

Мастер считает варианты на 5—6 ходов. Если измерять эти варианты в единицах шахматного времени (математики это время измеряют в полуходах), то длина вариантов равняется 10—12 полуходам. Примем, что варианты ограничены 6 полуходами, то есть в два раза короче. Примем также, что мы анализируем позицию, где в среднем в каждом узле (позиции) дерева возможно 20 различных ходов. Нетрудно подсчитать, что такое усеченное дерево содержит около 70 000 000 позиций...

Математики применяют тонкий метод, который позволяет сократить число ходов в дереве перебора, так называемый метод ветвей и границ. Суть дела в том, что далеко не все ходы в дереве необходимы для принятия решения (выбора хода). Этот метод ветвей и границ позволяет . освободиться от значительной части балласта (ненужных ходов). Дерево сокращается с 70 000 000 до нескольких десятков тысяч, то есть примерно в тысячу раз. Но если учесть, что у шахматного мастера варианты анализа содержат всего десятки ходов, то мусора в дереве перебора остается более чем достаточно. Если поделить 70 000 на 6 полуходов, то средняя ширина дерева превышает 10 000 позиций...

Разрастание дерева вширь с увеличением глубины расчета происходит катастрофически.

Человек решает задачи, подобные шахматам (а шахматы — типичная задача среди тех, которые непрерывно решают люди), формируя дерево перебора вариантов. Если вообще и можно решить задачу точно, то надо формировать полное дерево перебора всех вариантов. При этом оптимальный вариант определяется с помощью точной оценочной функции или, упрощенно говоря, точной цели игры. Но в подавляющем большинстве случаев формирование полного дерева — задача непосильная; приходится длину вариантов сокращать. А при усеченном дереве перебора точная цель игры, как правило, бесполезна, нужна уже другая, неточная цель. Да, сохранять в усеченном дереве перебора все варианты — и плохие, и хорошие — невыгодно, ибо приходится сильно ограничивать предельную длину вариантов. Вот если было бы возможным сделать так, что варианты обрывались логически, тогда вместо широкого и короткого дерева можно было бы сформировать узкое и длинное (да и при существенно меньшем количестве ходов, включенных в дерево перебора) — решение было бы более точным. В книжечке «О кибернетической цели игры», выпущенной в свет издательством «Советское радио» в 1975 году, объясняется, что успех определяется в первую очередь качеством избранной цели игры.