Gra pozycyjna
Gra pozycyjna jest rodzajem gry kombinatorycznej dla dwóch graczy. Jest opisany przez:
- - zbiór . Często nazywana jest elementy nazywane są pozycjami .
- - . _ _ Podzbiory te nazywane są zwykle zbiorami wygrywającymi .
- Kryterium wygranej gry.
W trakcie rozgrywki gracze na zmianę zajmują niezajęte wcześniej pozycje, aż do momentu, w którym jeden z graczy zwycięży. Jeśli wszystkie pozycje a żaden gracz nie wygra, grę uznaje się za remis.
Klasycznym przykładem gry pozycyjnej jest Kółko i krzyżyk . Zawiera w nim 9 kwadratów planszy, 8 linii określających zwycięstwo (3 poziome, 3 pionowe i 2 ukośne), a kryterium wygranej jest następujące: wygrywa gracz, który jako pierwszy zdobędzie cały zwycięski zestaw. Innymi przykładami gier pozycyjnych są Hex i gra przełączająca Shannon .
Dla każdej gry pozycyjnej istnieją dokładnie trzy możliwości: albo pierwszy gracz ma strategię wygrywającą , albo drugi gracz ma strategię wygrywającą, albo obaj gracze mają strategie wymuszające remis. Głównym pytaniem interesującym w badaniu tych gier jest to, która z tych trzech opcji ma zastosowanie w konkretnej grze.
Gra pozycyjna jest skończona, deterministyczna i zawiera doskonałe informacje ; dlatego teoretycznie możliwe jest stworzenie pełnego drzewa gry i określenie, która z tych trzech opcji ma zastosowanie. W praktyce jednak drzewo gry może być ogromne. Dlatego gry pozycyjne są zwykle analizowane za pomocą bardziej wyrafinowanych technik kombinatorycznych.
Terminologia alternatywna
Często dane wejściowe do gry pozycyjnej są uważane za hipergraf . W tym przypadku:
- Elementy nazywane są wierzchołkami (lub punktami i oznaczane V ;
- Elementy nazywane są krawędziami lub hiperkrawędziami ) i oznaczane przez E lub
Warianty
Istnieje wiele odmian gier pozycyjnych, różniących się zasadami i kryteriami wygranej.
Różne kryteria zwycięstwa
- Silna gra pozycyjna (zwana także grą Maker-Maker),
- w której pierwszy gracz zdobędzie wszystkie elementy zwycięskiego zestawu, wygrywa. Jeśli gra zakończy się zdobyciem wszystkich elementów planszy, ale żaden z graczy nie zdobył wszystkich elementów zwycięskiego zestawu, następuje remis. Przykładem jest klasyczne kółko i krzyżyk .
- W grze Maker-Breaker
- dwaj gracze nazywają się Maker i Breaker. Maker wygrywa, zdobywając wszystkie elementy zwycięskiego zestawu. Jeśli gra zakończy się zdobyciem wszystkich elementów planszy, a Stwórca jeszcze nie wygrał, wówczas wygrywa Breaker. Remisy nie są możliwe. Przykładem jest gra polegająca na zmianie Shannon .
- W grze „Unikacz-Egzekutor”
- gracze nazywają się „Unikacz” i „Egzekutor”. Enforcer wygrywa, jeśli Unikacz kiedykolwiek zdobędzie wszystkie elementy zwycięskiego zestawu. Jeśli gra zakończy się zdobyciem wszystkich elementów planszy, a Unikacz nie zdobędzie zwycięskiego zestawu, wówczas Unikacz wygrywa. Podobnie jak w grach typu „maker-breaker”, remis nie jest możliwy. Przykładem jest Sim .
- W grze rozbieżności
- gracze nazywają się Balancer i Unbalancer. Balancer wygrywa, jeśli upewni się, że we wszystkich zwycięskich setach każdy gracz ma mniej więcej połowę wierzchołków. W przeciwnym razie wygrywa Unbalancer.
Różne zasady gry
- Gra Kelner-Klient (zwana także grą Picker-Chooser), w
- której gracze nazywani są Kelnerem i Klientem. W każdej turze Kelner wybiera dwie pozycje i pokazuje je Klientowi, który może wybrać jedną z nich.
- Stronnicza gra pozycyjna
- Każda gra pozycyjna ma swój wariant stronniczy , w którym pierwszy gracz może wziąć jednocześnie p elementów, a drugi q elementów naraz (w wariancie nieobciążonym p = q =1).
Konkretne gry
W poniższej tabeli wymieniono niektóre konkretne gry pozycyjne, które były szeroko badane w literaturze.
| Nazwa | Pozycje | Zwycięskie sety |
|---|---|---|
| Wielowymiarowe kółko i krzyżyk | Wszystkie kwadraty w wielowymiarowym pudełku | Wszystkie linie proste |
| Gra zmiany Shannon | Wszystkie krawędzie grafu | Wszystkie ścieżki od s do t |
| Sim | Wszystkie krawędzie pomiędzy 6 wierzchołkami. | Wszystkie trójkąty [przegrywające sety]. |
| Gra klikowa (inaczej gra Ramseya ) | Wszystkie krawędzie pełnego wykresu o rozmiarze n | Wszystkie kliki rozmiaru k |
| Gra o łączność | Wszystkie krawędzie pełnego wykresu | Wszystkie drzewa rozpinające |
| Gra Hamiltoniczność | Wszystkie krawędzie pełnego wykresu | Wszystkie ścieżki Hamiltona |
| Gra nieplanarna | Wszystkie krawędzie pełnego wykresu | Wszystkie niepłaskie podgrafy |
| Gra w postęp arytmetyczny | Liczby {1,...,n} | Wszystkie postępy arytmetyczne rozmiaru k |
Zobacz też
- Gra topologiczna , uogólnienie gry pozycyjnej na zbiory nieskończone
- Gra Banacha – Mazura , gra rozgrywana w przestrzeni topologicznej poprzez wybór spośród pewnych podzbiorów, z warunkami wygranej przypominającymi grę twórca-łamacz