Ним

Ним

Матчи, выстроенные в ряды для игры в Ним. Игроки по очереди выбирают ряд и убирают из него любое количество спичек.
Жанры	Математическая игра абстрактная стратегическая игра
Игроки	2
Шанс	Никто

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

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

Варианты ним существуют с древних времен. ^[1] Говорят, что игра возникла в Китае — она очень похожа на китайскую игру цзянь-шицзы (捡石子), или «собирание камней» ^[2] — но ее происхождение неизвестно; самые ранние европейские упоминания ним относятся к началу XVI века. Ее нынешнее название было придумано Чарльзом Л. Бутоном из Гарвардского университета , который также разработал полную теорию игры в 1901 году, ^[3] но происхождение названия никогда полностью не объяснялось. Оксфордский словарь английского языка выводит название из немецкого глагола nimm , означающего «брать».

На Всемирной выставке в Нью-Йорке 1939 года Westinghouse представила машину, Ниматрон , которая играла в ним. ^[4] С 11 мая по 27 октября 1940 года только несколько человек смогли победить машину за этот шестимесячный период; если им это удалось, им вручали монету с надписью «Чемпион Ним». ^[5] Это была также одна из первых в истории электронных компьютерных игр. Ферранти построил компьютер, играющий в ним , который был представлен на Фестивале Британии в 1951 году. В 1952 году Герберт Коппель, Юджин Грант и Говард Бейлер, инженеры из WL Maxson Corporation, разработали машину весом 23 килограмма (50 фунтов), которая играла в ним против человека и регулярно побеждала. ^[6] Была описана машина для игры в ним, сделанная из игрушек-тинкертоев . ^[7]

Игра в ним была темой колонки «Математические игры» Мартина Гарднера в журнале Scientific American за февраль 1958 года . Разновидность ним разыгрывается — и имеет символическое значение — во французском фильме Новой волны « В прошлом году в Мариенбаде » (1961). ^[8]

В Nim обычно играют как в игру misère , в которой игрок, взявший последний предмет, проигрывает. В Nim также можно играть как в игру «нормальной игры», в которой побеждает игрок, взявший последний предмет. В любой из этих игр — обычной или misère — когда есть ровно одна куча с по крайней мере двумя предметами, игрок, который берет следующим, может легко победить. Если это уберет либо все, либо все, кроме одного предмета, из кучи, в которой их два или более, то ни в одной куче не будет больше одного предмета, поэтому игроки вынуждены поочередно убирать ровно один предмет до конца игры. Если игрок оставляет четное количество ненулевых куч (как игрок сделал бы в обычной игре), игрок берет последний; если игрок оставляет нечетное количество куч (как игрок сделал бы в игре misère), то другой игрок берет последний.

Обычная игра — игра между двумя игроками, в которой используются три кучи с любым количеством предметов. Два игрока по очереди берут любое количество предметов из любой из куч. Цель — быть последним, кто возьмет предмет. В игре misère цель — заставить противника взять последний оставшийся предмет.

Следующий пример обычной игры разыгрывается между вымышленными игроками Бобом и Алисой , которые начинают с кучками из трех, четырех и пяти предметов.

Практическая стратегия победы в игре ним заключается в том, чтобы игрок поставил другого в одну из следующих позиций, и каждый последующий ход должен быть в состоянии сделать одну из меньших позиций. Только последний ход меняется между misère и нормальной игрой.

Для обобщений n и m могут иметь любые значения > 0, а также они могут быть одинаковыми.

Нормальный ним (или, точнее, система нимберов ) является основополагающим принципом теоремы Спрага–Гранди , которая по сути утверждает, что в нормальной игре каждая беспристрастная игра эквивалентна куче ним, которая дает тот же результат при параллельной игре с другими нормальными беспристрастными играми (см. дизъюнктивную сумму ).

В то время как всем нормальным играм-беспристрастным играм может быть присвоено значение ним, это не относится к соглашению misère. Только в игры tame можно играть, используя ту же стратегию, что и misère nim.

Ним — это частный случай игры с частично упорядоченными множествами , в которой частично упорядоченное множество состоит из непересекающихся цепочек (куч).

Граф эволюции игры ним с тремя кучами совпадает с тремя ветвями графа эволюции автомата Улама–Уорбертона . ^[9]

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

Ключом к теории игры является двоичная цифровая сумма размеров кучи, т. е. сумма (в двоичном виде), пренебрегающая всеми переносами из одной цифры в другую. Эта операция также известна как « побитовое xor » или «векторное сложение по GF (2) » (побитовое сложение по модулю 2). В комбинаторной теории игр ее обычно называют ним-суммой , как она будет называться здесь. Ним-сумма x и y записывается как x ⊕ y, чтобы отличить ее от обычной суммы x + y . Пример расчета с кучами размером 3, 4 и 5 выглядит следующим образом:

Двоично-  десятичный  011 2 3 10 Куча А 100 2 4 10 Куча B 101 2 5 10 Куча C --- 010 2 2 10 Ним-сумма кучек A, B и C, 3 ⊕ 4 ⊕ 5 = 2

Эквивалентная процедура, которую часто проще выполнить в уме, состоит в том, чтобы выразить размеры кучи в виде сумм различных степеней числа 2, сократить пары равных степеней и затем сложить то, что осталось:

3 = 0 + 2 + 1 = 2 1 Куча A4 = 4 + 0 + 0 = 4 Куча B5 = 4 + 0 + 1 = 4 1 Куча C-------------------------------------------------- ------------------2 = 2 Что останется после вычитания единиц и четверок

В обычной игре выигрышная стратегия — заканчивать каждый ход с ним-суммой 0. Это всегда возможно, если ним-сумма не равна нулю перед ходом. Если ним-сумма равна нулю, то следующий игрок проиграет, если другой игрок не совершит ошибку. Чтобы узнать, какой ход сделать, пусть X будет ним-суммой всех размеров куч. Найдите кучу, где ним-сумма X и размера кучи меньше размера кучи; выигрышная стратегия — играть в такой куче, уменьшая эту кучу до ним-суммы ее исходного размера с помощью X. В приведенном выше примере взятие ним-суммы размеров равно X = 3 ⊕ 4 ⊕ 5 = 2 . Ним-суммы размеров куч A=3, B=4 и C=5 с X=2 равны

A ⊕ X = 3 ⊕ 2 = 1 [Так как (011) ⊕ (010) = 001 ]

В ⊕ Х = 4 ⊕ 2 = 6

С ⊕ Х = 5 ⊕ 2 = 7

Единственная куча, которая уменьшается, — это куча A, поэтому выигрышный ход — уменьшить размер кучи A до 1 (удалив два объекта).

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

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

Эти стратегии для обычной игры и игры misère одинаковы до тех пор, пока количество куч с двумя и более объектами не станет в точности равным одному. В этот момент следующий игрок удаляет либо все объекты (либо все, кроме одного) из кучи, в которой их два или более, так что ни в одной куче не будет больше одного объекта (другими словами, так что все оставшиеся кучи будут иметь ровно по одному объекту), поэтому игроки вынуждены поочередно удалять ровно один объект, пока игра не закончится. В обычной игре игрок оставляет четное количество ненулевых куч, поэтому тот же игрок берет последним; в игре misère игрок оставляет нечетное количество ненулевых куч, поэтому другой игрок берет последним.

В игре «мизер» с кучами размером три, четыре и пять фишек стратегия будет применяться следующим образом:

Правильность описанной выше оптимальной стратегии была продемонстрирована К. Бутоном.

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

Доказательство: Обратите внимание, что ним-сумма (⊕) подчиняется обычным ассоциативным и коммутативным законам сложения (+), а также удовлетворяет дополнительному свойству: x  ⊕  x  = 0.

Пусть x ₁ , ..., x _n будут размерами куч до хода, а y ₁ , ...,  y _n — соответствующими размерами после хода. Пусть s  =  x ₁  ⊕ ... ⊕  x _n и t  =  y ₁  ⊕ ... ⊕  y _n . Если ход был в куче k , то x _i  =  y _i для всех i ≠ k , и x _k  >  y _k . По свойствам ⊕ , упомянутым выше, имеем

$${\displaystyle {\begin{aligned}t&=0\oplus t\\&=s\oplus s\oplus t\\&=s\oplus (x_{1}\oplus \cdots \oplus x_{n})\oplus (y_{1}\oplus \cdots \oplus y_{n})\\&=s\oplus (x_{1}\oplus y_{1})\oplus \cdots \oplus (x_{n}\oplus y_{n})\\&=s\oplus 0\oplus \cdots \oplus 0\oplus (x_{k}\oplus y_{k})\oplus 0\oplus \cdots \oplus 0\\&=s\oplus x_{k}\oplus y_{k}\\[10pt](*)\quad t&=s\oplus x_{k}\oplus y_{k}\end{align}}}$$

Теорема следует из этих двух лемм индукцией по длине игры.

Лемма 1. Если s = 0, то t ≠ 0 независимо от сделанного хода.

Доказательство: Если нет возможного хода, то лемма бессмысленно верна (и первый игрок проигрывает в обычной игре по определению). В противном случае любой ход в куче k даст t  =  x _k  ⊕  y _k из (*). Это число отлично от нуля, так как x _k  ≠  y _k .

Лемма 2. Если s ≠ 0, то можно сделать ход так, что t = 0.

Доказательство: Пусть d будет позицией самого левого (наиболее значимого) ненулевого бита в двоичном представлении s , и выберем k таким образом, чтобы d -й бит x _k также был ненулевым. (Такое k должно существовать, так как в противном случае d -й бит s был бы равен 0.) Затем, положив y _k  =  s  ⊕  x _k , мы утверждаем, что y _k  <  x _k : все биты слева от d одинаковы в x _k и y _k , бит d уменьшается с 1 до 0 (уменьшая значение на 2 ^d ), и любое изменение в оставшихся битах составит не более 2 ^d −1. Таким образом, первый игрок может сделать ход, взяв x _k  −  y _k объектов из кучи k , тогда

t = s ⊕ x k ⊕ y k (по (*)) = с ⊕ х к ⊕ ( с ⊕ х к ) = 0.

Модификация для игры misère демонстрируется, если отметить, что модификация впервые возникает в позиции, в которой есть только одна куча размером 2 или более. Обратите внимание, что в такой позиции s ≠ 0, и поэтому эта ситуация должна возникнуть, когда наступает очередь игрока, следующего выигрышной стратегии. Обычная стратегия игры заключается в том, чтобы игрок уменьшил ее до размера 0 или 1, оставив четное количество куч с размером 1, а стратегия misère заключается в том, чтобы сделать наоборот. С этого момента все ходы являются вынужденными.

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

Анализ Бутона легко переносится на общую версию этой игры с несколькими кучами. Единственное отличие состоит в том, что в качестве первого шага, перед вычислением ним-сумм, мы должны уменьшить размеры куч по модулю k  + 1. Если это сделает все кучи размером ноль (в игре misère), выигрышным ходом будет взять k объектов из одной из куч. В частности, в идеальной игре с одной кучей из n объектов второй игрок может выиграть тогда и только тогда, когда

• 0  = n (mod  k  + 1) (в обычной игре) или
• 1  = n (mod  k  + 1) (в игре misère).

Это следует из вычисления ним-последовательности S ( 1, 2, ..., k ),

$${\displaystyle 0.123\ldots k0123\ldots k0123\ldots ={\dot {0}}.123\ldots {\dot {k}},}$$

из которой вышеизложенная стратегия следует из теоремы Шпрага–Гранди .

Игра «21» играется как игра в мизер с любым количеством игроков, которые по очереди называют число. Первый игрок говорит «1», и каждый игрок по очереди увеличивает число на 1, 2 или 3, но не может превышать 21; игрок, вынужденный сказать «21», проигрывает. Это можно смоделировать как игру на вычитание с кучей из 21 − n объектов. Выигрышная стратегия для версии этой игры для двух игроков — всегда говорить число, кратное 4; тогда гарантируется, что другой игрок в конечном итоге должен будет сказать 21; поэтому в стандартной версии, где первый игрок начинает с «1», они начинают с проигрышного хода.

В игру «21» можно играть и с другими числами, например, «Добавить максимум 5; проиграть на 34».

Пример игры 21, в которой второй игрок придерживается выигрышной стратегии:

Похожая версия — «игра 100»: два игрока начинают с 0 и поочередно добавляют к сумме число от 1 до 10. Игрок, достигший 100, побеждает. Выигрышная стратегия — достичь числа, в котором цифры являются последовательными (например, 01, 12, 23, 34,...) и контролировать игру, перепрыгивая через все числа этой последовательности. Как только игрок достигает 89, противник может выбирать только числа от 90 до 99, и следующим ответом в любом случае может быть 100.

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

Еще одна разновидность ним — «круговой ним», в котором любое количество предметов размещается в круге, и два игрока поочередно убирают один, два или три соседних предмета. Например, начиная с круга из десяти предметов,

. . . . . . . . . .

три предмета взяты в первом ходу

_ . . . . . . . _ _

затем еще три

_ . _ _ _ . . . _ _

затем один

_ . _ _ _ . . _ _ _

но тогда три предмета нельзя вытащить за один ход.

В игре Гранди , еще одной разновидности ним, некоторое количество объектов помещается в начальную кучу, и два игрока поочередно делят кучу на две непустые кучки разного размера. Таким образом, шесть объектов могут быть разделены на кучки 5+1 или 4+2, но не 3+3. Игра Гранди может быть сыграна как misère или как обычная игра.

Жадный ним — это разновидность, в которой игроки ограничены выбором камней только из самой большой кучи. ^[10] Это конечная беспристрастная игра . Жадный ним мизер имеет те же правила, что и жадный ним, но последний игрок, способный сделать ход, проигрывает.

Пусть наибольшее количество камней в куче равно m , а второе по величине количество камней в куче равно n . Пусть p _m — количество куч, содержащих m камней, а p _n — количество куч, содержащих n камней. Тогда существует теорема о том, что игровые позиции с четным p _m — это P позиций. ^[11] Эту теорему можно доказать, рассмотрев позиции, в которых p _m нечетно. Если p _m больше 1, все камни можно удалить из этой кучи, чтобы уменьшить p _m на 1, и новая p _m будет четной. Если p _m = 1 (т. е. наибольшая куча уникальна), возможны два случая:

• Если p _n нечетно, размер наибольшей кучи уменьшается до n (поэтому теперь новое p _m четно).
• Если p _n четное, то самая большая куча полностью удаляется, оставляя четное число самых больших куч.

Таким образом, существует ход в состояние, где p _m четно. И наоборот, если p _m четно, если возможен любой ход ( p _m ≠ 0), то он должен перевести игру в состояние, где p _m нечетно. Конечная позиция игры четная ( p _m = 0). Следовательно, каждая позиция игры с четным p _m должна быть P -позицией.

Обобщение многокучного ним было названо "ним " или "индекс -k " ним Э. Х. Муром ^[12] , который проанализировал его в 1910 году. В индекс -k ниме вместо удаления объектов только из одной кучи игроки могут удалять объекты по крайней мере из одной, но до k различных куч. Количество элементов, которые могут быть удалены из каждой кучи, может быть произвольным или ограниченным не более чем r элементами, как в "игре на вычитание" выше.${\displaystyle {}_{к}}$

Выигрышная стратегия выглядит следующим образом: как и в обычном многокучном nim, рассматривается двоичное представление размеров кучи (или размеров кучи по модулю r  + 1). В обычном nim формируется XOR-сумма (или сумма по модулю 2) каждой двоичной цифры, и выигрышная стратегия состоит в том, чтобы сделать каждую XOR-сумму нулевой. В обобщении до индекса k nim формируется сумма каждой двоичной цифры по модулю k  + 1.

Опять же, выигрышная стратегия — сделать ход так, чтобы эта сумма была равна нулю для каждой цифры. Действительно, вычисленное таким образом значение равно нулю для конечной позиции, и при заданной конфигурации кучек, для которой это значение равно нулю, любое изменение не более чем k кучек сделает значение ненулевым. И наоборот, при заданной конфигурации с ненулевым значением всегда можно взять не более чем из k кучек, тщательно подобранных, так что значение станет нулевым.

Построение ним — это вариант ним, в котором два игрока сначала строят игру ним. Имея n камней и s пустых куч, игроки, чередуя ходы, кладут ровно один камень в кучку по своему выбору. ^[13] После того, как все камни размещены, начинается игра в ним, начиная со следующего игрока, который будет делать ход. Эта игра обозначается BN(n,s) .

n -d ним играется на доске, на которой любое количество непрерывных фигур может быть удалено из любого гипер-строки. Начальной позицией обычно является полная доска, но допускаются и другие варианты. ^[14]${\displaystyle k_{1}\times \точки \times k_{n}}$

Начальная доска представляет собой несвязный граф, и игроки по очереди удаляют смежные вершины. ^[15]

Конфетный ним — это версия обычного ним, в которой игроки пытаются достичь двух целей одновременно: забрать последний предмет (в данном случае конфету) и забрать максимальное количество конфет к концу игры. ^[16]

• WW Рауз Болл: Математические развлечения и эссе , The Macmillan Company, 1947.
• Джон Д. Бисли: Математика игр , Oxford University Press, 1989.
• Элвин Р. Берлекамп, Джон Х. Конвей и Ричард К. Гай: Выигрышные пути для ваших математических пьес , Academic Press, Inc., 1982.
• Манфред Эйген и Рутильд Винклер : Законы игры , Издательство Принстонского университета, 1981.
• Уолтер Р. Фукс: Компьютеры: теория информации и кибернетика , Образовательные публикации Руперта Харта-Дэвиса, 1971.
• GH Hardy и EM Wright: Введение в теорию чисел , Oxford University Press, 1979.
• Эдвард Каснер и Джеймс Ньюман: Математика и воображение , Саймон и Шустер, 1940.
• М. Кайтчик: Математические развлечения , WW Norton, 1942.
• Дональд Д. Спенсер: Игры с компьютерами , Hayden Book Company, Inc., 1968.

На Викискладе есть медиафайлы по теме Ним (игра) .

• «50-фунтовый компьютер играет в Ним» – The New Yorker - «Talk of the Town» август 1952 г. (требуется подписка)
• Горячая игра Ним – Теория Ним и связи с другими играми на cut-the-knot
• Ним и 2-мерный СуперНим на cut-the-knot