Gra ósemkowa
Gry ósemkowe to klasa gier dla dwóch graczy, które polegają na usuwaniu żetonów (elementów gry lub kamieni) ze stosów żetonów. Zostały one zbadane w kombinatorycznej teorii gier jako uogólnienie gier Nim , Kayles i podobnych.
Gry ósemkowe są bezstronne , co oznacza, że każdy ruch dostępny dla jednego gracza jest również dostępny dla drugiego gracza. Różnią się między sobą liczbą żetonów, które można usunąć w jednym ruchu oraz (w zależności od tej liczby) czy można usunąć cały stos, zmniejszyć rozmiar stosu lub podzielić stos na dwa stosy . Te odmiany reguł można zwięźle opisać za pomocą systemu kodowania przy użyciu ósemkowych .
Specyfikacja gry
Rozgrywana jest gra ósemkowa, w której żetony są podzielone na stosy. Dwóch graczy na zmianę porusza się, dopóki żaden ruch nie jest możliwy. Każdy ruch polega na wybraniu tylko jednego ze stosów i jednego z nich
- usunięcie wszystkich tokenów ze sterty, nie pozostawiając żadnej sterty,
- usunięcie niektórych, ale nie wszystkich żetonów, pozostawienie jednego mniejszego stosu lub
- usunięcie części żetonów i podzielenie pozostałych na dwa niepuste stosy.
Sterty inne niż wybrana sterta pozostają niezmienione. Ostatni gracz, który poruszy się, wygrywa w normalnej grze . Grę można również rozegrać w grze misère , w której przegrywa ostatni gracz, który poruszy się.
Gry rozgrywane ze stosami w ten sposób, w których dozwolone ruchy dla każdego stosu są określone przez rozmiar pierwotnego stosu, nazywane są w literaturze grami Taking and Breaking . Gry ósemkowe to podzbiór gier typu „branie i łamanie”, w których dozwolone ruchy są określane na podstawie liczby żetonów usuniętych ze stosu.
Kod ósemkowy gry jest określony jako
- 0 . re 1 re 2 re 3 re 4 …,
gdzie cyfra ósemkowa d n określa, czy gracz może opuścić zero, jeden lub dwa stosy po usunięciu n żetonów ze stosu. Cyfra d n jest sumą
- 1, jeśli pozostawienie stert zerowych jest dozwolone, 0 w przeciwnym razie;
- 2 jeśli pozostawienie jednej sterty jest dozwolone, 0 w przeciwnym razie; I
- 4, jeśli pozostawienie dwóch stert jest dozwolone, 0 w przeciwnym razie.
Tokeny zerowe nie są liczone jako sterta. Zatem cyfra d n jest nieparzysta, jeśli stos n żetonów można całkowicie usunąć, a nawet inaczej. Specyfikacja wyników jednej sterty w d n dotyczy usuwania n tokenów ze sterty większej niż n . Wynik dwóch stert d n dotyczy usuwania n żetonów ze stosu co najmniej n +2 i rozdzielenia reszty na dwa niepuste stosy.
Gry ósemkowe mogą umożliwiać podzielenie stosu na dwie części bez usuwania żetonów, za pomocą cyfry 4 po lewej stronie przecinka dziesiętnego. Jest to podobne do ruchu w grze Grundy'ego , który polega na podzieleniu stosu na dwie nierówne części. Standardowa notacja gry ósemkowej nie ma jednak mocy, aby wyrazić ograniczenie nierównych części.
Gry ósemkowe, w których występuje tylko skończona liczba cyfr niezerowych, nazywane są skończonymi grami ósemkowymi .
Szczególne gry ósemkowe
Nim
Najbardziej podstawową grą w teorii gier kombinatorycznych jest Nim , w której można usunąć dowolną liczbę żetonów ze stosu, pozostawiając zero lub jeden stos. Kod ósemkowy dla Nim to 0,333… , pojawiający się w opublikowanej literaturze jako
- ,
oznaczać powtarzającą się część, jak w powtarzającym się ułamku dziesiętnym . Należy jednak zdać sobie sprawę, że powtarzająca się część nie odgrywa takiej samej roli jak w ułamkach ósemkowych, ponieważ gry
I
nie są identyczne, pomimo ich równości jako ułamków ósemkowych.
Kayles
Gra Kayles jest zwykle wizualizowana jako rozgrywana z rzędem n kręgli, ale może być modelowana przez stertę n żetonów. Można usunąć jeden lub dwa żetony ze stosu, a resztę ułożyć w stos zero, jeden lub dwa. Kod ósemkowy dla Kaylesa to 0,77 .
Szachy Dawsona
Dawson's Chess to gra wywodząca się z układanki szachowej ułożonej przez Thomasa Raynera Dawsona w Caissa's Wild Roses , 1938. Układanka została ustawiona jako obejmująca przeciwstawne rzędy pionków oddzielonych pojedynczym szeregiem. Chociaż łamigłówka nie jest pozowana jako bezstronna gra , założenie, że przechwytywanie jest obowiązkowe, oznacza, że ruch gracza w jakimkolwiek polu skutkuje jedynie usunięciem tego pliku i jego sąsiadów (jeśli istnieją) z dalszych rozważań, z ruchem przeciwnego gracza . Modelowanie tego jako sterty n żetonów, gracz może usunąć cały stos składający się z jednego, dwóch lub trzech żetonów, może zmniejszyć dowolny stos o dwa lub trzy żetony lub może podzielić stos na dwie części po usunięciu trzech żetonów. Szachy Dawsona są zatem reprezentowane przez kod ósemkowy 0,137 .
Kayles Dawsona
W grze 0.07 , zwanej Dawson's Kayles , ruch polega na usunięciu dokładnie dwóch żetonów ze stosu i rozłożeniu pozostałej części na stosy zero, jeden lub dwa. Dawson's Kayles został nazwany ze względu na swoje (nieoczywiste) podobieństwo do Dawson's Chess, ponieważ stos Kaylesa Dawsona złożony z n +1 żetonów działa dokładnie tak, jak stos n żetonów w szachach Dawsona . Mówi się, że Dawson's Kayles jest pierwszym kuzynem Dawson's Chess.
Uogólnienie na inne bazy
Gry ósemkowe, takie jak Nim , w których każdy ruch przekształca stos w zero lub jeden stos, nazywane są grami czwartorzędowymi , ponieważ jedynymi cyframi, które się pojawiają, są 0, 1, 2 i 3. Zapis ósemkowy można również rozszerzyć o gry szesnastkowe , w którym cyfry pozwalają na podzielenie stosu na trzy części. W rzeczywistości możliwe są dowolnie duże bazy. Analiza gier czwartorzędowych, ósemkowych i szesnastkowych pokazuje, że te klasy gier znacznie się od siebie różnią, a zachowanie większych baz nie zostało tak dokładnie zbadane.
Sekwencja Nim
Sprague -Grundy implikuje, że sterta o rozmiarze n jest równoważna stercie nim o danym rozmiarze, zwykle oznaczanej jako G (n). Analiza gry ósemkowej polega więc na znalezieniu sekwencji wartości nim dla rosnących stert. Ta sekwencja G(0), G(1), G(2)… jest zwykle nazywana sekwencją nim gry.
Wszystkie przeanalizowane do tej pory skończone gry ósemkowe wykazały, że sekwencja nim jest ostatecznie okresowa, a pytanie, czy wszystkie skończone gry ósemkowe są ostatecznie okresowe, pozostaje kwestią otwartą. Jest wymieniany przez Richarda Guya jako ważny problem w dziedzinie gier kombinatorycznych .
Rekordy obliczeń
Pełna analiza gry ósemkowej prowadzi do znalezienia jej okresu i przedokresu jej sekwencji nim. W Winning Ways for your Mathematical Plays pokazano , że tylko skończona liczba wartości sekwencji nim jest potrzebna, aby udowodnić, że skończona gra ósemkowa jest okresowa, co otworzyło drzwi do obliczeń za pomocą komputerów.
Gry ósemkowe zawierające maksymalnie 3 cyfry ósemkowe były analizowane przez lata. Istnieje 79 nietrywialnych gier ósemkowych, z których 14 zostało rozwiązanych:
- .156 autorstwa Jacka Kenyona w 1967 roku
- 0,356, 0,055, 0,644 i 0,165 autorstwa Richarda Austina w 1976 roku
- .16, .56, .127 i .376 autorstwa Anila Gangolliego i Thane'a Plambecka w 1989 roku
- .454, .104, .106, .054 i .354 autorstwa Achima Flammenkampa w latach 2000-2002
Pozostało 63 takich gier, pomimo obliczeń milionów wartości nim przez Achima Flammenkampa.