چرا سوپر ماریو از نظر ریاضی پیچیدهتر از اکثر الگوریتمها است
اگرچه ممکن است شبیه یک بازی پلتفرمر ساده درباره لولهکشای باشد که در حال نجات یک پرنسس است، اما سوپر ماریو در واقع دروازهای به سوی عمیقترین اسرار علوم کامپیوتر نظری است. تحقیقات جدید از MIT نشان میدهد که پیکربندیهای خاصی از این بازی از نظر ریاضی «تصمیمناپذیر» (undecidable) هستند، که آنها را در کلاس پیچیدگی بسیار فراتر از مسائل محاسباتی استاندارد قرار میدهد.
از PSPACE تا RE-Complete: جهشی عظیم در پیچیدگی
سالها بود که اجماع میان پژوهشگران، از جمله پروفسور اریک دیمین از MIT، بر این بود که سوپر ماریو به کلاس پیچیدگی PSPACE تعلق دارد. این کلاس شامل مسائلی است که قابل حل هستند، اما با افزایش اندازه ورودی، به مقدار غیرقابلکنترلی از حافظه و زمان نیاز دارند. اگرچه مسائل PSPACE دشوار هستند، اما همچنان اساساً توسط یک کامپیوتر با منابع کافی «قابل حل» محسوب میشوند.
با این حال، کار اخیر تیمی از دانشجویان — Hayashi Ani، Holden Hall، Ricardo Ruiz و Naveen Venkat — این فرض را در هم شکسته است. پژوهشگران با استفاده از ویرایشگرهای مرحله و بازی Super Mario Maker، مراحل خاصی را ساختند که RE-Complete هستند. این بدان معناست که بازی وارد قلمرو مسائل تصمیمناپذیر شده است. در این سناریوهای خاص، از نظر ریاضی غیرممکن است که بتوان برنامهای کامپیوتری نوشت که بتواند همیشه به درستی پیشبینی کند که آیا ماریو میتواند با موفقیت به میله پرچم یا قلعه برسد یا خیر.
ارتباط با مسئله توقف (Halting Problem)
برای درک اینکه چرا یک بازی ویدئویی میتواند تصمیمناپذیر باشد، باید به آلن تورینگ و مسئله توقف (Halting Problem) بازگشت. تورینگ ثابت کرد که هیچ الگوریتم جهانی وجود ندارد که بتواند تعیین کند آیا یک برنامه داده شده در نهایت متوقف میشود یا تا ابد اجرا خواهد شد.
تیم تحقیقاتی MIT این منطق را از طریق تکنیکی به نام کاهش (reduction) در قلمرو «مشروم کینگدم» (Mushroom Kingdom) به کار گرفتند. پژوهشگران با تجزیه یک مرحله از سوپر ماریو به اجزای محلی موسوم به «گجتها» (gadgets)، توانستند منطق محاسباتی پیچیدهای را در مکانیسمهای بازی شبیهسازی کنند. این گجتها مانند گیتهای منطقی عمل میکنند؛ وقتی در الگوهای خاصی از لولهها، سکوها و دشمنانی مانند Goombas یا Spinies چیده میشوند، میتوانند رفتار یک ماشین تورینگ را بازسازی کنند. در نتیجه، تعیین اینکه آیا ماریو به انتهای مرحله میرسد یا خیر، از نظر عملکردی با تعیین اینکه آیا یک برنامه پیچیده هرگز متوقف میشود یا نه، یکسان میشود.
چرا این موضوع برای آینده هوش مصنوعی و محاسبات اهمیت دارد
این کشف صرفاً یک واقعیت جالب برای گیمرها نیست؛ بلکه یادآور عمیقی از محدودیتهای بنیادی محاسبات است. همانطور که ما مرزهای هوش مصنوعی و استدلال خودکار را جابهجا میکنیم، باید تشخیص دهیم که برخی ساختارهای منطقی ذاتاً فراتر از دسترس هر الگوریتمی هستند، فارغ از اینکه چه مقدار قدرت پردازش یا حافظه در دسترس باشد.
گروه Hardness MIT با اثبات اینکه یک محیط بهظاهر ساده میتواند میزبان مسائل تصمیمناپذیر باشد، نشان میدهد که چگونه نظریه پیچیدگی میتواند در سیستمهای تعاملی و مبتنی بر قانون اعمال شود. این موضوع پیامدهایی برای نحوه طراحی نرمافزارهای پیچیده، تأیید سیستمهای خودکار و درک مرزهای آنچه در یک دنیای بهشدت الگوریتمی میتواند «محاسبه» شود، دارد.
نکات کلیدی
- تصمیمناپذیری: برخی از مراحل سوپر ماریو اکنون در دسته RE-Complete طبقهبندی میشوند، به این معنی که هیچ الگوریتمی نمیتواند هرگز به طور کامل پیشبینی کند که آیا یک بازیکن میتواند آنها را تمام کند یا خیر.
- تغییر سطح پیچیدگی: این بازی از کلاس PSPACE که «قابل حل اما دشوار» است، به قلمرو مسائل تصمیمناپذیر منتقل شده است که بازتابی از مسئله توقف است.
- گجتهای محاسباتی: پژوهشگران از مکانیسمهای بازی (لولهها، دشمنان و سکوها) به عنوان «گجت» برای ساخت گیتهای منطقی پیچیدهای استفاده کردند که محاسبات جهانی را شبیهسازی میکنند.