Nim

Nim – stara chińska gra (nazywana tam Jianshizi, czyli 'gra w zabieranie kamieni') dla dwóch osób z użyciem 15 do 60 pionków.

Pionki dzieli się na kupki dowolnej, parami różnej wielkości. Kupek powinno być co najmniej trzy, i powinny zawierać co najmniej 4 pionki; w każdej kupce powinna być inna liczba pionków. Następnie gracze zabierają na zmianę dowolną, niezerową liczbę pionów. W jednym ruchu wolno zbierać tylko z jednej kupki. W zależności od wersji, przegrywa lub wygrywa gracz, który zabiera ostatni pionek.

• Marienbad: 16 pionów ustawiamy w 4 rzędach: 1 rząd – 1 pion; 2 rząd – 3 piony; 3 rząd – 5 pionów; 4 rząd – 7 pionów. Ruch polega na wzięciu od 1 piona do całego rzędu. Przegrywa gracz, który zabiera ostatni pion.
• Wythoff (wyhoff): piony dzieli się na dwie różnoliczne kupki, bierzemy co najmniej 1 pion z 1 kupki; można brać piony z obu kupek w jednym ruchu, ale bierzemy wówczas tę samą ilość pionów z jednej i drugiej kupki
• Kayles: Ustawiamy 13 pionów w następujący sposób: O OOOOOOOOOOOO. Ruch polega na wzięciu 1 lub 2 pionów, ale gdy bierzemy 2 piony musimy pamiętać aby się stykały ze sobą. Wygrywa ten, kto bierze 1 lub 2 ostatnie piony.
• Kubo: 27 pionków ustawiamy w kwadrat 3x3 po trzy na sobie. gracz może zabrać 1,2 bądź 3 pionki z jednej z 9 kupek lub po jednej z sąsiadujących pionowo, bądź poziomo kupek.
• Dziewiętnaście: dziewiętnaście pionków ustawia się w sześciokąt foremny. wolno brać jeden kamień, dwa sąsiadujące, bądź trzy sąsiadujące (ale każdy z każdym – mały trójkącik).
• Taktix: 16 pionków ustawiamy w kwadrat 4x4. Wolno zbierać dowolną ilość kamieni byle z tylko jednej kolumny, bądź wersu.
• Chomp: Pionki ustawiamy w prostokąt. Zbierając wybrany kamień trzeba zabrać wszystkie na prawo i w górę od niego.

W klasycznej grze nim, jeżeli wygrywa ten, kto zbierze ostatnią kupkę, strategią wygrywającą jest oczywiście zebranie tej kupki. Jeśli kupek jest więcej, a znajdują się na nich odpowiednio a, b, c... pionów, należy się starać przejść do sytuacji, w której a⊕b⊕c⊕...=0 (dodawanie nimliczb).

W praktyce strategia wygranej w nim polega na każdorazowym doprowadzaniu do układu o parzystej liczbie grup binarnych. Grupy binarne to znajdujące się w jednej kupce piony w liczbie: 2⁰ = 1; 2¹ = 2; 2² = 4; 2³ = 8; ...; 2ⁿ. Należy doprowadzać do układów, w których np. grupa 8 pionów z jednej kupki ma do pary grupę ósemkową w innej kupce, następnie grupa 4 pionów ma do pary grupę czwórkową, grupa 2 pionów ma też swój odpowiednik i wreszcie pojedynczy pionek ma do pary innego singla. Parowanie grup należy rozpoczynać zawsze od najliczniejszej grupy binarnej^[1].

Przykład. Dla klarowności objaśnień przyjmijmy, że piony znajdują się nie na kupkach, lecz w 3 rzędach:

OOOOO	5 pionów = czwórka i singiel
OOOOOOO	7 pionów = czwórka, dwójka i singiel
OOOOOOOOO	9 pionów = ósemka i singiel

Jedyna ósemka nie ma pary, należy więc z niej część pionów usunąć tak, aby pozostał układ o parzystości binarnej wg strategii wygranej:

OOOOO	5 pionów = czwórka i singiel
OOOOOOO	7 pionów = czwórka, dwójka i singiel
OO	2 piony = dwójka

Mamy teraz dwie czwórki, dwie dwójki i dwa single. Każdy ruch przeciwnika psuje tę parzystość, co prowadzi do jego przegranej.

Istnienie optymalnej strategii wykazał Charles L. Bouton^[2].

Twierdzenie. W klasycznej grze nim gracz wykonujący ruch jako pierwszy ma zwycięską strategię wtedy i tylko wtedy gdy nim-suma liczebności kupek jest niezerowa. W przeciwnym przypadku drugi gracz ma zwycięską strategię.

Dowód: Zauważmy, że nim-suma ( ⊕ ) jest działaniem łącznym i przemiennym jak dodawanie arytmetyczne (+) i spełnia warunek x ⊕ x = 0.

Niech x₁, ..., x_n oznaczają liczebność kupek przed wykonaniem ruchu natomiast y₁, ..., y_n oznaczają odpowiednio liczebność po wykonaniu ruchu. Połóżmy s = x₁ ⊕ ... ⊕ x_n i t = y₁ ⊕ ... ⊕ y_n. Jeśli ruch został wykonany na k-tej kupce, to otrzymujemy x_i = y_i dla każdego i ≠ k oraz x_k > y_k. Z własności powyżej wspomnianych otrzymujemy:

    t = 0 ⊕ t
      = s ⊕ s ⊕ t
      = s ⊕ (x1 ⊕ ... ⊕ xn) ⊕ (y1 ⊕ ... ⊕ yn)
      = s ⊕ (x1 ⊕ y1) ⊕ ... ⊕ (xn ⊕ yn)
      = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (xk ⊕ yk) ⊕ 0 ⊕ ... ⊕ 0
      = s ⊕ xk ⊕ yk
 
(*) t = s ⊕ xk ⊕ yk.

Twierdzenie dowodzi się indukcyjnie ze względu wartość n na podstawie następujących dwóch lematów:

Lemat 1. Jeśli s = 0, to t ≠ 0 bez względu na to jaki możliwy ruch został wykonany.

Dowód: Jeśli żaden ruch nie jest możliwy, wówczas lemat jest pusto spełniony (pierwszy gracz nie może wykonać ruchu). W przeciwnym przypadku, dowolny ruch w k-tej kupce prowadzi do t = x_k ⊕ y_k na podstawie (*). Ta liczba jest różna od zera, gdyż x_k ≠ y_k.

Lemat 2. Jeśli s ≠ 0, to istnieje ruch taki, że t = 0.

Dowód: Niech d będzie indeksem pozycji najstarszego niezerowego bitu w binarnej reprezentacji liczby s. Wybieramy k tak aby bit na pozycji d liczby x_k był niezerowy (takie k musi istnieć – w przeciwnym przypadku bit na pozycji d liczby s wynosiłby 0). Kładąc y_k = s ⊕ x_k twierdzimy, że y_k < x_k. Istotnie, gdyż wszystkie bity na lewo od pozcyji d są te same w x_k i y_k, bit na pozycji d ma wartość zero (powoduje to zmniejszenie o wartości 2^d). Każda zmiana bitów powoduje zmianę wartości liczby o 2^d-1. Gracz pierwszy może zatem wykonać ruch na kupce x_k zabierając x_k - y_k pionków, wówczas

t = s ⊕ xk ⊕ yk           (z (*))
  = s ⊕ xk ⊕ (s ⊕ xk)
  = 0.

Jest to odmiana gry z ustaloną maksymalną liczbą elementów (k), które można pobrać w jednym ruchu. W praktyce gra się w takim przypadku na jednym stosie, jednak zasadę obierania zwycięskiej strategii można uogólnić na dowolną ich liczbę.

Wystarczy w pierwszym ruchu zmniejszyć wartość wszystkich stosów (początkowo a_i) do (a_i modulo k+1).

Dodatkowy warunek: Jeżeli po wykonaniu powyższej operacji, wszystkie stosy zostaną zredukowane do 0, zwycięską strategią jest pobieranie za każdym razem k elementów.

Nim w wersji Marienbad został stworzony jako gra komputerowa we wrocławskich zakładach Elwro, dla komputerów Odra 1003. Twórcą programu był Witold Podgórski, ręcznie ustawiając wartość każdej komórki pamięci; rozgrywka prowadzona była za pomocą dalekopisu. Odra 1003 wygrywała zawsze jeśli tylko gracz popełnił najmniejszy błąd, była też w stanie (przy czasie odpowiedzi szacowanym na jedną godzinę) grać z ośmioma tysiącami rządków zapałek. Mimo że program nie był rozpowszechniany oficjalnie przez Elwro, trafił on drogą towarzyską na Wojskową Akademię Techniczną, gdzie implementacji kodu dokonał ówczesny student uczelni, Bogdan Bleja. Nim był drugą co do popularności – po kółku i krzyżyku – grą, którą programowano wczesne maszyny liczące, z uwagi na prosty algorytm. Wojciech Pijanowski zaproponował nawet rozegranie partii Nima widzom Telewizji Polskiej, wykorzystując do tego komputer MOMIK 8b^[3].

Wariant gry jest łamigówką komputerową na stronie HackerRank^[4].

Zobacz hasło nim w Wikisłowniku

• Chomp

• LechL. Pijanowski LechL., Skarbnica gier, Warszawa: Młodzieżowa Agencja Wydawnicza, 1981, ISBN 83-203-0092-4, OCLC 830205881 .