Kayles
Kayles to prosta bezstronna gra z teorii gier kombinatorycznych , wynaleziona przez Henry'ego Dudeneya w 1908 roku. Biorąc pod uwagę rząd wyimaginowanych kręgli, gracze na zmianę wybijają jeden lub dwa sąsiednie kręgle, aż znikną wszystkie kręgle. Używając notacji gier ósemkowych , Kayles jest oznaczony jako 0,77 .
Zasady
W Kaylesa gra się rzędem żetonów, które przedstawiają kręgle. Rząd może mieć dowolną długość. Dwóch graczy zmienia się; każdy gracz w swojej turze może usunąć dowolny jeden kręgiel (piłka rzucona bezpośrednio na ten kręgiel) lub dwa sąsiednie kręgle (piłka rzucona w celu uderzenia w oba). Zgodnie z normalną konwencją gry gracz przegrywa, gdy nie ma żadnego legalnego ruchu (to znaczy, gdy wszystkie kręgle zniknęły). W grę można również grać na zasadach misère ; w takim przypadku wygrywa gracz, który nie może się ruszyć .
Historia
Kayles został wymyślony przez Henry'ego Dudeneya . Richard Guy i Cedric Smith jako pierwsi całkowicie przeanalizowali wersję normalnej gry, korzystając z teorii Sprague-Grundy'ego . Wersja misère została przeanalizowana przez Williama Siberta w 1973 roku, ale opublikował swoją pracę dopiero w 1989 roku.
Nazwa „Kayles” jest anglicyzacją francuskiego quilles , oznaczającego „kręgle”.
Analiza
Większość graczy szybko odkrywa, że pierwszy gracz ma gwarantowaną wygraną w normalnych Kayles, ilekroć długość rzędu jest większa od zera. Tę wygraną można osiągnąć za pomocą strategii symetrii. W swoim pierwszym ruchu pierwszy gracz powinien przesunąć się tak, aby rząd został podzielony na dwie części o równej długości. Ogranicza to wszystkie przyszłe ruchy do jednej lub drugiej sekcji. Teraz pierwszy gracz jedynie naśladuje ruchy drugiego gracza w przeciwległym rzędzie.
Bardziej interesujące jest pytanie, jaka jest wartość nim w rzędzie o długości . Jest to często oznaczane ; to jest nimber , a nie liczba . Zgodnie z -Grundy'ego , to mex po wszystkich możliwych ruchach sumy nim - dwóch wynikowych sekcji. Na przykład,
ponieważ z rzędu o długości 5 można przejść na pozycje
Rekurencyjne obliczanie wartości (zaczynając wyniki podsumowane w poniższej tabeli. znaleźć wartość tabeli, napisz i , kolumnę b: K n
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0+ | 0 | 1 | 2 | 3 | 1 | 4 | 3 | 2 | 1 | 4 | 2 | 6 |
| 12+ | 4 | 1 | 2 | 7 | 1 | 4 | 3 | 2 | 1 | 4 | 6 | 7 |
| 24+ | 4 | 1 | 2 | 8 | 5 | 4 | 7 | 2 | 1 | 8 | 6 | 7 |
| 36+ | 4 | 1 | 2 | 3 | 1 | 4 | 7 | 2 | 1 | 8 | 2 | 7 |
| 48+ | 4 | 1 | 2 | 8 | 1 | 4 | 7 | 2 | 1 | 4 | 2 | 7 |
| 60+ | 4 | 1 | 2 | 8 | 1 | 4 | 7 | 2 | 1 | 8 | 6 | 7 |
| 72+ | 4 | 1 | 2 | 8 | 1 | 4 | 7 | 2 | 1 | 8 | 2 | 7 |
W tym momencie sekwencja wartości nim staje się okresowa z okresem 12, więc wszystkie dalsze wiersze tabeli są identyczne z ostatnim wierszem.
Aplikacje
Ponieważ pewne pozycje w Kropkach i Pudełkach sprowadzają się do pozycji Kaylesa, zrozumienie Kaylesa jest pomocne w celu przeanalizowania ogólnej pozycji Kropek i Pudełek.
Złożoność obliczeniowa
W normalnej grze Kayles można rozwiązać w czasie wielomianowym, używając teorii Sprague-Grundy'ego.
Node Kayles jest uogólnieniem Kaylesa na grafy, w których każda misa „przewraca” (usuwa) żądany wierzchołek i wszystkie sąsiednie wierzchołki. (Alternatywnie, tę grę można postrzegać jako dwóch graczy, którzy razem znajdują niezależny zestaw ). Analogicznie w w tworzenie kliki dwóch graczy musi znaleźć klikę na grafie. Ostatni, który zagra, wygrywa. Schaefer (1978) udowodnił, że decydowanie o wyniku tych gier jest PSPACE-zupełne . Ten sam wynik dotyczy partyzanckiej wersji węzła Kayles, w której dla każdego węzła tylko jeden z graczy może wybrać ten konkretny węzeł jako cel powalenia.
Zobacz też
- ^ Dudeney, HE (2002), The Canterbury puzzle , Dover, s. 118–119, puzzle 73, ISBN 0-486-42558-4 . Pierwotnie opublikowany w 1908 r.
- ^ Conway, John H. O liczbach i grach. Prasa akademicka, 1976.
- ^ a b RK Guy i CAB Smith, wartości G różnych gier, Proc. Cambridge Philos. Soc., 52 (1956) 514-526.
- ^ TE Plambeck, Daisies, Kayles i rozkład Siberta-Conwaya w grach misere ósemkowych Zarchiwizowane 14.07.2010 w Wayback Machine , Theoret. Oblicz. Sci (gry matematyczne) (1992) 96 361–388.
- ^ a b Plambeck, Thane, Kayles , zarchiwizowane z oryginału w dniu 12.10.2008 , pobrane 15.08.2008
- ^ E. Berlekamp , JH Conway , R. Guy. Zwycięskie sposoby na Twoje matematyczne zabawy . Prasa akademicka, 1982.
- ^ Schaefer, Thomas J. (1978). „O złożoności niektórych dwuosobowych gier z doskonałą informacją” . Journal of Computer and System Sciences . 16 (2): 185–225. doi : 10.1016/0022-0000(78)90045-4 .