بازی کندی کراش پیچیده‌تر از آن است که فکر می‌کنید
اگر در مرحله مشخصی از بازی محبوب کندی کراش ساگا شکست خوردید، احساس ناامیدی نکنید؛ زیرا کامپیوترها نیز با این بازی دچار مشکل هستند.
آیا تا به حال ساعت‌ها مشغول بازی کندی کراش ساگا شده‌اید؟ شما تنها نیستید. این بازی از زمان انتشارش در سال ۲۰۱۲ به یکی از محبوب‌ترین بازی‌ها در فیسبوک و دستگاه‌های موبایل تبدیل شد. اپلیکیشن این بازی در نیمه‌ی اول سال ۲۰۲۳ بیش از ۱۰۶ میلیون بار دانلود شد و به‌این‌ترتیب عنوان دومین بازی پردانلود دنیا را در این دوره از آن خود کرد (بازی Subway Surfors در رتبه اول قرار دارد).
بازی کندی‌کراش اصل ساده‌ای دارد: در شبکه‌ای که با آب‌نبات‌های رنگی متنوع پوشیده شده است، باید زنجیره‌های افقی یا عمودی از حداقل سه آب‌نبات یکسان را بسازید. با شکل‌گیری چنین زنجیره‌ای آب‌نبات‌ها ناپدید می‌شوند و آب‌نبات‌های بالای آن‌ها حرکت می‌کند. مرحله‌های مختلف بازی، اهداف متفاوتی دارند. برای مثال یکی از اهداف می‌تواند شکل دادن به حداقل تعداد زنجیره‌ها با حداکثر تعداد جابه‌جایی‌ها باشد. از طرفی کندی‌کراش به دلیل سادگی به محبوبیت بالایی رسیده است. از طرفی به دلیل پتانسیل اعتیادآورش همیشه هدف انتقادها قرار داشته است. البته این جنبه‌ی اعتیادآور فقط به بازیکنان معمولی ختم نمی‌شود.
برای ریاضی‌دان‌ها نگاه کردن به کندی‌کراش به عنوان یک مسئله‌ی ریاضی هم می‌تواند اعتیادآور باشد. توبی والش، دانشمند کامپیوتر دانشگاه نیوساوث ولز استرالیا، در سال ۲۰۱۴ به دلیل وجود باگ در بازی کندی‌کراش شکست خورد، اما برخلاف دیگر هواداران بازی صرفا تلاش نکرد تا در آن به مهارت برسد. بلکه می‌خواست پیچیدگی کندی‌کراش را از دیدگاه ریاضی بررسی کند. به بیان دیگر، اگر عدد ماکزیمم یا حداکثری از جابه‌جایی‌های آب‌نباتی به کامپیوتر داده شود، شکل دادن به تعداد مشخصی از زنجیره‌های سه‌تایی تا چه حد برای دستگاه دشوار است؟
پیچیدگی کندی‌کراش
دانشمندان کامپیوتر برای مرتب‌سازی وظایف ریاضی بر اساس سطوح مختلف دشواری، مفهوم کلاس‌های پیچیدگی را معرفی کردند. برای مثال در برخی مسائل ریاضی مشخص نیست کامپیوتر اصلا می‌تواند به پاسخی برسد یا خیر و ممکن است تا ابد بدون رسیدن به یک پاسخ مشخص به کار ادامه دهد. این مسئله‌ها، سخت‌ترین از نوع خود هستند. برای مثال بازی کارتی Magic: The Gathering، موقعیت‌هایی رخ می‌دهند که امکان تصمیم‌گیری برای تعیین برنده‌ی بازی حتی در شرایط بهینه وجود ندارد.
برای تعیین پیچیدگی بازی، باید بتوانید راه‌حل پیشنهادی را به سرعت بررسی کنید. برای مثال اگر یک پازل پیچیده‌ی سودوکو به شما داده شود، باید بدون تلاش زیادی تشخیص دهید راه‌حل درست است یا خیر. اگر زمان محاسبات کامپیوتری برای بررسی راه‌حل به صورت چندجمله‌ای با افزایش اندازه‌ی عملیات بالا برود، مسئله به دسته‌ی NP (مسئله چندجمله‌ای غیرقطعی) تعلق می‌گیرد. این شرایط برای کندی‌کراش هم صدق می‌کند: با ردیابی جابه‌جایی‌های متعددی که زنجیره‌های آب‌نباتی را قدم به قدم ایجاد می‌کنند، می‌توان تشخیص داد که نتیجه‌ی نمایش یافته (تعداد زنجیره‌های آب‌نباتی که از بین رفته‌اند) درست است.
در بازی کندی‌کراش، آب‌نبات‌ها در صورت تشکیل زنجیره‌های سه‌تایی یکسان ناپدید می‌شوند
از سویی، صرفا قرار گرفتن یک مسئله در گروه NP چیزی درباره‌ی سختی یا آسانی رسیدن به راه‌حل نمی‌گوید. دلیل این مسئله این است که مسائل ساده در دسته‌ی زمان چندجمله‌ای (P) می‌توانند در گروه NP هم قرار بگیرند. برای مسائل P، زمان محاسباتی کامپیوتر تنها به صورت چندجمله‌ای و متناسب با اندازه‌ی مسئله رشد می‌کند. در نگاه اول این تعریف به NP شباهت دارد با این‌حال یک تفاوت اساسی این است که درباره‌ی زبان محاسبه‌ی لازم برای حل یک وظیفه صحبت می‌کنیم نه زمان لازم برای بررسی راه‌حل؛ بنابراین مسائل دسته‌ی P را می‌توان به شکل بهینه‌ای حل و بررسی کرد.
به‌عنوان‌مثال برای مسئلههای ساده‌ای مثل مرتب‌سازی یک فهرست، در بدترین سناریو، زمان محاسباتی بر اساس مربع اندازه‌ی فهرست رشد می‌کند. درنتیجه اگر تعداد عنصرها دو برابر شود باید چهار برابر بیشتر برای مرتب‌سازی لیست صبر کنیم. شاید این زمان به نظر زیاد برسد، اما از دید کامپیوتر چندان هم زیاد نیست؛ بنابراین عملیاتی که در گروه P قرار دارند، آسان ارزیابی می‌شوند چرا که معمولا بدون تلاش محاسباتی زیادی حل می‌شوند.
پیدا کردن راه‌حل برای برخی مسئلههای ریاضی می‌تواند تا ابد ادامه داشته باشد
در مقابل، مسئلههای دشواری در گروه NP قرار دارند که زمان محاسباتی لازم برای حل آن‌ها به صورت نمایی و متناسب با اندازه‌ی مسئله رشد می‌کند. برای مثال والش روی کامپیوتر دسکتاپ خود برنامه‌ای دارد که برای یافتن مسیریابی بهینه برای ۱۰ کامیون و نمایش راه‌حل به چند ساعت زمان نیاز دارد، اما همان برنامه برای ۱۰۰ کامیون می‌تواند به اندازه‌ی طول عمر کیهان، زمان نیاز داشته باشد. مسیریابی بهینه یکی از نمونه‌های اصلی مسائل ان‌پی سخت است.
بر اساس چنین تعریف‌هایی، بدیهی است که برای ارزیابی پیچیدگی یک بازی باید به دنبال تعمیم‌هایی از آن رفت. علاوه بر این، اندازه‌ی بازی‌هایی مثل شطرنج، Go و حتی کندی کراش بر اساس زمین بازی تعریف میشود. در چنین نمونه‌هایی، دانشمندان کامپیوتر نظری به تعمیم‌های خیالی از بازی‌ها می‌پردازند که در آن تخته و تعداد مهره‌ها و سنگ‌ها یا حتی شکلات‌ها به شکل قابل توجهی بزرگ هستند.
کندی کراش چگونه به عبارت‌های منطقی مربوط میشود؟
والش این پرسش را مطرح می‌کند که کندی کراش متعلق به کدام دسته از پیچیدگی است. آیا کامپیوتر همیشه می‌تواند بدون تلاش زیاد، استراتژی بهینه‌ای را برای حل این بازی پیدا کند؟ در این صورت آیا کندی‌کراش در دسته‌ی P قرار دارد یا آیا کامپیوتر با یافتن آب‌نبات‌های مناسب برای جابه‌جایی دست‌وپنجه نرم می‌کند؟ والش این پرسش را با استفاده از علم رایج کامپیوتر موسوم به «تنزل» آزمایش کرد. برای اثبات این فرضیه که مسئله‌ی کندی کراش از نوع NP سخت است، باید نشان داد تمام مسائل دیگر در گروه NP را می‌توان به آن تقلیل داد. به‌طوری‌که مسئله‌ی A از نوع NP سخت است، اگر الگوریتم راه‌حل A بتواند دیگر مسئلههای NP را هم حل کند.
والش، راهکاری برای حل این مسئله داشت. برای مثال، مجموعه‌ی کاملی از مسئلههای معروف در گروه NP و NP سخت قرار دارند. اگر بتوان نشان داد که یکی از آن‌ها مشابه کندی کراش است، به‌طوری‌که بتوان نگاشت آن‌ها را اجرا کرد، می‌توان ثابت کرد که این بازی محبوب از دیدگاه ریاضی پیچیده است. والش از مسئله‌ی 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 باشد، می‌توان از باقی‌مانده‌ی آب‌نبات‌های روی صفحه حدس زد که عبارت 3-SAT درست یا غلط است. برای مثال اگر مربع در سطر سوم و ستون دوم حاوی یک آب‌نبات لیمویی زرد پس از تمام جابه‌جایی‌ها باشد، متناظر با عبارت «درست» است. والش آب‌نبات زمین بازی را به گونه‌ای توزیع کرد که آب‌نبات لیمویی زرد تنها در صورتی روی زمین بازی قرار بگیرد که حداقل تعداد سه زنجیره‌ی آب‌نباتی شکل گرفته باشند.
به این ترتیب والش توانست در مارس ۲۰۱۴ ثابت کند که کندی‌کراش از نوع NP سخت است و می‌توان گفت پیچیدگی بالایی از دیدگاه ریاضی دارد. این پیچیدگی می‌تواند اطمینان دهد که بالاخره در مرحله‌ای از کندی‌کراش شکست می‌خورید با این‌حال همان‌گونه که والش می‌گوید، این بازی جذابیت‌هایی دارد: «این ویژگی می‌تواند بخشی از خاصیت اعتیادآور بازی کندی‌کراش باشد، اگر حل آن راحت بود، به این اندازه جذاب نمی‌شد.»