কেন সুপার মারিও বেশিরভাগ অ্যালগরিদমের চেয়ে গাণিতিকভাবে বেশি জটিল
যদিও এটি একজন প্লাম্বার কর্তৃক রাজকন্যাকে উদ্ধার করার একটি সাধারণ প্ল্যাটফর্মার গেম বলে মনে হতে পারে, সুপার মারিও আসলে তাত্ত্বিক কম্পিউটার বিজ্ঞানের গভীরতম রহস্যগুলোর একটি প্রবেশদ্বার। এমআইটি (MIT)-র নতুন গবেষণা প্রকাশ করেছে যে গেমটির কিছু নির্দিষ্ট কনফিগারেশন গাণিতিকভাবে অনির্ণেয় (undecidable), যা তাদের সাধারণ কম্পিউটেশনাল সমস্যার তুলনায় অনেক উচ্চতর একটি জটিলতা শ্রেণীতে (complexity class) নিয়ে যায়।
PSPACE থেকে RE-Complete: জটিলতার এক বিশাল উল্লম্ফন
বছরের পর বছর ধরে, এমআইটি অধ্যাপক এরিক ডেমেইনেসহ গবেষকদের মধ্যে একটি ঐক্যমত ছিল যে, সুপার মারিও PSPACE জটিলতা শ্রেণীর অন্তর্ভুক্ত। এই শ্রেণীর অন্তর্ভুক্ত সমস্যাগুলো সমাধানযোগ্য, তবে ইনপুট সাইজ বাড়ার সাথে সাথে এগুলো সমাধান করতে অবাস্তব পরিমাণ মেমরি এবং সময়ের প্রয়োজন হয়। যদিও PSPACE সমস্যাগুলো কঠিন, তবুও পর্যাপ্ত রিসোর্স থাকলে কম্পিউটার দিয়ে এগুলো মৌলিকভাবে "সমাধান করা" সম্ভব।
তবে, শিক্ষার্থী দল—হায়াশী আনি, হোল্ডেন হল, রিকার্ডো রুইজ এবং নাভীন ভেঙ্কট-এর সাম্প্রতিক কাজ এই ধারণাটিকে ভেঙে দিয়েছে। লেভেল এডিটর এবং Super Mario Maker ব্যবহার করে গবেষকরা এমন কিছু নির্দিষ্ট লেভেল তৈরি করেছেন যা RE-Complete। এর মানে হলো গেমটি এখন undecidable problems বা অনির্ণেয় সমস্যার জগতে প্রবেশ করেছে। এই নির্দিষ্ট পরিস্থিতিগুলোতে, এমন একটি কম্পিউটার প্রোগ্রাম লেখা গাণিতিকভাবে অসম্ভব যা সবসময় সঠিকভাবে বলতে পারবে মারিও সফলভাবে ফ্ল্যাগপোল বা দুর্গে পৌঁছাতে পারবে কি না।
Halting Problem-এর সাথে সংযোগ
একটি ভিডিও গেম কেন অনির্ণেয় হতে পারে তা বুঝতে হলে অ্যালান টিউরিং এবং Halting Problem-এর দিকে তাকাতে হবে। টিউরিং প্রমাণ করেছিলেন যে এমন কোনো সার্বজনীন অ্যালগরিদম নেই যা নির্ধারণ করতে পারে যে কোনো নির্দিষ্ট প্রোগ্রাম শেষ পর্যন্ত থেমে যাবে নাকি চিরকাল চলতে থাকবে।
এমআইটি গবেষণা দলটি reduction নামক একটি কৌশলের মাধ্যমে এই যুক্তিটি মাশরুম কিংডমে (Mushroom Kingdom) প্রয়োগ করেছে। সুপার মারিও লেভেলগুলোকে "gadgets" নামে পরিচিত কিছু স্থানীয় উপাদানে বিভক্ত করার মাধ্যমে গবেষকরা গেমের মেকানিক্সের মধ্যে জটিল কম্পিউটেশনাল লজিক সিমুলেট করতে সক্ষম হয়েছেন। এই গ্যাজেটগুলো লজিক গেট হিসেবে কাজ করে; পাইপ, প্ল্যাটফর্ম এবং গোম্বা (Goombas) বা স্পিনিস (Spinies)-এর মতো শত্রুদের নির্দিষ্ট প্যাটার্নে সাজালে সেগুলো একটি টিউরিং মেশিনের আচরণকে প্রতিফলিত করতে পারে। ফলস্বরূপ, মারিও লেভেলের শেষে পৌঁছাতে পারবে কি না তা নির্ধারণ করা একটি জটিল প্রোগ্রাম কখনো থামবে কি না তা নির্ধারণ করার মতোই কার্যকরীভাবে অভিন্ন হয়ে দাঁড়ায়।
কৃত্রিম বুদ্ধিমত্তা (AI) এবং কম্পিউটিং-এর ভবিষ্যতের জন্য এটি কেন গুরুত্বপূর্ণ
এই আবিষ্কারটি গেমারদের জন্য কেবল একটি মজার তথ্য নয়; এটি কম্পিউটেশনের মৌলিক সীমাবদ্ধতার একটি গভীর অনুস্মারক। আমরা যখন কৃত্রিম বুদ্ধিমত্তা (AI) এবং স্বয়ংক্রিয় যুক্তির (automated reasoning) সীমানা প্রসারিত করছি, তখন আমাদের অবশ্যই স্বীকার করতে হবে যে কিছু নির্দিষ্ট লজিক্যাল কাঠামো সহজাতভাবেই যেকোনো অ্যালগরিদমের নাগালের বাইরে, তা প্রসেসিং পাওয়ার বা মেমরি যতই বেশি থাকুক না কেন।
একটি আপাতদৃষ্টিতে সহজ পরিবেশ যে অনির্ণেয় সমস্যা ধারণ করতে পারে তা প্রমাণ করার মাধ্যমে, এমআইটি হার্ডনেস গ্রুপ (MIT Hardness Group) দেখিয়ে দিয়েছে যে কীভাবে জটিলতা তত্ত্বকে (complexity theory) ইন্টারেক্টিভ এবং নিয়ম-ভিত্তিক সিস্টেমের ক্ষেত্রে প্রয়োগ করা যেতে পারে। এটি আমরা কীভাবে জটিল সফটওয়্যার ডিজাইন করি, স্বয়ংক্রিয় সিস্টেম যাচাই করি এবং ক্রমবর্ধমান অ্যালগরিদমিক বিশ্বে কী কী "গণনা" করা সম্ভব তার সীমানা বুঝতে সাহায্য করবে।
মূল বিষয়সমূহ
- Undecidability (অনির্ণেয়তা): সুপার মারিও-র কিছু লেভেল এখন RE-Complete হিসেবে শ্রেণীবদ্ধ করা হয়েছে, যার অর্থ কোনো অ্যালগরিদমই নিখুঁতভাবে বলতে পারবে না একজন খেলোয়াড় সেগুলো শেষ করতে পারবে কি না।
- Complexity Shift (জটিলতার পরিবর্তন): গেমটি "সমাধানযোগ্য কিন্তু কঠিন" PSPACE শ্রেণী থেকে অনির্ণেয়তার জগতে চলে গেছে, যা Halting Problem-এর প্রতিফলন।
- Computational Gadgets: গবেষকরা গেমের মেকানিক্স (পাইপ, শত্রু এবং প্ল্যাটফর্ম) ব্যবহার করেছেন "gadgets" হিসেবে, যা সার্বজনীন কম্পিউটেশন সিমুলেট করার জন্য জটিল লজিক গেট তৈরি করতে সক্ষম।