Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu
Oddaję w ręce Czytelnika rozgrzewkowy kącik, rozpoczynający kilkukącikowy (wielokątny?) cykl o grach kombinatorycznych. Oto kilka przykładów takich gier:
Kółko i krzyżyk. Tej gry nie trzeba nikomu przedstawiać. Oryginalna wersja szybko się nudzi, ale są ciekawe uogólnienia, na przykład w gomoku gramy do \(5\) znaczków pod rząd na planszy \(19\times19.\)
Dominacja. Na szachownicy \(n\times n\) zawodnicy stawiają na zmianę prostokąty \(2\times1\) (domina), zakrywające dwa pola, jeden gracz wyłącznie pionowo, drugi wyłącznie poziomo. Nie można dwa razy zakryć tego samego pola. Przegrywa ten, kto nie może wykonać ruchu.
Mosty. Gracze na zmianę stawiają mosty pomiędzy sąsiednimi kwadracikami w swoim kolorze. Nie można przecinać mostu przeciwnika. Wygrywa ten, który jako pierwszy zbuduje połączenie pomiędzy brzegami w jego kolorze.
Chrup! Planszą gry jest tabliczka czekolady \(n\times m.\) Ruch polega na wyborze jednej z kostek, następnie zjedzeniu wszystkiego, co ta kostka ogranicza z góry i z lewej (rysunek). Zawodnicy wykonują ruchy na zmianę. Lewa-górna kostka jest zatruta i jej zjedzenie powoduje przegraną oraz inne nieprzewidziane konsekwencje.
Ciekawostka. Pewna firma produkująca czekolady posługiwała się w roku 2015 hasłem reklamowym: A Ty komu podarujesz ostatnią kostkę?
Gra Wythoffa. Gramy na szachownicy \(m\times n.\) Na początku w prawym-górnym polu stoi hetman. Zawodnik może w swoim ruchu go przesunąć w lewo, w dół lub skośnie w lewo-dół o dowolną liczbę pól. Gracze wykonują ruchy na zmianę. Wygrywa ten, kto ustawi hetmana w lewym-dolnym polu szachownicy.
Hex. Gracze na zmianę kolorują białe sześciokąty na czerwono i niebiesko. Zwycięża ten, który jako pierwszy zbuduje połączenie pomiędzy brzegami swojego koloru.
kółko i krzyżyk
dominacja
mosty
chrup!
gra Wythoffa
hex
Wszystkie wyżej opisane gry mają następujące cechy wspólne:
w grze biorą udział dwaj gracze, którzy wykonują ruchy na zmianę;
każdy z graczy widzi wszystkie elementy gry w trakcie całej rozgrywki;
nie ma elementów losowych;
gra zawsze kończy się po skończonej liczbie ruchów, a jej wynikiem jest zwycięstwo jednego z graczy lub remis.
Takie gry nazywamy kombinatorycznymi i tylko o takich będę dalej pisał.
Pozycję w grze nazywamy wygraną dla danego gracza, jeżeli ma on w niej strategię wygrywającą (może grać w taki sposób, że zawsze wygra, niezależnie od tego, co zrobi przeciwnik).
Zadania
Ocenić pozycje widoczne na rysunkach. Zakładamy, że zaczyna krzyżyk i kolor czerwony, a w grze chrup! zaznaczony ruch został już wykonany.
Wskazówka Pozycja z gry hex jest wygrana dla niebieskiego (mimo że jest ruch czerwonego). Pozostałe są wygrane dla mającego ruch.
Wskazać strategię wygrywającą dla gracza pierwszego w następujących grach:
kółko i krzyżyk, \(3\) znaczki pod rząd, na planszy \(4\times4\);
gra Wythoffa na planszy \(n\times(n+1)\) dla \(n\ge3\);
chrup! w wersji \(2\times n\) dla \(n\ge2.\)
Wskazówka Można ustawić dwa krzyżyki w centrum planszy, jeden obok drugiego, tak by stwarzały podwójną groźbę przedłużenia linii do trzech.
W pierwszym ruchu przestawiamy hetmana na pole o współrzędnych \((2,3).\)
Pierwszy gracz w każdym ruchu pozostawia przeciwnikowi czekoladę \(2\times k\) z brakującą prawą-dolną kostką.