Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu
Graf pozycji gry hex \(2\times 2\)
(z dokładnością do symetrii)[0.4]
Graf stanów planszy gry chrup! \(3\times 2\) (z dokładnością do symetrii)
Przed lekturą warto zajrzeć do poprzedniego kącika, w którym są potrzebne definicje i przykłady. Graczem I nazywamy tego, który rozpoczyna grę, a gracz II to jego przeciwnik. Będziemy też rozróżniać grę (na przykład szachy) od rozgrywki (partii).
Przez pozycję rozumiemy sytuację w rozgrywce na jej początku lub po ruchu jednego z graczy. Pozycja składa się z dwóch części: stanu (w większości gier to po prostu „wygląd” planszy) i informacji, który z graczy ma ruch. Jest to informacja niezbędna – na przykład w warcabach są takie ułożenia pionków, w których ruch mogą mieć zarówno białe, jak i czarne; traktujemy to jako dwie różne pozycje.
Dla każdej gry kombinatorycznej możemy zbudować strukturę zwaną grafem pozycji. Wierzchołki tego grafu odpowiadają pozycjom, a zorientowane krawędzie – ruchom (czyli \(A\to B,\) jeśli gracz może wykonać ruch z pozycji \(A\) do pozycji \(B\)). Pozycja początkowa jest jedyną, z której strzałki wyłącznie wychodzą. Końcowe pozycje to takie, z których nie wychodzi już żadna strzałka – określają one jednoznacznie wynik rozgrywki. Na rysunku obok widać graf pozycji gry hex na planszy \(2\times2\) (z dokładnością do symetrii).
Najłatwiejsze do analizy są gry, które zawsze kończą się zwycięstwem jednego z graczy (remis jest niemożliwy). Poniższe rozważania dotyczą właśnie takich gier.
Pozycję nazwiemy rozstrzygniętą, jeśli w rozgrywce rozpoczynającej się od niej jeden z graczy może zapewnić sobie zwycięstwo niezależnie od poczynań przeciwnika. Jest jasne, że:
jeśli w pozycji \(A\) gracz może wykonać ruch do wygranej dla niego pozycji, to pozycja \(A\) również jest dla niego wygrana;
jeśli w pozycji \(B\) wszystkie ruchy gracza prowadzą do przegranej dla niego pozycji, to pozycja \(B\) jest również dla niego przegrana.
To pozwala na proste sformułowanie uniwersalnej strategii: gracz, jeśli tylko może, wykonuje ruch do pozycji dla niego wygranej.
Twierdzenie. W grach kombinatorycznych bez remisów każda pozycja jest rozstrzygnięta. W szczególności, w każdej takiej grze jeden z graczy ma strategię wygrywającą (krócej: każda gra jest rozstrzygnięta).
Dowód. Dla każdej pozycji jej głębokością nazwiemy największą możliwą liczbę ruchów od tej pozycji do zakończenia rozgrywki. Jeśli pozycja ma głębokość \(0,\) to jest końcowa i jest rozstrzygnięta z definicji. Ustalmy \(d\ge1\) i załóżmy indukcyjnie, że rozstrzygnięte są wszystkie pozycje o głębokościach mniejszych od \(d.\) Z każdej pozycji można wykonać ruch wyłącznie do pozycji o mniejszych głębokościach, więc możemy rozstrzygnąć wszystkie pozycje z głębokością \(d\) na podstawie wcześniej wymienionych reguł. Ze względu na skończoność gry, rozstrzygniemy w ten sposób wszystkie pozycje. Należy do nich również pozycja początkowa. \(\square\)
Dowód twierdzenia dostarcza nam metodę rozstrzygania pozycji – „od końca”.
Wracamy teraz do gier z możliwym remisem. Można udowodnić (przeprowadzając analogiczne rozumowanie lub wywnioskować – jak? – bezpośrednio z twierdzenia), że albo jeden z graczy ma strategię wygrywającą, albo obaj mają strategię zapewniającą co najmniej remis.
To straszne! Z powyższego wynika, że każda idealna rozgrywka w grze kombinatorycznej skazana jest na z góry określony rezultat. Jednak wielu ludzi gra, a w niektóre gry organizowane są nawet mistrzostwa świata: szachy, go, hex, gomoku… A to dlatego, że znalezienie strategii jest znacznie trudniejszym problemem od wykazania jej istnienia. Nawet bardzo małe gry mogą mieć skomplikowane grafy – tu namawiam Czytelnika do podjęcia daremnej próby narysowania grafu pozycji gry kółko i krzyżyk na planszy \(3\times3.\)
W niektórych grach zamiast grafu pozycji możemy rozważyć graf stanów, ze strzałkami \(S\to T,\) jeśli ze stanu \(S\) gracz mający ruch może go wykonać do stanu \(T.\) Warunkiem jest to, że dla każdego stanu obaj gracze mają ten sam zestaw stanów, do których mogą przejść, wykonując ruch. Jest tak, dla przykładu, w grze chrup! i w grze Wythoffa. Dzięki takiemu podejściu mamy do \(50\%\)* mniej sytuacji do rozstrzygnięcia, w stosunku do grafu pozycji. Na rysunku obok widać graf stanów gry chrup! na czekoladzie \(3\times2\) (z dokładnością do symetrii).
* wynik niezależnych badań wykonanych przez redakcję Delty
Jeśli remis jest niemożliwy, to każdy stan można określić jako wygrany (W) bądź przegrany (P) dla gracza, który aktualnie ma ruch. Przypisanie wartości stanom jest analogiczne jak wcześniej: stan P to taki, z którego wszystkie ruchy prowadzą do stanu W, a stan W – w którym co najmniej jeden ruch prowadzi do stanu P. Rozumując analogicznie jak w przypadku grafu pozycji, możemy każdemu stanowi przypisać W lub P. Strategia polega na wyborze, o ile to możliwe, stanu P – czyli przegranej dla naszego przeciwnika, który będzie miał wtedy ruch.
Na koniec dwie porady praktyczne.
Ustalając strategię wygrywającą dla jednego z graczy, wystarczy rozważyć tylko te pozycje lub stany, które wystąpią w grze podczas stosowania tej strategii – nie trzeba analizować całego grafu.
Wygodnym zabiegiem jest uznawanie pozycji w oczywisty sposób rozstrzygniętych jako końcowe.
Zadania
Rozstrzygnąć wszystkie pozycje/stany następujących gier:
dominacja na planszy \(3\times3,\)
gra Wythoffa na planszy \(6\times4.\)
Wskazówka Najlepiej narysować graf pozycji dla dominacji i graf stanów dla gry Wythoffa.
Ciekawostka. Stany typu P w grze Wythoffa to \((\lfloor k\Phi\rfloor,\lfloor k\Phi^2\rfloor)\) i \((\lfloor k\Phi^2\rfloor,\lfloor k\Phi\rfloor)\) dla całkowitych dodatnich \(k,\) przy czym \(\Phi=\frac{1+\sqrt 5}2.\)Jakim ruchem powinien rozpocząć grę chrup! na czekoladzie \(4\times3\) gracz I?
Wskazówka Można narysować uproszczony graf stanów, posiłkując się praktyczną poradą (2). W grze chrup! w oczywisty sposób rozstrzygnięte są czekolady \(n\times 1,\) czekolady \(n\times n\) z usuniętym kwadratem \((n-1)\times(n-1)\) oraz wszystkie niedochrupki czekolady \(n\times 2\) (zob. poprzedni kącik).
Znaleźć przykładową strategię wygrywającą dla jednego z graczy w grze
hex na planszy \(4\times4,\)
dominacja na planszy \(4\times4.\)
Wskazówka Ciekawostka. Wiadomo, że w grze hex remis jest niemożliwy oraz pierwszy gracz ma strategię wygrywającą (zob. następny kącik). Aby zmniejszyć przewagę rozpoczynającego, na turniejach stosuje się prawo zamiany: po wykonaniu przez gracza I pierwszego ruchu gracz II, zamiast wykonać swój ruch, może zdecydować, że zamienia się rolami z graczem I, przejmując jego kolor i wykonany ruch.
Ciekawostka. Gracz II wygrywa na planszach \(1\times 1\) i \(5\times 5,\) a na pozostałych \(n\times n\) dla \(n\le 11\) – gracz I. Dla \(n\ge 12\) nie wiadomo.