Kayles - Kayles

Řada bowlingových kolíků. Ve svém tahu se hráč může rozhodnout eliminovat jeden nebo dva sousední kolíky.

Kayles je jednoduchý nestranná hra v kombinatorická teorie her, vynalezl Henry Dudeney v roce 1908. Vzhledem k řadě domnělých bowlingových kolíků se hráči střídají, aby vyřadili jeden kolík nebo dva sousední kolíky, dokud všechny kolíky nezmizí. Použití notace osmičkové hry Je označena Kayles 0.77.

Pravidla

Kayles se hraje s řadou žetonů, které představují kuželky. Řádek může mít libovolnou délku. Oba hráči se střídají; každý hráč může na svém tahu odstranit jeden libovolný kolík (míč udeřený přímo na tomto kolíku) nebo dva sousední kolíky (míč udeřený, aby zasáhl oba). Pod konvence normální hry, hráč prohraje, když nemá žádný legální tah (tj. když jsou všechny piny pryč). Hru lze také hrát pomocí misère pravidla; v tomto případě hráč, který se nemůže hýbat vyhrává.

Dějiny

Kayles vynalezl Henry Dudeney.^[1][2] Richard Guy a Cedric Smith nejprve kompletně analyzovali verzi s normálním přehráváním pomocí Sprague-Grundyova teorie.^[3][4] The misère verze byla analyzována William Sibert v roce 1973, ale svou práci publikoval až v roce 1989.^[5]

Jméno „Kayles“ je anglicizací francouzštiny quilles, což znamená „bowling“.

Analýza

Většina hráčů rychle zjistí, že první hráč má zaručenou výhru v normálních Kayles, kdykoli je délka řady větší než nula. Této výhry lze dosáhnout pomocí a strategie symetrie. Při svém prvním tahu by se měl první hráč pohnout tak, aby byla řada rozdělena na dvě stejně dlouhé úseky. To omezuje všechny budoucí pohyby na jednu nebo druhou část. První hráč nyní pouze napodobuje pohyby druhého hráče v opačné řadě.

Zajímavější je ptát se, co nim-hodnota má řadu délky ${ displaystyle n}$. To se často označuje ${ displaystyle K_ {n}}$; to je prudký, ne a číslo. Podle Sprague – Grundyho věta, ${ displaystyle K_ {n}}$ je mex přes všechny možné pohyby nim-součet z hodnoty nim ze dvou výsledných sekcí. Například,

${ displaystyle K_ {5} = { mbox {mex}} {K_ {0} + K_ {4}, K_ {1} + K_ {3}, K_ {2} + K_ {2}, K_ {0 } + K_ {3}, K_ {1} + K_ {2} }, ,}$

protože z řady o délce 5 se lze pohybovat do pozic

${ displaystyle K_ {0} + K_ {4}, quad K_ {1} + K_ {3}, quad K_ {2} + K_ {2}, quad K_ {0} + K_ {3}, { text {and}} K_ {1} + K_ {2}. ,}$

Rekurzivní výpočet hodnot (počínaje ${ displaystyle K_ {0} = 0}$) uvádí výsledky shrnuté v následující tabulce. Chcete-li zjistit hodnotu ${ displaystyle K_ {n}}$ na stůl, napište ${ displaystyle n}$ tak jako ${ displaystyle 12a + b}$, a podívejte se na řádek a, sloupec b:

Kayles Nim hodnoty prostřednictvím ${ displaystyle K_ {83}}$

${ displaystyle 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

V tomto okamžiku se sekvence nim-hodnota stává periodickou^[5] s obdobím 12, takže všechny další řádky tabulky jsou totožné s posledním řádkem.

Aplikace

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Červenec 2016)

Protože určité pozice v Tečky a krabice snížit na pozice Kayles,^[6] je užitečné porozumět Kaylesovi, aby bylo možné analyzovat obecnou pozici Dots and Boxes.

Výpočetní složitost

Při normální hře může být Kayles vyřešen v polynomiálním čase pomocí teorie Sprague-Grundy.^[3]

Uzel Kayles je zobecnění Kayles na grafy, ve kterých každá mísa „srazí“ (odstraní) požadovaný vrchol a všechny jeho sousední vrcholy. (Alternativně lze tuto hru považovat za dva hráče, kteří hledají nezávislá sada společně.) Schaefer (1978)^[7] dokázal, že rozhodování o výsledku této hry je PSPACE - kompletní. Stejný výsledek platí pro partyzánskou verzi uzlu Kayles, ve kterém je pro každý uzel povolen pouze jeden z hráčů zvolit tento konkrétní uzel jako srazit cíl.

Viz také

• Kombinatorická teorie her
• Osmičkové hry
• Dawson's Kayles
• Nimber

Reference