اگر در یک مرحله خاص از بازی محبوب “کندی کراش ساگا” باختید، ناامید نشوید؛ زیرا کامپیوترها نیز ممکن است در این بازی مشکلاتی داشته باشند.
آیا تا به حال ساعت‌ها بازی “کندی کراش ساگا” کرده‌اید؟ شما در این تجربه تنها نیستید. این بازی که از سال ۲۰۱۲ به یکی از محبوب‌ترین بازی‌ها در فیسبوک و دستگاه‌های موبایل تبدیل شده، به تازگی در نیمه‌ی اول سال ۲۰۲۳ بیش از ۱۰۶ میلیون بار دانلود شد. این بازی به عنوان دومین بازی پردانلود دنیا در این دوره محسوب می‌شود (بازی Subway Surfors در رتبه اول قرار دارد).
در این بازی، شما با شبکه‌ای پر از آب‌نبات‌های رنگی متنوع روبرو می‌شوید و می‌بایست زنجیره‌های افقی یا عمودی حاوی حداقل سه آب‌نبات یکسان بسازید. با ساختن چنین زنجیره‌هایی، آب‌نبات‌ها از بازی حذف می‌شوند و آب‌نبات‌های بالاتر از آن‌ها حرکت می‌کنند. هر مرحله اهداف متفاوتی دارد؛ برخی از این اهداف ممکن است شامل کاهش حداکثر تعداد زنجیره‌ها با حداکثر جابه‌جایی‌ها باشد. کندی کراش به دلیل سادگی گیم‌پلی‌اش محبوبیت زیادی دارد، اما به دلیل اعتیادآور بودنش همیشه هدف انتقادات بوده است. این جذابیت اعتیادآور این بازی تنها مختص بازیکنان عادی نیست و برای ریاضی‌دان‌ها نیز می‌تواند جذاب باشد. به عنوان مثال، توبی والش، یک دانشمند کامپیوتر در دانشگاه نیوساوت ولز در استرالیا، در سال ۲۰۱۴ تصمیم گرفت با استفاده از این بازی وجود یک باگ در آن را از نگاه ریاضی بررسی کند. او نه فقط به دنبال مهارت در بازی نبود، بلکه می‌خواست پیچیدگی بازی کندی کراش را از نظر ریاضی مورد بررسی قرار دهد. به عبارت دیگر، اگر ما تعداد حداکثر جابه‌جایی‌های آب‌نباتی را به کامپیوتر بدهیم، تا چه حد ممکن است تعداد زنجیره‌های سه‌تایی را در این شرایط به حداقل برساند؟
پیچیدگی کندی‌کراش
دانشمندان کامپیوتر نوعی ترتیب‌بندی برای مسائل ریاضی در مختلف سطوح دشواری به نام کلاس‌های پیچیدگی معرفی کردند. برای مثال، در بعضی مسائل ریاضی، مشخص نیست آیا کامپیوتر قادر به پیدا کردن پاسخ است یا خیر، و ممکن است بدون رسیدن به یک پاسخ مشخص باید ادامه کار کند. این نوع مسائل، دشوارترین نوع مسائل محسوب می‌شوند. به عنوان مثال، در بازی کارتی Magic: The Gathering، مواقعی پیش می‌آید که حتی در شرایط بهینه، تصمیم‌گیری برای تعیین برنده‌ی بازی ممکن نیست.
برای ارزیابی پیچیدگی یک بازی، لازم است که بتوانید راه‌حل پیشنهادی را به سرعت بررسی کنید. به عنوان مثال، اگر یک پازل پیچیده‌ی سودوکو به شما داده شود، باید بدون زحمت زیادی بتوانید تشخیص دهید که راه‌حل پیشنهادی درست است یا خیر. اگر زمان محاسبات کامپیوتری برای بررسی راه‌حل به طور چندجمله‌ای با افزایش اندازه‌ی عملیات به شدت افزایش یابد، مسئله به دسته‌ی NP (مسئله چندجمله‌ای غیرقطعی) تعلق می‌گیرد. این شرایط برای بازی کندی‌کراش هم درست است: با ردیابی جابه‌جایی‌های متعددی که زنجیره‌های آب‌نباتی را قدم به قدم ایجاد می‌کنند، می‌توان تشخیص داد که نتیجه‌ی نشان داده شده (تعداد زنجیره‌های آب‌نباتی که حذف شده‌اند) صحیح است یا خیر.
در بازی کندی‌کراش، آب‌نبات‌ها در صورت تشکیل زنجیره‌های سه‌تایی یکسان ناپدید می‌شوند
از یک طرف، فقط قرار دادن یک مسئله در دسته NP چیزی درباره سختی یا آسانی رسیدن به راه‌حل نمی‌گوید. دلیل این امر این است که مسائل ساده در دسته زمان چندجمله‌ای (P) ممکن است در دسته NP هم قرار بگیرند. در مورد مسائل P، زمان محاسباتی کامپیوتر تنها به صورت چندجمله‌ای و متناسب با اندازه مسئله رشد می‌کند. در نگاه اول، این تعریف به نظر می‌رسد مشابه NP باشد، اما تفاوت اصلی در اینجاست: در اینجا درباره‌ی زبان محاسباتی لازم برای حل یک وظیفه صحبت می‌شود نه زمان لازم برای بررسی راه‌حل. بنابراین، مسائل دسته P به بهینه‌ترین شکل ممکن حل و بررسی می‌شوند.
برای مثال، در مواردی که مرتب‌سازی یک لیست را در نظر می‌گیریم، در حالت بدترین، زمان محاسباتی بر اساس مربع تعداد عناصر فهرست رشد می‌کند. به عبارت دیگر، اگر تعداد عناصر دو برابر شود، باید چهار برابر بیشتر برای مرتب‌سازی لیست صبر کنیم. این زمان ممکن است به نظر برسد زیاد، اما از دید کامپیوتر چندان چیزی نیست؛ بنابراین، عملیاتی که در دسته P قرار دارند، به راحتی قابل ارزیابی هستند زیرا معمولاً بدون زحمت محاسباتی زیادی حل می‌شوند.
در مقابل، مسائل دشواری در دسته NP قرار دارند و زمان محاسباتی برای حل آن‌ها به صورت نمایی و متناسب با اندازه مسئله رشد می‌کند. به عنوان مثال، یک برنامه رایانه‌ای که برای یافتن مسیر بهینه برای ۱۰ کامیون نیاز به چند ساعت دارد، ممکن است برای ۱۰۰ کامیون به مدت زمانی معادل عمر کیهان نیاز داشته باشد. یافتن مسیر بهینه یکی از نمونه‌های اصلی مسائل NP دشوار است.
بر اساس این تعریف‌ها، بدیهی است که برای ارزیابی پیچیدگی یک بازی، باید به تعمیم‌هایی از آن پرداخت. علاوه بر این، اندازه بازی‌هایی مانند شطرنج، Go و حتی کندی کراش بر اساس ابعاد تخته و تعداد مهره‌ها، سنگ‌ها یا حتی شکلات‌ها تعریف می‌شود. در چنین مواردی، دانشمندان کامپیوتر به تعمیم‌های خیالی از بازی‌ها پرداخته‌اند که در آن تخته، تعداد مهره‌ها و سنگ‌ها یا حتی شکلات‌ها به صورت قابل توجهی بزرگ هستند.
کندی کراش چگونه به عبارت‌های منطقی مربوط می‌شود؟
والش پرسش می‌کند که آیا کندی کراش به کدام دسته از پیچیدگی تعلق دارد؟ آیا کامپیوتر همیشه می‌تواند بدون تلاش زیاد، استراتژی بهینه‌ای را برای حل این بازی پیدا کند؟ در واقع، این پرسش به این معناست که آیا کندی‌کراش در دسته‌ی P قرار دارد و کامپیوتر می‌تواند با یافتن آب‌نبات‌های مناسب برای جابه‌جایی، به آسانی این بازی را حل کند؟ والش این پرسش را با استفاده از یک مفهوم مرسوم در علم کامپیوتر به نام “تنزل” بررسی کرد. برای اثبات این فرضیه که مسئله‌ی کندی کراش از نوع NP سخت است، باید نشان داد که تمام مسائل دیگر در دسته NP را می‌توان به آن تقلیل داد. به عبارت دیگر، اگر یک مسئله با نام A از نوع NP سخت باشد، و الگوریتمی وجود داشته باشد که بتواند مسئله A را حل کند، آنگاه می‌توان نشان داد که کندی کراش نیز از همین دسته پیچیدگی است. برای این منظور، والش از یک مسئله‌ی مشهور در دسته NP سخت به نام 3-SAT برای بررسی کندی‌کراش استفاده کرد.
عملیات 3-SAT در منطق، بررسی می‌کند که آیا یک مجموعه از سری‌های مرتبط یا الحاقی از عبارت‌های منطقی درست هستند یا منجر به تناقض می‌شوند. یک نمونه از این الحاقی عبارت این است: “x ∧ ¬x”. در نگاه اول، این عبارت ممکن است پیچیده به نظر برسد، اما با دانستن معنی ∧ و ¬ (نماد سلب) می‌توان به راحتی آن را تفسیر کرد. بنابراین، این عبارت می‌تواند به این صورت تفسیر شود: “x و در عین حال ¬x”. این عملیات به معنای تخصیص مقدار “درست” یا “غلط” به متغیر x است، به‌طوری‌که عبارت کلی درست باشد (یعنی به تناقض نیافتد).
در مثال ذکر شده، این نتیجه غیر ممکن است زیرا در صورتی که x درست باشد (x=true)، به دو عبارت “درست” و “در عین حال غلط” منجر می‌شود و در صورتی که x=false باشد، به دو عبارت “غلط” و “غلط در عین حال” می‌انجامد. هیچ‌کدام از این عبارات معنایی ندارند؛ زیرا یک چیز نمی‌تواند همزمان درست و غلط باشد. بنابراین، الحاق عبارات درستی ندارند.
مسئله‌های 3-SAT شامل عبارات زنجیره‌ای هستند که هرکدام به صورت مستقیم سه متغیر را به شکل “(a1 ∨ b1 ∨ c1) ∧ (a2 ∨ b2 ∨ c2) ∧ … ∧ (an ∨ bn ∨ cn)” به یکدیگر وصل می‌کنند. در اینجا “V” نمایانگر “یا” است. کامپیوتر باید سعی کند تا مقادیر درستی به متغیرها اختصاص دهد به‌طوری‌که عبارت کلی، درست باشد. همان‌طور که پیداست، این عملیات از نوع NP سخت است و با افزایش طول عملیات، زمان محاسباتی نمایی افزایش می‌یابد.
والش در مرحله‌ی بعد نشان داد که هر مسئله‌ی 3-SAT را می‌توان در کندی‌کراش نمایش داد و حل کندی‌کراش به صورت خودکار به حل مسئله‌ی مرتبط 3-SAT می‌انجامد. او برای رسیدن به این هدف، آرایش‌های آب‌نباتی بازی کندی‌کراش را با متغیرها و اتصال‌های منطقی در مسئله‌ی 3-SAT تطبیق داد به گونه‌ای که یک الگوی مشخصی از آب‌نبات‌ها نمایشگر یک متغیر باشد. این کار توسط والش انجام شد تا نشان دهد که هر عبارت منطقی می‌تواند با توزیع مناسبی از آب‌نبات‌ها در کندی‌کراش نمایش داده شود.
در این روش، وقتی بازیکن یک جابه‌جایی مشخصی انجام می‌دهد، والش آن را به معنای تخصیص یک مقدار درست به یک متغیر تفسیر می‌کند. به‌عنوان مثال، اگر متغیر ۱ اشتباه باشد، هر جابه‌جایی می‌تواند زمین بازی را تغییر دهد. همچنین، او می‌تواند زنجیره‌ای با سه آب‌نبات ایجاد کند که به‌صورت آنی ناپدید می‌شوند و به دیگر آب‌نبات‌ها اجازه می‌دهد از صفحه پائین بروند.
در صورتی که تعداد جابه‌جایی‌ها متناظر با متغیرهای مسئله‌ی 3-SAT باشد، می‌توان از باقی‌مانده‌ی آب‌نبات‌های روی صفحه حدس زد که عبارت 3-SAT مورد نظر، درست یا غلط است. به‌عنوان مثال، اگر مربع در سطر سوم و ستون دوم حاوی یک آب‌نبات لیمویی زرد پس از تمام جابه‌جایی‌ها باشد، این معادل با عبارت “درست” است. والش آب‌نبات‌ها را در زمین بازی به گونه‌ای توزیع می‌کند که آب‌نبات لیمویی زرد تنها در صورتی روی زمین بازی قرار بگیرد که حداقل سه زنجیره‌ی آب‌نباتی شکل گرفته باشند.
با این روش، والش توانست در مارس ۲۰۱۴ نشان دهد که کندی‌کراش از نوع NP سخت است و این نشان می‌دهد که این بازی از دیدگاه ریاضی دارای پیچیدگی بالایی است. این پیچیدگی می‌تواند تضمین کند که در نهایت در مرحله‌ای از کندی‌کراش شکست می‌خورید، با این‌حال همان‌گونه که والش می‌گوید، این ویژگی ممکن است جزء خصوصیاتی باشد که این بازی را جذاب می‌کن
نظرات کاربران