Форма реальности. Скрытая геометрия стратегии, информации, общества, биологии и всего остального

ТРИ ПРАВИЛА

Первое правило: если каждый мой ход ведет в позицию В, то моя текущая позиция – П.

Второе правило: если я могу сделать ход, ведущий в позицию П, то моя текущая позиция – В.

Третье правило: если ни один мой ход не ведет в позицию П и не все мои ходы ведут в позицию В, то моя текущая позиция – Н.

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

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

Неудивительно, что никакой секретной стратегии для игры в крестики-нолики нет. Если оба игрока действуют идеально, неизменно получится ничья.

В математике так часто бывает. Вы сели решать одну задачу, а когда закончили (через день, месяц или год), понимаете, что одновременно решили еще несколько. Если у вас есть гвоздь и требуется изобрести для него молоток, то этим молотком можно будет забивать все, что похоже на гвоздь. Так происходит в большинстве случаев.

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

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

1. У первого игрока есть стратегия, которая всегда гарантирует ему победу.

2. У второго игрока есть стратегия, которая всегда гарантирует ему победу.

3. Каждая безошибочно сыгранная игра заканчивается вничью.

Мы можем выяснить эти стратегии, маркируя дерево буквами В, П и Н в соответствии с тремя правилами от листьев к корню. Это может потребовать много времени, но результат будет гарантирован.

Многие игры – это деревья. Английские шашки – дерево. «Четыре в ряд» – дерево. Шахматы – дерево. Да, даже шахматы! Мы считаем их своего рода романтическим искусством, способом передать дух сражения на маленькой деревянной доске. Что-то в этом есть. О них сняты фильмы, написаны романы и даже мюзикл, созданный бывшими участниками группы ABBA.

И тем не менее это дерево. Игроки ходят по очереди, случайностей нет, а игра не может длиться дольше 5898 ходов. Этот теоретический максимум никогда не появится в партии, где игроки действительно стремятся выиграть. Самая длинная из когда-либо сыгранных турнирных игр[214] состояла из 269 ходов и заняла чуть больше 20 часов.

Если вы не разбираетесь в шахматах, то можете задаться вопросом, почему число ходов ограниченно. Это ведь не «Ним», вы не теряете пешку или фигуру с каждым ходом. Почему бы ладье и коню не гоняться друг за другом на доске вечно? Причина в том, что в шахматах установлены правила, запрещающие это. Если за 50 ходов не было взятий или ходов пешкой, то партия признается закончившейся вничью. Такие правила обусловлены той же логикой, которая заставляет нас исключить 1 из перечня простых чисел. Если бы 1 было простым числом, то процесс разложения на множители мог бы продолжаться бесконечно: 15 = 5 × 3 × 1 × 1 × 1… Это не совсем неверно, но совершенно бессмысленно. Правило 50 ходов не позволяет шахматам двигаться по тому же унылому вечному пути[215].

Так что шахматы, несмотря на все легенды и загадочность, по сути, то же самое, что крестики-нолики или «Ним». При встрече двух идеальных игроков либо белые всегда выигрывают, либо белые всегда проигрывают, либо неизменно будет ничья. И в принципе вычисление, какой из вариантов будет реализован, – всего лишь вопрос продвижения по дереву до корня. Шахматы – это сложная задача, но не настолько, как написание стихотворения, отражающего[216] пересечение политики атомного века середины столетия с модернизацией городов, ностальгией по детству, бесконечными отзвуками Гражданской войны и заменой человеческого духа механизированными изобретениями, а в смысле перемножения двух действительно больших чисел. Это может занять много времени, но в принципе вы знаете, как постепенно, шаг за шагом справиться с задачей.

В принципе. Это словосочетание – маленький коврик, элегантно уложенный над бездонной пропастью трудностей!

Игра «Ним» с двумя кучками по два камня – проигрыш. «Четыре в ряд»[217] – победа. Но для шахмат мы не знаем, будет победа, поражение или ничья. Возможно, никогда и не узнаем. У шахматного дерева очень много листьев. Нам доподлинно неизвестно сколько, но уж точно больше, чем способен рассмотреть восьмифутовый робот. Клод Шеннон, которого мы оставили за созданием фальшивого английского текста с помощью цепей Маркова, также написал одну из первых серьезных работ[218] о машинных шахматах; по его оценке, количество листьев на этом дереве выражается числом, примерно состоящим из единицы и 120 нулей, – сто миллионов триллионов гуголов. Это не просто большое число, оно больше, чем количество чего-либо во Вселенной, и уж точно это не то количество вещей, которые вам захочется просмотреть и обозначить буквами В, П или Н. В принципе, конечно, можно, но в реальности – нельзя.

Это явление (вычисления, которые мы умеем делать, но не делаем за неимением времени) – минорный мотив, звучащий на протяжении всей истории математики компьютерной эпохи. Вернемся на секунду к разложению на простые множители. Мы уже видели, что это можно делать без особых размышлений. Если вы начинаете, скажем, с числа 1001, то вам нужно найти число, на которое 1001 делится нацело, а если такого нет, то 1001 – простое число. Годится ли 2? Нет, 1001 не делится пополам. А 3? Нет. А 5? Нет. А 7? Да, поскольку 1001 = 7 × 143. (Тысяча и одна ночь – это сто сорок три недели.) Теперь можно махать топором над числом 143, проверяя деление за делением, пока не обнаружим, что 143 = 11 × 13.

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

И это хорошо, поскольку в реальном мире, несомненно, есть нечто более ценное для вас, чья безопасность зависит от сложности этой задачи. Какое отношение факторизация чисел имеет к безопасности? Для этого нам нужно вернуться к криптографии конфедератов и книге экспериментальной поэзии в прозе Гертруды Стайн Tender Buttons («Нежные кнопки»).