Даглас Хофштадтер - ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда

Классическим примером рекурсивной процедуры с параметрами может служить программа для выбора лучших ходов в шахматной партии. Лучшим ходом можно, по-видимому, считать тот, что оставляет противника в наихудшей ситуации. Таким образом, проверка лучшего хода весьма проста: представьте себе, что вы сделали ход… а теперь мысленно переверните доску и оцените позицию с точки зрения вашего противника. Но каким образом оценивает позицию ваш противник? Он ищет свой лучший ход. Это значит, что он мысленно перебирает все возможные варианты и оценивает их, как ему кажется, с вашей точки зрения, надеясь, что вы найдете их опасными для себя. Обратите внимание, что мы определили «лучший ход» рекурсивно: то, что лучше для одного противника, хуже для другого. Рекурсивная процедура, занятая поисками лучшего хода, пробует один ход за другим и каждый раз вызывает саму себя в качестве противника ! В этой роли она пробует следующий ход, и вызывает себя в качестве противника противника — то есть, снова себя самой.

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

В программах подобного «игрового» типа, каждый анализируемый ход порождает «дерево анализа вариантов», где сам ход является стволом, возможные ответы — основными ветвями, контр-ответы — ветвями потоньше, и так далее. На рис. 38 я показал простое дерево анализа, иллюстрирующее начало игры в крестики-нолики. Существуют способы, позволяющие избежать анализа каждой ветви до конца. В искусстве выращивания шахматных деревьев лидируют люди, а не компьютеры. Известно, что лучшие игроки просчитывают варианты на относительно небольшое число ходов, в сравнении с компьютером — и играют при этом намного лучше! В начале развития компьютерных шахмат считалось, что не пройдет и десяти лет, как компьютер (или программа) станет чемпионом мира. Однако, эта цель не достигнута и по сей день… Это может служить еще одним подтверждением очень рекурсивного

Закона Хофштадтера:

На любое дело требуется больше времени, чем казалось в начале, даже если вы учитывали при этом закон Хофштадтера.

Рис. 38. Разветвляющееся дерево ходов и контрходов в начале игры в крестики и нолики.

В чем связь между рекурсивными множествами предыдущей главы и рекурсивными процедурами этой главы? Ответ на этот вопрос затрагивает понятие рекурсивно перечислимых множеств. Чтобы множество было р.п., оно должно быть получено на основе начальных точек (аксиом) при помощи повторного применения правил вывода. Таким образом, множество растет и растет, и каждый новый элемент так или иначе составлен из предыдущих — что-то вроде «математического снежного кома». Но ведь это и есть основа рекурсии: вместо явного определения нечто определяется через более простые версии себя самого. Числа Фибоначчи и Лукаса — превосходные примеры р.п. множеств, вырастающих из двух данных элементов до бесконечности путем применения рекурсивного правила. По соглашению, множество, чье дополнение также р.п., называется «рекурсивным».

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

Ахилл и Черепаха только что доели превосходный ужин на двоих в лучшем китайском ресторане города.

Ахилл : Здорово вы управляетесь с палочками, г-жа Ч.

Черепаха : Приходится — я с детства питаю слабость к восточной кухню. Как насчет вас, Ахилл — вам понравилось?

Ахилл : Еще как! Я никогда раньше не пробовал китайской еды, и сегодняшний ужин был приятным знакомством с ней. А сейчас, если вы не торопитесь мы можем еще немного посидеть и поболтать.

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

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

Черепаха : Боюсь, что нет. Что это такое?

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

Черепаха : Такая краткость — всего семнадцать слогов — но где же здесь смысл?

Ахилл : Смысл живет также в голове читателя — не только в хайку.

Черепаха : Гм-м-м… Это утверждение наводит на размышления.

(Подходит официант со счетом, чайничком, полным чая, и парой печений «с сюрпризом» — бумажкой, на которой написана судьба едока.)