Dołącz do czytelników
Brak wyników

Otwarty dostęp , Pomysł na lekcję

18 marca 2021

NR 48 (Marzec 2021)

Gra nim i jej krewni

124

Gra Nim to jeden z ciekawszych matematycznych „obiektów”. Jej zaletami są proste reguły i możliwość odgadnięcia teorii w wielu przypadkach. Uczniowie mogą sami odkrywać strategie gry zapewniające zwycięstwo.

Klasyczna gra Nim

Wikipedia podaje, że Nim to stara chińska gra dla dwóch osób (Jianshizi, czyli „gra w zabieranie kamieni”). Załóżmy, że mamy n stosów kamieni: w pierwszym stosie jest a1 kamieni, w drugim a2, …, w n-tym an kamieni. Dwaj gracze (rozpoczynającego nazwij­-
my A, grającego jako drugi B) wykonują na zmianę ruchy. Każdy ruch polega na wybraniu dowolnego stosu (powiedzmy i-tego), a następnie wzięciu z tego stosu 1 lub 2, …, lub ai kamieni. Wygrywa ten gracz, który weźmie ostatni (ostatnie kamienie). Opisaną klasyczną wersję gry Nim oznaczać będziemy Nim (a1, a2, …, an).
Gra Nim jest grą strategiczną, nie ma w niej remisów; istnieje także wersja tej gry (nazywa się ją misère, co z francuskiego można przetłumaczyć jako uboga), w której przegrywa ten gracz, który weźmie ostatni kamień. Naszym zadaniem jest opisanie strategii gry Nim, tzn. metody, która jednemu z graczy zapewnia zwycięstwo – oczywiście pod warunkiem, że nie popełnia błędów.

POLECAMY

Odkrywanie strategii gry Nim

Jasne jest, że w grze Nim, gdy jest tylko jeden stos kamieni, wygrywa gracz A. Warto poprosić uczniów o uzasadnienie, warto także zapytać ich o grę w wersji misère. Kolejny etap to gra Nim z dwoma stosami. Tutaj też uczniowie poradzą sobie z teorią: gdy oba stosy są równoliczne, to wygrywa gracz B, w przeciwnym przypadku gracz A. Nieco trudniej znaleźć odpowiedź dla wersji misère – tutaj przy równolicznych stosach wygrywa też gracz B, dla nierównolicznych gracz A.
Zajmijmy się teraz grami Nim (a1, a2, a3). Zadaniem uczniów jest odkrycie teorii i strategii, przy czym warto podzielić pracę nad grą z trzema stosami na trzy przypadki:

  • Nim (a1, a1, a1); trzy stosy mają jednakową liczbę elementów, uczniowie bez trudu poradzą sobie z uzasadnieniem, że w tej grze wygrywa A – wystarczy, że weźmie cały jeden stos, doprowadzając do gry z dwoma jednakowymi stosami, w tej „nowej” grze gracz A staje się graczem B i powtarza ruchy swojego przeciwnika. Taka analiza będzie powtarzana wielokrotnie, jeśli gracz A ma strategię zwycięską, to powinien wykonać ruch do takiej pozycji, w której drugi gracz powinien wygrać. Natomiast istnienie strategii zwycięskiej dla B oznacza, że niezależnie od ruchu przeciwnika doprowadza zawsze do pozycji zwycięskiej dla pierwszego gracza, którym po ruchu A staje się gracz B.
  • Nim (a1, a1, a2); analizę pozostawiamy Czytelnikowi.
  • Nim (a1, a2, a3), przy czym liczby a1, a2, a3 są różne (bez zmniejszania ogólności możemy zakładać, że a1 < a2, < a3).

Rozpatrzmy na przykład grę Nim (1, 2, 3). Jasne jest, że wzięcie przez A któregoś całego stosu prowadzi do jego porażki (Dlaczego?), zatem gracz A powinien spróbować zmniejszyć drugi lub trzeci stos. Spójrzmy na możliwości takiego ruchu dla gracza A:
(1, 2, 3) → (1, 1, 3) – gracz A zmniejszył drugi stos o 1. Jaki ruch powinien wykonać B, aby wygrać?
(1, 2, 3) → (1, 0, 3) – gracz A zabrał cały drugi stos. Jaki ruch powinien wykonać B, aby wygrać?
(1, 2, 3) → (1, 2, 2) – gracz A zmniejszył trzeci stos o 1. Jaki ruch powinien wykonać B, aby wygrać?
(1, 2, 3) → (1, 2, 1) – gracz A zmniejszył trzeci stos o 2. Jaki ruch powinien wykonać B, aby wygrać?
(1, 2, 3) → (1, 2, 0) – gracz A zabrał cały trzeci stos. Jaki ruch powinien wykonać B, aby wygrać?

Z przeprowadzonej analizy wynika, że zwycięzcą gry Nim (1, 2, 3), przy dobrej grze, jest gracz B, co zapiszemy tak: z (Nim (1, 2, 3)) = B. Zauważmy, że z (Nim (1, 2, n)) = A dla dowolnego n ≥ 4. Czytelnik zechce to sprawdzić sam, podając przy tym pierwszy zwycięski ruch gracza A.

Gra Nim – teoria

Teorię gry Nim opracował amerykański matematyk Charles L. Bouton; jego artykuł Nim, A Game with a Complete Mathematical Theory został opublikowany w „The Annals of Mathematics” 2 nd ser., v. 3, nr 1/4, 1901–1902, str. 35–39. Bouton w artykule tym wspomina, że podobną teorię opisał Paul E. More w 1899 roku, ale nie podał on żadnych dowodów. W rozumowaniu Boutona pojawiła się funkcja, którą definiuje się tak: 
Dwie liczby naturalne m, n zapisujemy w systemie dwójkowym i dodajemy modulo 2, tzn.:
nimsuma (m, n) = (m1, …, mk)2 + (n1, …, nk)2 = (m1 + n1 (mod 2), …, mk + nk (mod 2));
np. nimsuma (2, 4) = (0, 1, 0)2 + (1, 0, 0)2 = (1, 1, 0). 

Zauważmy, że jeśli liczby cyfr liczb w zapisie dwójkowym są różne, to wyrównujemy je, dopisując z przodu „krótszej” liczby odpowiednią liczbę zer.
Funkcję nimsuma możemy zastosować także dla trzech, czterech, … liczb. Bouton zauważył, że nimsuma (a1, a2, …, an) jednoznacznie wskazuje, kto powinien wygrać, A czy B. Sprawdźmy to dla dwóch oraz dla trzech stosów.


W grze Nim (a1, a2, …, an) wygrywa gracz A wtedy i tylko wtedy, gdy nimsuma (a1, a2, …, an) zawiera co najmniej jedną cyfrę 1. 

Dowód tego twierdzenia (ma ono formę równoważności) nie jest trudny, zwłaszcza wynikanie ⇒. Można rozumować tak: gdy nimsuma (a1, a2, …, an) = 
= (0, … , 0), to po każdym ruchu gracza A otrzymujemy grę z nimsumą niezerową, a to znaczy, że gracz rozpoczynający w nowej pozycji (B) powinien wygrać. Kluczowy jest dowód ⇐; A powinien znaleźć odpowiedni stos oraz wziąć z niego tyle kamieni, aby po tym ruchu otrzymać grę z zerową nimsumą. Wiemy, że na przykład dla gry Nim (1, 2, 4) wzięcie jednego kamienia z trzeciego stosu to jedyny ruch A przynoszący mu zwycięstwo, dlatego wybór stosu jest istotny. W praktyce rozumujemy tak: ponieważ spełniony jest warunek nimsuma (a1, a2, …, an) = (cn, cn − 1, …, c1) ≠ (0, …, 0), weźmy największe takie k, że ck ≠ 0. Oznaczmy przez aʹk liczbę, której zapis dwójkowy jest równy nimsuma (ak, (cn, cn − 1, …, c1)). Wtedy z k-tego stosu należy wziąć taką liczbę, aby w stosie tym pozostało aʹk elementów. Dla ilustracji tej procedury spójrzmy jeszcze raz na Nim (1, 2, 4); zauważmy, że nimsuma (1, 2, 4) = (1, 1, 1), zatem k = 3 oraz aʹ3 = 3 = (0, 1, 1)2 (ze stosu numer 3 zabieramy jeden kamień). 

Marienbad

Jednym z wariantów Nima jest gra Marienbad, którą Wikipedia opisuje tak:

16 pionów ustawiamy w 4 rzędach: rząd nr 1 – 1 pionek; rząd nr 2 – 3 pionki; rząd nr 3 – 5 pionków; rząd nr 4 – 7 pionków. Ruch polega na wzięciu od jednego pionka do całego rzędu. Przegrywa gracz, który zabiera ostatni pionek.

Zauważmy, że Marienbad jest wersją misère gry Nim (1, 3, 5, 7). Gra ta wzbudziła spore poruszenie w warszawskim środowisku matematycznym, ale nie z powodów artystycznych. Wojciech Guzicki w artykule Zeszłego roku w Marienbadzie („Matematyka” 2-23/1990, str. 100–110) pisze, że on i wielu jego kolegów było na filmie właśnie o takim tytule dwa razy: w filmie jeden z bohaterów zapraszał gości do tej gry i zawsze wygrywał. Matematycy starali się rozwikłać zagadkę nieomylności tego pana. Gorąco polecam wspomniany artykuł, można w nim znaleźć programy komputerowe do symulacji matematycznej gry Nim i gry w matematyczne kręgle (angielska nazwa Kayles). 
Obliczmy nimsuma (1, 3, 5, 7): nimsuma (1, 3, 5, 7) = nimsuma ((0, 0, 1)2, (0, 1, 1)2, (1, 0, 1)2, (1, 1, 1)2) = (0, 0, 0, 0)

Według przedstawionego twierdzenia Boutona w klasycznym Nimie powinien wygrać gracz. Twierdzenie to jest także prawdziwe dla gry Nim w wersji misère, przy czy zwycięska strategia wymaga więcej skupienia od gracza, który powinien wygrać. Do ćwiczeń z grą Marienbad polecam stronę: https://www.archimedes-lab.org/How_to_Solve/Win_at_Nim.html#.
Klikając w zakładkę Play_Now, możemy spróbować swoich sił w rozpatrywanej grze; oto trzy zrzuty ekranu (grałem jako pierwszy). Przegrałem, komputer znał strategię zwycięską! (ryc. 1).
 

Ryc. 1


Przed kolejnym moim ruchem było jasne, że przegram. I tak rzeczywiście się stało, przed wzięciem przeze mnie ostatniej zapałki pojawił się komunikat:  Sorry… I won!

Kto pierwszy do n?

Ostatni omawiany w tym artykule wariant gry Nim można nazwać Nim z ograniczeniami. Tym razem dysponujemy jednym stosem z n kamieniami, ale w każdym ruchu możemy zabrać jeden lub dwa kamienie. Wygrywa ta osoba, która weźmie ostatni lub dwa ostatnie kamienie. Spójrzmy na wersję „wyścigową” (atrakcyjniejszą dla uczniów); będziemy korzystać z wizualizacji napisanej w języku Logo (wersja Logomocja Imagine) (ryc. 2).

Ryc. 2

 

Ryc. 3

 

Ryc. 4


Spójrzmy na ekran z finałem gry (ryc. 4).
Gra została napisana w kilku wersjach, ta nosi nazwę: 
gra20_mądry_komputer. Grałem w grę „Kto pierwszy do 20” z wieloma uczniami (ze szkół podstawowych i ponadpodstawowych). Zawsze radość pokonania komputera była ogromna (niektórzy uczniowie bacznie obserwowali strategię komputera). Warto z uczniami przeprowadzić eksperyment polegający na odkryciu teorii gry. Jeśli dobrze nimi pokierujemy, znajdą strategię (teorię) gry bez trudu. Liczba 20 została wybrana celowo – jest zbyt duża, aby rozpatrywać wszystkie możliwości, a jednocześnie na tyle mała, że pojedyncza rozgrywka trwa krótko. Uczniowie mogą rysować 20 kółek i skreślać jedno lub dwa kółka. 
Na czym polega rola nauczyciela? Na zwróceniu uwagi, że warto odgadnąć teorię gry dla liczb mniejszych od 20. Spójrzmy na tabelkę:
 

Meta Kto wygra?
1 A
2 A
3 B
4 A
5 A
6 B
7 A


Uczniowie bez trudu uzupełnią tabelkę o dalsze wyniki – ważne jest, aby wyjaśniali, dlaczego wybrali A lub B. Na koniec warto ich poprosić o sformułowanie ogólnej własności:

W grze „Kto pierwszy do n” wygrywa gracz A wtedy i tylko wtedy, gdy liczba n nie dzieli się przez 3.

Uwagi końcowe

Gra Nim to jeden z ciekawszych matematycznych „obiektów”. Jej zaletami są proste reguły i możliwość odgadnięcia teorii w wielu przypadkach. Ostatni przykład ma także bardzo ważną szkolną zaletę – łatwo go modyfikować: zamiast ruchów 1, 2 można rozpatrywać ruchy 1, 2, 3 lub 1, 2, 3, 4 itd.; uczniowie mogą też proponować swoje własne reguły wykonywania ruchów. 

Przypisy