Havannah (gra planszowa)

Przykłady trzech zwycięskich struktur w Havannah na planszy o podstawie 8. Od lewej do prawej są to rozwidlenie , pierścień i most .

Havannah to abstrakcyjna strategiczna gra planszowa dla dwóch graczy wymyślona przez Christiana Freelinga . Należy do rodziny gier nazywanych potocznie grami połączeniowymi ; jego krewni to Hex i TwixT . Havannah ma „wyrafinowaną i zróżnicowaną strategię” i najlepiej grać na sześciokątnej planszy o podstawie 10, oddalonej o 10 heksów z boku.

Gra była wydawana przez pewien czas w Niemczech przez firmę Ravensburger , z mniejszą planszą o podstawie 8, odpowiednią dla początkujących. Obecnie jest produkowany tylko przez firmę Hexboards.

Zasady gry

Jeden gracz gra czarnym; drugi gra białymi. Białe zaczynają, po czym ruchy naprzemienne. Zasady są następujące:

Każdy gracz umieszcza na planszy jeden kamień w swoim kolorze na turę.
Kamienie nigdy nie są przesuwane, przechwytywane ani w żaden inny sposób zmieniane.
Gracz wygrywa, gdy ukończy jedną z trzech różnych struktur z nieprzerwanych linii lub ścieżek połączonych kamieni, wszystkie w swoim kolorze:
- Pierścień to pętla wokół jednej lub więcej komórek (bez względu na to, czy otoczone komórki są zajęte przez dowolnego gracza, czy puste) ;
- Most , który łączy dowolne dwie z sześciu narożnych komórek planszy;
- Widelec , który łączy dowolne trzy krawędzie planszy; punkty narożne nie są uważane za części krawędzi.

Przykład wszystkich trzech zwycięskich kombinacji pokazano powyżej. Struktura na środku planszy to pierścień; struktura po lewej stronie to widelec; konstrukcja po prawej stronie to most.

Ponieważ pierwszy gracz, który poruszy się w Havannah, ma wyraźną przewagę, reguła kołowa jest generalnie stosowana dla zachowania sprawiedliwości. Ta zasada pozwala drugiemu graczowi wybrać, czy zamienić się miejscami z pierwszym graczem po tym, jak pierwszy gracz wykona pierwszy ruch.

Gracze o różnej sile nadal mogą rozegrać interesującą grę, gdy słabszy gracz (jako biały) może położyć dwa lub więcej kamieni w pierwszej turze.

Różnica w porównaniu do Hex

W Hex, gdy plansza jest całkowicie wypełniona, dokładnie jeden gracz będzie miał zwycięskie połączenie; w Havannah całkowicie wypełniona plansza będzie miała zwykle więcej niż jedną zwycięską strukturę (ale gra kończy się na pierwszej zwycięskiej strukturze).

W przeciwieństwie do Hex, w Havannah losowania są technicznie możliwe, w praktyce są niezwykle rzadkie. Odnotowano jeden znany remis między ludzkimi graczami. Taktyka jest znacznie łatwiejsza do opanowania niż strategia, a różnice w poziomie gry są znaczne.

Komputerowa Havannah

W 2002 roku Freeling zaoferował nagrodę w wysokości 1000 euro, dostępną do 2012 roku, za dowolny program komputerowy, który mógłby go pokonać nawet w jednej grze z dziesięciu gier. Przez wiele lat programy komputerowe pozostawały daleko w tyle za ludzkimi graczami. Jednak od 2010 roku kilka programów gry w Havannah zastosowało wyszukiwania drzew Monte Carlo, co przyniosło znaczną poprawę siły gry. „Havannah Challenge 2012” odbyło się w dniach 15–19 października 2012 r., Podczas których Freeling rozegrał dziesięć meczów z trzema najsilniejszymi dostępnymi programami do gry w Havannah, grając (co najmniej) jedną grę czarnymi i jedną białą przeciwko każdemu przeciwnikowi. Freeling przegrał wyzwanie, gdy musiał zrezygnować z gry białymi przeciwko programowi Lajkonika.

Do 2019 roku najlepsi ludzie wciąż byli znacznie silniejsi niż komputery. Jednak MetaTotoro , oparty na Polygames (projekt open source, początkowo rozwijany przez Facebook Artificial Intelligence Research i kilka uniwersytetów), wygrał cztery razy z rzędu na planszy rozmiaru 8 przeciwko ludzkiemu graczowi z najlepszą rangą ELO na LittleGolem , który był także zwycięzcą różnych turniejów.

Wynik ten osiągnięto tym samym programem, który wykorzystano do pokonania najlepszych ludzi na Hex . Jest to algorytm oparty na zerowym uczeniu się, podobnie jak w AlphaZero, ale z nowościami: niezmienność rozmiaru tablicy dzięki w pełni splotowym sieciom neuronowym (jak w U-Net) i globalnemu łączeniu. Pozwala to na rozbudowę architektur, co oznacza, że program może uczyć się na małej płytce, a następnie ekstrapolować na dużej płytce.

Złożoność obliczeniowa

Rozwiązanie Havannah jest PSPACE-zupełne w odniesieniu do rozmiaru grafu wejściowego. Dowód polega na redukcji z uogólnionej geografii i opiera się na wykorzystaniu zagrożeń pierścieniowych do przedstawienia grafu geograficznego. W szczegółach, ponieważ Lichtenstein i Sipser udowodnili, że uogólniona geografia pozostaje PSPACE-twarda, nawet jeśli graf jest tylko dwudzielny i ma stopień co najwyżej 3 , pozostaje tylko skonstruować równoważną pozycję Havannah z takiego grafu, co jest osiągane przez konstruowanie różnych gadżety w Havannah.

Opinie

Gry i strategie #9

Linki zewnętrzne