Войти
Матчи, расположенные в строках для игры в Ним. Игроки по очереди выбирают ряд и удаляют из него любое количество совпадений. Ним - это математическая игра стратегии, в которой два игрока по очереди удаляют (или "нимминг") предметы из разных куч или куч. На каждом ходу игрок должен удалить хотя бы один объект и может удалить любое количество объектов при условии, что все они происходят из одной и той же кучи или стопки. В зависимости от используемой версии цель игры - либо избежать взятия последнего объекта, либо взять последний объект.
Варианты Нима разыгрываются с древних времен. Считается, что игра возникла в Китае - она очень похожа на китайскую игру 捡 石子 jiǎn-shízi, или «собирать камни», но происхождение неизвестно; Самые ранние упоминания Нима в Европе относятся к началу 16 века. Нынешнее название было придумано Чарльзом Л. Бутоном из Гарвардского университета, который также разработал полную теорию игры в 1901 году, но происхождение названия так и не было полностью объяснено.
Ним обычно разыгрывается как игра с неудачниками, в которой игрок, взявший последний объект, проигрывает. В Ним также можно играть как в обычную игру, в которой побеждает игрок, взявший последний предмет. Это называется нормальной игрой, потому что последний ход является выигрышным в большинстве игр, даже несмотря на то, что это не обычный способ игры Нима. Как в обычной игре, так и в игре «Мизер», когда количество куч с как минимум двумя объектами точно равно единице, следующий игрок, который берет следующий, может легко выиграть. Если при этом удаляются все или все объекты, кроме одного, из кучи, содержащей два или более, то ни одна кучка не будет содержать более одного объекта, поэтому игроки вынуждены поочередно удалять только один объект, пока игра не закончится. Если игрок оставляет четное количество ненулевых куч (как это сделал бы игрок в обычной игре), игрок берет последнее; если игрок оставляет нечетное количество куч (как это сделал бы игрок в игре misère), то другой игрок берет последнее.
Нормальная игра Ним (или, точнее, система пилотов ) лежит в основе теоремы Спрэга – Гранди, которая, по сути, гласит, что в нормальной игре каждые беспристрастная игра эквивалентна куче нимов, которая дает тот же результат, когда в нее играют параллельно с другими беспристрастными играми с нормальной игрой (см. дизъюнктивная сумма ).
В то время как всем нормальным беспристрастным играм может быть присвоено значение нима, в соответствии с соглашением Мизера это не так. Только ручные игры можно играть, используя ту же стратегию, что и Мизер Ним.
Ним является частным случаем игры по заданию, где поуст состоит из непересекающихся цепочек (кучек).
График эволюции игры Ним с тремя кучами такой же, как три ветви графика эволюции автомата Улама-Уорбертона.
На Всемирной выставке в Нью-Йорке 1940 года Вестингауз показал машину, Ниматрон, которая играла Нима. С 11 мая 1940 г. по 27 октября 1940 г. только несколько человек смогли победить машину за этот шестинедельный период; если они это сделали, им подарили монету с надписью «Ним Чамп». Это также была одна из первых компьютерных компьютерных игр. Ферранти построил игровой компьютер Nim, который был показан на Фестивале Великобритании в 1951 году. В 1952 году Герберт Коппел, Юджин Грант и Говард Бейлер, инженеры из WL Maxon Corporation разработала машину весом 23 килограмма (50 фунтов), которая играла Нима против человеческого противника и регулярно побеждала. Была описана игровая машина Ним, сделанная из TinkerToy.
. Игра в Ним была предметом Мартина Гарднера в февральской 1958 г. колонке «Математические игры» в журнале Scientific American. Версия Нима играет - и имеет символическое значение - в фильме Французская новая волна Прошлый год в Мариенбаде (1961).
обычная игра - это игра между двумя игроками с тремя кучами любого количества объектов. Два игрока по очереди берут любое количество предметов из любой одной из куч. Цель состоит в том, чтобы взять предмет последним. В игре misère цель вместо этого состоит в том, чтобы противник был вынужден взять последний оставшийся объект.
Следующий пример нормальной игры разыгрывается между вымышленными игроками Бобом и Алисой, которые начинают с кучей из трех, четырех и пяти объектов.
Размеры куч Перемещения ABC 3 4 5 Боб берет 2 у A 1 4 5 Алиса берет 3 у C 1 4 2 Боб берет 1 у B 1 3 2 Алиса берет 1 у B 1 2 2 Боб берет всю A куча, оставляя две двойки 0 2 2 Алиса берет 1 у B 0 1 2 Боб берет 1 у C, оставляя две единицы. (В игре «Мизер» он взял бы 2 у C, оставив (0, 1, 0).) 0 1 1 Алиса забирает 1 у B 0 0 1 Боб забирает всю кучу C и выигрывает
Практическая стратегия победы в игре Ним состоит в том, чтобы игрок занял одну из следующих позиций, и каждый последующий ход после этого он должен иметь возможность занять одну из меньших позиций. Только последний ход меняется между мизерным и нормальным ходом.
| 2 кучи | 3 кучи | 4 кучи |
|---|---|---|
| 1 1 * | 1 1 1 ** | 1 1 1 1 * |
| 2 2 | 1 2 3 | 1 1 nn |
| 3 3 | 1 4 5 | 1 2 4 7 |
| 4 4 | 1 6 7 | 1 2 5 6 |
| 5 5 | 1 8 9 | 1 3 4 6 |
| 6 6 | 2 4 6 | 1 3 5 7 |
| 7 7 | 2 5 7 | 2 3 4 5 |
| 8 8 | 3 4 7 | 2 3 6 7 |
| 9 9 | 3 5 6 | 2 3 8 9 |
| nn | 4 8 12 | 4 5 6 7 |
| 4 9 13 | 4 5 8 9 | |
| 5 8 13 | ннмм | |
| 5 9 12 | nnnn |
* Действительно только для обычного воспроизведения.
** Действительно только для misere.
Для обобщений n и m могут иметь любое значение>0, и они могут быть одинаковыми.
Ним математически решен для любого количества начальных куч и объектов, и есть легко вычисляемый способ определить, какой игрок и какой выиграет. ходы открыты для этого игрока.
Ключ к теории игры - это двоичная цифровая сумма размеров кучи, то есть сумма (в двоичном формате) без учета всех переносов из одного цифра в другую. Эта операция также известна как «поразрядное xor » или «сложение вектора по GF(2) » (поразрядное сложение по модулю 2). В рамках комбинаторной теории игр это обычно называется ним-суммой, как она будет здесь называться. Ним-сумма x и y пишется x ⊕ y, чтобы отличать ее от обычной суммы, x + y. Пример расчета с кучей размером 3, 4 и 5 выглядит следующим образом:
Двоичный Десятичный 011 2310Куча A 100 2410Куча B 101 2510Куча C --- 010 2210Ним-сумма куч A, B и C, 3 ⊕ 4 ⊕ 5 = 2
Эквивалентная процедура, которую часто легче выполнить мысленно, - это выразить размеры кучи как суммы различных степеней 2, отмените пары равных степеней, а затем сложите то, что осталось:
3 = 0 + 2 + 1 = 2 1 Куча A 4 = 4 + 0 + 0 = 4 Куча B 5 = 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, поэтому выигрышный ход - уменьшить размер кучи A до 1 (удалив два объекта).
В частном простом случае, если осталось только две кучи, стратегия состоит в том, чтобы уменьшить количество объектов в большей куче, чтобы сделать кучи равными. После этого, независимо от того, какой ход сделает ваш противник, вы можете сделать тот же ход на другой куче, гарантируя, что вы заберете последний объект.
Когда игра ведется как мизерная игра, стратегия Нима отличается только тогда, когда обычный игровой ход оставляет только кучи размера один. В этом случае правильный ход - оставить нечетное количество куч размером один (при нормальной игре правильным ходом было бы оставить четное количество таких куч).
Эти стратегии для нормальной игры и для игры в «мизер» одинаковы до тех пор, пока количество куч с как минимум двумя объектами не станет точно равным одному. В этот момент следующий игрок удаляет все или все объекты, кроме одного, из кучи, содержащей два или более объекта, поэтому в кучах не будет более одного объекта (другими словами, все оставшиеся кучи имеют ровно по одному объекту), поэтому игроки вынуждены поочередно удалять ровно один объект, пока игра не закончится. В обычной игре игрок оставляет четное количество ненулевых куч, поэтому тот же игрок занимает последнее место; в игре «Мизер» игрок оставляет нечетное количество куч, отличных от нуля, поэтому второй игрок занимает последнее место.
В игре «Мизер» с кучей размеров три, четыре и пять, стратегия будет применяться следующим образом:
ABC-ним-сумма 3 4 5 010 2=210Я беру 2 из A, оставив сумму 000, значит, я выиграю. 1 4 5 000 2=010Вы берете 2 из C 1 4 3 110 2=610Я беру 2 из B 1 2 3 000 2=010Вы берете 1 из C 1 2 2 001 2=110Я беру 1 из A 0 2 2 000 2=010Вы берете 1 из C 0 2 1 011 2=310Обычная стратегия игры состоит в том, чтобы взять 1 из B, оставив четное число (2) кучки размера 1. Для игры типа misère я беру всю B куча, чтобы оставить нечетное количество (1) куч размером 1. 0 0 1 001 2=110Вы берете 1 из C и проигрываете.
Предыдущую стратегию для игры в мизер можно легко реализовать (например, в Python, ниже).
import functools MISERE = 'misere' NORMAL = 'normal' def nim (heaps, game_type): "" "Вычисляет следующий ход для Нима, для обоих типов игры normal и misere. Если есть выигрышный ход: 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], NORMAL)) normal [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 (game_type, heaps, end = '') is_misere = game_type == MISERE is_ne ar_endgame = False count_non_0_1 = sum (1 для x в кучах, если x>1) is_near_endgame = (count_non_0_1 <= 1) # nim sum will give the correct end-game move for normal play but # misere requires the last move be forced onto the opponent if is_misere and is_near_endgame: moves_left = sum(1 for x in heaps if x>0) is_odd = (move_left% 2 == 1) sizeof_max = max (heaps) index_of_max = heaps_index) (sizeof_max) if sizeof_max == 1 и is_odd: return "Вы проиграете :(" # уменьшите игру до нечетного числа 1 return index_of_max, sizeof_max - int (is_odd) nim_sum = functools.reduce (lambda x, y: x ^ y, heaps) if nim_sum == 0: return "Вы проиграете :(" # Расчет, который нужно сделать для index, heap in enumerate (heaps): target_size = heap ^ nim_sum if target_size < heap: amount_to_remove = heap - target_size return index, amount_to_remove if __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>yk. По свойствам ⊕, упомянутым выше, мы имеем
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 также отличен от нуля. (Такой ak должен существовать, поскольку в противном случае d-й бит s был бы равен 0.) Тогда, полагая y k = s ⊕ x k, мы утверждаем, что y k< xk: все биты слева от d одинаковы в x k и y k, бит d уменьшается с 1 до 0 (уменьшая значение на 2), и любое изменение в оставшихся битах будет составляют не более 2−1. Таким образом, первый игрок может сделать ход, взяв x k - y k объектов из кучи k, затем
t = s ⊕ x k ⊕ y k (по (*)) = s ⊕ x k ⊕ (s ⊕ x k) = 0.
модификация для игры misère демонстрируется, отмечая, что модификация сначала возникает в позиции, которая имеет только одну кучу размера 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 объектов второй игрок может выиграть тогда и только тогда, когда
Это следует из вычисления nim-последовательности для S (1,2,..., k),
из которого следует стратегия, приведенная выше, на основании теоремы Спрага – Гранди.
Игра «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»: два игрока начинают с 0 и поочередно добавляют число от 1 до 10 до суммы. Побеждает игрок, набравший 100 очков. Выигрышная стратегия состоит в том, чтобы набрать число, в котором цифры идут подряд (например, 01, 12, 23, 34,...), и управлять игрой, перебирая все числа этой последовательности. Достигнув 89, противник проиграл; они могут выбирать только числа от 90 до 99, и следующий ответ в любом случае может быть 100).
В другом варианте Nim, помимо удаления любого количества объектов из одной кучи, разрешено удалять одинаковое количество объектов из каждой кучи.
Еще одна разновидность нима - это «Круглый ним», где любое количество объектов помещается в круг, и два игрока поочередно удаляют один, два или три соседних объекта. Например, начиная с круга из десяти объектов,
..........
три объекта взяты в первый ход
_....... _ _
, затем еще три
_. _ _ _... _ _
, затем один
_. _ _ _.. _ _ _
но тогда три объекта нельзя вынуть за один ход.
В игре Гранди, другом варианте Нима, несколько объектов помещаются в начальную кучу, и два игрока поочередно делят кучу на две непустые кучи разного размера. Таким образом, шесть объектов можно разбить на стопки по 5 + 1 или 4 + 2, но не 3 + 3. В игру Гранди можно играть как в обычную, так и в обычную игру.
Жадный Ним - это вариант, в котором игроки могут выбирать камни только из самой большой кучи. Это конечная беспристрастная игра. Жадный Ним Мизер имеет те же правила, что и Жадный Ним, но здесь проигрывает последний игрок, который может сделать ход.
Пусть наибольшее количество камней в стопке равно m, а второе по величине количество камней в куче - n. Пусть p m - количество стопок, содержащих m камней, p n - количество стопок, содержащих n камней. Тогда есть теорема, что игровые позиции с четным p m являются P позициями. Эту теорему можно показать, рассматривая позиции, в которых p m нечетно. Если p m больше 1, все камни могут быть удалены из этой кучи, чтобы уменьшить p m на 1, и новое p m будет четным. Если p m = 1 (т.е. самая большая куча уникальна), возможны два случая:
Таким образом, существует переход в состояние, в котором p m четно. И наоборот, если p m четно, если возможен любой ход (p m ≠ 0), тогда он должен привести игру к состоянию, где p m равно странный. Конечная позиция игры четная (p m = 0). Следовательно, каждая позиция в игре с четным p m должна быть P-позицией.
Обобщение Nim с несколькими кучами называлось «Nim 
Выигрышная стратегия заключается в следующем: Как и в обычном Nim с несколькими кучами, каждый рассматривает двоичное представление размеров кучи (или размеров кучи по модулю r + 1). В обычном Nim формируется сумма XOR (или сумма по модулю 2) каждой двоичной цифры, и выигрышная стратегия состоит в том, чтобы сделать каждую сумму XOR равной нулю. В обобщении для индекса-k Nim формируется сумма каждой двоичной цифры по модулю k + 1.
Опять же, выигрышная стратегия заключается в перемещении так, чтобы эта сумма была равна нулю для каждой цифры. В самом деле, вычисленное таким образом значение равно нулю для конечной позиции, и, учитывая конфигурацию куч, для которой это значение равно нулю, любое изменение не более чем k куч сделает значение ненулевым. И наоборот, учитывая конфигурацию с ненулевым значением, всегда можно взять максимум из k куч, тщательно выбранных, так что значение станет нулевым.
Строительство нима - это вариант нима, в котором два игрока сначала создают игру нима. Учитывая n камней и s пустых стопок, игроки по очереди кладут ровно один камень в стопку по своему выбору. После того, как все камни будут размещены, начинается игра Ним, начиная со следующего игрока, который сделает ход. Эта игра обозначается BN (n, s).
и ним играет на 
Начальная доска - это несвязный граф, и игроки по очереди удаляют соседние вершины.
Кэнди Ним - это вариант обычного игрового Нима, в котором игроки пытались достичь двух целей одновременно: захватить последний предмет (в данном случае «конфету»), и взяв максимальное количество конфет к концу игры.
.
 | На Викискладе есть материалы, связанные с Ним. |
