От редактора

Прошло семь лет с момента выхода в свет книги М. Ботвинника "Алгоритм игры в шахматы". Это не малый срок в жизни человека, и читатель, вероятно, хочет узнать, что произошло за эти годы, приблизился ли Ботвинник к достижению своей цели? Произошло немало событий. Ботвинник переступил через рубеж шестидесяти лет, перестал выступать па шахматной арене, посвятил себя полностью работе по созданию искусственного шахматиста-гроссмейстера, создал и возглавил группу, работающую над составлением шахматной программы для ЭВМ, довел алгоритм игры в шахматы почти до конца (работа над алгоритмом будет закончена только после испытания и возможной корректировки программы). Идеи, изложенные Ботвинником семь лет тому назад, не только получили свое развитие и уточнение, но и подверглись в некоторой своей части значительной переработке. Настоящая книга не является переизданием предыдущей. Однако можно с уверенностью сказать, что и она вызовет большой интерес.

Машинная игра в шахматы - это очень интересно, но машинная игра в силу гроссмейстера - это потрясающе интересно. А именно такова цель Ботвинника, и есть основания надеяться, что она будет достигнута. Выше было перечислено то, что произошло за истекшие годы. Скажем теперь, что за это время не произошло. Ботвинник не потерял своей энергии, не утратил замечательной способности анализировать свою собственную игру, свое собственное шахматное мышление. Новая книга Ботвинника так же доступна для широкого круга читателей, как предыдущая. Она безусловно привлечет к себе внимание и многих ученых: математиков, специалистов по кибернетике, психологов, экономистов, работающих в области автоматизации процессов планирования. И, конечно, ее пожелает прочесть каждый шахматист.

Как уже было сказано, в книге рассматривается вопрос о машинной игре в шахматы. Остановимся прежде всего на том, о каких машинах идет речь и каким образом они могут играть в шахматы. Имеются в виду современные электронные вычислительные машины дискретного действия, так называемые ЭВМ, которые относятся к числу программно управляемых. Применение электронной техники делает их очень быстродействующими, однако основная их черта - автоматическое управление процессами переработки информации - вовсе не связана с этой техникой. Такие машины представляют собой сложные автоматы, состоящие из ряда связанных между собой устройств: устройства управления, запоминающего устройства (называемого также памятью), операционного устройства, устройства ввода информации и устройства выдачи результатов. Информация может быть введена в программно управляемую машину и фиксирована в ее памяти в алфавитно-цифровом виде (в виде слов и чисел, которые представлены, понятно, в машинном коде).

Информацию, вводимую в машину, можно, грубо говоря, разделить на управляющую и перерабатываемую. Управляющей информацией является программа работы машины, состоящая из некоторого числа так называемых команд. Устройство управления в каждом такте работы прочитывает в программе, введенной в память, команды одну за другой и заставляет все устройства машины выполнять операции, предусмотренные в этих командах. Само устройство управления также выполняет некоторые из таких операций, например, производит поиск очередной команды или их видоизменение и т. п. После получения искомого результата, выполняя соответствующую команду, машина выдает его в том или в ином виде. Современные машины, кроме ряда других устройств выдачи, имеют электрическую пишущую машинку, которая может также служить устройством ввода. Если человек-оператор напечатает что-либо на этой машинке, набранный на ее клавиатуре текст вводится в память машины. В свою очередь, при наличии в программе соответствующей команды, машинка автоматически печатает полученные результаты. Обычно такая машинка использует двухцветную ленту. Текст, вводимый в машину, печатается одним цветом (например, черным), а выводимый из машины - другим (например, красным). Таким образом, диалог человека-оператора и машины фиксируется на бумаге в виде дословного протокола. Машина, конечно, располагает и устройствами ввода и вывода больших объемов информации, но для игры в шахматы большое удобство представляет именно такая пишущая машинка (еще лучше дисплей).

Гибкость работы программно управляемой машины достигается тем, что устройство управления может изменять порядок выбора команд в зависимости от получаемых результатов, а также тем, что управляющая информация, как и перерабатываемая, представлена в алфавитно-цифровом виде и может подвергаться переработке. Современные программы составляются так, что, кроме выполнения операций над перерабатываемой информацией, в них предусмотрено также видоизменение входящих в них команд и выполнение их в новом виде, так что по короткой программе машина может выполнять очень длинные последовательности операций.

Машинная игра в шахматы протекает следующим образом. Заранее разработанную программу вводят в машину через устройство ввода (описанная выше пишущая машинка непригодна для этой цели). Затем в память машины вводят (в качестве перерабатываемой информации) описание начальной позиции на доске. Устанавливают право первого хода, и эту информацию тоже вводят в память машины. Если первый ход принадлежит машине, то, выполняя программу, она вычисляет его и выдает на пишущую машинку. Одновременно машина вычисляет новую позицию и сохраняет ее в своей памяти вместо предыдущей. После этого машина "ждет" - (для чего в программе предусматривают "цикл" из команд, выполнение которых не затрагивает ни программы, ни перерабатываемой информации, из которого машина может выйти только в результате так называемого прерывания, возникающего, в частности, и при вводе информации через пишущую машинку).

Шахматист, сражающийся с машиной, воспроизводит на доске выданный ею ход и делает ответный ход, запись которого вводят в машину через пишущую машинку. Если первый ход принадлежит человеку, то, получив об этом информацию, машина "ждет" до тех пор, пока в нее не введут информацию о ходе ее противника. Дальнейшее течение игры одинаково как при первом ходе машины, так и при первом ходе человека.

Возможна и игра одной машины против другой и даже игра в одной и той же машине одной программы против другой. Но на этих, вообще говоря, интересных вопросах мы останавливаться не будем.

Как уже было сказано, программа представляет собой ряд команд, каждая из которых для каждого варианта исходных данных определяет однозначно операции, выполняемые устройствами машины, в том числе и выбор следующей команды. Таким образом, машина является исполнителем предписания,заданного в виде программы. Другими словами, программа-это предписание, определяющее действия машины и изложенное на машинном языке. Предписание, которое для каждого конкретного исходного данного определяет процесс переработки информации, получило в науке название алгоритма. Можно сказать, что, играя в шахматы, программно управляемая машина выполняет алгоритм шахматной игры.

Алгоритм шахматной игры вначале составляют не на машинном, а на каком-либо другом, более удобном для человека, точном (формальном) языке, например на языке математических описаний. После этого проблема сводится к переводу с одного языка на другой. Перевод алгоритма на машинный язык получил название программирования.

Первоначальное составление алгоритма представляет собой творческую работу. Человек, создающий алгоритм, приводит в действие все свои творческие способности: воображение, предвидение, художественное чувство (да! алгоритм должен быть не только эффективным, но и красивым, изящным), тонкий научный анализ, изобретательность и многое другое. Однако и программирование - в значительной части творческая работа. При программировании приходится решать каждый раз заново много сложных вопросов, например: определение общей организации программы, распределение работы по выполнению алгоритма между различными ее устройствами (это особенно важно и сложно в современных машинах, устройства которых могут работать параллельно), размещение исходных данных и результатов в памяти, контроль за правильностью получаемых результатов (ибо при эксплуатации машин на всех этапах этой работы могут возникать случайные ошибки).

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

Возникает вопрос, нельзя ли позаимствовать алгоритм игры в шахматы у кого-нибудь из видных шахматистов? Этот вопрос тесно связан с темой данной книги Ботвинника, и к нему мы вернемся немного позже.

Возможен и другой способ игры машины в шахматы. Можно разработать алгоритм самообучения машины игре в шахматы, по которому на основании ряда игр машина сама для себя вырабатывает алгоритм шахматной игры и при дальнейших играх его совершенствует. Проблема создания программ для самообучения машин весьма интересна и очень трудна. Для ее решения нужно представить в виде алгоритма процесс творческой деятельности. Пока что методика создания алгоритмов самообучения находится на самой начальной стадии своего развития.

В данной книге говорится об игре машины по заранее состав-ленной программе, являющейся готовым алгоритмом шахматной игры. В пользу создания такой программы (и против самообучающейся программы), кроме неизученности проблемы создания алгоритмов самообучения, говорит еще и то обстоятельство, что люди в течение тысячелетий играют в шахматы и многому успели научиться. По-видимому, машина очень нескоро накопит такой же по своему объему опыт. Поэтому, если мы хотим побыстрее увидеть совершенную игру машин в шахматы, целесообразно составить алгоритм шахматной игры, используя накопленный человечеством опыт. Но этот путь требует, чтобы разработкой алгоритма шахматной игры занялся человек, изучивший этот опыт. А Ботвинник именно такой человек.

Многие гроссмейстеры играют в шахматы хорошо и даже отлично, но ни один из них не знает алгоритма точной игры в шахматы. Если их методы алгоритмизировать, то получатся алгоритмы более или менее хорошей игры в шахматы. Существующие сегодня программы игры машин в шахматы могут быть названы алгоритмами лишь более или менее удовлетворительной игры. Но возможен ли алгоритм точной игры, или, как говорят математики, существует ли такой алгоритм? Прежде всего, что это такое? Выше было сказано, что алгоритм игры в шахматы - это алгоритм, который при любой заданной шахматной позиции позволяет вычислить ход. Под алгоритмом точной игры в шахматы, мы будем понимать алгоритм, который, если во время игры руководствоваться только им, ведет неукоснительно к достижению цели.

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

Покажем, что в ходе шахматной игры могут встречаться ситуации только трех видов: 1) обеспеченный (при правильной игре игрока) выигрыш, 2) бесспорный (при правильной игре противника) проигрыш, 3) ничья (при правильной игре обоих игроков). Одновременно покажем, что существует алгоритм точной и наилучшей игры в шахматы, пользуясь которым можно при ситуации обеспеченного выигрыша сделать мат за наименьшее число ходов, при ничейной ситуации не проиграть, а в случае отступления противника от алгоритма наилучшей игры перейти к ситуации обеспеченного выигрыша, при ситуации бесспорного проигрыша - проиграть за наибольшее число ходов или при ошибке противника перейти к самой лучшей из ставших возможными ситуации. То, что сказано в предыдущей фразе о возможностях алгоритма точной (и наилучшей) игры в шахматы, именно и должно быть принято за цель шахматной игры, которую нужно иметь в виду, разрабатывая алгоритм точной игры.

Сразу подчеркнем, что упомянутый алгоритм существует лишь потенциально, что он до сих пор не составлен и в том виде, в котором мы его опишем, практически невыполним из-за того, что требует осуществления астрономического числа машинных операций. Тем не менее факт его существования интересен, он обнадеживает, позволяет предполагать, что когда-нибудь будет реально построен эффективный алгоритм точной игры в шахматы. Какие же к этому основания? Оказывается, такие основания есть. Во-первых, математический факт, что для каждого алгоритма существует бесконечное количество эквивалентных ему алгоритмов,- приводящих к получению тождественных результатов, хотя и различными путями. Во-вторых, практически невероятно, чтобы из бесконечного числа алгоритмов, решающих нашу задачу, описываемый ниже алгоритм предусматривал самый короткий путь решения. Можно даже доказать (это доказательство не может быть здесь приведено), что наш алгоритм предусматривает вовсе не самый короткий путь получения хода. Наконец, в-третьих, существует путь, идя которым можно, отправляясь от описанного ниже алгоритма точной игры, получать эквивалентные ему "лучшие" алгоритмы. Что это за путь будет сказано несколько позже.

Прежде всего, убедимся в том, что и для белой и для черной стороны вопрос о том, как следует играть, может решаться одинаково. Для этого покажем, что реальная игра в шахматы эквивалентна игре, которую мы назовем белой игрой. Белую игру можно осуществить, если каждому из двух сражающихся шахматистов дать отдельную доску, на которой он играет белыми, и привлечь помощника, который после каждого хода, совершаемого на одной из досок белыми, перемещает на второй доске черную фигуру, одноименную с переместившейся белой и симметрично расположенную с этой белой фигурой относительно "вертикальной" оси (т. е. оси, делящей доску на правую и левую половины).

Итак, для простоты, мы свели задачу исследования шахматной игры к задаче исследования белой игры. При белой игре шахматная партия представляет собой последовательность позиций, в каждой из которых ход принадлежит белым. Если все позиции перенумеровать в порядке их возникновения с помощью целых чисел 1 (начальная позиция), 2, 3, ..., то позиции 1, 3, 5, ... возникают перед первым из шахматистов, а позиции 2, 4, 6, ... - перед вторым.

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

Теперь покажем, что количество различных между собой позиций на шахматной доске конечно. Под позицией мы будем понимать расположение фигур на доске, снабженное, если это может быть нужным для выбора хода, некоторой дополнительной информацией Именно информацией о возможности взятия пешки на проходе и о возможности рокировки для каждого из играющих. Сразу подчеркнем, что нас интересует лишь сам факт конечности множества шахматных позиций и не интересует их число. Нужный нам результат можно получить следующим образом.

Введем следующий способ кодирования произвольной шахматной позиции. Шахматную доску будем изображать в виде последовательности 64 символов, каждый из которых соответствует одной из клеток шахматной доски. При этом, если некоторая клетка является пустой, то соответствующий ей символ должен быть нулем, а если на этой клетке расположена некоторая фигура (безразлично какая), то указанный символ должен быть единицей. Таким образом, шахматная доска представлена в виде строки из 64 нулей и единиц. Нужно теперь только добавить информацию о том, что за фигуры стоят на местах, изображенных в виде единиц, и двигались ли короли и ладьи, а также имеется ли возможность взятия какой-либо пешки на проходе. Примем следующие обозначения:

Дальнейшее построение кода позиции выполним так. Будем двигаться по строке, изображающей шахматную доску, слева направо и каждый раз, встречая единицу, будем справа от имеющейся строки приписывать четверку цифр, обозначающую шахматную фигуру. Процесс закончим, достигнув самой правой цифры в изображении доски (т. е. 64-й, если считать слева направо). К полученной строке, если это не вытекает из расположения фигур, добавим справа одну цифру, характеризующую возможность рокировки для черных (0 - если не возможна, 1 - если возможна), и, если нужно, одну цифру, характеризующую возможность рокировки для белых (опять же 0 - если не возможна, 1 - если возможна). Построение кода, изображающего позицию, закончено.

Наибольшее число символов содержит код позиции в начальный момент игры: 194. В процессе игры число символов либо остается неизменным, либо уменьшается по мере того, как фигуры покидают доску и играющие лишаются прав рокировки. Наименьшая возможная длина кода позиции равна 72, когда на доске остаются лишь два короля. Условимся в тех случаях, когда код содержит менее чем 194 цифры, дополнять его справа соответствующим числом нулей для того, чтобы, его длина всегда равнялась 194.

Мы видим, что любую позицию можно закодировать в виде строки, состоящей из 194 нулей и единиц. Однако не все подобные строки являются изображениями позиций, например строки, являющиеся кодами расположений фигур, при которых короли обеих сторон находятся под шахом или под матом. Следовательно, число шахматных позиций меньше (и значительно), чем число всевозможных строк из нулей и единиц, имеющих длину 194. А число таких строк, как легко подсчитать, равно 2¹⁹⁴. Тем самым доказано, что число шахматных позиций конечно потому, что оно не превосходит хоть и большого, но вполне определенного числа.

Читатель может подумать, что учтенная нами дополнительная информация недостаточна для того, чтобы иметь возможность выбрать ход, так как нужно еще знать, не входит ли данное расположение фигур в серию расположений, которая уже повторялась один или два раза. Ответим на это, что при правильной игре, ведущей по кратчайшему пути к выигрышу, повторение серий расположений не может иметь места и потому для нашей цели подобная информация излишня.

Итак, мы убедились, что количество возможных шахматных позиций конечно. Это значит, что оно потенциально перечислимо (хотя реально их перечислить и невозможно: их так много, что на перечисление ушли бы многие годы).

Выполним теперь (конечно, лишь мысленно) следующий процесс. Отберем все позиции, содержащие мат белым, и отнесем их к классу 0. Далее отберем все позиции, позволяющие при ходе белых сделать мат черным, и отнесем их к классу 1. При белой игре для каждой позиции класса 1 существует хотя бы один ход, превращающий ее в позицию класса 0. Потом отберем все позиции, которые при любом ходе белых превращаются в позиции класса 1, и отнесем их к классу 2. Продолжаем этот процесс, пока он не прекратится из-за того, что просмотрены уже все возможные позиции. При этом, каждый раз формируя класс с нечетным номером, будем включать в него все позиции, каждая из которых допускает только ходы, ведущие к позициям, принадлежащим уже сформированным классам с четными номерами. Отбирая позиции в класс с четным номером, будем включать в него все позиции, каждая из которых допускает хотя бы один ход, ведущий к позиции класса, имеющего номер, на единицу меньший, чем номер формируемого класса. После окончания описанного процесса (обозначим наибольший полученный при этом номер класса через М) останется некоторое количество позиций, не вошедших ни в один из классов (например, позиции, содержащие пат белым и некоторые другие). Эти оставшиеся позиции отнесем к классу М+1.

Из самого способа классификации видно, что если перед шахматистом возникла позиция, принадлежащая классу с нечетным номером n (n≤М), то при правильной игре он выиграет за n полуходов (если противник тоже будет играть наилучшим образом) или даже быстрее. Наилучшим ходом при этом будет любой ход, в результате которого для противника возникнет ситуация, входящая в класс номер n-1 (четный). Если перед шахматистом возникла ситуация с четным номером m (m≤М), то при правильной игре противника выигрыш невозможен. Наилучший ход позволяет проиграть за наибольшее число полуходов. Если же возникла позиция из класса с номером М+1, то наилучшим будет ход, который ведет к позиции того же класса, т. е. сохраняет ничейную ситуацию. Заметим, что в каждой позиции наилучших ходов может быть и несколько.

Теперь легко представить себе правило наилучшей игры в шахматы. Оно и является искомым алгоритмом точной игры в шахматы. Вот этот алгоритм.

1. Просмотрев классы позиций, начиная с класса 0, найти свою позицию. По номеру класса, к которому она относится, мы заранее узнаем возможный исход партии.
2. Перебрав возможные ходы, найти наилучший (т. е. при позиции класса М+1, ведущей к позиции того же класса, а при позиции всякого другого класса - к позиции класса, номер которого на единицу меньше).

Пользуясь указанным правилом, Вы будете играть наилучшим образом.

Мы видим, что само правило игры весьма просто, но число позиций, которые необходимо сначала рассортировать, а затем просмотреть, является числовым гигантом. Но нельзя ли, видоизменив и, может быть, усложнив это правило, сделать его реально осуществимым? Поставленная таким образом проблема относится к области равносильных преобразований алгоритмов и является уже не шахматной, а математической проблемой.

После того, как получен хоть какой-нибудь алгоритм точной игры в шахматы (а нам удалось получить, но, к сожалению, неэффективный), его преобразования уже не требуют искусства шахматиста. Существует путь, идя которым, можно имеющийся алгоритм преобразовывать в другие алгоритмы, дающие решение той же самой задачи. Этот путь заключается в следующем. Алгоритм точной игры нужно записать на формальном алгоритмическом языке, для которого разработаны правила формальных равносильных преобразований. В настоящее время такие правила разработаны для алгоритмического языка, получившего название языка логических схем (коротко ЯЛС). Этот язык возник в теории программирования как результат развития операторного метода, созданного в 1953 г. выдающимся советским математиком член.-корр. АН СССР А. А. Ляпуновым. На языке логических схем алгоритм точной игры в шахматы можно записать в виде строки специальных символов. Правила равносильных преобразований алгоритмов, заданных на ЯЛС^*, имеют вид формул. Каждое применение формулы превращает имеющуюся строку символов в новую строку, также являющуюся записью алгоритма, причем алгоритма, который равносилен исходному. Выполняя одно или несколько преобразований, мы можем получать разные, но равносильные между собой алгоритмы точной игры в шахматы. Некоторые из них могут быть "лучше", а другие "хуже", чем исходный алгоритм. Нашим критерием качества является эффективность. По существу, этот критерий сводится к тому, чтобы, во-первых, необходимый при выполнении алгоритма объем запоминающих устройств не превосходил объема запоминающих устройств используемой ЭВМ и, во-вторых, время, расходуемое на выполнение алгоритма, не превышало допустимого (например, было не больше 3 мин. 45 с, что обеспечивает установленные нормы: 2,5 ч на первые 40 ходов каждой стороне и по одному часу на каждые последующие 16 ходов).

^* (Язык логических схем и правила равносильных преобразований алгоритмов, заданных на нем, описаны в книге Н. А. Криницкого "Равносильные преобразования алгоритмов и программирование", М., "Сов. радио", 1970.)

Обозначим через V₀ объем запоминающих устройств машины. Можно считать, что из двух алгоритмов тот лучше, который требует меньшего объема запоминающих устройств, если хотя бы один из них требует объема запоминающих устройств большего, чем V₀. Если же требуемые объемы запоминающих устройств одинаковы или оба они не превосходят V₀, то из двух алгоритмов тот лучше, который требует меньшего времени. Наша задача состоит в том, чтобы выбрать такую цепочку преобразований, после выполнения которой будет получен эффективный алгоритм. Правда, возникает опасение, что описанный выше неэффективный алгоритм никак нельзя преобразовать в эффективный. Но всякая работа, если она выполняется в первый раз, связана с риском; кроме того, переходя к более подходящей по своим операционным возможностям машине, мы всегда получаем дополнительные возможности улучшения алгоритма.

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

Ответ на этот вопрос дать нетрудно, потому что для одной игры, которой многие увлекались, такой алгоритм был найден. Мы имеем в виду игру "такен", известную также как игра в пятнадцать^*, изобретенную знаменитым составителем шахматных задач Сэмюэлем Ллойдом. Увлечение ею достигло своего апогея в 1880 г.; за решения отдельных возникающих в ней задач назначались крупные денежные премии (до 1000 долл.). Но вскоре, после появления математической теории этой игры и составления алгоритма наилучшей игры, интерес к игре в пятнадцать упал, чтобы никогда не возродиться. Значит, если будет найден эффективный алгоритм точной игры в шахматы, интерес к шахматам исчезнет? Безусловно! Но человек, который создаст этот алгоритм, войдет в историю человеческой культуры. Могут сказать, что его слава будет славой Герострата^**. По нашему мнению, такая оценка неверна. Герострат не много сделал. Он уничтожил сделанное другими. Изобретатель же точного алгоритма игры в шахматы ничего не уничтожит. Он научит всех делать то, чего сейчас не может делать никто: вести точную игру в шахматы.

^* (Игра в пятнадцать описана в книге Я. И. Перельмана "Живая математика", см. например, изд. 10-е, "Наука", 1974.)

^** (Герострат, желая прославиться, в 356 г. до н. э. сжег в Эфесе храм Артемиды, выдающееся произведение античного искусства.)

Представим себе на минуту, что некто овладел эффективным алгоритмом точной игры в шахматы. Если бы алгоритм был настолько хорош, что его можно было выполнять в уме, этот некто мог бы выступить в роли шахматиста и в результате последовательных участий в ряде матчей и турниров завоевать шахматную корону. После этого он мог бы сам себя развенчать. Но как! Это развенчание было бы более блистательным, чем пожизненное сохранение шахматной короны.

Мы видим, что стать создателем точной игры в шахматы очень заманчиво. Но все же, настолько ли заманчиво, что найдутся люди, которые захотят тратить свой досуг и усилия на его разработку? На этот вопрос ответить трудно. Но можно опять сослаться на историю. Теперь уже на историю одной из математических проблем. Имеется в виду так называемая великая теорема Ферма, сформулированная еще в XVII в. и полностью не доказанная (и не опровергнутая) по сей день^*. Многие сотни людей (в своем большинстве не специалисты в области математики) потратили годы своей жизни на попытки доказать эту теорему. Некоторыми из них руководили научные интересы, но многих соблазняла денежная премия (в размере 100 000 марок), назначенная тому, кто первым даст доказательство этой теоремы (заметим, между прочим, что эта премия в конце концов была аннулирована). Если ради ста тысяч марок многие не жалели ни труда, ни времени, то, может быть, найдутся

^* (См. Курант Р. и Робине Г. Что такое математика, изд. 2-е. М., "Просвещение", 1967, с. 67.)

и энтузиасты, которые будут готовы потрудиться ради более благородной цели.

Вернемся теперь к основной нашей теме - к теме данной книги. Ботвинник не ставит перед собой цели создать алгоритм точной игры в шахматы. Он хочет переложить на точный язык команд машины свой собственный метод игры в шахматы. На его работу можно взглянуть по крайней мере с двух точек зрения. Одна из них - это точка зрения шахматного мастерства. Ведь Ботвинник - один из крупнейших шахматистов нашего столетия. Пользуясь своим методом, он не раз одерживал победы. Вторая точка зрения позволяет понять трудность задачи, которую поставил перед собой Ботвинник. Эта трудность сравнима с трудностью, которую испытал бы человек, который умеет правильно говорить, но не знает грамматики и приступает к ее составлению (правда, в наша время такие задачи стали легче, чем были когда-то, ко все же они очень трудны).

Ботвинник вводит понятие неточной задачи, понимая под этим каждую задачу, для решения которой нужно произвести переработку столь большого количества информации, что при существующих средствах эта переработка реально не может быть выполнена. Задачу определения хода в заданной шахматной позиции он и относит к числу неточных. Анализируя понятие неточной задачи, М. Ботвинник приходит к выводу, что невозможность произвести переработку информации равноценна отсутствию определенной ее части. Исходя из этого, он предлагает своеобразный подход к решению таких задач, названный им методом горизонта. Метод горизонта заключается в том, что учитываемая при решении задачи информация ограничивается (мы видим окружающий нас мир только до горизонта). Одна-но, если при анализе информации мы переходим от одних ее частей к другим, учитываемая информация становится другой (горизонт перемещается). Характерным при метода горизонта является то, что в состав учитываемой информации включается именно та ее часть, которая наиболее существенна при решении задачи. При каждом конкретном применении метода горизонта определение понятия горизонта производится вполне естественным способом. При решении шахматной проблемы под горизонтом понимают заданное число полуходов.

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

Рассматривая класс неточных задач, М. Ботвинник, по существу, затрагивает проблематику новой научной дисциплины, известной под названием теории сложных систем. При изучении многих реальных систем некоторые из них удается описать с помощью алгоритма. Делается это так: внешние воздействия на систему и ее ответы на них изображаются в виде наборов чисел, а действия системы описывают в виде алгоритма, точного правила, позволяющего по данным внешним воздействиям вычислить отвечающую им реакцию системы. Если это удалось сделать, то алгоритм, описывающий действия системы, является математическим описанием самой системы.

Систему, описанную в виде алгоритма, можно автоматизировать, заменить ее комплексом машин, управляемых с помощью ЭВМ. Однако это возможно только при условии, что полученный алгоритм эффективен, не требует при современном уровне техники слишком большого расхода времени или слишком много места в запоминающих устройствах. Когда речь идет о реальных системах, а не просто о решении задач, то выполнение алгоритма может быть связано также с расходованием каких-нибудь ресурсов, отличных от времени и объема запоминающих устройств, например с расходованием энергии (машинами, управляемыми с помощью нашего алгоритма), материальных средств. Поэтому можно сказать, что сложной системой называется алгоритм, выполнение которого требует большего расхода ресурсов, чем предназначено для этой цели. Основной задачей теории сложных систем является задача построения системы, которая, не являясь сложной, по своим результатам близка к рассматриваемой сложной системе. Легко видеть, что введенные Ботвинником в рассмотрение неточные задачи сродни сложным системам. Метод горизонта является одним из методов решения основной задачи теории сложных систем. Ботвинник рассматривает задачу определения хода при заданной шахматной позиции как сложную систему.

Но такой подход к решению проблемы делает удобным для изложения ее идей применение языка кибернетики. В соответствии с этим первую часть своей книги Ботвинник посвящает рассмотрению структуры систем, которые он называет полными системами управления. Проблему шахматной игры, которая в нашей терминологии является сложной системой, он сводит к несложной системе, достаточно близкой (по его мнению) к ней по своим результатам. При этом шахматы рассматриваются как иерархическая полная система управления, имеющая три уровня. На нижнем уровне этой системы находятся фигуры, каждая из которых действует на некоторой траектории и имеет свою цель игры, следующий уровень образуют группы фигур, взаимодействующие в так называемых зонах игры и преследующие свои цели. Высшим уровнем системы является совокупность всех фигур. Этой совокупности соответствует общая главная цель. Цели, преследуемые на всех трех уровнях, определенным образом согласованы, причем цели более низкого уровня имеют подчиненное значение по отношению к целям более высокого уровня. Для шахмат содержанием целей на всех трех уровнях является стремление выиграть материал. Анализ целей, стоящих перед полной системой управления и ее составными частями, М. Ботвинник вполне основательно считает одной из важнейших проблем при создании алгоритма шахматной игры, что и подчеркивает названием данной книги.

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

Как известно, еще в 1949 г. американским математиком Клодом Шенноном были высказаны основные соображения о возможности машинной игры в шахматы. Идея игры в общем сводилась к тому, чтобы на глубину, равную некоторому выбранному числу полуходов, просмотреть все возможные свои ходы, на каждый из них - все возможные ответы противника и т. д. При этом используется некоторая функция, присваивающая каждой возникающей позиции некоторую цену. Такая функция называется оценочной. В качестве наилучшего выбирается такой ход, который после конца перебора позволяет прийти к позиции, имеющей наибольшую цену, при условии, что противник каждый раз так отвечает на наши ходы, что оценочная функция при этом к концу перебора получает, поскольку это от него зависит, как можно меньшее значение. Легко видеть, что при таком алгоритме охватываются все фигуры, стоящие на доске, и анализу подвергаются все ходы, как представляющие собой интерес, так и заведомо бесполезные Шеннон отмечал, что полный перебор всех возможных ходов требует чрезмерного расхода машинного времени и высказал пожелание, чтобы будущие разработчики шахматных программ применяли какие-нибудь методы, суживающие область перебора путем исключения из рассмотрения заведомо бессмысленных ходов.

Таким образом, Шеннон предложил строить шахматные программы на следующих трех китах: 1) перебор ходов на заданную глубину; 2) оценочная функция позиций; 3) ограничение области перебора. Все известные до настоящего времени шахматные программы покоятся на этих китах. Самым капризным из этих китов оказался третий. До сих пор нет ни одного метода ограничения области перебора, который бы вместе с бессмысленными ходами не исключал из рассмотрения и самые ценные. Второй кит (оценочная функция) тоже подводит. Шеннон рекомендовал саму идею оценочной функции. Конкретную оценочную функцию он предложил всего лишь в качестве наводящего примера. Но до сего дня ничего лучшего, чем эта, приведенная в качестве примера функция, не придумано. А эта функция определяет цену позиции в зависимости от ряда факторов, каждый из которых в большинстве случаев (как это следует из учебников шахматной игры) способствует успеху, но далеко не всегда! Такая оценочная функция не работает в эндшпиле и, как утверждают шахматисты, не подтверждается анализом партий мастеров шахматной игры. Правда, сама по себе идея оценочной функции, без сомнения, правомерна. Если читатель согласен с тем, что среди возможных позиций есть худшие и лучшие, то он тем самым признает существование оценочной функции, которая имеет тем большее значение, чем лучше оцениваемая позиция. Но, наверное, оценить позицию не так-то просто. Что же касается разработчиков шахматных программ, то им мы пожелаем побольше фантазии и посоветуем увеличить творческие усилия.

Отметим, что и у первого кита есть ахиллесова пята. Перебор дает тем лучшие результаты, чем больше его глубина. Но с увеличением глубины сильно возрастает время перебора. Тем не менее этот кит надежен.

В чем же отличие метода Ботвинника от метода, предложенного Шенноном? Прежде всего в том, что у Ботвинника нет статической функции, оценивающей позиции. В его концепции основу составляют не позици, а траектории. Каждая траектория "пронизывает" большое число позиций. Искомый ход выбирается по одной из траекторий. Руководством для выбора хода является цель игры. Перебор возможных ходов имеется и у Ботвинника, но каждый ход является не столько шагом, ведущим от одной позиции к другой, * сколько движением по траектории, которое наиболее способствует достижению цели игры.

Некоторые математики, знакомившиеся с методом Ботвинника, считают этот метод лишь новой реализацией идей Шеннона. Выбор траекторий они оценивают как удачный способ отбрасывания бессмысленных ходов, т. е. как способ ограничения области перебора. Анализ действий на траекториях они хотят рассматривать как перебор ходов, имеющих смысл. Выбор хода, наилучшим образом соответствующего цели игры, они представляют как выбор с помощью функции, определяющей цену позиции, но заданной в замаскированном виде. Отчасти это так, но все же против такой "прокрустации" нужно категорически возражать. Если основными элементами структуры метода Шеннона являются позиции, которые можно условно представить себе в виде различных между собой поверхностей, то основными элементами структуры метода Ботвинника являются траектории и их пучки, которые можно представлять себе линиями, ортогональными поверхностям - позициям.

Сказанное не означает, что после соответствующих исследований нельзя построить алгоритм шахматной игры, основанный на методе Шеннона и эквивалентный алгоритму Ботвинника. Но я не вижу реально осуществимого способа для выполнения такой работы и в то же время отчетливо вижу, что алгоритм Ботвинника не является алгоритмом, основанным на методе Шеннона.

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

Хорошо, скажет читатель, предположим, что алгоритм Ботвинника уже завершен и что программа шахматной игры уже готова. Что же мы имеем? Законный вопрос.

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

Пожелаем Ботвиннику и его соратникам успешно завершить начатую ими и уже далеко продвинувшуюся большую работу.

Н. А. Криницкий.