Kayles - Kayles

Rivi keilailunastoja. Pelaaja voi vuorollaan poistaa yhden tai kaksi vierekkäistä nastaa.

Kayles on yksinkertainen puolueeton peli vuonna kombinatorisista peliteorian , keksi Henry Dudeney vuonna 1908. Koska rivi kuvitellut keiloja, pelaajat vuorotellen tyrmätä joko yksi tappi, tai kaksi vierekkäistä nastaa, kunnes kaikki nastat ovat menneet. Käyttäen merkintätapa oktaali pelejä , Kayles merkitään 0,77 .

Säännöt

Kaylesia pelataan rivillä merkkejä, jotka edustavat keilailunastoja. Rivi voi olla minkä tahansa pituinen. Kaksi pelaajaa vuorotellen; jokainen pelaaja vuorollaan voi poistaa joko yhden nastan (pallo, joka on keilattu suoraan tälle tappiolle), tai kaksi vierekkäistä nastaa (pallo, joka on keilattu lyömään molempia). Alle normaalin toiston yleissopimus , pelaaja häviää, kun hänellä ei ole laillista siirtoa (eli kun kaikki nastat ovat menneet). Peliä voidaan pelata myös väärinkäytöksillä ; tässä tapauksessa pelaaja, joka ei voi liikkua, voittaa .

Historia

Kaylesin keksi Henry Dudeney . Richard Guy ja Cedric Smith analysoivat ensin täysin normaalin version version käyttäen Sprague-Grundy -teoriaa . Misere versio analysoitiin William Sibert vuonna 1973, mutta hän ei julkaista työnsä vasta 1989.

Nimi "Kayles" on englanninkielinen ranskalainen quilles , eli "keilailu".

Analyysi

Useimmat pelaajat huomaavat nopeasti, että ensimmäisellä pelaajalla on taattu voitto normaalissa Kaylesissa aina, kun rivin pituus on suurempi kuin nolla. Tämä voitto voidaan saavuttaa käyttämällä symmetriastrategiaa . Ensimmäisellä liikkeellään ensimmäisen pelaajan tulisi liikkua siten, että rivi jaetaan kahteen yhtä pituiseen osaan. Tämä rajoittaa kaikki tulevat siirrot yhteen tai toiseen osaan. Nyt ensimmäinen pelaaja vain jäljittelee toisen pelaajan liikkeitä vastakkaisella rivillä.

On mielenkiintoisempaa kysyä, mikä nim-arvo on rivillä . Tätä kutsutaan usein ; se on nimber , ei numero . Jonka Sprague-Grundy lause , on mex kaikilla mahdollisilla liikkuu ja NIM-summa on NIM-arvot saadut kaksi osaa. Esimerkiksi, ${\ 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} \}, \,}

koska riviltä, jonka pituus on 5, voidaan siirtyä asemiin

{\ displaystyle K_ {0} + K_ {4}, \ quad K_ {1} + K_ {3}, \ quad K_ {2} + K_ {2}, \ quad K_ {0} + K_ {3}, { \ text {ja}} K_ {1} + K_ {2}. \,}

Arvojen rekursiivinen laskeminen (alkaen ) antaa tulokset yhteenvetona seuraavassa taulukossa. Löydät taulukon arvon kirjoittamalla nimellä ja katsomalla rivin a saraketta b: ${\ displaystyle K_ {0} = 0}$ ${\ displaystyle K_ {n}}$ ${\ displaystyle n}$ ${\ displaystyle 12a + b}$

Kayles nim-arvot läpi ${\ 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

Tässä vaiheessa nim-arvon sekvenssi muuttuu jaksolliseksi jakson 12 kanssa, joten kaikki taulukon muut rivit ovat identtisiä viimeisen rivin kanssa.

Sovellukset

Koska tietyt pisteiden ja laatikoiden sijainnit pienenevät Kaylesin sijainteihin, on hyödyllistä ymmärtää Kayles, jotta voidaan analysoida yleinen pisteiden ja laatikoiden sijainti.

Laskennallinen monimutkaisuus

Normaalissa pelissä Kayles voidaan ratkaista polynomi-ajassa käyttämällä Sprague-Grundy -teoriaa.

Solmu Kayles on yleistys Kaylesista kaavioihin, joissa kukin kulho “kaataa” (poistaa) halutun kärjen ja kaikki sen vierekkäiset pisteet. (Vaihtoehtoisesti tämän pelin voidaan katsoa olevan kaksi pelaajaa, jotka löytävät itsenäisen sarjan yhdessä.) Schäfer (1978) osoitti, että tämän pelin lopputuloksen päättäminen on PSPACE-täydellinen . Sama tulos pätee solmun Kaylesin partisaaniversiolle, jossa jokaiselle solmulle vain yksi pelaajista saa valita kyseisen solmun pudotuskohteeksi.

Katso myös

Viitteet

^ Dudeney, HE (2002), The Canterbury puzzles , Dover, s. 118–119, palapeli 73, ISBN 0-486-42558-4. Alun perin julkaistu vuonna 1908.
^ Conway, John H. Numeroista ja peleistä. Academic Press, 1976.
^ ^a ^b R. K. Guy ja CAB Smith, Eri pelien G- arvot, Proc. Cambridge Philos. Soc., 52 (1956) 514–526.
^ TE Plambeck, Daisies, Kayles ja Sibert-Conway hajoaminen MISERE oktaalimuodossa peleissä arkistoitu 2010-07-14 klo Wayback Machine , Theoret. Laske. Sci (Math Games) (1992) 96361–388.
^ ^B Plambeck, Thane, Kayles , arkistoitu alkuperäinen on 2008-10-12 , haettu 2008-08-15
^ E. Berlekamp , JH Conway , R. Guy. Voittavia tapoja matemaattisille näytelmillesi . Academic Press, 1982.
^ Schaefer, Thomas J. (1978). "Joidenkin kahden hengen täydellisen tietopelin monimutkaisuudesta" . Journal of Computer and System Sciences . 16 (2): 185–225. doi : 10.1016 / 0022-0000 (78) 90045-4 .

[1] Dudeney, HE (2002), The Canterbury puzzles , Dover, s. 118–119, palapeli 73, ISBN 0-486-42558-4. Alun perin julkaistu vuonna 1908.

[onag-2] Conway, John H. Numeroista ja peleistä. Academic Press, 1976.

[guy-smith-3] R. K. Guy ja CAB Smith, Eri pelien G- arvot, Proc. Cambridge Philos. Soc., 52 (1956) 514–526.

[plambeck-4] TE Plambeck, Daisies, Kayles ja Sibert-Conway hajoaminen MISERE oktaalimuodossa peleissä arkistoitu 2010-07-14 klo Wayback Machine , Theoret. Laske. Sci (Math Games) (1992) 96361–388.

[plambeck2-5] B Plambeck, Thane, Kayles , arkistoitu alkuperäinen on 2008-10-12 , haettu 2008-08-15

[ww-6] E. Berlekamp , JH Conway , R. Guy. Voittavia tapoja matemaattisille näytelmillesi . Academic Press, 1982.

[7] Schaefer, Thomas J. (1978). "Joidenkin kahden hengen täydellisen tietopelin monimutkaisuudesta" . Journal of Computer and System Sciences . 16 (2): 185–225. doi : 10.1016 / 0022-0000 (78) 90045-4 .

Languages

In other projects