Нім (гра)

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

Сірники розкладені рядками для гри в Нім. Гравці по черзі вибирають рядок і видаляють з нього будь-яку кількість сірників.

У класичному варіанті гри число купок дорівнює трьом.

Окремий випадок, коли купка одна, але максимальне число предметів, які можна взяти за хід, обмежена, відома як гра Баше.

Нім — кінцева гра з повною інформацією.

Класична гра Нім має фундаментальне значення для теореми Шпрага-Гранді. Ця теорема стверджує, що звичайна гра в суму неупереджених ігор може прирівнюватися до гри в Нім. При цьому кожній неупередженій грі-доданку відповідає купка Нім, число предметів в якій дорівнює значенню функції Шпрага-Гранді для ігрової позиції даної гри.

Математична теорія

Нім розв'язали для будь-якої кількості купок і об'єктів. Існує простий спосіб обчислення, який з гравців виграє і, які виграшні кроки має гравець.

Ключ до теорії гри — це двійкова поцифрова сума розмірів куп, тобто, сума (двійкова) нехтуючи всіма переносами з однієї цифри в іншу. Ця операція також відома як "додавання за модулем два" (xor). В комбінаторній теорії ігор її зазвичай називають нім-сума, як і в цій статті. Нім-сума x і y записується x ⊕ y, щоб відрізнити від звичайної суми, x + y. Наведемо приклад, обчислень з купками розмірів 3, 4 і 5:

Двійкова  Десяткова
 
  0112    310    Купа A
  1002    410    Купа B
  1012    510    Купа C
  ---
  0102    210    Нім-сума куп 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. Нім-суми окремих куп з X:

A ⊕ X = 3 ⊕ 2 = 1 [Бо (011) ⊕ (010) = 001 ]

B ⊕ X = 4 ⊕ 2 = 6

C ⊕ X = 5 ⊕ 2 = 7

Єдина купа нім-сума якої з X менша ніж розмір купи це A, отже виграшний крок це зменшення розміру A до 1 (видаляючи два об'єкти).

Як окремий простий приклад можна розглянути випадок з двома купами. Тут стратегія буде зменшити кількість предметів в більшій купі до кількості предметів в меншій. Після цього неважливо, що робитиме супротивник, завжди можливо буде зрівняти купи знов.

У разі мізер-гри, стратегія відрізняється лише коли стратегія нормальної гри залишає лише купи розміру один. Тоді правильний крок — це залишити непарну кількість куп розміру один (в нормальній грі правильно було б залишити парну кількість таких куп).

Література

• Болл У., Коксетер Г. Математические эссе и развлечения = Mathematical Recreations and Essays. — М. : Мир, 1986. — С. 47-51.