پیچیدگی محاسباتی و نظریه بازی‌ها: چرا حل کامل شطرنج و تخته‌نرد از توان ابررایانه‌ها فراتر است؟
در علوم کامپیوتر و هوش مصنوعی، بازی‌های فکری دو نفره با اطلاعات کامل (Complete Information Games) همواره استاندارد طلایی برای ارزیابی الگوریتم‌های تصمیم‌گیری و جستجوی خصمانه بوده‌اند. از نظر تئوری، بر اساس قضیه مشهور ارنست زرملو (Zermelo's Theorem) در سال ۱۹۱۳، هر بازی متناهی دو نفره بدون عامل شانس، دارای یک ارزش بازی قطعی است؛ یعنی یا سفید دارای استراتژی برد قطعی است، یا سیاه، و یا هر دو می‌توانند بازی را به تساوی بکشانند. اما چرا با وجود گذشت بیش از یک قرن و ظهور قدرتمندترین ابررایانه‌های کوانتومی و خوشه‌های پردازش موازی، بازی‌هایی چون شطرنج و تخته‌نرد هرگز به صورت تحلیلی و کامل حل نشده‌اند؟
۱. تمایز میان بازی‌های حل‌شده و حل‌نشده
بازی‌ها از نظر وضعیت محاسباتی به سه دسته تقسیم می‌شوند:
- حل ضعیف (Ultra-weakly Solved): مشخص بودن نتیجه بازی از وضعیت آغازین (برد یا مساوی) بدون ارائه درخت کامل حرکات.
- حل شده (Weakly Solved): ارائه استراتژی عملی که از وضعیت آغازین، برد یا مساوی را برای یکی از طرفین در برابر هر حرکت حریف تضمین کند (مانند حل بازی دوز در زمان‌های باستان و حل بازی کانکت فور در سال ۱۹۸۸ توسط ویکتور آلیس).
- حل قوی (Strongly Solved): ارائه الگوریتمی که برای تمام وضعیت‌های ممکن و قانونی تخته، بهترین حرکت بهینه را با کمترین مسافت تا برد مشخص کند. بزرگ‌ترین بازی تخته‌ای حل شده تا امروز، بازی چکرز انگلیسی (۸×۸) است که در سال ۲۰۰۷ توسط پروفسور جاناتان شفر پس از ۱۸ سال محاسبات مداوم اثبات شد که با بازی بی‌نقص دو طرف به تساوی می‌انجامد.
۲. عدد شانون و انفجار ترکیبیاتی در شطرنج
کلود شانون، پدر نظریه اطلاعات، در سال ۱۹۵۰ تعداد بازی‌های ممکن و منحصر به فرد در شطرنج را تخمین زد که به عدد شانون (Shannon Number) مشهور شد و برابر با حدود ۱۰^۱۲۰ بازی است. همچنین تعداد وضعیت‌های معتبر تخته شطرنج حدود ۱۰^۴۳ برآورد می‌شود.
برای درک عظمت این عدد، کافی است یادآوری کنیم که کل اتم‌های موجود در جهان قابل مشاهده حدود ۱۰^۸۰ تخمین زده می‌شود. بنابراین، هیچ حافظه فیزیکی و هیچ سیستم ذخیره‌سازی داده‌ای در جهان هستی نمی‌تواند درخت کامل بازی شطرنج را ذخیره یا تحلیل پس‌رو (Backward Induction) کند.
۳. چالش نودهای شانس (Chance Nodes) در تخته‌نرد
در تخته‌نرد، اگرچه هندسه تخته متناهی است (۱۵ مهره در برابر ۱۵ مهره در ۲۴ خانه)، اما ورود تاس باعث دگرگونی ماهیت درخت بازی از مینی‌ماکس کلاسیک به اکسپکتی‌مینی‌ماکس (Expectiminimax) می‌شود.
در هر دور، ۳۶ حالت پرتاب دو تاس وجود دارد که به ۲۱ برآمد متمایز تجزیه می‌شوند. در نتیجه، در هر نیم‌حرکت (Ply)، فاکتور انشعاب بازی در عدد ۲۱ ضرب می‌شود:
فاکتور انشعاب مؤثر ≈ تعداد انتخاب‌های مجاز حرکت مهره × ۲۱
حتی یک نگاه دو دوری رو به جلو (۲-ply lookahead)، نیازمند بررسی صدها هزار وضعیت است. علاوه بر این، مکعب دو برابر کننده (Doubling Cube) پویایی مالی و گزینه‌های تصمیم‌گیری استاپ-لاس (Stop-loss) و کال آپشن (Call Option) را وارد اکوئیتی بازی می‌کند که باعث می‌شود هرس آلفا-بتا به سادگی در نودهای تصادفی کار نکند.
۴. راه‌حل علوم کامپیوتر: تلفیق جدول‌های پایان بازی با شبکه‌های عصبی
چون حل سراسری از نقطه آغاز تا پایان به علت انفجار ترکیبیاتی غیرممکن است، معماری موتورهای مدرن بازی‌های فکری بر دو پایه مهندسی استوار شده است:
- پایگاه‌های داده پس‌رو پایان بازی (Endgame Tablebases): مانند جدول‌های ۷ مهره‌ای نالیموف و سیزگی در شطرنج (شامل ۴۲۳ میلیارد وضعیت)، که تمام وضعیت‌های با ۷ مهره یا کمتر را به صورت بازگشتی از آخر به اول حل کرده و ارزش دقیق ریاضی هر وضعیت را ثبت کرده‌اند.
- شبکه‌های عصبی ارزشیاب (Neural Evaluation Functions): جایگزینی جستجوی کور با شبکه‌های یادگیری تقویتی عمیق (Deep Reinforcement Learning) و ارزیابی موضعی (NNUE)، که با شبیه‌سازی میلیون‌ها بازی خود-آموز (Self-play) یا رول‌اوت‌های مونت کارلو، برآورد آماری دقیقی از شانس برد تولید می‌کنند.
نتیجه‌گیری
عدم امکان حل کامل بازی‌هایی نظیر شطرنج و تخته‌نرد به معنای نقص رایانه‌ها نیست، بلکه نشان‌دهنده زیبایی ریاضیاتی و شکوه عمق ترکیبیاتی این بازی‌هاست. بازی‌هایی که قوانین مینیمال و ساده آن‌ها، فضایی از بی‌نهایت انتخاب خلق می‌کند که تا ابد ذهن انسان و توان هوش مصنوعی را به چالش خواهد کشید.