Борис Бирюков - Жар холодных числ и пафос бесстрастной логики

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

Перефразируя выражение А. А. Маркова, заметим, что это, как-никак, веский аргумент. Пусть практика работы на ЭВМ насчитывает не 4000, а лишь 20— 25 лет, но какая это практика! Чего только ни делали с помощью ЭВМ — и составляли планы отраслей хозяйства, и находили выгоднейшие варианты перевозок, и играли в различные игры, но ни единого раза проблема, если она была четко поставлена, не упиралась в тот барьер, что для нее в принципе невозможно написать программу. Можно ли, однако, сказать, что все четко поставленные, но не решенные до сих пор на ЭВМ проблемы (или такие проблемы, относительно которых имеется уверенность, что их со временем можно поставить четко) просто ждут своей очереди: того дня, когда быстродействие и память «компьютеров» станут достаточно большими?

В качестве примера рассмотрим программирование на ЭВМ шахматной игры. Шахматы часто справедливо сравнивают с искусством, и для этой древней игры придумали даже свою «музу» — Каиссу. Широко известны многочисленные попытки моделировать процесс шахматного мышления на машине; их пока нельзя признать успешными, поскольку самые удачные шахматные программы значительно уступают мышлению хороших шахматистов. Каковы, однако, перспективы «машинных шахмат»?

Тезис кибернетики утверждает, что всякий детерминированный процесс, сущность которого можно объяснить человеку, потенциально осуществим машиной, то есть будет фактически выполнен на ЭВМ, которой предоставлено неограниченное время и которая имеет неограниченную память [4]. Первое условие можно переформулировать как условие достаточного быстродействия, поэтому данный тезис можно выразить еще и так: процесс, о котором сказано выше, всегда можно фактически выполнить на машине с достаточно высоким быстродействием и обладающей достаточно емким запоминающим устройством. Если бы такая машина существовала, то «шахматная проблема» давно была бы решена.

Программа для ее решения не представляет трудности; идея такой программы была выдвинута одним из основателей кибернетики Клодом Шенноном больше двадцати лет назад [5]. Соответствующий метод называется «построением дерева игры», и смысл его заключается в следующем. Выписываются все варианты первого хода белых; для каждого из них выписываются все пары ходов, состоящие из текущего первого хода белых и возможного, допустимого правилами игры ответного хода черных (то есть с каждым возможным ходом белых сопоставляются по очереди все возможные ходы черных, включая нелепые); затем с каждым ходом черных сопоставляются по очереди все возможные ходы белых и так далее. Если изобразить это на диаграмме, возникает ветвящееся «дерево» (отсюда и название метода). Ветви будут обрываться на ходах, ведущих к поражению одной из сторон или ничейным ситуациям.

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