Nim

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

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: 20 = 1; 21 = 2; 22 = 4; 23 = 8; ...; 2n. 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.

Dowód zwycięskiej strategii[edytuj | edytuj kod]

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 x1, ..., xn oznaczają liczebność kupek przed wykonaniem ruchu natomiast y1, ..., yn oznaczają odpowiednio liczebność po wykonaniu ruchu. Połóżmy s = x1 ⊕ ... ⊕ xn i t = y1 ⊕ ... ⊕ yn. Jeśli ruch został wykonany na k-tej kupce, to otrzymujemy xi = yi dla każdego i ≠ k oraz xk > yk. Z własności powyżej wspomnianych otrzymujemy:

    t = 0 ⊕ t
      = sst
      = s ⊕ (x1 ⊕ ... ⊕ xn) ⊕ (y1 ⊕ ... ⊕ yn)
      = s ⊕ (x1y1) ⊕ ... ⊕ (xnyn)
      = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (xkyk) ⊕ 0 ⊕ ... ⊕ 0
      = sxkyk
 
(*) t = sxkyk.

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 = xk ⊕ yk na podstawie (*). Ta liczba jest różna od zera, gdyż xk ≠ yk.

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 xk był niezerowy (takie k musi istnieć – w przeciwnym przypadku bit na pozycji d liczby s wynosiłby 0). Kładąc yk = s ⊕ xk twierdzimy, że yk < xk. Istotnie, gdyż wszystkie bity na lewo od pozcyji d są te same w xk i yk, bit na pozycji d ma wartość zero (powoduje to zmniejszenie o wartości 2d). Każda zmiana bitów powoduje zmianę wartości liczby o 2d-1. Gracz pierwszy może zatem wykonać ruch na kupce xk zabierając xk - yk pionków, wówczas

t = sxkyk           (z (*))
  = sxk ⊕ (sxk)
  = 0.

Gra z limitem elementów[edytuj | edytuj kod]

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 ai) do (ai 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.

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. Stanisław Ubermanowicz, Piotr Fiorek, Gra logiczna NIM, [w:] Program nauczania-uczenia się infotechniki, [red.] Stanisław Ubermanowicz, Krzysztof Wawrzyniak. Poznań: FWiOO, tom 2., 2014, s. 366-371.
  2. Bouton, C. L. Nim, a Game with a Complete Mathematical Theory Ann. Math. Princeton 3, ss. 35-39.

Bibliografia[edytuj | edytuj kod]