بازی MTG به‌عنوان پیچیده‌ترین بازی جهان معرفی شد
«سحر و جادو: گردهمایی» (Magic: The Gathering) بازی کارتی آنلاین است که در آن، جادوگران با استفاده از اوراد و اشیاء جادویی و احضار موجودات از دنیاهای موازی، برای شکست‌دادن دشمنانشان تلاش می‌کنند. در این بازی، هر بازیکن ۶۰ کارت را که هر دام از قدرت متفاوتی برخوردار است، روی عرشه مرتب می‌کند. آن‌ها کارت‌های خود را از میان مجموعه‌ای شامل ۲۰ هزار کارت مختلف که طی روند بازی ایجاد می‌شوند، انتخاب می‌کنند. این بازی تا اندازه‌ای شبیه بازی‌های فانتزی مانند Dungeons و Dragons است؛ اما کارت‌های بسیار بیشتر و قوانین به‌شدت پیچیده‌تری درمقایسه‌با سایر بازی‌های کارتی دارند.
سؤال جالبی که در اینجا مطرح می‌شود، این است: در میان بازی‌های دنیای واقعی، یعنی آن دسته از بازی‌هایی که افراد واقعا مشغول بازی هستند، نه بازی‌های فرضی که معمولا مدنظر نظریه‌پردازان است، این بازی آنلاین ازنظر پیچیدگی چه جایگاهی دارد؟
بازی MTG ازنظر محاسباتی پیچیده‌ترین نمونه‌ی دنیای واقعی در تاریخ بازی‌های آنلاین است
امروزه به‌لطف بررسی‌های الکس چرچیل، پژوهشگر مستقل و طراح بازی فکری (بورد گیم) از کمبریج انگلستان و استلا بایدرمن، از مؤسسه فناوری جورجیا و آستین هریک از دانشگاه پنسیلوانیا، پاسخ این پرسش پیدا شده است. آن‌ها پیچیدگی محاسباتی اولین اجرای بازی را اندازه‌گیری کردند و برای این کار، آن را طوری کدنویسی کردند که با کامپیوتر یا ماشین تورینگ اجراکردنی باشد. آن‌ها می‌گویند:
این پژوهش ثابت کرد بازی MTG ازنظر محاسباتی پیچیده‌ترین نمونه دنیای واقعی در تاریخ بازی آنلاین است.
بهتر است ابتدا برخی از نکات مهم درباره‌ی پیچیدگی یک بازی فکری توضیح داده شود. اول اینکه، یکی از کارهای مهم در علوم کامپیوتر تعیین امکان حل مسئله است. به‌عنوان مثال، تصمیم‌گیری درمورد اینکه آیا دو عدد نسبت به هم اول هستند یا خیر (به‌عبارتی، بزرگ‌ترین مقسوم علیه مشترک دو عدد برابر با «یک» یا به‌عبارتی هیچ مقسوم‌علیه مشترکی به جز «یک» نداشته باشد)، کاری است که طی چند مرحله‌ی محدود و ازپیش‌تعریف‌شده شدنی است؛ بنابراین، این کار محاسبه‌شدنی است.
در مسابقات معمولی شطرنج، اینکه آیا مهره‌های سفید استراتژی برنده دارند، هم محاسبه‌شدنی است. این فرایند شامل آزمایش همه‌ی توالی‌های مختلف حرکت مهره‌ها است تا ببینند آیا مهره‌های سفید می‌توانند برنده شوند یا خیر. بااین‌حال، نکته‌ی مهم در این است که اگرچه هر دو این مثال‌ها محاسبه‌شدنی هستند، منابعی که برای حل آن‌ها لازم است، از تنوع زیادی برخوردار هستند. اینجا است که مفهوم پیچیدگی محاسباتی مطرح می‌شود. این اصطلاح نوعی رتبه‌بندی مبتنی‌بر منابع موردنیاز برای حل مشکلات است. تصمیم‌گیری درباره‌ی این موضوع که «آیا دو عدد نسبت به هم اول هستند» را می‌توان طی مراحی متناسب با یک تابع چندجمله‌ای متشکل از اعداد ورودی حل کرد. اگر ورودی این تابع را x در نظر بگیریم، مهم‌ترین جمله در یک تابع چندجمله‌ای به شکل Cxn نوشته خواهد شد که در آن، C و n اعدادی ثابت هستند. این جمله در کلاسی می‌گنجد که به‌عنوان P شناخته می‌شود و P در آن، نشان‌دهنده‌ی زمان چندجمله‌ای‌ها است.
درمقابل، مسئله‌ی شطرنج را باید با الگوریتم جستجوی فراگیر حل کرد که طی آن، تعداد مراحل لازم‌الاجرا باتوجه‌به تابع نمایی ورودی افزایش می‌یابد. اگر ورودی برابر با x باشد، مهم‌ترین جمله در این تابع نمایی به‌صورت Cnx نوشته می‌شود که در آن، C و n اعداد ثابت هستند. همچنین، با بیشترشدن مقدار x این جمله خیلی سریع‌تر از Cxn رشد می‌کند. بنابراین، آن در کلاسی با پیچیدگی بیشتر قرار می‌گیرد که به‌نام EXP یا زمان نمایی شناخته می‌شود. از این گذشته، دسته‌های مختلف دیگری هم ازلحاظ شدت پیچیدگی‌های حل مسئله وجود دارد و حتی مسائلی هستند که هیچ الگوریتمی برای حل آن‌ها وجود ندارد. این مسائل را «محاسبه‌ناشدنی» می‌نامند.
بررسی این موضوع که هرکدام از بازی‌ها ازلحاظ پیچیدگی در کدام دسته‌بندی قرار می‌گیرند، کار پرزحمتی است. بیشتر بازی‌های دنیای واقعی محدودیت‌های معینی براساس پیچیدگی‌های خود دارند؛ مانند اندازه‌ی یک بورد گیم. همین عامل باعث می‌شود بسیاری از آن‌ها از دیدگاه پیچیدگی بی‌اهمیت تلقی شوند. چرچیل و همکارانش معتقد هستند:
بیشتر پژوهش‌هایی که در حوزه‌ی نظریه‌ی بازی الگوریتمی در باز‌های جهان واقعی انجام می‌شوند، عمدتا به مسئله‌ی عمومی‌سازی بازی‌هایی می‌پردازند که زیاد بازی می‌شوند، نه بازی‌هایی که در دنیای واقعی روی می‌دهند.
تعیین نتیجه‌ی بازی MTG، پس از یک دور بازی، محاسبه‌شدنی نیست
بنابراین، تنها چند نمونه از بازی‌های دنیای واقعی وجود دارند که از پیچیدگی خوبی بهره می‌برند. این‌ها عبارت‌اند از: Dots-and-Boxes و Jenga و Tetris. چرچیل و همکارانش می‌گویند:
بر این باوریم که هیچ بازی دنیای واقعی وجود ندارد که پیچیده‌تر از چندجمله‌ای‌های غیرقطعی (Non Deterministic Polynomial) قبلی باشند.
کار جدید نشان می‌دهد بازی MTG، بازی آنلاین بسیار پیچیده‌ای است. روش پژوهشی استفاده‌شده در این کار، روشی ساده و مستقیم است. پژوهشگران ابتدا شروع به ترجمه و تبدیل قدرت و ویژگی‌های هر کارت کردند و آن را به‌شکل مجموعه‌ای از مراحلی درآوردند که قابلیت رمزنگاری‌شدن را داشته باشند. سپس، دو بازیکن شروع به بازی کردند تا ماشین تورینگ نحوه‌ی بازی آن را یاد بگیرد و سرانجام، ثابت کردند احتمال تعیین اینکه آیا کدام‌یک از بازیکن‌ها از استراتژی برد استفاده می‌کنند، با مسئله‌ی توقف معروف (Halting Problem) در علوم کامپیوتر برابر است.
مسئله‌ی توقف در علوم کامپیوتر به این شرح است که آیا اجرای برنامه‌ای کامپیوتری با ورودی خاص، بالاخره در جایی به‌پایان می‌رسد یا اینکه همیشه ادامه می‌یابد. در سال ۱۹۳۶، آلن تورینگ ثابت کرد هیچ الگوریتمی نمی‌تواند به این سؤال پاسخ بدهد. به‌عبارت‌دیگر، این مسئله حل‌نشدنی است. بنابراین، نتیجه‌ی مهمی که چرچیل و همکارانش به‌دست آوردند، آن است که تعیین نتیجه‌ی بازی MTG پس از یک‌بار بازی محاسبه‌ناشدنی است:
این اولین‌بار است که ثابت می‌شود تعیین استراتژی برد در یک بازی دنیای واقعی محاسبه‌شدنی نیست.
این پژوهش جالب سؤالات اصولی مهمی را درباره‌ی نظریه‌ی بازی مطرح می‌کند. به‌عنوان مثال، چرچیل و همکارانش می‌گویند در نظریه‌ی پیشرو رسمی درباره‌ی بازی‌ها، فرض بر این است که هر بازی باید محاسبه‌شدنی باشد و به‌عقیده‌ی آن‌ها، بازی MTG اصلا برای فرضیات مطرح‌شده‌ی دانشمندان علوم کامپیوتر مناسب نیست؛ بلکه بیشتر با مدل‌سازی بازی‌ها سازگاری دارد. این، یعنی دانشمندان کامپیوتر باید ایده‌هاشان درباره‌ی بازی‌ها را بازنگری کنند؛ به‌ویژه اگر همچنان امیدوار هستند که نظریه‌ی محاسباتی یکپارچه‌ای برای بازی‌ها تولید کنند.