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

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

Варианты Нима разыгрываются с древних времен. [1] Считается , что игра возникла в Китае - она ​​очень похожа на китайскую игру 捡 石子jiǎn-shízi , или «собирать камни» [2], но происхождение неизвестно; Самые ранние европейские упоминания Нима относятся к началу 16 века. Его нынешнее название было придумано Чарльзом Л. Бутоном из Гарвардского университета , который также разработал полную теорию игры в 1901 году [3], но происхождение названия так и не было полностью объяснено.

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

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

В то время как всем нормальным беспристрастным играм может быть присвоено значение нима, это не относится к соглашению о мизере. Только в ручные игры можно играть, используя ту же стратегию, что и Мизер Ним.

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

Граф эволюции игры Ним с тремя кучами - это то же самое, что и три ветви графа эволюции автомата Улама-Уорбертона . [4]

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

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

Игра и иллюстрации [ править ]

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

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

Размеры отвала ХодыABC 3 4 5 Боб берет 2 из A1 4 5 Алиса берет 3 из C1 4 2 Боб берет 1 у B1 3 2 Алиса берет 1 из B1 2 2 Боб забирает всю кучу A, оставляя две двойки0 2 2 Алиса берет 1 из B0 1 2 Боб берет 1 у C, оставляя две единицы. ( В игре «Мизер» он взял бы 2 из C, оставив (0, 1, 0). )0 1 1 Алиса берет 1 из B0 0 1 Боб забирает всю C-кучу и побеждает

Выигрышные позиции [ править ]

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

2 кучи3 кучи4 кучи
1 1 *1 1 1 **1 1 1 1 *
2 21 2 31 1 нн
3 31 4 51 2 4 7
4 41 6 71 2 5 6
5 51 8 91 3 4 6
6 62 4 61 3 5 7
7 72 5 72 3 4 5
8 83 4 72 3 6 7
9 93 5 62 3 8 9
nn4 8 124 5 6 7
4 9 134 5 8 9
5 8 13ннмм
5 9 12нннн

* Действительно только для нормальной игры.

** Действительно только для misere.

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

Математическая теория [ править ]

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

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

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

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

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

В обычной игре выигрышная стратегия состоит в том, чтобы заканчивать каждый ход с ним-суммой, равной 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]
B ⊕ X = 4 ⊕ 2 = 6
С ⊕ X = 5 ⊕ 2 = 7

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

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

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

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

В игре misère с кучей размеров три, четыре и пять стратегия будет применяться следующим образом:

Ним-сумма ABC  3 4 5 010 2 = 2 10 Я беру 2 из A, оставляя сумму 000, так что я выиграю.1 4 5 000 2 = 0 10 Вы берете 2 из C1 4 3110 2 = 6 10 Я беру 2 из B1 2 3 000 2 = 0 10 Вы берете 1 из C1 2 2 001 2 = 1 10 Я беру 1 из A0 2 2 000 2 = 0 10 Вы берете 1 из C0 2 1 011 2 = 3 10 Обычная стратегия игры состоит в том, чтобы взять 1 из B, оставив четное число (2) кучи размера 1. Для игры с мизером я беру всю кучу B, чтобы не было лишних количество (1) куч размером 1.0 0 1 001 2 = 1 10 Вы берете 1 у C и проигрываете.

Пример реализации [ править ]

Предыдущую стратегию для игры типа misère можно легко реализовать (например, на Python , см. Ниже).

import  functoolsMISERE  =  'misere' NORMAL  =  'нормальный'Защиту  NIM ( отвалы ,  game_type ):  «» "Вычисляет следующий шаг для Nim, для обоих типов игровых нормальных и мизер. если есть выигрышный ход:  return tuple (heap_index, amount_to_remove)  else:  return "Вы проиграете :(" - сценарии в середине игры одинаковы для обоих типов игр >>> print (nim ([1, 2, 3], MISERE))  misere [1, 2, 3] Вы проиграете :(  >>> print (nim ([1, 2, 3], NORMAL))  normal [1, 2, 3] Вы проиграете :(  >>> print (nim ([1, 2, 4], MISERE))  misere [1, 2, 4] (2, 1)  >>> print (nim ( [1, 2, 4], ОБЫЧНЫЙ))  нормальный [1, 2, 4] (2, 1) - сценарии эндшпиля меняются в зависимости от типа игры >>> print (nim ([1], MISERE))  misere [1] Вы потеряете :(  >>> print (nim ([1], NORMAL))  normal [1] (0, 1)  >>> print (nim ([1, 1], MISERE))  misere [1, 1] (0, 1)  >>> print (nim ([1, 1], NORMAL))  normal [1, 1] Вы проиграете :(  >>> print (nim ([1, 5], MISERE))  misere [1, 5] (1, 5)  >>> print (nim ([1, 5], NORMAL))  normal [1, 5] ( 1, 4)  "" " print ( тип_игры ,  кучи ,  конец = '' ) is_misere  =  game_type  ==  MISERE is_near_endgame  =  False  count_non_0_1  =  sum ( 1  для  x  в  кучах,  если  x  >  1 )  is_near_endgame  =  ( count_non_0_1  <=  1 ) # nim sum даст правильный ход в конце игры для нормальной игры, но  # misere требует, чтобы последний ход был принудительно направлен противнику,  если  is_misere  и  is_near_endgame :  move_left  =  sum ( 1  для  x  в  кучах,  если  x  >  0 )  is_odd  =  ( move_left  %  2  ==  1 )  sizeof_max  =  max ( кучи )  index_of_max  =  кучи . индекс ( sizeof_max ) если  sizeof_max  ==  1  и  is_odd :  return  "Вы проиграете :(" # уменьшаем игру до нечетного числа из 1  return  index_of_max ,  sizeof_max  -  int ( is_odd ) nim_sum  =  functools . уменьшить ( лямбда  х ,  у :  х  ^  у ,  отвалы ) ,  если  nim_sum  ==  0 :  возвращение  «Вы потеряете :(» # Calc , которые перемещаются , чтобы сделать  для  индекса ,  кучи  в  Перечислять ( отвалы ):  target_size  =  куча  ^  nim_sum  если  target_size  <  вороха :  amount_to_remove  =  куча  -  target_size  возвращение  индекса ,  amount_to_removeесли  __name__  ==  "__main__" :  import  doctest  doctest . testmod ()

Доказательство формулы выигрыша [ править ]

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

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

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

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

 t = 0 ⊕ t = s ⊕ s ⊕ t = s ⊕ ( x 1 ⊕ ... ⊕ x n ) ⊕ ( y 1 ⊕ ... ⊕ y n ) = s ⊕ ( x 1 ⊕ y 1 ) ⊕ ... ⊕ ( x n ⊕ y n ) = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ ( x k ⊕ y k ) ⊕ 0 ⊕ ... ⊕ 0 = s ⊕ x k ⊕ y k (*) t = s ⊕ x k ⊕ y k .

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

Лемма 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 одинаковы в х к и у к, бит d уменьшается с 1 до 0 (уменьшая значение на 2 d ), и любое изменение в оставшихся битах составит не более 2 d -1. Таким образом, первый игрок может сделать ход, взяв x k  -  y k объектов из кучи k , затем

t = s ⊕ x k ⊕ y k (согласно (*)) = s ⊕ x k ⊕ ( s ⊕ x k ) = 0.

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

Варианты [ править ]

Игра на вычитание [ править ]

Интерактивная игра на вычитание: игроки по очереди удаляют 1, 2 или 3 объекта из начального пула, состоящего из 21 объекта. Выигрывает игрок, взявший последний предмет.

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

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

n  ≡ 0 (mod  k  + 1) (при нормальном воспроизведении) или
n  ≡ 1 (mod  k  + 1) (в игре misère).

Это следует из расчета NIM-последовательность из S (1,2, ..., K ),

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

Игра 21 [ править ]

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

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

Пример игры из 21, в которой второй игрок следует выигрышной стратегии:

Номер игрока 1 1 2 4 1 5, 6 или 7 2 8 1 9, 10 или 11 2 12 1 13, 14 или 15 2 16 1 17, 18 или 19 2 20 1 21

Игра 100 [ править ]

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

Правило нескольких куч [ править ]

Смотрите также: Игра Уайтхоффа

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

Круглый Ним [ править ]

Также: Кейлс

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

. . . . . . . . . .

три объекта берутся в первый ход

_. . . . . . . _ _

затем еще три

_. _ _ _. . . _ _

затем один

_. _ _ _. . _ _ _

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

Игра Гранди [ править ]

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

Жадный Ним [ править ]

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

Пусть наибольшее количество камней в стопке равно m, а вторым по величине количество камней в куче будет n . Пусть p m - количество стопок с m камнями, а p n - количество стопок с n камнями. Тогда есть теорема, что игровые позиции с четным p m являются P позициями. [12] Эту теорему можно показать, рассматривая позиции, в которых p m нечетно. Если p m больше 1, все камни могут быть удалены из этой кучи, чтобы уменьшить p m на 1 и новое значение p.м будет ровным. Если 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.

Index- k Nim [ править ]

Обобщение нескольких кучного Нима был назван «Nim » или «index- к » Nim по ЕН Мур , [13] , который анализировал в 1910 г. В index- K Нима, вместо того , чтобы извлекать объекты только из одной кучи, игроки могут удалить объекты по крайней мере из одной, но до k разных куч. Количество элементов, которые могут быть удалены из каждой кучи, может быть произвольным или ограничиваться не более чем r элементами, как в «игре на вычитание» выше.

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

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

Строительство Нима [ править ]

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

Ним из более высоких измерений [ править ]

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

Граф Ним [ править ]

Стартовая доска представляет собой несвязный граф, и игроки по очереди удаляют соседние вершины.

Кэнди Ним [ править ]

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


См. Также [ править ]

  • Доктор НИМ
  • Ним Фибоначчи
  • Нечеткая игра
  • Нимбер
  • Восьмеричные игры
  • Звезда (теория игр)
  • Вычесть квадрат
  • Нулевая игра
  • Android Nim
  • Раймонд Редхеффер
  • Notakto
  • Чавкать
  • Кувырок Тьюринга

Ссылки [ править ]

  1. ^ Йоргенсен Анкер Хелмс (2009), «Контекст и движущие силы в развитии ранней компьютерной игры нимбы» , IEEE Анналы истории вычислительной техники , 31 (3): 44-53, DOI : 10.1109 / MAHC.2009.41 , MR  2767447 , Математическая игра для двух человек «Ним», которая, по мнению многих, возникла в Китае, вероятно, является одной из старейших игр в мире.
  2. ^ Яглом, И.М. (2001), «Две игры со спичками», Табачников, Серж (ред.), Квант Селекта: Комбинаторика, I, Том 1 , Мир математики, 17 , Американское математическое общество , стр. 1–8, ISBN 9780821821718
  3. ^ Bouton, CL (1901-1902), "Nim, игра с полной математической теории ", Анналы математики , 3 (14): 35-39, DOI : 10,2307 / 1967631 , JSTOR 1967631 
  4. ^ Хованов, Таня; Сюн, Джошуа (2014). «Ним Фракталы». arXiv : 1405.5942 [ math.CO ].
  5. ^ Флеш, Рудольф (1951). Искусство ясного мышления . Нью-Йорк: издательство Harper and Brothers. п. 3.
  6. ^ "ExpoMuseum / New York World's Fair, 1939-40" . www.expomuseum.com . Проверено 20 апреля 2018 года .
  7. ^ "1940: Ниматрон" . platinumpiotr.blogspot.com . Проверено 20 апреля 2018 года .
  8. ^ Грант, Юджин Ф .; Ларднер, Рекс (2 августа 1952 г.). "Разговор о городе - это" . Житель Нью-Йорка .
  9. ^ Коэн, Харви А. "Как построить игровой автомат NIM" (PDF) .
  10. ^ Morrissette, Брюс (1968), "Игры и игровые структуры в Роб-Грийе", Yale French Studies , 41 (41): 159-167, DOI : 10,2307 / 2929672 , JSTOR 2929672 . Морриссетт пишет, что Ален Роб-Грийе , один из сценаристов фильма, «думал, что он изобрел» игру.
  11. ^ --- (2001). Выигрышные способы для ваших математических пьес . 4 тт. (2-е изд.). AK Peters Ltd.CS1 maint: числовые имена: список авторов ( ссылка ); Berlekamp, ​​Elwyn R .; Конвей, Джон Хортон; Гай, Ричард К. (15.06.2003). т. 1 . ISBN 978-1-56881-130-7.; Berlekamp, ​​Elwyn R .; Конвей, Джон Хортон; Гай, Ричард К. (15.06.2003). т. 2 . ISBN 978-1-56881-142-0.; Berlekamp, ​​Elwyn R .; Конвей, Джон Хортон; Гай, Ричард К. (15.06.2003). т. 3 . ISBN 978-1-56881-143-7.; Berlekamp, ​​Elwyn R .; Конвей, Джон Хортон; Гай, Ричард К. (2004-06-15). т. 4 . ISBN 978-1-56881-144-4.
  12. ↑ MH Альберт, RJ Новаковски (2004). «Ограничения Нима» (PDF) . INTEGERS: Электронный журнал комбинаторной теории чисел : 2.
  13. ^ Мур, Э. Х. Обобщение игры под названием Nim . Annals of Mathematics 11 (3), 1910, стр. 93–94.
  14. ^ Ларссон, Урбан; Хойбах, Сильвия ; Дюфур, Матье; Дюшен, Эрик (2015). «Строительство Ним». arXiv : 1502.04068 [ cs.DM ].
  15. ^ "1021 - 2D-Ним" . Poj.org . Проверено 9 января 2019 .
  16. ^ Rubinstein-Salzedo, Саймон (18 мая 2018). "Играть в Candy Nim" (PDF) . Дата обращения 5 июля 2020 .

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

  • 50-фунтовая компьютерная игра Nim - журнал New Yorker "Talk of the Town", август 1952 г. (требуется подписка)
  • Горячая игра Нима - теория Нима и связи с другими играми на пороге
  • Nim и 2-мерных SuperNim в вырез в-узел
  • Игра на вычитание: иллюстрация игры на вычитание в Appstore.
  • Классический Ним - Реализация Нима для iOS.
  • Matchstick Nim - Реализация Nim для устройств Android.