Nim

Z Wikipedii, wolnej encyklopedii

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.
  • Chomp: Pionki ustawiamy w prostokąt. Zbierając wybrany kamień trzeba zabrać wszystkie na prawo i w górę od niego.

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
      = 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 = 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 = s ⊕ xk ⊕ yk           (z (*))
  = s ⊕ xk ⊕ (s ⊕ xk)
  = 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.

Implementacje komputerowe[edytuj | edytuj kod]

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 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.
  3. ↑ Bartłomiej Kluska, Bartosz Rozwadowski: Bajty polskie. Sosnowiec: 2014, s. 5-7. ISBN 978-83-927229-2-2.
  4. ↑ Misère Nim [online], HackerRank [dostęp 2023-09-29] (ang.).

Bibliografia[edytuj | edytuj kod]

Źródło: „https://pl.wikipedia.org/w/index.php?title=Nim&oldid=71405050”