كايلز

لعبة كايلز هي لعبة بسيطة ومحايدة في نظرية الألعاب التوافقية ، ابتكرها هنري دوديني عام 1908. تُعطى مجموعة من دبابيس البولينج المتخيلة، ويتناوب اللاعبون على إسقاط دبوس واحد أو دبوسين متجاورين، حتى يتم إسقاط جميع الدبابيس. باستخدام ترميز الألعاب الثمانية ، يُرمز إلى لعبة كايلز بالرمز 0.77 .

تُلعب لعبة كايلز بصف من القطع، التي تُمثل دبابيس البولينج. يمكن أن يكون طول الصف أي طول. يتناوب اللاعبان؛ في دور كل لاعب، يُمكنه إزالة دبوس واحد (برمي الكرة مباشرةً نحو ذلك الدبوس)، أو دبوسين متجاورين (برمي الكرة لتصيبهما معًا). وفقًا لقواعد اللعب المعتادة ، يخسر اللاعب عندما لا يكون لديه أي حركة قانونية (أي عندما تُزال جميع الدبابيس). يُمكن أيضًا لعب اللعبة باستخدام قواعد "ميزير" ؛ في هذه الحالة، يفوز اللاعب الذي لا يستطيع التحرك .

ابتكر هنري دوديني نظام كايلز . ^{[ 1 ] [ 2 ]} وكان ريتشارد جاي وسيدريك سميث أول من قام بتحليل نسخة اللعب العادي تحليلاً كاملاً، باستخدام نظرية سبراغ-غروندي . ^{[ 3 ] [ 4 ]} أما نسخة الميزير فقد حللها ويليام سيبرت عام 1973، لكنه لم ينشر عمله حتى عام 1989. ^{[ 5 ]}

اسم "Kayles" هو تحريف إنجليزي للكلمة الفرنسية quilles ، والتي تعني "دبابيس البولينج".

يكتشف معظم اللاعبين سريعًا أن اللاعب الأول يضمن الفوز في لعبة كايلز العادية كلما كان طول الصف أكبر من صفر. ويمكن تحقيق هذا الفوز باستخدام استراتيجية التناظر . في حركته الأولى، يجب على اللاعب الأول أن يحرك قطعه بحيث ينقسم الصف إلى قسمين متساويين في الطول. هذا يُقيد جميع الحركات اللاحقة إلى أحد القسمين. الآن، يُقلد اللاعب الأول ببساطة حركات اللاعب الثاني في الصف المقابل.

من المثير للاهتمام أكثر أن نسأل عن قيمة نيم لصف طوله${\displaystyle n}$ويُشار إلى ذلك غالبًا بـ${\displaystyle K_{n}}$هو عدد ، وليس رقمًا . وفقًا لنظرية سبراغ-غروندي ،${\displaystyle K_{n}}$يمثل هذا التعبير المتوسط ​​(mex) لجميع الحركات الممكنة لمجموع قيم نيم ( nim-sum) للقسمين الناتجين. على سبيل المثال،

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

لأنه من صف طوله 5، يمكن الانتقال إلى المواضع

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

الحساب التكراري للقيم (بدءًا من${\displaystyle K_{0}=0}$يُعطي ) النتائج المُلخصة في الجدول التالي. لإيجاد قيمة${\displaystyle K_{n}}$اكتب على الطاولة${\displaystyle n}$مثل${\displaystyle 12a+b}$وانظر إلى الصف أ، العمود ب:

قيم كايلز نيم من خلال${\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

عند هذه النقطة، يصبح تسلسل قيمة نيم دوريًا ^{[ 5 ]} بفترة 12، لذا فإن جميع الصفوف اللاحقة من الجدول متطابقة مع الصف الأخير.

لأن بعض المواضع في النقاط والمربعات تختزل إلى مواضع كايلز، ^{[ 6 ]} من المفيد فهم كايلز من أجل تحليل موضع النقاط والمربعات العام.

في ظل اللعب العادي، يمكن حل مسألة كايلز في وقت متعدد الحدود باستخدام نظرية سبراغ-غروندي. ^{[ 3 ]}

في تعميم لعبة كايلز على الرسوم البيانية ، تقوم كل كرة "بإسقاط" (إزالة) رأس مرغوب فيه وجميع الرؤوس المجاورة له ^{[ 7 ]} ، ^{[ 8 ]} . ويمكن النظر إلى هذه اللعبة، بدلاً من ذلك، على أنها لعبة يتنافس فيها لاعبان لإيجاد مجموعة مستقلة معًا. ويمكن حل مسألة تحديد الفائز في النسخة العادية (يفوز آخر من يلعب) في وقت متعدد الحدود لأي عائلة من الرسوم البيانية ذات عدد كويكبي محدود (يُعرَّف بأنه حجم أكبر مجموعة فرعية من الرؤوس بحيث تؤدي إزالة الجوار المغلق لأي رأس في المجموعة إلى بقاء الرؤوس المتبقية في المجموعة ضمن نفس المكون المتصل). ^{[ 8 ]}

وبالمثل، في لعبة تكوين الزمر ، يجب على لاعبين إيجاد زمرة في الرسم البياني. في النسخة العادية (يفوز آخر من يلعب)، أثبت شيفر ^{[ 9 ]} عام 1978 أن تحديد نتيجة هذه الألعاب مسألة كاملة في فضاء PSPACE (وينطبق الأمر نفسه على النسخ الحزبية، حيث يُسمح للاعب واحد فقط باختيار كل رأس كهدف للإسقاط). أُثبتت اكتمال نسخ "ميزير" من هذه اللعبة في فضاء PSPACE عام 2024 ^{[ 10 ]} ، ونسخ التحسين عام 2025 ^{[ 11 ]} .

• نظرية الألعاب التوافقية
• ألعاب ثمانية
• كايلز من داوسون
• رقم