لماذا تُعد لعبة سوبر ماريو أكثر تعقيداً من الناحية الرياضية من معظم الخوارزميات

بينما قد تبدو مجرد لعبة منصات بسيطة تدور حول سباك ينقذ أميرة، إلا أن سوper Mario هي في الواقع بوابة لأعمق أسرار علوم الحاسوب النظرية. كشف بحث جديد من معهد ماساتشوستس للتكنولوجيا (MIT) أن بعض تكوينات اللعبة غير قابلة للتقرير رياضياً (undecidable)، مما يضعها في فئة تعقيد تتجاوز بكثير المشكلات الحسابية القياسية.

من PSPACE إلى RE-Complete: قفزة هائلة في التعقيد

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

ومع ذلك، فإن العمل الأخير الذي قام به فريق من الطلاب — Hayashi Ani، وHolden Hall، وRicardo Ruiz، وNaveen Venkat — قد حطم هذا الافتراض. فمن خلال استخدام محررات المستويات ولعبة Super Mario Maker، قام الباحثون ببناء مستويات محددة تُصنف على أنها RE-Complete. وهذا يعني أن اللعبة قد دخلت مجال المشكلات غير القابلة للتقرير. في هذه السيناريوهات المحددة، من المستحيل رياضياً كتابة برنامج حاسوبي يمكنه دائماً التنبؤ بدقة بما إذا كان ماريو سيتمكن من الوصول بنجاح إلى سارية العلم أو القلعة.

الصلة بـ "مشكلة التوقف" (Halting Problem)

لفهم سبب كون لعبة فيديو غير قابلة للتقرير، يجب العودة إلى آلان تورينج ومشكلة التوقف (Halting Problem). فقد أثبت تورينج أنه لا توجد خوارزمية عالمية يمكنها تحديد ما إذا كان أي برنامج معين سيتوقف في النهاية أم سيستمر في العمل إلى الأبد.

طبق فريق بحث MIT هذا المنطق على "مملكة الفطر" (Mushroom Kingdom) من خلال تقنية تسمى الاختزال (reduction). ومن خلال تقسيم مستوى في Super Mario إلى مكونات محلية تُعرف باسم "الأدوات" (gadgets)، تمكن الباحثون من محاكاة منطق حسابي معقد داخل ميكانيكا اللعبة. تعمل هذه الأدوات كبوابات منطقية؛ فعند ترتيبها في أنماط محددة من الأنابيب والمنصات والأعداء مثل Goombas أو Spinies، يمكنها محاكاة سلوك آلة تورينج. وبناءً على ذلك، يصبح تحديد ما إذا كان ماريو سيصل إلى نهاية المستوى متطابقاً وظيفياً مع تحديد ما إذا كان برنامج معقد سيتوقف يوماً ما.

لماذا يهم هذا مستقبل الذكاء الاصطناعي والحوسبة

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

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

النقاط الرئيسية

• عدم القابلية للتقرير: تُصنف مستويات معينة في Super Mario الآن على أنها RE-Complete، مما يعني أنه لا توجد خوارزمية يمكنها أبداً التنبؤ بدقة بما إذا كان اللاعب يستطيع إنهاءها.
• تحول التعقيد: انتقلت اللعبة من فئة PSPACE "القابلة للحل ولكن الصعبة" إلى مجال المشكلات غير القابلة للتقرير، مما يعكس مشكلة التوقف.
• الأدوات الحسابية: استخدم الباحثون ميكانيكا اللعبة (الأنابيب والأعداء والمنصات) كـ "أدوات" (gadgets) لبناء بوابات منطقية معقدة تحاكي الحوسبة الشاملة.