Przeskocz do treści

Delta mi!

Loading

Gra Grim i twierdzenie Sprague’a–Grundy’ego

Martha Łącka i Mateusz Łącki

o artykule ...

  • Publikacja w Delcie: czerwiec 2014
  • Publikacja elektroniczna: 02-06-2014
  • Autor: Martha Łącka
    Afiliacja: studentka, Wydział Matematyki i Informatyki, Uniwersytet Jagielloński
    Autor: Mateusz Łącki
    Afiliacja: doktorant, Uniwersytet Jagielloński

Pewnie część czytelników Delty zna grę Nim – zarówno jej zasady, jak i właściwą dla niej strategię wygrywającą. W tym artykule chcemy przedstawić inną grę grafową. Grę o prostych zasadach, ale trudniejszą niż Nim do dokładnego przeanalizowania. Tą grą jest – stworzony przez Jamie Peabody i Karen Willis – Grim. Podamy efektywny sposób orzekania, który gracz ma strategię wygrywającą. Co najciekawsze, można go zastosować do szerokiej klasy tego typu gier dwuosobowych, zawierającej Grima i Nima.

obrazek

Rys. 1 Graf, który określamy mianem „łańcucha”. W tym przypadku jest to łańcuch długości 8.

Rys. 1 Graf, który określamy mianem „łańcucha”. W tym przypadku jest to łańcuch długości 8.

W Grimie dwaj uczestnicy naprzemiennie wykonują ruchy. Na początku rozgrywki mają oni do dyspozycji pewien graf. W tym artykule będziemy rozważać jedynie grafy początkowe, które są „łańcuchami”, tzn. takie grafy spójne, w których dwa wierzchołki mają stopień 1, a reszta wierzchołków ma stopień 2 (taki graf pokazany jest na rysunku 1).

W każdym ruchu gracz wybiera dowolny nieizolowany wierzchołek grafu i usuwa go wraz ze wszystkimi krawędziami z niego wychodzącymi. Przegrywa gracz, który jako pierwszy nie może wykonać ruchu.

obrazek

Rys. 2 Przykładowa rozgrywka dla nieparzystej liczby wierzchołków przy założeniu, że gracz pierwszy gra zgodnie z opisaną w artykule strategią wygrywającą.

Rys. 2 Przykładowa rozgrywka dla nieparzystej liczby wierzchołków przy założeniu, że gracz pierwszy gra zgodnie z opisaną w artykule strategią wygrywającą.

Jeśli liczba wierzchołków grafu jest nieparzysta (oczywiście, większa od 1), to istnieje strategia wygrywająca dla gracza pierwszego – wystarczy jako pierwszy wierzchołek wybrać wierzchołek będący środkiem symetrii, a następnie odbijać ruchy przeciwnika względem środka (Rys. 2). Po każdym ruchu pierwszego gracza, postępującego zgodnie z opisanym tu algorytmem, pozostałe wierzchołki są ponownie symetryczne względem środka. Dopóki drugi gracz jest w stanie wykonać ruch, dopóty pierwszy gracz może rozpocząć następną kolejkę. Zatem drugi gracz nie może wykonać dozwolonego ruchu jako ostatni. Ponieważ wierzchołków jest skończenie wiele, gra musi zakończyć się jego przegraną.

Trudniejszy do rozważenia jest przypadek, gdy liczba wierzchołków jest parzysta. Gdy wynosi ona 2, to strategię wygrywającą ma gracz pierwszy – niezależnie od wykonanego ruchu, drugiemu graczowi pozostanie jedynie izolowany wierzchołek. Dla czterech wierzchołków strategię wygrywającą ma gracz drugi. Dla łańcucha długości 6, 8 lub 10 znów wygrywa gracz pierwszy, ale dla długości 12 – drugi. Można tego dowieść, rozrysowując drzewo gry, niestety, o wykładniczej zależności liczby węzłów od długości łańcucha. Co dalej? Z pomocą przychodzi nam komputer i twierdzenie Sprague’a–Grundy’ego. Żeby je przedstawić, wprowadzimy najpierw kilka pojęć.

Grę nazwiemy normalną, jeśli przegrywa w niej ten z graczy, który jako pierwszy nie jest w stanie wykonać ruchu. Będziemy mówić, że gra jest bezstronna, jeśli obaj gracze mogą wykonać te same ruchy, mając do dyspozycji daną planszę. Przykładowo gra w kółko i krzyżyk bezstronna nie jest, gdyż gracz stawiający kółko nie może postawić krzyżyka. Grim i Nim zaliczają się do gier bezstronnych.

Funkcja mex (ang. minimum excludant) przyporządkowuje podzbiorowi zbioru liczb naturalnych najmniejszą liczbę naturalną do niego nienależącą. Na przykład,

display-math

Funkcja Sprague’a–Grundy’ego  math określona jest rekurencyjnie dla poszczególnych pozycji w grze. Dla konfiguracji  math w której gracz nie jest w stanie wykonać ruchu, definiujemy math Dla innych pozycji funkcja ta zwraca math zbioru wartości  math dla wszystkich pozycji  math do których możemy dojść w jednym ruchu z  math Do poprawności definicji  math wystarczy acykliczność gry, czyli brak możliwości powtórzenia konfiguracji w czasie rozgrywki, oraz założenie, że dla każdej konfiguracji początkowej gra może potrwać co najwyżej skończenie wiele tur.

obrazek

W grze Grim dla pozycji składającej się z jednego bądź kilku izolowanych wierzchołków nie ma możliwości wykonania ruchu, więc math przyjmuje wartość math Łańcuchowi długości 2 funkcja  math przyporządkowuje math równe math z wartości  math dla wierzchołka izolowanego, który uzyskujemy niezależnie od tego, na który z dwóch możliwych ruchów się zdecydujemy. Zatem math Wartość math równa jest natomiast wartości funkcji math dla zbioru zawierającego: wartość  math dla dwóch izolowanych wierzchołków math oraz dla łańcucha długości 2, math a zatem math

Nim-suma to pewne działanie  math które dwóm liczbom naturalnym przyporządkowuje również liczbę naturalną. Aby obliczyć Nim-sumę, należy zapisać oba argumenty w systemie dwójkowym, dodać liczby stojące przy tych samych potęgach dwójki (a więc zera lub jedynki) modulo 2, a następnie wynik zinterpretować jako zapis dwójkowy szukanej liczby. Z powyższego przepisu wynika od razu, że  math

Twierdzenie Sprague’a–Grundy’ego pozwala wyznaczyć wartości funkcji  math w sytuacji, gdy gracze grają w kilka normalnych i bezstronnych gier jednocześnie: w każdym ruchu wybierają jedną z plansz i wykonują na niej ruch zgodnie z zasadami odpowiadającej jej gry. Tak powstałą „multigrę” nazywamy sumą gier.

Twierdzenie 1 (Sprague–Grundy). Funkcja Sprague’a–Grundy’ego  math dla sumy normalnych, bezstronnych gier jest równa Nim-sumie funkcji Sprague’a–Grundy’ego poszczególnych gier. Gracz wykonujący ruch ma strategię wygrywającą wtedy i tylko wtedy, gdy wartość funkcji  math dla aktualnej pozycji gry jest niezerowa.

W przypadku, gdy funkcja  math dla pozycji gry  math przyjmuje wartość math możliwy jest ruch do takiej pozycji  math by math zgodnie z definicją funkcji math Pozycja  math  może kończyć grę (dla takich  math  z definicji math), choć nie musi. Jeżeli math to wówczas dla każdej pozycji  math osiągalnej za pomocą jednego ruchu, mamy math Strategia wygrywająca polega na takim wykonywaniu ruchów, by po każdym z nich trafić do takiej pozycji  math że  math

Jako przykład zastosowania rozważmy sumę dwóch egzemplarzy pewnej gry bezstronnej i normalnej (gramy tymi samymi zasadami, rozpoczynamy z tą samą pozycją początkową  math na obu planszach). Wygrywa ten z graczy, który jako ostatni jest w stanie wykonać ruch. Na mocy podanego twierdzenia wartość funkcji Sprague’a–Grundy’ego dla tak powstałej gry będzie równa

display-math

a zatem nie istnieje strategia wygrywająca dla pierwszego gracza. Do takiego wniosku możemy też dojść bezpośrednio. Wystarczy zauważyć, że gracz drugi może zapewnić sobie zwycięstwo przez kopiowanie ruchów gracza pierwszego na planszy, na której ostatnio nie wykonał ruchu gracz pierwszy.

Jaki związek ma twierdzenie Sprague’a–Grundy’ego z grą Grim? Jeśli startując z łańcucha, usuniemy jeden wierzchołek, to otrzymamy dwa krótsze łańcuchy (być może jeden pusty, czyli długości 0), z których każdy od tej pory można traktować jako osobną grę. Chcąc wyznaczyć wartość funkcji Sprague’a–Grundy’ego dla łańcucha długości  math należy obliczyć math z wartości  math dla gier będących sumami łańcuchów długości  math oraz math dla math ze zbioru math Wartość tej funkcji dla każdej takiej sumy łańcuchów otrzymujemy z twierdzenia Sprague’a–Grundy’ego – jest to math Stąd otrzymujemy definicję rekurencyjną:

display-math

Powyższy przepis można bardzo efektywnie (w porównaniu z przeszukiwaniem pełnego drzewa gry) wykorzystać do obliczenia wartości  math za pomocą komputera. Uproszczenie bierze się stąd, iż zamiast rozpatrywać wszystkie możliwe konfiguracje planszy, możemy, dzięki twierdzeniu, ograniczyć się do rozpatrywania konfiguracji będących łańcuchem lub sumą dwóch łańcuchów. Prosta implementacja ma pesymistyczną złożoność  math  przy założeniu, że operację xor liczymy w czasie stałym.

Wykorzystując tę technikę, można sprawdzić, że jedynymi liczbami wierzchołków mniejszymi od  math przy których strategię wygrywającą ma gracz drugi, są dokładnie liczby ze zbioru:

display-math

Pytanie, czy to jedyne liczby o tej własności, pozostaje otwarte.

Podanie jawnego wzoru na wartości funkcji Sprague’a–Grundy’ego dla różnych dwuosobowych gier bezstronnych w ogólności uchodzi za zadanie trudne. Obliczanie wartości tej funkcji za pomocą komputera (a nawet, przy odrobinie wytrwałości, na kartce papieru) zazwyczaj jest dużo prostsze, a pozwala określać, który z graczy ma strategię wygrywającą, dla konkretnych, także nietrywialnych sytuacji. Tak otrzymane wyniki mogą prowadzić do ciekawych hipotez dotyczących postaci funkcji  math Czytelnika Wnikliwego zachęcamy również do wyznaczenia jawnego wzoru funkcji Sprague’a–Grundy’ego dla gry Nim.