Kayles - Kayles

Un rând de boluri. La rândul său, un jucător poate alege să elimine un singur ac sau două adiacente.

Kayles este un joc imparțial simplu în teoria jocurilor combinatorii , inventat de Henry Dudeney în 1908. Având în vedere un rând de pene de bowling imaginate, jucătorii fac rând pe rând să bată fie un pini, fie doi pini adiacenți, până când toți pini sunt dispăruți. Folosind notația jocurilor octale , Kayles este notat 0,77 .

Reguli

Kayles este jucat cu un rând de jetoane, care reprezintă bolii. Rândul poate avea orice lungime. Cei doi jucători alternează; fiecare jucător, la rândul său, poate îndepărta fie orice ac (o minge aruncată direct la acul ac), fie două ace adiacente (o minge aruncată pentru a lovi pe amândouă). Conform convenției normale de joc , un jucător pierde atunci când nu are nicio mișcare legală (adică atunci când toate pinii au dispărut). Jocul poate fi jucat și folosind reguli misère ; în acest caz, câștigă jucătorul care nu se poate mișca .

Istorie

Kayles a fost inventat de Henry Dudeney . Richard Guy și Cedric Smith au fost primii care au analizat complet versiunea normală, folosind teoria Sprague-Grundy . Versiunea misère a fost analizată de William Sibert în 1973, dar nu și-a publicat opera decât în ​​1989.

Numele „Kayles” este o anglicizare a quilles-urilor franceze , care înseamnă „bowling”.

Analiză

Majoritatea jucătorilor descoperă rapid că primul jucător are o victorie garantată în Kayles normal ori de câte ori lungimea rândului este mai mare decât zero. Această victorie poate fi obținută folosind o strategie de simetrie . La prima sa mutare, primul jucător ar trebui să se miște astfel încât rândul să fie împărțit în două secțiuni de lungime egală. Aceasta restricționează toate mutările viitoare la o secțiune sau alta. Acum, primul jucător doar imită mișcările celui de-al doilea jucător în rândul opus.

Este mai interesant să ne întrebăm care este valoarea nim a unui rând de lungime . Acest lucru este adesea notat ; este un nimer , nu un număr . Prin teorema Sprague-Grundy , este MEX peste toate mișcările posibile ale nim-suma dintre nim-valorile celor două secțiuni rezultate. De exemplu, ${\ 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} \}, \,}$

deoarece dintr-un rând de lungime 5, se poate trece la poziții

${\ displaystyle K_ {0} + K_ {4}, \ quad K_ {1} + K_ {3}, \ quad K_ {2} + K_ {2}, \ quad K_ {0} + K_ {3}, { \ text {și}} K_ {1} + K_ {2}. \,}$

Calculul recursiv al valorilor (începând cu ) oferă rezultatele rezumate în tabelul următor. Pentru a găsi valoarea de pe masă, scrieți ca și uitați-vă la rândul a, coloana b: ${\ displaystyle K_ {0} = 0}$${\ displaystyle K_ {n}}$${\ displaystyle n}$${\ displaystyle 12a + b}$

Kayles nim-valori prin ${\ 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
Peste 60 de ani	4	1	2	8	1	4	7	2	1	8	6	7
Peste 72 de ani	4	1	2	8	1	4	7	2	1	8	2	7

În acest moment, secvența valorii nim devine periodică cu perioada 12, deci toate rândurile din tabel sunt identice cu ultimul rând.

Aplicații

Deoarece anumite poziții din puncte și cutii se reduc la pozițiile Kayles, este util să înțelegeți Kayles pentru a analiza o poziție generică a punctelor și casetelor.

Complexitatea computațională

În joc normal, Kayles poate fi rezolvat în timp polinomial folosind teoria Sprague-Grundy.

Nodul Kayles este o generalizare a lui Kayles în grafice în care fiecare castron „doboară” (elimină) un vârf dorit și toate vârfurile sale învecinate. (Alternativ, acest joc poate fi privit ca doi jucători care găsesc împreună un set independent .) Schaefer (1978) a dovedit că a decide rezultatul acestui joc este complet PSPACE . Același rezultat este valabil și pentru o versiune partizană a nodului Kayles, în care, pentru fiecare nod, numai unuia dintre jucători este permis să aleagă acel anumit nod ca țintă doborâtă.

Vezi si

• Teoria jocurilor combinatorii
• Jocuri octale
• Kayles al lui Dawson
• Nimber

Referințe