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.

Zasady

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.

Warianty

• 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 dzielimy 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.

Strategia

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)

Dowód zwycięskiej strategii

Istnienie optymalnej strategii wykazał Charles L. Bouton.

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 najważniejszego 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.

Gra z limitem elementów

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.

Bibliografia

• L. Pijanowski Skarbnica gier, Warszawa 1981 (ISBN 83-203-0092-4)

Zobacz też

• Chomp