Kayles - Kayles

En rekke bowlingnåler. På sin tur kan en spiller velge å eliminere en enkelt pin, eller to tilstøtende.

Kayles er et enkelt upartisk spill i kombinatorisk spillteori , oppfunnet av Henry Dudeney i 1908. Gitt en rekke forestilte bowlingpinner, bytter spillerne på å slå ut enten en pin, eller to tilstøtende pins, til alle pins er borte. Ved å bruke notasjonen av oktale spill , er Kayles betegnet 0,77 .

Regler

Kayles spilles med en rad tokens, som representerer bowlingpinner. Raden kan være av hvilken som helst lengde. De to spillerne veksler hverandre; hver spiller kan på sin tur fjerne enten en pin (en ball som er kastet rett ved den pin), eller to tilstøtende pins (en ball som er bowlet for å slå begge). Under den vanlige spillkonvensjonen , taper en spiller når han eller hun ikke har noe lovlig trekk (det vil si når alle pinnene er borte). Spillet kan også spilles med misère regler; i dette tilfellet vinner spilleren som ikke kan bevege seg .

Historie

Kayles ble oppfunnet av Henry Dudeney . Richard Guy og Cedric Smith var de første som fullstendig analyserte den normale spillversjonen ved å bruke Sprague-Grundy-teorien . Den misere versjonen ble analysert ved William Sibert i 1973, men han gjorde ikke publisere sitt arbeid frem til 1989.

Navnet "Kayles" er en anglisisering av den franske quilles , som betyr "bowling".

Analyse

De fleste spillere oppdager raskt at den første spilleren har en garantert seier i normale Kayles når radlengden er større enn null. Denne seieren kan oppnås ved hjelp av en symmetri-strategi . Ved sitt første trekk skal den første spilleren bevege seg slik at raden blir brutt i to seksjoner av samme lengde. Dette begrenser alle fremtidige trekk til den ene delen eller den andre. Nå imiterer den første spilleren bare den andre spillerens trekk i motsatt rad.

Det er mer interessant å spørre hva nim-verdien er av en lengderad . Dette er ofte betegnet ; det er en klipper , ikke et tall . Ved teoremet Sprague – Grundy , er mex over alle mulige bevegelser av nim-summen av nim-verdiene til de to resulterende seksjonene. For eksempel, ${\ displaystyle n}$${\ displaystyle K_ {n}}$${\ displaystyle K_ {n}}$

${\ 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} \}, \,}$

fordi fra en rad med lengde 5 kan man flytte til posisjonene

${\ 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}. \,}$

Rekursiv beregning av verdier (starter med ) gir resultatene oppsummert i følgende tabell. For å finne verdien av på bordet, skriv som , og se på rad a, kolonne b: ${\ displaystyle K_ {0} = 0}$${\ displaystyle K_ {n}}$${\ displaystyle n}$${\ displaystyle 12a + b}$

Kayles nim-verdier gjennom ${\ 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

På dette tidspunktet blir nim-verdisekvensen periodisk med periode 12, så alle ytterligere rader i tabellen er identiske med den siste raden.

applikasjoner

Fordi visse posisjoner i Dots and Boxes reduseres til Kayles-posisjoner, er det nyttig å forstå Kayles for å analysere en generell Dots and Boxes-posisjon.

Beregningskompleksitet

Under normalt spill kan Kayles løses på polynomisk tid ved hjelp av Sprague-Grundy-teorien.

Node Kayles er en generalisering av Kayles til grafer der hver bolle "slår ned" (fjerner) et ønsket toppunkt og alle dets nærliggende hjørner. (Alternativt kan dette spillet sees på som to spillere som finner et uavhengig sett sammen.) Schaefer (1978) beviste at det å bestemme utfallet av dette spillet er PSPACE-komplett . Det samme resultatet gjelder for en partisanversjon av node Kayles, der det kun er én spiller som får lov til å velge den aktuelle noden som nedslagsmål for hver node.

Se også

• Kombinatorisk spillteori
• Octal-spill
• Dawson's Kayles
• Nimber

Referanser