Wythoff Nim, czyli krótkie warsztaty z kombinatorycznej teorii gier

Afiliacja: Wydział Matematyki i Nauk Informacyjnych, Politechnika Warszawska

W pewnym miejscu na skończonej szachownicy ustawiono hetmana. Dwóch graczy wykonuje nim ruchy naprzemiennie, a grę przegrywa ten z graczy, który ruchu nie może wykonać (a jest jego kolej). Jednak aby mieć pewność, że gra kiedyś się skończy, dopuszczamy jedynie ruchy w lewo, w dół oraz po jednej z przekątnych (tyle samo pól w lewo co w dół). Gra ta nosi nazwę Wythoff Nim, od nazwiska holenderskiego matematyka Willema Abrahama Wythoffa, który na początku dwudziestego wieku ją zaproponował i badał. Gra ta jest przykładem szerszej klasy gier kombinatorycznych, tzw. gier bezstronnych (impartial). Są to gry, w których gracze wykonują ruchy naprzemiennie, dostępne ruchy zależą jedynie od kolejności graczy, a przegrywa ten, który ruchu nie może wykonać – tak jak w Wythoff Nim. Co więcej, zakładamy, że niezależnie od przebiegu gry kończą się w pozycji terminalnej (nie ma remisów), a liczba wszystkich możliwych pozycji jest skończona (w skrócie: gra jest skończona). Zatem jeżeli będziemy w dalszej części używali terminu gra, to właśnie takie gry będziemy mieli na myśli. Naszym celem jest oczywiście ustalenie strategii wygrywającej.

Aby tego dokonać, podzielimy pozycje (czyli pola szachownicy) na dwa rodzaje. Pozycje P, czyli pożądane, oraz pozycje N, czyli niepożądane. Celem każdego gracza będzie wykonanie ruchu na pozycje pożądane, czyli zwycięskie, a unikanie pól niepożądanych. Precyzyjna definicja wygląda następująco:

Chwila refleksji pozwala nam stwierdzić, że taki podział umożliwia jednemu z graczy rozegrać zwycięską partię. Dokładniej, gracz, który wykonuje ruch z pozycji N, ma zwycięską strategię, wykonując ruch do P. Z kolei ruszając się z  P, nigdy do pozycji P nie trafimy, czyli w szczególności do lewego dolnego rogu – jedynej pozycji terminalnej. Zatem gracz wykonujący ruch z pozycji P nie ma strategii wygrywającej. Co więcej, przytoczona tutaj definicja w istocie pokazuje, jak rekurencyjnie (i jednoznacznie) podzielić pozycje na N i  P. Zróbmy to w sytuacji gry Wythoff Nim na standardowej szachownicy 8 na 8. Podziału można dokonać w kilku prostych krokach, zaczynając od pozycji terminalnej, jak ukazane jest to na rysunku  2.

Jak widać na rysunku  2, pozycje pożądane P są znacznie rzadsze niż pozycje  N. Ostatnia szachownica na powyższym rysunku daje nam pełen opis strategii w grze na szachownicy 8 na 8.

Zdefiniujmy następujące zbiory: \(A = \{\lfloor n\varphi \rfloor:\; n \in \mathbb{N} \cup \{0\}\}\) oraz \(B = \{\lfloor n\varphi \rfloor + n:\; n \in \mathbb{N} \cup \{0\}\}.\) Pokaż, że \(A \cap B = \{0\}\) oraz \(A \cup B = \mathbb{N} \cup \{0\}.\) Korzystając z tego faktu, udowodnij twierdzenie  1.

1. Jeżeli na początku gry hetman jest ustawiony na pozycji P, to pierwszy z graczy przegrywa.

2. Jeżeli zaś na początku gry hetman jest ustawiony na pozycji N, to pierwszy z graczy przesuwa go na pozycję P, i tak za każdym razem, kiedy jest jego kolej. Postępując w ten sposób, gwarantuje sobie wygraną.

Jeżeli kolumny i wiersze będziemy numerować, poczynając od 0, to przy pewnym niewielkim wysiłku (co pozostawiamy Czytelnikowi) można wykazać, że pozycje  P są postaci \((a_n,a_n+ n)\) bądź symetrycznie \((a_n+n,a_n),\) gdzie \(a_n\) to ciąg spełniający następujący wzór rekurencyjny: \[\text{$a_0=0$ oraz $a_n = \operatorname{mex} \{a_i, a_i+i \mid 0 \leq i < n\},$}\] w którym \(\operatorname{mex}(A) = \min (\mathbb{N} \cup \{0\} \setminus A).\) Przyjrzyjmy się wykresowi  \(a_n\) dla pierwszych 100 wartości.

Widać, że wartości \(a_n\) rosną w sposób prawie liniowy. Dokładniejszy rachunek pokazuje, że \(\lim_{n \rightarrow \infty} \frac{a_n}{n} \approx 1{,}61803.\) Nietrudno rozpoznać, że jest to \(\varphi = \frac{1+\sqrt{5}}{2},\) czyli tzw. złoty podział. Można wykazać, że \(a_n= \lfloor n\varphi \rfloor,\) uzyskując rozwiązanie nierekurencyjne Wythoff Nim:

Zastanówmy się teraz, co wydarzy się, gdy na planszy rozstawionych zostanie kilka hetmanów, a gracze w swojej turze mogą poruszyć tylko jednego z nich. Dopuszczamy możliwość, że na jednym polu stoi wiele hetmanów. Gra kończy się, gdy nie można poruszyć żadnego z nich. Do tej pory pozycję w grze mogliśmy utożsamiać z polem, na którym stoi hetman. Natomiast jeśli na planszy jest ich więcej, to mówiąc ,,pozycja”, mamy na myśli całą planszę z zadanym układem. Dla rozróżnienia polem P będziemy nazywać takie pole szachownicy, że po ustawieniu tam jednego hetmana odpowiadająca pozycja (w grze z jednym hetmanem) jest pozycją P. Analogicznie definiujemy pole N. Podziału na pola  P i  N dokonaliśmy w pierwszej części artykułu. W pewnych sytuacjach strategia wygrywająca jest łatwa do przewidzenia:

1. Gdy wszystkie hetmany, poza jednym, ustawione są na polu P, to zwycięża gracz wykonujący ruch, mianowicie: przesuwając hetmana z pola N na pole  P.

2. W grze z dwoma hetmanami, jeżeli ustawione są na tym samym polu (lub polach symetrycznych), to drugi z graczy ma strategię zwycięską: wystarczy, że będzie kopiował ruchy przeciwnika.

W pełnej ogólności sam podział na pola P i  N nie wystarczy. Wtedy w sukurs przychodzi pojęcie wartości Sprague’a–Grundy’ego (w skrócie S-G). Dokładniej, wartość S-G \(g(x)\) dla pozycji \(x\) w grze z jednym hetmanem definiujemy rekurencyjnie: \(g(t)=0\) dla dowolnej pozycji terminalnej, \(g(x)=\operatorname{mex}\{g(y)|\; \text{ z } x \text{ istnieje ruch do pozycji } y \}.\) Postępując podobnie jak z wyznaczaniem pozycji P i  N, otrzymujemy wartości S-G dla pozycji w grze z jednym hetmanem, co ilustruje rysunek  4.

Dla dwóch liczb \(a,b\) całkowitych nieujemnych definiujemy sumę Nim \(a \oplus b\) jako xor ich rozwinięć binarnych, wyrażony na powrót w systemie dziesiętnym. Przykładowo, chcąc policzyć \(29 \oplus 11,\) najpierw reprezentujemy liczby w systemie dwójkowym, czyli \(29 = 11101_2\) oraz \(11 = 1011_2,\) następnie \[\begin{array}[b]{c@{}c@{}c@{}c@{}c@{}c@{}} & 1 & 1 & 1 & 0 & 1_2 \\ \texttt{xor} & & 1 & 0 & 1 & 1_2 \\ \hline & 1 & 0 & 1 & 1 & 0_2 \\ \end{array}.\] Ponieważ \(10110_2=22,\) więc możemy zapisać, że \(29 \oplus 11=22.\)

Obserwację tę nietrudno udowodnić, i to nie tylko dla Wythoff Nim, ale dla wszystkich gier kombinatorycznych bezstronnych, skończonych i bez remisów. Zatem wartości S-G niosą więcej informacji niż tylko podział na pozycje P i  N. Zachodzi bowiem znane klasyczne twierdzenie Sprague’a–Grundy’ego, które w wersji dla gry Wythoff Nim formułuje się następująco:

Sformułowanie twierdzenia Sprague’a–Grundy’ego w pełnej ogólności wymaga wprowadzenia pojęcia sumy gier. Suma gier kombinatorycznych \(G+H\) to nowa gra, gdzie gracze w każdej turze wykonują ruch tylko w jednej z nich. Grę przegrywa ten gracz, który nie może wykonać ruchu. W istocie opisana wersja gry Wythoff Nim z wieloma hetmanami jest sumą gier Wythoff Nim z jednym hetmanem. Gdy mamy do czynienia z grami bezstronnymi, skończonymi i bez remisów, gdzie ostatni wykonujący ruch wygrywa, przyjmujemy wartość S-G dla każdej pozycji \(x\) w \(G,\) \(y\) w \(H\) oraz dla \((x,y),\) która jest pozycją w \(G+H,\) jako odpowiednio \(g(x),g(y)\) i \(g(x,y).\) Wtedy \(g(x,y) = g(x) \oplus g(y).\) Oczywiście twierdzenie zachodzi również dla sumy większej liczby gier.

Przykładowo na rysunku 5 mamy hetmany ustawione na pozycjach o wartościach S-G \(6,9\) i \(5\) (lewa szachownica, korzystamy z rys.  4. ) Ponieważ \(6 \oplus 9 \oplus 5 = 10,\) jest to pozycja N. Rzeczywiście, jeśli przesunąć hetmana z pozycji o współrzędnych \((7,3)\) na pozycję \((5,1),\) hetmany stałyby na polach o wartościach S-G \(6,3,5.\) Skoro \(6 \oplus 3 \oplus 5 = 0,\) z twierdzenia 2 otrzymujemy, że prawa szachownica to pozycja P.

Okazuje się, że wyznaczenie wzoru nierekurencyjnego wartości Sprague’a–Grundy’ego dla gry Wythoff Nim jest problemem otwartym. Podkreślmy, że opisaną tutaj technikę można zastosować jedynie w grach kombinatorycznych, bezstronnych i skończonych.

Gdybyśmy jednak dopuścili dwa rodzaje hetmanów, czarnych i białych, a każdemu z graczy pozwolili poruszać jedynie hetmanami w swoim kolorze, to taka gra nie byłaby bezstronna i do jej analizy potrzebne byłyby inne narzędzia. Podobnie zmiana warunku zwycięstwa na odwrotny, czyli na zwycięstwo gracza pozbawionego ruchu, zazwyczaj dużo bardziej komplikuje analizę gier bezstronnych. Zachęcamy Czytelnika do dalszych dociekań.

Zadanie. Na trzech stołach rozrzucona została pewna ilość monet. Dwóch graczy może naprzemiennie zabierać 1, 2 lub 3 monety, ale tylko z jednego, wybranego przez siebie stołu. Oczywiście wyboru stołu gracze mogą dokonywać za każdym razem, gdy wykonują swój ruch. Opisz pozycje pożądane P oraz niepożądane N. Wskaż zwycięski ruch z pozycji, gdzie na stołach mamy odpowiednio 61, 101 i 15 monet.

Zadanie. Rozważ grę Wythoff Nim z jednym hetmanem z odwrotnym warunkiem zwycięstwa. Rozwiąż ją dla szachownicy 8 na 8.