هل لعبة الداما محلولة رياضيًا؟ كيف برهن 18 عامًا من الحوسبة على التعادل الحتمي وماذا يعني ذلك للاعبين

على مدار قرون طويلة، تساءل الرياضيون وأساتذة الألعاب اللوحية في شتى أنحاء العالم عن الحقيقة الكامنة خلف نقلات الداما: هل تمتلك هذه اللعبة مصيرًا حسابيًا محتومًا منذ النقلة الأولى؟ حين يجلس لاعبان خبيران أمام رقعة مربعة مكونة من أربعة وستين مربعًا ولا يقترف أي منهما أدنى هفوة، هل يمتلك البادئ بالنقلة أفضلية تضمن له الفوز الحتمي؟ وهل يرزح اللاعب الثاني تحت عبء خسارة لا مفر منها؟ أم أن الصراع المتكافئ ينتهي حتمًا بنقطة تعادل منصفة؟

في صيف عام 2007، حسمت ورقة بحثية بارزة نُشرت في مجلة Science هذا الجدل التاريخي^[1]. أعلن فريق بحثي من جامعة ألبرتا الكندية بقيادة عالم الحاسوب جوناثان شيفر أن لعبة الداما الإنجليزية، المعروفة في المراجع الغربية باسم checkers، قد حُلّت حسابيًا بصورة قاطعة. وبعد مسيرة علمية استغرقت 18 عامًا بدأت في عام 1989، أثبت برنامجهم الحاسوبي المسمى تشينوك (Chinook) حقيقة رياضية دامغة: اللعب المثالي الخالي من الأخطاء من كلا الطرفين يؤدي بصورة حتمية إلى التعادل.

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

مستويات الحل الثلاثة في نظرية الألعاب والذكاء الاصطناعي

في حديثنا اليومي المعتاد، نقول إننا قمنا بحل لغز ما عندما نكتشف الخدعة التي تجعله بسيطًا وسهل الإدراك. أما في الرياضيات المتقطعة ونظرية الألعاب، فيخضع هذا المفهوم لتعريف علمي دقيق صاغه الباحث فيكتور أليس في عام 1994^[2]. قسّم أليس حلول الألعاب التنافسية ذات المعلومات الكاملة إلى 3 مراتب رئيسية:

1. الحل فائق الضعف (Ultra-weakly solved). يثبت البرهان الرياضي النتيجة النظرية للوضعية الابتدائية دون أن يقدم خوارزمية صريحة أو سلسلة نقلات تفصيلية لتحقيقها. ومن أشهر الأمثلة على ذلك لعبة هيكس، حيث تثبت نظرية الألعاب وجود فوز حتمي للبادئ بفضل حجة سرقة الاستراتيجية، دون التمكن من حساب النقلات الفائزة عمليًا على الرقع الكبيرة.
2. الحل الضعيف (Weakly solved). تقدم الخوارزمية استراتيجية كاملة ومبرهنة تكفل التعادل أو الفوز انطلاقًا من الوضعية الابتدائية للرقعة ضد أي نقلة محتملة يختارها الخصم. قد لا تعرف الخوارزمية التقييم الدقيق لكل وضعية شاذة ناتجة عن أخطاء فادحة، لكنها من نقطة البداية لا تُقهر أبدًا. وتنتمي لعبة الداما تمامًا إلى هذه المرتبة^[1].
3. الحل القوي (Strongly solved). تحسب الخوارزمية القيمة الحسابية الدقيقة والنقلة المثالية لكل وضعية يمكن بلوغها قانونيًا على الرقعة، بصرف النظر عن كمية الأخطاء السابقة. حُلت لعبة كوناكت فور حلًا قويًا في عام 1988: يضمن اللاعب البادئ الفوز دائمًا عند اختيار العمود الأوسط بدقة^[2].

حُلت الداما حلًا ضعيفًا وليس قويًا، لأن تخزين مليارات الوضعيات العشوائية الخارجة عن المنطق كان سيتطلب طاقة استيعابية تتجاوز قدرة حواسيب العصر. وركز فريق شيفر أبحاثه على إثبات المسار المنطلق من نقطة البداية الرسمية. تبدأ المواجهة مع 12 حجرًا داكنًا في مواجهة 12 حجرًا فاتحًا فوق 32 مربعًا داكنًا، ليصبح المجموع 24 قطعة تتنافس على الرقعة^[3].

رحلة الثمانية عشر عامًا: كيف برهن تشينوك على التعادل؟

إن الفضاء الاحتمالي للعبة الداما يفوق بكثير ما توحي به بساطة قواعدها الظاهرة. فعلى رقعة 8×8 القياسية، يبلغ عدد الوضعيات القانونية الممكنة ما يقرب من 5 × 10^20 وضعية^[1]. وهذا الرقم الهائل يوازي نصف تريليون مليار تشكيلة. ولو فحص حاسوب عادي هذه الوضعيات وضعية تلو أخرى بصورة تسلسلية، لاستغرقت الحسابات آلاف السنين.

ولتجاوز هذه العقبة الفلكية، قسم الباحثون المعضلة إلى مسارين متكاملين: الحساب العكسي انطلاقًا من النهايات، والبحث المتقدم انطلاقًا من الافتتاحية.

التحليل التراجعي وقاعدة بيانات تضم 39 تريليون وضعية

شكلت قواعد بيانات نهايات الأدوار الأساس المتين للبرهان. فبدلًا من البدء من النقلة الأولى والغرق في متاهات التفريعات، بدأ العلماء من نقطة النهاية الحتمية حين لا يتبقى على الرقعة سوى عدد ضئيل من القطع. فالوضعية التي تضم ملكًا داكنًا ضد ملك فاتح وحيد تعد وضعية بديهية تنتهي بتعادل فوري، بينما وضعية تضم ملكين يحاصران حجرًا وحيدًا في زاوية تعد فوزًا مضمونًا.

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

وفي المدة الممتدة من عام 1989 إلى عام 2007، انتهى الفريق من حوسبة جداول النهايات الكاملة لجميع الوضعيات التي تحتوي على 10 قطع أو أقل^[1]. تشتمل هذه القاعدة الضخمة على 39 تريليون وضعية فريدة. وبمجرد وصول الدور إلى 10 قطع أو أقل، يتوقف تشينوك عن التفكير والحساب، ويقرأ القرار الحتمي مباشرة من ذاكرة النظام.

بناء الجسر الواصل بين الافتتاح وقواعد النهايات

بعد اكتمال قاعدة العشر قطع، تمثلت المهمة المتبقية في تشييد جسر حسابي يربط التشكيلة الابتدائية المكونة من 24 قطعة بتلك القاعدة المحسومة^[1].

وظف الباحثون خوارزميات البحث بأرقام الإثبات المدمجة مع تقنيات تقليم ألفا-بيتا. عملت الخوارزمية على تتبع المسارات الرئيسية مع إعطاء الأولوية للتضحيات الإجبارية والتبسيطات المؤدية لقواعد النهايات، مع استبعاد التفريعات الضعيفة التي يثبت بطلانها سريعًا.

وعلى مدار سنوات من العمل المتوازي عبر مئات المعالجات المترابطة، استُبعدت مليارات التفريعات الثانوية لتشييد شجرة إثبات موثقة تضم عشرات الملايين من الوضعيات الحاسمة. قاد كل فرع رئيسي من الافتتاح إما إلى حصن دفاعي منيع أو اتصل مباشرة بوضعية تعادل من قاعدة البيانات المكونة من 39 تريليون تشكيلة. وفي عام 2007، اكتمل البرهان التاريخي: الداما تنتهي رياضيًا بالتعادل^[1].

ماريون تينسلي: العبقرية البشرية في مواجهة الآلة

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

تتجاوز مسيرة تينسلي حدود التصديق المألوف؛ فطوال مسيرة امتدت 45 عامًا في بطولات النخبة العالمية، لم يتلقَّ تينسلي سوى 9 هزائم فقط من بين آلاف المباريات الرسمية التي خاضها^[1]. تربع على عرش بطولة العالم عقودًا متواصلة، ولم يتخلَّ عن لقبه إلا برغبته حين فتر حماسه للمنافسة. ولاختبار قدرات تشينوك أمام الذروة القصوى للعقل البشري، نسق جوناثان شيفر مباراة رسمية على بطولة العالم في عام 1992 ضد تينسلي.

كان نزال عام 1992 مواجهة ملحمية بين الحدس الإنساني والحساب الآلي الصارم. وخلال 39 مباراة مجهدة، أظهر تينسلي براعة استراتيجية استثنائية وهزم تشينوك بنتيجة 4 انتصارات مقابل هزيمتين و33 تعادلًا^[1]. وكانت تلك المرة الأولى في التاريخ التي ينافس فيها برنامج حاسوبي على لقب عالمي رسمي ضد بطل عالم بشري متوج في لعبة كلاسيكية.

وفي عام 1994، أقيمت مباراة الإياب المنتظرة بشغف. وبعد 6 تعادلات متتالية، اضطر تينسلي للانسحاب بسبب مرض مفاجئ ألم به، ثم وافته المنية في عام 1995^[1]. ونال تشينوك لقب بطل العالم في مواجهات الإنسان والآلة. وأظهرت التحليلات اللاحقة لمباريات تينسلي تطابقًا شبه تام بين نقلاته وبين القرارات المثالية لقواعد بيانات النهايات، ما برهن على قدرة العقل البشري على استيعاب الهندسة العميقة للعبة بالحدس المجرد.

سلم التعقيد الحسابي: من كوناكت فور إلى الشطرنج

لإدراك حجم الإنجاز الذي تحقق في الداما، يجدر بنا مقارنتها بدرجات التعقيد الرياضي في الألعاب اللوحية الشهيرة.

في عام 1950، حلل عالم الرياضيات كلود شانون التعقيد الحسابي للعبة الشطرنج في ورقته التأسيسية الشهيرة حول برمجة الحواسيب^[4]. قدّر شانون عدد الوضعيات القانونية في الشطرنج بنحو 10^44 وضعية، وعدد الأدوار المحتملة بما لا يقل عن 10^120 دورًا، وهو المقياس المعروف اليوم برقم شانون^[4].

لنقارن مراتب هذه الألعاب الشهيرة:

• كوناكت فور: حُلت حلًا قويًا في عام 1988^[2]. تحتوي على تريليونات الوضعيات ويمكن لأي حاسوب محمول معاصر حلها في ثوانٍ معدودة.
• الداما الإنجليزية 8×8: حُلت حلًا ضعيفًا في عام 2007 مع فضاء يقارب 5 × 10^20 وضعية^[1]. تطلب حلها 18 عامًا من المعالجة الموزعة وبناء قاعدة بيانات لنهايات الأدوار تضم 39 تريليون وضعية.
• الشطرنج: غير محلول تمامًا. فمع وجود 10^44 وضعية و10^120 مسارًا متفرعًا^[4]، يتجاوز الشطرنج بكثير أقصى إمكانات المعالجة الشاملة. وتغطي قواعد نهايات الشطرنج حاليًا الوضعيات حتى 7 قطع فقط؛ وسيتطلب الانتقال إلى 8 قطع مساحات تخزين عملاقة، بينما يبقى حل اللعبة الكاملة المكونة من 32 قطعة مستحيلًا على الحواسيب التقليدية.
• الداما الدولية 10×10: غير محلولة. تُلعب على مئة مربع مع عشرين حجرًا لكل جانب، ويصل فضاء حالاتها التقديري إلى 10^30 وضعية. وتؤدي حركة الترقية الحرة وقاعدة الأغلبية الإجبارية في الأكل إلى تضخيم شجرة الاحتمالات بما يستعصي على الحوسبة التراجعية.

لماذا لا يقضي الحل الرياضي على متعة اللعبة؟

حين تصدر إعلان عام 2007 عناوين الأخبار، سارع بعض المعلقين إلى الادعاء بأن لعبة الداما قد انتهت ومات بريقها. فما الجدوى من الجلوس أمام الرقعة إذا كان الحاسوب قد أثبت أن النهاية المحتومة هي التعادل؟

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

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

وفي المباريات التنافسية، تحسم 3 عناصر أساسية مسار النزال:

1. دقة الافتتاح. مع أن المسار المثالي يؤدي للتعادل، إلا أن الافتتاحيات تعج بالأفخاخ التكتيكية العميقة. وقد يؤدي الانحراف بنقلة واحدة في البداية إلى انهيار الموقف برمته خلال نقلتين.
2. المناورة التموضعية. تتطلب السيطرة على مربعات الوسط، وحماية صف الترقية الخلفي، وبناء الهياكل الدفاعية وعيًا استراتيجيًا راقيًا. ويتمكن اللاعب الذي يستوعب أصول استراتيجية الداما من فرض تفوقه بانتظام على الهواة.
3. إتقان نهايات الأدوار. عند تكافؤ عدد القطع، يحدد قانون المعارضة مصير الجولة. وقد تؤدي هفوة صغيرة إلى تبديد فوز مضمون أو السماح للخصم بالفرار إلى حصن تعادل، كما نوضح بالتفصيل في دليلنا حول نهايات الداما.

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

أبعاد المنافسة الإنسانية على الرقعة

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

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

أسئلة شائعة حول حل لعبة الداما

هل الداما محلولة لجميع الأخطاء والتفرعات الممكنة؟

كلا، حُلت الداما الإنجليزية حلًا ضعيفًا وليس قويًا. يضمن الإثبات استراتيجية مثالية للتعادل انطلاقًا من الوضعية الابتدائية التي تضم 24 قطعة موزعة على 32 مربعًا داكنًا^[1]. كما حُسمت كل الوضعيات المشتملة على 10 قطع أو أقل عبر قاعدة بيانات تضم 39 تريليون وضعية. لكن التفرعات العشوائية بعد أخطاء كارثية فادحة لم تُفهرس بالكامل.

هل يستطيع لاعب بشري التغلب على تشينوك اليوم؟

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

هل تمتلك القطع الداكنة أفضلية في الداما الإنجليزية؟

في الداما الإنجليزية، تنطلق النقلة الأولى بالقطع الداكنة. ورغم أن أسبقية التحرك تمنح المبادرة للضغط على المربعات المركزية، إلا أن برهان شيفر أكد أن هذه الأسبقية لا تكفي لفرض الفوز أمام الدفاع السليم^[1]. ومع اللعب المثالي من الجانبين، تتلاشى المبادرة تدريجيًا ويستقر الدور عند نقطة التعادل المنصفة.

المصادر

1. Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P., & Sutphen, S. (2007). Checkers Is Solved. Science, 317(5844), 1518–1522.
2. Allis, L. V. (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. thesis, University of Limburg, Maastricht.
3. Boardgammon. “Checkers Rules: How to Play, Movement, and Captures.”
4. Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine, Ser. 7, 41(314), 256–275.
5. Boardgammon. “Checkers Crown: Play Online Checkers and Regional Draughts Variants.”
6. Boardgammon. “Play Checkers Online: Free Browser and Mobile Draughts.”
7. Boardgammon. “Checkers Variants: The Kinds of Draughts Played Around the World.”

وجدتَ خطأً أو عبارة ركيكة؟ راسلنا