كالا

كالاه هي نسخة حديثة من عائلة ألعاب مانكالا القديمة. حصل ويليام جوليوس تشامبيون الابن على براءة اختراع لوحة كالاه وباعها لأول مرة في الولايات المتحدة في خمسينيات القرن العشرين. ^{[ 1 ] [ 2 ]} تُعرف هذه اللعبة أحيانًا باسم "كالهاري"، ربما بسبب اشتقاق خاطئ من صحراء كالهاري في ناميبيا .

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

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

1. في بداية اللعبة، يتم وضع أربع بذور في كل بيت. هذه هي الطريقة التقليدية.
2. يتحكم كل لاعب في المنازل الستة والبذور الموجودة على جانبه من اللوحة. وتُحسب نقاط اللاعب بعدد البذور الموجودة في المخزن على يمينه.
3. يتناوب اللاعبون على زرع بذورهم. في كل دور، يزيل اللاعب جميع البذور من أحد البيوت التي يسيطر عليها. يتحرك اللاعب عكس اتجاه عقارب الساعة، ويضع بذرة واحدة في كل بيت بالتناوب، بما في ذلك بذرته الخاصة، ولكن ليس في بيوت خصمه.
4. إذا سقطت البذرة الأخيرة المزروعة في منزل فارغ يملكه اللاعب، وكان المنزل المقابل يحتوي على بذور، فسيتم التقاط كل من البذرة الأخيرة والبذور المقابلة ووضعها في مخزن اللاعب.
5. إذا سقطت آخر بذرة مزروعة في مخزن اللاعب، يحصل اللاعب على حركة إضافية. لا يوجد حد أقصى لعدد الحركات التي يمكن للاعب القيام بها في دوره.
6. عندما ينفد مخزون البذور لدى أحد اللاعبين، تنتهي اللعبة. ينقل اللاعب الآخر جميع البذور المتبقية إلى مخزنه، ويفوز اللاعب الذي يملك أكبر عدد من البذور في مخزنه.

من الممكن أن تنتهي المباراة بالتعادل.

مثال على الدوران

يبدأ اللاعب بالزراعة من المنزل المظلل.

تسقط البذرة الأخيرة في المتجر، لذا يحصل اللاعب على حركة إضافية.

تسقط البذرة الأخيرة في منزل فارغ في جانب اللاعب. يجمع اللاعب البذور المميزة من منزله ومن منزل خصمه المقابل، ثم ينقلها إلى المتجر.

طُبِّقَتْ لعبة كالا على جهاز PDP-1 في أوائل الستينيات، ^{[ 3 ]} واستطاعت التفوق على اللاعبين البشريين ذوي الخبرة. ^{[ 4 ]} ومنذ ذلك الحين، ظهرت تطبيقات عديدة للعبة كالا على أنظمة مختلفة، بما في ذلك MS -DOS ^{[ 5 ]} ونوكيا 3310. ^{[ 6 ]}

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

كما ذُكر سابقًا، إذا سقطت آخر بذرة زرعها اللاعب في مخزنه، يحصل على حركة إضافية. يستطيع اللاعب الماهر استغلال هذه القاعدة لربط عدة حركات إضافية. بهذه الطريقة، يمكن مسح بعض تشكيلات صف معين من اللوحة في حركة واحدة، أي يستطيع اللاعب الاستيلاء على جميع الأحجار في صفه، كما هو موضح على اليمين. أطول سلسلة ممكنة من هذا النوع على لوحة كالا القياسية ذات 6 حفر تستغرق 17 حركة. على لوحة عامة ذات n حفرة، كانت أنماط البذور التي يمكن مسحها في حركة واحدة بهذه الطريقة موضوع دراسة رياضية. ^{[ 9 ]} يمكن إثبات أنه، لكل قيمة لـ n ، يوجد نمط واحد فقط يمكن مسحه في n حركة بالضبط، أو بصورة مكافئة، نمط واحد فقط يمكن مسحه ويتكون من n بذرة بالضبط.

تتطلب هذه الأنماط صفوفًا من الحفر بأطوال مختلفة، وتزداد قيمة n مع ازدياد عدد الحفر. على سبيل المثال، يمكن ملاحظة على اليمين أن نمط البذور الخمس الفريد يتطلب 3 حفر فقط، بينما يتطلب نمط البذور السبعة عشر 6 حفر. يمكن وصف العلاقة بين عدد الحفر المطلوبة وعدد البذور على النحو التالي: لنفترض أن s ( n ) يمثل الحد الأدنى لعدد البذور الذي يتطلب n حفرة لإزالتها. ${\displaystyle s(n)\sim {\frac {n^{2}}{\pi }},}$ حيث الرمز${\displaystyle \sim }$يشير إلى التكافؤ التقاربي ، أي${\displaystyle \lim _{n\to \infty }{\frac {s(n)}{n^{2}/\pi }}=1}$أو ما يعادل ذلك،${\displaystyle \lim _{n\to \infty }{\frac {n^{2}}{s(n)}}=\pi }$[ ^{9 ]​}

قام مارك راولينغز بكتابة برنامج حاسوبي لتحليل كلٍّ من النسخة "القياسية" من لعبة كالا ونسخة "الاستيلاء الفارغ"، وهي النسخة الأساسية. وقد أُتيح هذا التحليل بفضل إنشاء أكبر قواعد بيانات لنهايات لعبة كالا على الإطلاق. تتضمن هذه القواعد نتائج اللعب الأمثل لجميع المواضع البالغ عددها 38,902,940,896 موضعًا والتي تحتوي على 34 بذرة أو أقل. في عام 2015، ولأول مرة، تم تحديد كل حركة من الحركات الأولية للنسخة القياسية من كالا (6،4) وكالا (6،5) كميًا: كالا (6،4) هي فوز مؤكد بفارق 8 نقاط للاعب الأول، وكالا (6،5) هي فوز مؤكد بفارق 10 نقاط للاعب الأول. بالإضافة إلى ذلك، ثبت أن كالا (6،6) وفقًا للقواعد القياسية تضمن فوزًا بفارق 4 نقاط على الأقل. ولا يزال التحليل الإضافي لكالا (6،6) وفقًا للقواعد القياسية جاريًا.

في نسخة "الاستحواذ الفارغ"، أثبت جيفري إيرفينغ وجيرون دونكرز (2000) أن كالا (6،4) تُحقق فوزًا بفارق 10 نقاط للاعب الأول الذي يلعب بشكل مثالي، وأن كالا (6،5) تُحقق فوزًا بفارق 12 نقطة للاعب الأول الذي يلعب بشكل مثالي. كما أثبت أندرس كارستنسن (2011) أن كالا (6،6) تُحقق فوزًا للاعب الأول. وقد وسّع مارك راولينغز (2015) نتائج "الاستحواذ الفارغ" هذه من خلال تحديد الحركات الأولية لكل من كالا (6،4) وكالا (6،5) وكالا (6،6) بدقة. وباستخدام عمليات بحث بلغ مجموعها 106 أيام وأكثر من 55 تريليون عقدة، أثبت أن كالا (6،6) تُحقق فوزًا بفارق نقطتين للاعب الأول الذي يلعب بشكل مثالي. وكانت هذه النتيجة مفاجئة، نظرًا لأن متغيري "البذور 4" و"البذور 5" يُحققان فوزًا بفارق 10 و12 نقطة على التوالي. تُعتبر مسألة Kalah(6,6) عميقة ومعقدة للغاية عند مقارنتها بالاختلافات ذات 4 بذور و 5 بذور، والتي يمكن حلها الآن في جزء من الثانية وأقل من دقيقة على التوالي.

تم تحميل قواعد بيانات نهاية اللعبة التي أنشأها مارك راولينغز في ذاكرة الوصول العشوائي (RAM) أثناء تهيئة البرنامج (يستغرق التحميل 17 دقيقة). ولتمكين البرنامج من العمل على جهاز كمبيوتر مزود بذاكرة وصول عشوائي سعتها 32 جيجابايت، لم يتم تحميل قواعد بيانات البذرة 30 والبذرة 33.

عدد إحصائيات قاعدة بيانات نهاية اللعبة: عدد مواقع البذور، العدد التراكمي ------------------------------------------- 2-25 1,851,010,435 1,851,010,435 26854652330 2705662765 27 1,202,919,536 3,908,582,301 28 1,675,581,372 5,584,163,673 29 2,311,244,928 7,895,408,601 30 3,158,812,704 11,054,221,305 31 4,279,807,392 15,334,028,697 32 5,751,132,555 21,085,161,252 33 7,668,335,248 28,753,496,500 34 10,149,444,396 38,902,940,896 -------------------------------------------

في الأقسام التالية، تُرقّم الصناديق كما هو موضح، ويكون اللعب عكس اتجاه عقارب الساعة. ينتقل الجنوب من الصناديق من 1 إلى 6، وينتقل الشمال من الصناديق من 8 إلى 13. الصندوق 14 هو متجر الشمال، والصندوق 7 هو متجر الجنوب.

 <--- شمال ------------------------ 13 12 11 10 9 8 14 7 1 2 3 4 5 6 ------------------------ الجنوب --->

 <--- شمال ------------------------ 4 4 4 4 4 4 0 0 4 4 4 4 4 4 ------------------------ الجنوب --->

القواعد القياسية: نتيجة الحركة: استمرار مثالي للعب ------------------------------------------------------- 1 يخسر بفارق 14 10 13 3 9 13 12 1 13 11 5 13 خسر الفريقان بفارق 10 نقاط. 10 13 5 9 13 8 4 10 13 8 5 خسارة 3-1 بفارق 6 نقاط 10 11 2 13 1 12 1 13 9 4 12 تعادل 3-2 10 13 5 9 13 8 3 11 1 13 10 فوز 3-4 بفارق نقطتين 10 9 13 2 1 12 3 5 8 12 13 فوز 3-5 بفارق 4 نقاط 9 10 2 5 12 1 2 11 2 13 5 فوز 3-6 بفارق 8 9 8 2 12 6 5 11 6 1 6 5 4 يخسرون بفارق نقطتين 10 12 2 4 13 1 5 9 13 12 13 5 يخسر بفارق 8 10 9 11 2 5 10 1 8 4 12 5 فاز الفريق 6 بفارق 4 نقاط (9، 12، 2، 6، 1، 11، 4، 10، 6، 5، 13). -------------------------------------------------------

نسخة "التقاط فارغ": نتيجة الحركة: استمرار مثالي للعب ------------------------------------------------------- 1 يخسر بفارق 14 10 13 4 9 13 11 2 13 8 13 10 خسر الفريقان بفارق 8 نقاط، 10 نقاط، 13 نقطة، 5 نقاط، 9 نقاط، 13 نقطة، 8 نقاط، 4 نقاط، 10 نقاط، 13 نقطة، 9 نقاط، 5 نقاط. خسارة 3-1 بفارق 8 نقاط. 10 11 4 9 12 2 10 5 11 12 9 خسارة 3-2 بفارق نقطتين 10 13 5 9 13 8 3 11 5 13 10 فوز 3-4 بفارق نقطتين 10 9 13 2 1 12 3 5 8 12 13 فوز 3-5 بفارق 4 نقاط 9 11 2 4 8 12 5 13 5 11 4 فوز 3-6 بفارق 10 نقاط في المباريات التالية: 9، 8، 4، 11، 6، 2، 6، 4، 9، 5، 13 4 يخسرون بفارق نقطتين 10 12 2 5 9 8 12 9 4 10 11 5 يخسرون بفارق 6 نقاط 10 9 11 4 8 13 5 6 4 12 6 فاز الفريق 6 بفارق 4 نقاط (9، 12، 2، 6، 1، 11، 4، 10، 6، 5، 13). -------------------------------------------------------

الوضع الابتدائي مع 5 بذور في كل صندوق:

 <--- شمال ------------------------ 5 5 5 5 5 5 0 0 5 5 5 5 5 5 ------------------------ الجنوب --->

القواعد القياسية: نتيجة الحركة: استمرار مثالي للعب ------------------------------------------------------- 1 يخسر بفارق 10 9 11 4 8 13 2 9 6 3 11 13 خسارة 2-1 بفارق 4 نقاط 9 10 2 12 1 11 3 12 8 11 1 فوز 2-3 بفارق 10 نقاط 10 1 6 9 5 13 6 2 8 4 13 فوز 2-4 بفارق 10 نقاط في المباريات التالية: 8، 11، 1، 6، 9، 2، 13، 11، 4، 12، 6 فوز 2-5 بفارق 8 8 10 1 6 9 5 13 12 2 13 11 تعادل ٢-٦ ٨ ١١ ١ ٦ ٣ ١١ ٦ ٥ ١٢ ٦ ٨ فاز الفريق 3 بفارق نقطتين 9 8 12 1 4 11 2 12 10 4 3 فاز الفريق 4 بفارق نقطتين 8 11 1 5 12 3 10 5 2 11 6 5 يفوز بفارق 2 8 12 1 4 9 2 12 4 9 3 11 6 تعادل 8 12 1 6 4 10 6 2 11 4 3 -------------------------------------------------------

نسخة "التقاط فارغ": نتيجة الحركة: استمرار مثالي للعب ------------------------------------------------------- 1 يخسر بفارق 10 9 12 6 8 12 11 2 8 6 5 12 خسارة 2-1 بفارق 6 نقاط. 9 10 2 12 4 8 9 3 10 11 3 فوز 2-3 بفارق 12 نقطة في النقاط التالية: 8، 10، 1، 6، 10، 5، 13، 9، 6، 4، 11 فوز 2-4 بفارق 8 8 9 1 6 11 4 13 10 4 13 9 فوز 2-5 بفارق 8 8 10 1 6 9 5 13 12 3 13 6 2-6 يخسر بفارق نقطتين 8 11 1 6 5 9 6 3 11 12 5 فاز الفريق 3 بفارق نقطتين 9 8 12 1 4 11 2 10 4 5 10 4 تعادل 8 11 1 5 12 3 9 5 2 11 3 5 تعادل 8 10 1 4 12 5 11 2 9 4 13 6 تعادل 8 12 1 6 4 9 6 2 12 6 5 -------------------------------------------------------

 <--- شمال ------------------------ 6 6 6 6 6 6 0 0 6 6 6 6 6 6 ------------------------ الجنوب --->

النسخة "القياسية": نتيجة الحركة ------------------------------------------------------- فوز مؤكد بنتيجة 1-2، بفارق لا يقل عن نقطتين. فوز مؤكد بنتيجة 1-3، بفارق لا يقل عن 4 نقاط. 1-4 1-5 خسارة مؤكدة من 1 إلى 6، بفارق لا يقل عن 2 2 يتجه نحو الفوز 3 4 5 6 خسائر مؤكدة، بفارق لا يقل عن 2 ------------------------------------------------------- أما الحركات المتبقية (1-4، 1-5، 3، 4، و5) فهي تعادلات محتملة بناءً على عمليات بحث عميقة للغاية، ومع ذلك، لم يتم إثبات النتيجة بعد.

نسخة "التقاط فارغ": نتيجة الحركة: استمرار مثالي للعب ------------------------------------------------------- فوز 1-2 بفارق نقطتين 10 3 12 4 8 6 10 11 6 3... فوز 1-3 بفارق 2 11 1 8 2 10 6 8 3 11 5... تعادل 1-4 10 3 12 5 10 3 9 1 12 3... تعادل 1-5 9 4 8 3 10 2 10 4 1 9... 1-6 تعادل 10 4 9 6 3 11 6 8 2 10... فوز 2 بفارق نقطتين 12 4 10 1 12 8 1 11 3 9... 3 تعادل 10 5 12 4 11 1 12 8 4 3... 4 تعادل 10 3 11 1 9 5 11 2 10 8... 5 تعادل 10 3 11 4 12 2 11 4 10 5... خسارة 6 بفارق 2 10 3 8 6 4 13 1 10 13 8... -------------------------------------------------------

زمن الانتقال (ثانية) عدد العقد التي تم البحث فيها ---------------------------------------- 1-2 305,791 2,214,209,715,560 1-3 403,744 2,872,262,354,066 1-4 401,349 2,335,350,353,288 1-5 317,795 1,886,991,523,192 1-6 392,923 2,313,607,567,702 2 1,692,886 9,910,945,999,186 3 1,296,141 7,398,319,653,760 4 1,411,091 9,623,816,064,478 5 1,607,514 9,318,824,643,697 6 1,354,845 7,824,794,014,305 ---------------------------------------- المجموع 9,184,079 55,699,121,889,234

• بالانجوزي
• أوير