Apodyktyczny
 Przykładowa gra Domineering rozgrywana na planszy 5x5, gdzie gracz poziomy („H” lub „Prawy”) wykonuje pierwszy ruch i przegrywa w 13. rundzie gry.
| |
| Gatunki | gra oparta na kafelkach |
|---|---|
| Gracze | 2 |
| Szansa | nic |
| Umiejętności | strategia |
Domineering (zwana także Stop-Gate lub Crosscram ) to gra matematyczna , w którą można grać na dowolnym zbiorze kwadratów na kartce papieru milimetrowego . Na przykład można grać na kwadracie 6×6, prostokącie, całkowicie nieregularnym poliomino lub kombinacji dowolnej liczby takich elementów. Dwóch graczy ma kolekcję kostek domina , które kolejno umieszczają na siatce, zakrywając kwadraty. Jeden gracz układa płytki pionowo, a drugi poziomo. (Tradycyjnie ci gracze nazywani są odpowiednio „Lewy” i „Prawy” lub „V” i „H”. W tym artykule zastosowano obie konwencje.) Jak w większości gier w kombinatorycznej teorii gier , pierwszy gracz, który nie może się poruszać przegrywa.
Domineering to gra partyzancka , w której gracze używają różnych elementów: bezstronną wersją gry jest Cram .
Podstawowe przykłady
Pojedyncze pudełko
Oprócz pustej gry, w której nie ma siatki, najprostszą grą jest pojedyncze pudełko.
W tej grze, oczywiście, żaden z graczy nie może się ruszyć. Ponieważ jest to wygrana drugiego gracza, jest to zatem gra zerowa .
Poziome rzędy
Ta gra to siatka 2 na 1. Istnieje konwencja przypisywania grze liczby dodatniej , gdy wygrywa Lewy, i ujemnej , gdy wygrywa Prawica. W tym przypadku Lewy nie ma żadnych ruchów, podczas gdy Prawy może zagrać w domino, aby pokryć całą planszę, nie pozostawiając nic, co jest oczywiście grą zerową. Tak więc w surrealistycznym zapisie liczb ta gra to {|0} = −1. Ma to sens, ponieważ ta siatka daje przewagę 1 ruchu dla prawego.
Ta gra jest również {|0} = −1, ponieważ pojedyncze pudełko jest niegrywalne.
Ta siatka jest pierwszym wyborem. Prawy mógłby zagrać lewe dwa pola, pozostawiając -1. Skrajne prawe pola również pozostawiają -1. Mógł również zagrać na środkowych dwóch polach, pozostawiając dwa pojedyncze pola. Ta opcja pozostawia 0+0 = 0. Tak więc ta gra może być wyrażona jako {|0,−1}. To jest −2. Jeśli ta gra jest rozgrywana w połączeniu z innymi grami, są to dwa wolne ruchy dla prawej.
Pionowe rzędy
Kolumny pionowe są oceniane w ten sam sposób. Jeśli istnieje rząd 2 n lub 2 n +1 pól, liczy się jako − n . Kolumna o takim rozmiarze liczy się jako + n .
Bardziej złożone siatki
To jest bardziej złożona gra. Jeśli Lewy idzie pierwszy, każdy ruch opuszcza siatkę 1×2, czyli +1. Prawo, z drugiej strony, może przejść do -1. Zatem surrealistyczna notacja liczbowa to {1|−1}. Nie jest to jednak liczba surrealistyczna, ponieważ 1 > −1. To jest gra, ale nie liczba. Notacja to ±1 i jest to gorąca gra , ponieważ każdy gracz chce się tu przenieść.
Jest to siatka 2×3, która jest jeszcze bardziej złożona, ale tak jak w każdej grze Domineering, można ją rozbić, patrząc na różne ruchy dla lewej i prawej strony. Lewy może zająć lewą kolumnę (lub równoważnie prawą kolumnę) i przejść do ±1, ale zdecydowanie lepszym pomysłem jest podzielenie środka, pozostawiając dwie oddzielne gry, każda warta +1. Zatem najlepszym ruchem Lewego jest +2. Prawo ma cztery „różne” ruchy, ale wszystkie pozostawiają następujący kształt w pewnym obrocie :
Ta gra nie jest gorącą grą (zwaną też zimną grą ), ponieważ każdy ruch rani gracza, który go wykonuje, co możemy zobaczyć badając ruchy. Lewy może przesunąć się do -1, Prawy może przesunąć się do 0 lub +1. Zatem ta gra to {−1|0,1} = {−1|0} = −½.
Nasza siatka 2×3 to zatem {2|−½}, co może być również reprezentowane przez średnią wartość ¾ wraz z premią za ruch („temperatura”), 1¼, czyli:
Gra na wysokim poziomie
Instytut Nauk Matematycznych zorganizował turniej Domineering , z nagrodą w wysokości 500 $ dla zwycięzcy. W tę grę grano na planszy 8×8. Zwycięzcą został matematyk Dan Calistrate, który w finale pokonał Davida Wolfe'a . Turniej został szczegółowo opisany w „Games of No Chance” Richarda J. Nowakowskiego (s. 85).
Zwycięska strategia
Problemem związanym z dominacją jest obliczenie zwycięskiej strategii dla dużych szachownic, a zwłaszcza plansz kwadratowych. W 2000 roku Dennis Breuker, Jos Uiterwijk i Jaap van den Herik obliczyli i opublikowali rozwiązanie dla planszy 8x8. Tablica 9x9 pojawiła się wkrótce po pewnych ulepszeniach swojego programu. Następnie, w 2002 roku, Nathan Bullock rozwiązał planszę 10x10 w ramach swojej pracy magisterskiej na temat dominacji. Plansza 11x11 została ułożona przez Josa Uiterwijka w 2016 roku.
Domineering to zwycięstwo pierwszego gracza na kwadratowych planszach 2x2, 3x3, 4x4, 6x6, 7x7, 8x8, 9x9, 10x10 i 11x11 oraz zwycięstwo drugiego gracza na planszach 1x1 i 5x5. Niektóre inne znane wartości prostokątnych desek można znaleźć na stronie Nathana Bullocka.
Dopchać
Cram to bezstronna wersja Domineering. Jedyna różnica w zasadach polega na tym, że każdy gracz może umieścić swoje kostki domina w dowolnej orientacji. Wydaje się, że to tylko niewielka zmiana zasad, ale skutkuje zupełnie inną grą, którą można przeanalizować za pomocą twierdzenia Sprague-Grundy'ego .
Zobacz też
- Blockbusting (gra) Gra kombinatoryczna, której analizę zastosowano do Dominacji.
- Bibliografia _ Uiterwijk, JWHM; van den Herik, HJ (2000-01-06). „Rozwiązywanie dominacji 8 × 8” . Informatyka teoretyczna . 230 (1–2): 195–206. doi : 10.1016/S0304-3975(99)00082-1 .
- ^ Nathan Bullock Domineering: Rozwiązywanie dużych kombinatorycznych przestrzeni wyszukiwania mgr inż. praca magisterska, 2002
- ^ Uiterwijk, JWH 11x11 Domineering jest rozwiązany: pierwszy gracz wygrywa . Komputery i gry 2016. s. 129–136. doi : 10.1007/978-3-319-50935-8_12 .
- ^ „Zaktualizowane teoretyczne wartości gier dla dominujących plansz” . webdocs.cs.ualberta.ca . Źródło 2023-02-16 .
- Albert, Michael H .; Nowakowski, Richard J.; Wolfe, David (2007). Lekcje w grze: wprowadzenie do teorii gier kombinatorycznych . AK Peters, Ltd. ISBN 978-1-56881-277-9 .
- Berlekamp, Elwyn R .; Conway, John H .; Facet, Richard K. (2003). Zwycięskie sposoby na Twoje zabawy matematyczne . AK Peters, Ltd. ISBN 978-0-12-091150-9 .
- Gardner, Martin (1974). „Gry matematyczne: Cram, crosscram i quadraphage: nowe gry o nieuchwytnych strategiach wygrywania”. Naukowy Amerykanin . 230 (2): 106–108. doi : 10.1038/scientificamerican0374-102 .