Сегодня я расскажу об игре, чьё название совпадает с названием одного французского райцентра, и которую можно назвать прародительницей многих игр. А ещё она была одним из героев культового кино, и век назад был разработан алгоритм выигрыша в неё. И надо бы уточнить, что название игры совпадает с названием французского города на русском языке. По-французски они пишутся по-разному.

Есть две разные, хоть и достаточно схожие игры. Считается, что одна из них пришла в Европу из Китая. Во всяком случае, отмечается её сходство с китайской игрой Jianshizi. И случилось это в 16 веке. Другой же мы обязаны человеку, которому много чем обязаны. Например, тем, что я написал «16 век» вместо «XVI век», но читатели меня поняли. Леонардо Фибоначчи известен не только рядом его имени (результатом решения «задачи о размножении кроликов»), но и введением в Европе арабских цифр. В первую очередь для облегчения ведения бухучёта. Возможно, и игра его служила той же цели. Правила очень просты. Два игрока поочерёдно выбирают цифры от 1 до 10 и называют сумму выбранного числа и всех предыдущих. Кто скажет 100, тот и выиграл.

Памятник Фибоначчи в Пизе и титульный лист книги Баше

Но эта игра осталась в тени других, более известных задач Фибоначчи, и популярна стала после выхода в 1612 году книги математика и поэта Клода Баше (Claude Gasperd Bachet) «Занимательные числовые задачи». Правда, и название она обрела в честь популяризатора — сейчас игра называется «Баше». И играют в неё не на возрастание, а на убывание. Есть кучка объектов, каждый берёт от 1 до 3, кто взял последний — тот выиграл. Ну или проиграл, но о вариантах позже.

Первая же игра, придя из Китая в 16 веке, известное нам название получила только в 20 веке. Одновременно с доказательством того, что у неё есть выигрышная стратегия.  И то, и другое в 1901 году сделал Чарльз Бутон (Charles Bouton).  Есть версия, что NIM — это WIN, прочитанное вверх ногами. От «Баше» игра отличается тем, что здесь у нас несколько кучек. Брать можно лишь из одной за ход, зато неограниченное количество элементов. Алгоритм же победной игры очень прост, но требует счёта в уме в двоичной системе счисления. Не случайно «Ним» в 1952 году стал одной из первых компьютерных игр. И, присвоив себе право первого хода, компьютер всегда выигрывал у человека.

Математики очень любят эту игру за то, что она является игрой с полной информацией. Т.е. нет никакого рандома, в любой момент игры игроки обладают полной информацией о состоянии игры и всех возможных изменениях этого состояния. И в 30-х годах независимо друг от друга два математика — Шпраг и Гранди — разработали теорию Шпрага-Гранди, что все игры с полной информацией можно свести к «Ниму», т.е. доказать, какой будет исход при оптимальной игре обоих игроков. Извините, математический аппарат теории мне понять несколько сложновато, поэтому пересказать не смогу. А если образно, то можно построить граф, где узлами будут возможные состояния игры, а векторами — ходы игроков. И, проанализировав граф от любого узла вниз, можно определить оптимальный переход из этого узла. Так что, если я правильно понял идею теории, то должен цинично заявить, что какой-то миллион-другой лет, и игры типа шахмат, шашек, го и т.д. обречены.

Популярности игры не только среди математиков способствовал выход фильма «Прошлым летом в Мариенбаде», обладатель Золотого льва Венецианского фестиваля 1961 года. Я не знаю, что сказать про фильм, разве что сказать, что выйди он сейчас, фильм бы обязательно попал в «Закрытый показ» Гордона. После полутора часов просмотра зритель так и не понимает, что же на самом деле произошло прошлым летом. Зато знакомится с игрой, которая играет важную роль в сюжете:

— Я знаю игру, в которую всегда выигрываю.

— Если Вы не можете проиграть, то это не игра.

— Могу, но не проигрываю.

— Давайте сыграем.

И всю 79-ю минуту фильма герои играют в «Ним». А зрители вокруг стола обсуждают партию и кто-то произносит абсолютно верную фразу: «Надо знать финт, тогда будешь выигрывать». Я решил выписать ходы игроков, чтобы не заставлять читателей смотреть фильм.

• Первый даёт второму возможность сделать ход за него: 1-3-5-6.
• Ход второго игрока: 1-3-3-6 (знал бы он алгоритм, убрал бы одну карту).
• Первый игрок: 1-3-3-1 (А вот это ход по алгоритму. И поэтому — победный).
• Второй игрок: 1-1-3-1.
• Первый игрок: 1-1-0-1.
• Второй тянет руку, останавливается и говорит: я проиграл.

Тут надо писать статью о «Ниме», чтобы заметить, что они играют не в классический «Ним», а в «Ним-мизер». Т.е. тот, кто берёт последним, проигрывает. Как ни странно, но победный алгоритм большую часть игры аналогичен обычному «Ниму», меняется он только в эндшпиле, последний ход первого игрока — это как раз изменение алгоритма. Играли бы они по обычным правилам, он бы взял не 3, а 2 карты — и опять бы выиграл.

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

• Стартовая расстановка: 001 XOR 011 XOR 101 XOR 111 = 000. Т.е. хода, ведущего к победе, у первого игрока нет, поэтому можно безнаказанно предлагать противнику сделать ход за тебя.
• После первого хода: 001 XOR 011 XOR 110 = 001. Второму игроку надо было забирать не 2, а 1 карту из любого ряда с нечётным количеством.
• После второго хода: 001 XOR 011 XOR 011 XOR 110 = 101. Первый игрок делает единственно возможный ход — забирает 5 карт из последнего ряда.
• После третьего хода: 001 XOR 011 XOR 011 XOR 001 = 000. Всё, второй игрок обречен.

При игре в «Ним-мизер» алгоритм меняется в тот момент, когда в каждом ряду остаётся не более одного объекта. Теперь 0 в конце хода ведёт к проигрышу.

Итак, обобщая. Игры класса «Ним» — это игры, где на начало игры есть несколько кучек объектов, игроки поочерёдно должны взять из одной от X до Y объектов. Брать обязательно. Кто берёт последний, тот или выигрывает, или проигрывает, в зависимости от договорённости на начало игры. Если куча одна, X=1, Y=3 — это «Баше». Если куч несколько, X=1, Y=бесконечности, то это классический «Ним».

Ну а производных вариантов от этих игр — бесконечное множество. Среди математических игр, например, можно упомянуть:

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

Но нам более интересны настольные игры, чьи корни надо искать в «Ниме». Их можно разделить на две части — те, в которых убрали полноту информации, и те, которые в разной степени замаскировали своё родство.

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

Первая игра достаточно любима в моей семье. Это «Лобо 77», выпущенная «Амиго» в 1993 году. Игроки набирают по 5 карт, поочерёдно выкладывают карту в общую колоду и добирают новую. Проигрывает тот, кто делает сумму очков в колоде больше 77. Или если сумма делится без остатка на 11. Т.е. родство с «Баше» заметно невооружённым взглядом.

Автор игры Томас Паули кроме «Лобо» известен также играми:

• «Да Капо» — коммерческая версия карточной игры «Злоба и ярость»,
• «Соло» — коммерческая версия карточной игры «Мау-мау»,
• «Король Артур» — переделка игры Trumpet.

Да, у него в активе 4 игры. И если про 3 из них мне известно, что его вклад, так сказать, частичный, то и у четвёртой вполне мог быть промежуточный источник между книгой Баше и придумкой игры.

Несмотря на то, что «Амиго» до сих пор выпускает «Лобо», в 2006 году Ричард Джеймс, владелец издательства Evertide Games, выпускает под своим именем игру Straw. Которая отличается от «Лобо» по большому счёту лишь дизайном. А более крупное издательство AEG покупает права на эту игру. Зачем-то.

Более интересна вторая ветвь потомков, где полнота информации осталась. Но что игры решаемы —игрокам не сразу очевидно. И начнем мы с Бруно Файдутти, автора многих игр, из которых не так много на слуху. Вот и игра «Вавилон» среди тех, которые не очень известны.

Вся игра — это 12 фишек, по 3 штуки 4 разных цветов. В свой ход игрок может объединить две стопки фишек (на начало игры в каждой стопке по фишке), если верхние фишки совпадают по цветам или обе стопки одинакового размера. Проигрывает тот, кто не может сделать ход.

Вторая игра выпущена тем же издательством, что издавало «Вавилон», совсем недавно, поэтому хорошо известна нашим игрокам.

Это игра «22 яблока». Игроки по определённым правилам собирают яблоки с поля. Выигрывает тот, кто либо соберёт сам нужное число яблок, либо вынудит соперника сделать ход с перебором.

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

Игра с очень неудачным названием Colors. Придумана гейм-дизайнером Эннио Пересом, автором единственной игры. Выпущена в 1990 году маленьким итальянским издательством, которое в основном занимается покером и тому подобными вещами. И сейчас я на сайте издательства вообще не нашёл этой игры.

Правила просты. У нас есть поле 7х7 и по 7 фишек семи разных цветов, которые выкладывают на поле. В свой ход можно снять от 1 до 4 фишек, лежащих подряд по вертикали, горизонтали или диагонали. Когда поле разобрано, каждый игрок получает по 1 победному очку за цвет, в котором у него чётное число фишек. И на мой взгляд, вот это конечное изменение цели игры делает партии в «Колорс» напряжёнными и интересными до последнего хода. Ну и думаю, что её не так-то и просто просчитать в уме.