هذه هي أعقد لعبة في العالم، رسمياً!

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

وفي هذه اللعبة التي يشارك فيها شخصان على الأقل، يقوم كل لاعب بتجميع مجموعة مؤلفة من 60 بطاقة تحمل قوى وقدرات مختلفة، ويختارون هذه المجموعات من بين حوالي 20,000 بطاقة صُممت بالتدريج مع تطور اللعبة. وعلى الرغم من أن هذه اللعبة مماثلة لألعاب أخرى تعتمد أيضاً على تقمص الأدوار، مثل "دانجنز أند دراجونز Dungeons and Dragons"، إلا أنها أكثر تعقيداً وتتضمن عدداً أكبر من البطاقات مقارنة بغيرها من ألعاب البطاقات.

وهو ما قد يدفعنا للتساؤل: من بين جميع ألعاب العالم الحقيقي (التي يلعبها أشخاص حقيقيون بدلاً من الألعاب الافتراضية التي تكون مجرد موضع دراسات نظرية)، أين تقع لعبة ماجيك من حيث التعقيد؟

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

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

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

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

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

في هذه الحالة، فإن تحديد ما إذا كان العددان أوليين بالنسبة لبعضهما يمكن التوصل إليه بعدد خطوات يتناسب طرداً مع تابع كثير الحدود لأعداد الدخل. فإذا كان الدخل x، فإن الحد الأكبر في تابع كثير الحدود هو من الشكل C.x^n (C مضروباً بـ x بعد رفعه للقوة n)، حيث C وn ثابتان. وهو ما يقع في فئة تسمى P التي ترمز للزمن المتعلق بكثير الحدود polynomial.

ومن ناحية أخرى، فإن مسألة الشطرنج يجب أن تحل بطريقة القوة القاسية، ويزداد عدد الخطوات المطلوبة لهذا طرداً مع التابع الأسي للدخل. فإذا كان الدخل x، فإن الحد الأكبر في كثير الحدود هو من الشكل C.n^x، حيث C وn ثابتان. ومع زيادة x، يصبح هذا الحد أكبر بشكل أسرع بكثير من C.x^n، وبالتالي فهو يقع ضمن فئة أكبر للتعقيد تسمى EXP، أو الزمن الأُسِّي exponential.

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

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

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

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

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

إذن فإن النتيجة الأساسية التي توصل إليها تشرتشل وزملاؤه هي إثبات أنه لا يمكن حساب نتيجة لعبة ماجيك، ويقولون: "هذه النتيجة الأولى التي تبين وجود لعبة حقيقية لا يمكن تحديد الإستراتيجية الفائزة فيها".

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

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

مرجع: arxiv.org/abs/1904.09828:
ماجيك: ذا غاذرينج عامة حسابياً