Kayles - Kayles

Bir sıra bowling pinleri. Sıra kendilerine geldiğinde, bir oyuncu tek bir pimi veya iki bitişik pimi ortadan kaldırmayı seçebilir.

Kayles , 1908'de Henry Dudeney tarafından icat edilen, kombinatoryal oyun teorisinde basit, tarafsız bir oyundur . Bir dizi hayali bowling lobutu verildiğinde, oyuncular sırayla tüm lobutlar bitene kadar ya bir ya da iki bitişik lobutu nakavt ederler. Sekizli oyunların gösterimi kullanılarak Kayles 0.77 ile gösterilir .

Kurallar

Kayles, bowling pinlerini temsil eden bir dizi jetonla oynanır. Satır herhangi bir uzunlukta olabilir. İki oyuncu dönüşümlü olarak; her oyuncu, sırası geldiğinde, herhangi bir pimi (doğrudan o pime atılan bir top) veya iki bitişik pimi (ikisine de vurmak için bir top atılır) çıkarabilir. Altında Normal oyun kongre o geçerli bir hamlesi zaman, bir oyuncu kaybeder (olduğunu, bütün iğneler gitmiş olduğunda). Oyun aynı zamanda misère kuralları kullanılarak da oynanabilir ; bu durumda hareket edemeyen oyuncu kazanır .

Tarih

Kayles, Henry Dudeney tarafından icat edildi . Richard Guy ve Cedric Smith , Sprague-Grundy teorisini kullanarak normal oyun versiyonunu tamamen analiz eden ilk kişilerdi . Misère'den versiyonu ile analiz edilmiştir William Sibert 1973 yılında, ancak 1989 yılına kadar işini yayımlamak vermedi.

"Kayles" adı , "bovling" anlamına gelen Fransız quilles'in İngilizceleştirilmesidir .

analiz

Çoğu oyuncu, sıra uzunluğu sıfırdan büyük olduğunda, normal Kayles'ta ilk oyuncunun garantili bir galibiyete sahip olduğunu hemen keşfeder. Bu kazanç bir simetri stratejisi kullanılarak elde edilebilir . İlk hamlesinde, ilk oyuncu sıra eşit uzunlukta iki bölüme ayrılacak şekilde hareket etmelidir. Bu, gelecekteki tüm hareketleri bir bölüme veya diğerine kısıtlar. Şimdi, ilk oyuncu sadece ikinci oyuncunun karşı sıradaki hareketlerini taklit ediyor.

Bir satır uzunluğundaki nim değerinin ne olduğunu sormak daha ilginçtir . Bu genellikle belirtilir ; Bir olan nimber değil, bir sayı . Tarafından Sprague-Grundy teoremi , bir mex mümkün olan tüm hareketleri boyunca niml-sum of niml-değerleri edilen iki bölümden. Örneğin, ${\görüntüleme stili n}$ ${\ Displaystyle K_{n}}$ ${\ Displaystyle K_{n}}$

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

çünkü 5 uzunluğundaki bir satırdan pozisyonlara hareket edilebilir

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

Değerlerin özyinelemeli hesaplaması ( ile başlayarak ), aşağıdaki tabloda özetlenen sonuçları verir. Tablodaki değerini bulmak için olarak yazın ve a satırı, b sütununa bakın: $K_{0}=0$ ${\ Displaystyle K_{n}}$ ${\görüntüleme stili n}$ ${\ Displaystyle 12a+b}$

Kayles nim-değerleri aracılığıyla $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

Bu noktada, nim-değer dizisi 12. periyotla periyodik hale gelir, bu nedenle tablonun diğer tüm satırları son satırla aynıdır.

Uygulamalar

Noktalar ve Kutulardaki belirli konumlar Kayles konumlarına indirgendiğinden, genel bir Noktalar ve Kutular konumunu analiz etmek için Kayles'ı anlamak yardımcı olur.

hesaplama karmaşıklığı

Normal oyun altında Kayles , Sprague-Grundy teorisi kullanılarak polinom zamanında çözülebilir .

Düğüm Kayles , Kayles'in , her bir kasenin istenen bir köşeyi ve onun tüm komşu köşelerini "düşürdüğü" (kaldırdığı) grafiklere yönelik bir genellemesidir. (Alternatif olarak, bu oyun iki oyuncunun birlikte bağımsız bir set bulması olarak görülebilir .) Schaefer (1978), bu oyunun sonucuna karar vermenin PSPACE-tamamlandığını kanıtladı . Aynı sonuç, Kayles düğümünün partizan bir versiyonu için de geçerlidir; burada, her düğüm için, oyunculardan yalnızca birinin o belirli düğümü yıkma hedefi olarak seçmesine izin verilir.

Ayrıca bakınız

Referanslar

^ Dudeney, HE (2002), Canterbury bulmacaları , Dover, s. 118–119, bulmaca 73, ISBN 0-486-42558-4. İlk olarak 1908'de yayınlandı.
^ Conway, John H. Sayılar ve Oyunlar Üzerine. Akademik Basın, 1976.
^ ^a ^b R. K. Guy ve CAB Smith, Çeşitli oyunların G değerleri, Proc. Cambridge Philos. Soc., 52 (1956) 514-526.
^ TE Plambeck, Papatyalar, Kayles ve Sibert-Conway ayrışma içinde misere sekizli oyunlar Arşivlenen en 2010-07-14 Wayback Machine , Theoret. Bilgisayar. Bilim (Matematik Oyunları) (1992) 96 361–388.
^ ^a ^b Plambeck, Thane, Kayles , orijinalinden 2008-10-12 tarihinde arşivlendi , alındı 2008-08-15
^ E. Berlekamp , JH Conway , R. Guy. Matematik Oyunlarınız İçin Kazanma Yolları . Akademik Basın, 1982.
^ Schaefer, Thomas J. (1978). "Bazı iki kişilik mükemmel bilgi oyunlarının karmaşıklığı üzerine" . Bilgisayar ve Sistem Bilimleri Dergisi . 16 (2): 185-225. doi : 10.1016/0022-0000(78)90045-4 .

[1] Dudeney, HE (2002), Canterbury bulmacaları , Dover, s. 118–119, bulmaca 73, ISBN 0-486-42558-4. İlk olarak 1908'de yayınlandı.

[onag-2] Conway, John H. Sayılar ve Oyunlar Üzerine. Akademik Basın, 1976.

[guy-smith-3] R. K. Guy ve CAB Smith, Çeşitli oyunların G değerleri, Proc. Cambridge Philos. Soc., 52 (1956) 514-526.

[plambeck-4] TE Plambeck, Papatyalar, Kayles ve Sibert-Conway ayrışma içinde misere sekizli oyunlar Arşivlenen en 2010-07-14 Wayback Machine , Theoret. Bilgisayar. Bilim (Matematik Oyunları) (1992) 96 361–388.

[plambeck2-5] Plambeck, Thane, Kayles , orijinalinden 2008-10-12 tarihinde arşivlendi , alındı 2008-08-15

[ww-6] E. Berlekamp , JH Conway , R. Guy. Matematik Oyunlarınız İçin Kazanma Yolları . Akademik Basın, 1982.

[7] Schaefer, Thomas J. (1978). "Bazı iki kişilik mükemmel bilgi oyunlarının karmaşıklığı üzerine" . Bilgisayar ve Sistem Bilimleri Dergisi . 16 (2): 185-225. doi : 10.1016/0022-0000(78)90045-4 .

Languages

In other projects