Nim

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Ujednoznacznienie Ten artykuł dotyczy gry. Zobacz też: technologia 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[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)

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

Istnienie optymalnej strategii wykazał Charles L. Bouton[1].

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

Przypisy

  1. Bouton, C. L. Nim, a Game with a Complete Mathematical Theory Ann. Math. Princeton 3, ss. 35-39.

Bibliografia[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]