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

ДЕРЕВО ИГРЫ «НИМ»

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

Но кто?

Оказывается, дерево может нам сказать и это.

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

А если есть всего один камень? Тогда у меня только один вариант. Я беру камень и выигрываю. Поэтому я пишу букву В над каждой такой позицией.

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

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

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

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

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

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