WikiSort.ru - Комьютерные игры

Ним — математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет. В классическом варианте игры число кучек равняется трём.

Частный случай, когда кучка одна, но максимальное число предметов, которые можно взять за ход, ограничено, известен как игра Баше. Ним — конечная игра с полной информацией. Классическая игра Ним имеет фундаментальное значение для теоремы Шпрага-Гранди. Эта теорема утверждает, что обычная игра в сумму беспристрастных игр эквивалентна обычной игре в Ним. При этом каждой беспристрастной игре-слагаемому соответствует кучка Ним, число предметов в которой равно значению функции Шпрага-Гранди для игровой позиции данной игры.

История игры

Китайская игра ним упоминалась европейцами ещё в XVI веке. Имя «ним» было дано игре американским математиком Чарльзом Бутоном (англ. Charles Bouton), описавшим в 1901 году выигрышную стратегию игры. Существует несколько вариантов происхождения названия игры:

• от немецкого глагола nehmen или от староанглийского глагола Nim, имеющих значение «брать»;
• от английского глагола Win («побеждать») переворачиванием слова.

Игрушка «Доктор Ним», небольшой шариковый компьютер, придуманный в 1960-х, играл не в ним, а в игру Баше.

Стратегия игры

В общем случае рассматривается ${\displaystyle p}$ кучек предметов с ${\displaystyle N_{1},N_{2},\cdots N_{p}}$ предметами. Игроки ходят по очереди. Ход заключается в том, что игрок берёт из кучки ${\displaystyle i\in [1,p]}$ ${\displaystyle n\in [1,N_{i}]}$ предметов. Каждой позиции игры ставится в соответствие ним-сумма этой позиции — результат сложения размеров всех кучек в двоичной системе счисления без учёта переноса разрядов, то есть сложение двоичных разрядов чисел в поле вычетов по модулю 2: ${\displaystyle S=N_{1}\oplus N_{2}\oplus \cdots \oplus N_{p}}$

Выигрышная стратегия состоит в том, чтобы оставлять после своего хода позицию с ним-суммой, равной нулю. Она основана на том, что из любой позиции с ним-суммой, не равной нулю, можно одним ходом получить позицию с нулевой ним-суммой, а из позиции с нулевой ним-суммой любой ход ведёт в позицию с ним-суммой, отличной от нуля.

Пример: предположим, в игре три кучки, в них соответственно 2 (0010 в бинарном представлении), 8 (1000) и 13 (1101) предметов. Ним-сумма этой позиции — 7 (0111). Следовательно, выигрышная стратегия состоит в том, чтобы взять 3 предмета из третьей кучки — там останется 10 (1010) предметов, и ним-сумма позиции станет 0 (0000). Предположим, после вашего хода противник забирает все предметы из первой кучки — выигрышная стратегия будет заключаться в том, чтобы забрать 2 предмета из третьей кучки. В таком случае после вашего хода в кучках будет соответственно 0 (0000), 8 (1000) и 8 (1000) предметов, ним-сумма по прежнему будет равняться 0.

Варианты игры

В кино и телевидении

• Эта игра служит метафорой происходящего в фильме «В прошлом году в Мариенбаде»^[1].

См. также

• Функция Шпрага-Гранди
• Игра Баше
• Пешечная дуэль
• Хакенбуш

Примечания

Литература

• Болл У., Коксетер Г. Математические эссе и развлечения = Mathematical Recreations and Essays. — М.: Мир, 1986. — С. 47-51.
• Фомин С. В. Системы счисления. — 5-е изд. — М.: Наука, 1987. — С. 48.
• Гарднер М. Крестики-нолики. —М.: Мир, 1988. ISBN 5-03-001234-6.
• Jean-Paul Delahaye. Stratégies magiques au pays de Nim // Pour la science : Журнал. — Paris: Belin, 2009. — Т. 377, № 3. — С. 88-93.