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

Вот так на данный момент выглядит наше дерево.

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

Вы выигрываете, когда ваш противник вынужден проиграть. Звучит как мотивационный плакат в спортзале, но на самом деле это математика. На языке деревьев это означает следующее: «Обозначайте позицию буквой В, если в ней существует ветвь, ведущая в позицию П». По тем же соображениям обозначайте позицию буквой П, если это не так. Ведь это означает, что при любом выборе вы оставляете оппоненту позицию В. Вы проигрываете, когда ваш оппонент может победить, что бы вы ни делали.

Все сводится к следующему.

ДВА ПРАВИЛА

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

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

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

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

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

, как это работает.

Метод дерева работает для игры «Ним» с большим количеством кучек и камней, то есть для всех вариантов игры. Хотите знать, кто выиграет с двумя кучками по 20 камней в каждой? Можете нарисовать большое дерево, спуститься по нему и выяснить это. (Побеждает Джефф.) Две кучки по 100 камней? (Все равно Джефф.) Одна куча из 100 камней, а вторая из 1000? (Здесь победит Акбар[199].) Более того, промаркированное дерево не просто говорит вам, кто победит, – оно показывает, как побеждать. Если вы находитесь в позиции В, то знаете, что как минимум один ход ведет в положение П, – сделайте его. Если вы в положении П, философски пожмите плечами, сделайте произвольный ход и надейтесь, что противник накосячит.

В случае, когда в игре «Ним» только две кучки, можно избежать утомительной маркировки всего дерева, применив более простой (и, честно говоря, более красивый) способ выяснить, кто победит, использующий симметрию левого и правого. Помните, насколько проще доказательство Паппа для моста ослов, основанное на симметрии, чем исходное евклидово? С «Ним» во многом то же. Предположим, что Акбар и Джефф начинают игру с двумя кучками по 100 камней в каждой. Хотите рисовать такое дерево? Я тоже не хочу. Поэтому есть способ получше. Думаю, вам знакома такая невероятно раздражающая ситуация, когда младший ребенок повторяет все за старшим? «Прекрати за мной повторять». «Прекрати за мной повторять». «Ты надоел». «Ты надоел». И так далее. Что ж, представьте, что Джефф выбрал такую тактику в игре. Что бы ни сделал Акбар, Джефф повторяет его действие на другой кучке. Акбар берет 15 камней из левой кучи, оставляя 85? Тогда Джефф берет 15 камней из правой; теперь в обеих кучах по 85 камней. Акбар переключается на правую кучу и забирает 17 камней, оставляя 68? Джефф делает то же самое с левой. Джефф всегда зеркально отражает действия Акбара, постоянно уравнивая стопки. В частности, Джефф никогда не сможет первым забрать всю кучу, потому что всего лишь повторяет действия Акбара. Поэтому Акбар первым покончит с одной из кучек, и тогда Джефф повторит это действие на другой кучке и выиграет. Следовательно, игра «Ним» с двумя равными кучами – это победа Джеффа. Его стратегия столь же непобедима, сколь и раздражительна.

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