Przeskocz do treści

Delta mi!

Loading

Wielkie granie

Gra hex i punkty stałe

Filip Murlak

o artykule ...

  • Publikacja w Delcie: maj 2006
  • Publikacja elektroniczna: 23-06-2011
  • Autor: Filip Murlak
    Afiliacja: Instytut Informatyki Uniwersytetu Warszawskiego
obrazek

Hex jest jedną z najprostszych i jednocześnie jedną z najciekawszych z matematycznego punktu widzenia gier planszowych. Rozgrywka heksa jest prowadzona na romboidalnej planszy złożonej z sześciokątnych pól. Najbardziej typowe są plansze math jak na rysunku, ale można grać na dowolnie dużej planszy.


Reguły gry

Gracze na przemian stawiają na wolnym polu jeden pionek, kolorowy lub szary. Celem gracza I jest połączenie przeciwległych czarnych krawędzi za pomocą łańcucha szarych pionków, jak na rysunku. Taki łańcuch pionków będziemy nazywali wygrywającym dla gracza I. Gracz II chce zbudować łańcuch wygrywający łączący krawędzie kolorowe.

Remisy

Łatwo zaobserwować, że łańcuch wygrywający całkowicie izoluje od siebie krawędzie przeciwnika. Zatem nie mogą istnieć jednocześnie wygrywające łańcuchy dla szarych i kolorowych. A co będzie, jeśli po całkowitym wypełnieniu planszy żaden z graczy nie ma wygrywającego łańcucha? Pokażemy, że taka sytuacja nie może mieć miejsca. Innymi słowy, partia heksa nie może zakończyć się remisem.

obrazek

Rozważmy przykładową planszę heksa. Dla wygody dodajmy sztuczne rzędy pól wzdłuż krawędzi planszy i oznaczmy skrajne punkty planszy literami: math jak na rysunku obok.

Rozpoczynając w punkcie math  poruszajmy się po krawędziach między polami według następującej reguły. Na każdym rozgałęzieniu wybierzmy tę z dwóch krawędzi, która oddziela pola różnego koloru. Za każdym razem istnieje dokładnie jeden dobry wybór. Wyobraźmy sobie, że dochodzimy do pewnego rozgałęzienia. Przypuśćmy, że po lewej stronie mamy pole szare, a po prawej kolorowe (tak jak na pierwszym rozgałęzieniu, w wierzchołku math ). Jeśli pole przed nami jest szare, to skręcamy w prawo, jeśli jest kolorowe, to skręcamy w lewo. Zwróćmy uwagę, że dzięki temu zawsze po lewej stronie mamy pola szare, a po prawej kolorowe.

Postępując w ten sposób, nigdy nie wrócimy do wierzchołka, w którym już byliśmy. Przypuśćmy przeciwnie, że doszliśmy do wierzchołka już raz odwiedzonego i że jest to pierwszy taki moment w naszej wędrówce. W takim razie musieliśmy dojść do niego krawędzią, której przedtem nie używaliśmy. Ale krawędź taka zawsze leży między polami tego samego koloru, więc nie mogliśmy jej wybrać – sprzeczność.

obrazek

Plansza do heksa jest skończona, więc w końcu musimy z niej wyjść. Do dyspozycji mamy jedynie drogi przez math  gdyż wszystkie inne wiodą między polami tego samego koloru.

Jeśli ścieżka skończy się w wierzchołku math jak to ma miejsce na rysunku powyżej, to wyznacza wygrywający łańcuch dla szarych. Analogicznie, jeśli ścieżka dotrze do wierzchołka math  to wyznacza wygrywający łańcuch dla kolorowych. Zwróćmy uwagę, że ścieżka nie może opuścić planszy przez wierzchołek math bo musielibyśmy minąć kolorowe pole po lewej, a szare po prawej.Uwaga!

Strategie

Istnieje sprytna metoda, która pozwala na wykazanie, że w grze hex gracz, który zaczyna (czyli szary), ma strategię wygrywającą. Metoda ta polega na podkradaniu strategii przeciwnikowi. Przypuśćmy, że wygrywającą strategię ma gracz II. Gracz I powinien rozpocząć od zupełnie dowolnego ruchu, a następnie postępować tak, jak nakazuje hipotetyczna strategia gracza II, zamieniając miejscami kolory. Jedyny kłopot, jaki może się pojawić, to sytuacja, w której podkradziona strategia nakazuje zająć pole, na którym już stoi pionek. Może się to zdarzyć tylko wtedy, gdy jest to pionek postawiony podczas rozpoczynającego, losowego ruchu (w przeciwnym przypadku strategia nie wskazałaby tego pola). Wtedy ponownie wykonujemy dowolny możliwy ruch. Jest jasne, że posiadanie dodatkowego pionka na planszy nie pogarsza sytuacji gracza, zatem podkradziona strategia gwarantuje zwycięstwo pierwszemu graczowi. W ten sposób otrzymujemy sprzeczność z założeniem o istnieniu strategii dla drugiego gracza.

Powyższe rozumowanie jest całkowicie niekonstruktywne, nie daje graczowi I żadnych wskazówek odnośnie tego, jak powinien grać. Rozwiązanie tego problemu w praktyce jest bardzo trudne. Dotychczas udało się wyliczyć strategię dla planszy o rozmiarze math Mimo to, żeby zniwelować ewidentną przewagę gracza I, zaawansowani gracze dodają dodatkową regułę zamiany. Po tym, jak gracz I postawi pierwszy pionek, gracz II może zdecydować, czy będzie grał kolorowymi, czy szarymi. W ten sposób teoretycznie istnieje strategia wygrywająca dla gracza II, ale w praktyce gra staje się wystarczająco sprawiedliwa.

obrazek

Dualna plansza

Czy hex może się przydać matematykowi do czegoś poza rozrywką? Okazuje się, że ta prosta gra ma głęboki związek z topologią. Żeby to dokładniej wyjaśnić, zastąpimy planszę do heksa przez planszę dualną. Na planszy dualnej pola reprezentowane są przez wierzchołki. Wierzchołki reprezentujące sąsiednie pola łączymy krawędzią. Dualną planszę math przedstawia rysunek.

W tej interpretacji gracze stawiają pionki na wierzchołkach i usiłują zbudować ścieżkę łączącą przeciwległe krawędzie kwadratu. Nietrudno zauważyć, że jest to inny opis tej samej gry i wszystko, co powiedzieliśmy o heksie, jest prawdą również dla tej wersji.

Twierdzenie o punkcie stałym

Pokażemy teraz, jak wykorzystać grę hex na dualnej planszy w dowodzie ważnego twierdzenia topologicznego zwanego twierdzeniem Brouwera. Głosi ono, że każde ciągłe przekształcenie kwadratu w siebie pozostawia pewien punkt na swoim miejscu. Jeśli oznaczymy przez math kwadrat math to twierdzenie powyższe można sformułować następująco: dla dowolnego ciągłego przekształcenia math istnieje taki punkt math że math Taki punkt nazywamy punktem stałym przekształcenia math Zauważmy najpierw, że wystarczy udowodnić, że istnieje ciąg punktów math należących do math spełniających warunek:

display-math

Rzeczywiście, kwadrat math jest zbiorem domkniętym i ograniczonym, zatem z takiego ciągu math można wybrać podciąg math zbieżny do pewnego punktu math Z nierówności trójkąta otrzymujemy

display-math

Obie odległości dążą do zera, więc granicą ciągu math jest punkt math Jednocześnie z ciągłości funkcji math wynika, że math dąży do math Zatem math Spróbujmy więc wykazać istnienie takiego ciągu. Ustalmy math Wybierzmy math i tak duże, żeby spełniony był warunek:

  • jeśli math to math

Podzielmy kwadrat math tak, aby otrzymać dualną planszę do gry hex o rozmiarze math Przyjmijmy math  oraz math  math Przez math  będziemy oznaczali zbiór wierzchołków, które pod wpływem math przesuwają się w górę o co najmniej math to znaczy math Podobnie definiujemy zbiory math   math  math jako zbiory wierzchołków, które przesuwają się o co najmniej math odpowiednio, w dół, w lewo i w prawo.

Ustalmy wierzchołki math  W takim razie,

display-math

Jeśli math i math są połączone krawędzią, to ich pionowe współrzędne math i math różnią się co najwyżej o math a zatem

display-math

Dodając powyższe trzy nierówności stronami, dostajemy

display-math

Stąd odległość między math  a math  wynosi co najmniej math to jednak jest sprzeczne z tym, że wierzchołki math i math są połączone krawędzią. Jeśli bowiem dwa wierzchołki sąsiadują ze sobą, to odległość między nimi wynosi najwyżej math (długość skośnej krawędzi na planszy dualnej), zatem na mocy wyboru liczby math odległość między ich obrazami musi być ostro mniejsza niż math Wykazaliśmy więc, że wierzchołki ze zbiorów math  i math  nie mogą sąsiadować. Oczywiście, wierzchołki ze zbioru math  nie mogą leżeć na górnej krawędzi planszy, bo stamtąd nie da się pójść do góry. Podobnie wierzchołek ze zbioru math  nie może leżeć na dolnej krawędzi planszy. W takim razie zbiór math  nie może zawierać łańcucha wygrywającego dla gracza chcącego połączyć górną i dolną krawędź. Podobnie math nie może zawierać łańcucha wygrywającego dla drugiego gracza. Skoro na planszy do gry w hex nie może być układu remisowego, to math nie może wyczerpywać wszystkich wierzchołków planszy. Weźmy dowolny wierzchołek math leżący poza math Z definicji zbiorów math  wynika, że obraz wierzchołka math jest zawarty w kwadracie o środku math i krawędzi math Zatem obraz math jest odległy od math najwyżej o math Podobny dowód z użyciem zwykłej szachownicy można znaleźć w Delcie 9/1980 (zadania 232–4).

Inny dowód twierdzenia Brouwera, także w wyższych wymiarach, Czytelnik może znaleźć w znakomitych książkach Co to jest matematyka? oraz Dowody z księgi.


Literatura
[1]
M. Aigner, G. M. Ziegler, Dowody z Księgi, PWN, 2002.
[2]
R. Courant, H. Robbins, Co to jest matematyka? Prószyński i S-ka, 1998.
[3]
D. Gale. The game of hex and the Brouwer fixed-point theorem, American Mathematical Monthly, 86, grudzień 1979, str. 818–827.