آیا بازی چکرز حل شده است؟ چگونه ۱۸ سال محاسبات رایانه‌ای تساوی حتمی را اثبات کرد و این موضوع چه پیامی برای بازیکنان دارد

برای قرن‌های متمادی، اندیشمندان و دوستداران بازی‌های تخته‌ای همواره این پرسش بنیادین را پیش روی خود می‌دیدند: آیا سرنوشت نهایی یک نبرد فکری از همان لحظه نخست از نظر ریاضی تعیین شده است؟ هنگامی که دو استاد برجسته پشت صفحه‌ای متشکل از شصت و چهار خانه می‌نشینند و هیچ‌کدام حتی یک خطای کوچک مرتکب نمی‌شوند، آیا بازیکنی که بازی را آغاز می‌کند برتری قطعی دارد؟ آیا بازیکن دوم زیر بار شکستی ناگزیر قرار دارد؟ یا اینکه بازی در صورت اجرای دقیق‌ترین تصمیم‌ها، در تعادلی مطلق و تساوی کامل به پایان می‌رسد؟

در تابستان سال ۲۰۰۷ میلادی، مقاله‌ای بنیادین در نشریه معتبر Science پاسخی قطعی و مستند به این پرسش دیرینه داد^[1]. گروهی از پژوهشگران برجسته به سرپرستی دانشمند نامدار علوم رایانه، جاناتان شیفر از دانشگاه آلبرتا در کانادا، اعلام کردند که بازی چکرز انگلیسی (که در زبان انگلیسی با نام checkers یا draughts شناخته می‌شود) رسماً و از نظر ریاضی حل شده است. برنامه رایانه‌ای آن‌ها به نام چینوک (Chinook)، پس از پروژه‌ای فراگیر که ۱۸ سال به طول انجامید و در سال ۱۹۸۹ کلید خورده بود، حقیقتی قاطع را اثبات کرد: در صورتی که هر دو بازیکن از نخستین حرکت تا پایان بازی بی‌نقص بازی کنند، بازی سنتی چکرز ناگزیر با نتیجه مساوی خاتمه می‌یابد.

با این حال، این دستاورد علمی هرگز به معنای نابودی هیجان رقابت بر سر صفحه بازی نبود. برای درک اینکه چرا حل ریاضی بازی مانع از لذت بردن علاقه‌مندان نمی‌شود، باید نخست دید نظریه بازی‌ها چه تعریفی برای مفهوم حل شدن ارائه می‌دهد.

سطوح سه‌گانه حل بازی‌ها در نظریه بازی‌ها

در گفت‌وگوهای روزمره، زمانی که می‌گوییم معمایی حل شد، منظورمان پیدا کردن راه‌حلی ساده است که گره معما را می‌گشاید. اما در ریاضیات ترکیبیاتی و هوش مصنوعی، این واژه بر تعریفی بسیار دقیق و نظام‌مند استوار است که ویکتور آلیس در سال ۱۹۹۴ فرمول‌بندی کرد^[2]. آلیس راه‌حل‌های مربوط به بازی‌های با اطلاعات کامل را به ۳ سطح متمایز طبقه‌بندی نمود:

1. حل فوق‌ضعیف (Ultra-weakly solved). برهان ریاضی به روشنی مشخص می‌کند که از وضعیت آغازین، بازیکن اول برنده می‌شود، بازیکن دوم پیروز است یا بازی مساوی خواهد شد؛ اما هیچ‌گونه الگوریتم مشخص یا توالی عملی حرکات برای رسیدن به آن نتیجه به دست نمی‌دهد. بازی هگز نمونه بارز این رده است، چرا که نظریه بازی‌ها با استدلال دزدی استراتژی اثبات می‌کند بازیکن اول برد دارد، بی‌آنکه حرکات برنده را روی صفحه‌های بزرگ نشان دهد.
2. حل ضعیف (Weakly solved). یک الگوریتم محاسباتی یا درخت اثبات معتبر راهبردی کامل ارائه می‌دهد که از وضعیت آغازین صفحه، دست‌کم تساوی یا برد را در برابر هر حرکت احتمالی حریف تضمین می‌کند. برنامه شاید ارزش دقیق وضعیت‌های نامتعارفی را که پس از زنجیره‌ای از اشتباهات عجیب رخ می‌دهند در حافظه نداشته باشد، اما از نقطه شروع بازی هرگز شکست نمی‌خورد. چکرز دقیقاً در این رده قرار می‌گیرد^[1].
3. حل قوی (Strongly solved). الگوریتم برای تک‌تک وضعیت‌های قانونی ممکن بر روی صفحه، فارغ از خطاهای گذشته، ارزش ریاضی دقیق و حرکت بهینه را مشخص می‌سازد. بازی چهار در یک خط در سال ۱۹۸۸ میلادی به شکل قوی حل شد: بازیکن نخست با حرکت در ستون میانی برد قطعی را به دست می‌آورد^[2].

بازی چکرز به شکل ضعیف حل شد، چرا که ذخیره‌سازی داده‌های مربوط به تمامی وضعیت‌های نامعقول و غیرمنطقی نیازمند فضایی ورای توان سخت‌افزارهای جهان بود. تیم شیفر محاسبات خود را بر اثبات نتیجه نهایی حاصل از وضعیت رسمی آغازین متمرکز کردند. بازی با ۱۲ مهره تیره در برابر ۱۲ مهره روشن بر روی ۳۲ خانه تیره آغاز می‌شود که در مجموع ۲۴ مهره را در بر می‌گیرد^[3].

۱۸ سال پردازش computational: چینوک چگونه چکرز را رمزگشایی کرد؟

فضای جست‌وجو و احتمالات در چکرز بی‌نهایت فراتر از سادگی ظاهری قوانین آن است. روی یک صفحه استاندارد ۸×۸، شمار وضعیت‌های قانونی مجاز به حدود ۵ × ۱۰^۲۰ وضعیت می‌رسد^[1]. این عدد خیره‌کننده معادل پانصد میلیارد میلیارد چینش گوناگون است. اگر یک رایانه معمولی می‌خواست این وضعیت‌ها را به شکل پیاپی بررسی کند، این فرآیند هزاران سال طول می‌کشید.

دانشمندان برای رویارویی با این چالش، پژوهش خود را به دو مسیر موازی تقسیم کردند: تحلیل معکوس از پایان بازی به سمت گذشته، و جست‌وجوی روبه‌جلو از وضعیت شروع به سمت آینده.

تحلیل معکوس و پایگاه داده ۳۹ تریلیون وضعیتی

سنگ بنای اصلی این اثبات علمی، ساخت پایگاه‌های داده پایان بازی بود. پژوهشگران به جای سردرگم شدن در شاخه‌های بی‌پایان گشایش، کار را از نقطه پایانی بازی، یعنی زمانی که تنها چند مهره روی صفحه باقی مانده است، آغاز کردند. وضعیتی با یک شاه تیره در برابر یک شاه روشن آشکارا مساوی است؛ در حالی که دو شاه در برابر یک مهره تنها در گوشه صفحه به بردی قطعی ختم می‌شوند.

نرم‌افزار چینوک با افزودن تدریجی مهره‌ها به صفحه‌های خالی، ارزش قطعی هر ساختار را سنجید. هرگاه حرکتی به یک وضعیت برنده پیشین منتهی می‌شد، وضعیت مبدأ نیز به‌عنوان برد علامت‌گذاری می‌شد. چنانچه تمام پاسخ‌های قانونی به شکست می‌انجامید، موقعیت باخته محسوب می‌شد؛ و در صورتی که بازی دقیق توازن را حفظ می‌کرد، تساوی ثبت می‌گردید.

در بازه زمانی میان سال‌های ۱۹۸۹ تا ۲۰۰۷ میلادی، جداول پایان بازی برای تمامی وضعیت‌های دارای ۱۰ مهره یا کمتر به پایان رسید^[1]. این پایگاه عظیم داده شامل ۳۹ تریلیون وضعیت گوناگون است. به محض آنکه تعداد مهره‌های روی صفحه به ۱۰ مهره یا کمتر کاهش یابد، چینوک دیگر به محاسبه نیازی ندارد؛ بلکه حقیقت را مستقیماً از حافظه فراخوانی می‌کند.

پل ارتباطی از گشایش تا جداول پایان بازی

پس از اتمام پایگاه ۱۰ مهره‌ای، وظیفه نهایی ساخت پلی استوار بود که وضعیت اولیه ۲۴ مهره‌ای را به آستانه این ۱۰ مهره پیوند دهد^[1].

پژوهشگران برای این مقصود الگوریتم‌های پیشرفته جست‌وجو با شماره‌های اثبات را با روش کلاسیک هرس آلفا-بتا ترکیب کردند. الگوریتم شاخه‌هایی را دنبال می‌کرد که به تعویض‌های اجباری و ساده‌سازی به سمت جداول پایانی می‌انجامیدند، در حالی که مسیرهای فرعی نامناسب را به سرعت کنار می‌گذاشت.

این محاسبات سال‌ها به صورت موازی بر روی صدها سرور پیشرفته انجام گرفت. میلیاردها شاخه غیرضروری حذف شدند تا درختی معتبر از ده‌ها میلیون موقعیت کلیدی بنا شود. هر شاخه اصلی از گشایش یا به یک دژ دفاعی تسخیرناپذیر می‌رسید یا مستقیماً به پایگاه داده ۳۹ تریلیون وضعیتی متصل می‌شد. در سال ۲۰۰۷ میلادی اثبات نهایی کامل شد: چکرز از نظر ریاضی مساوی است^[1].

انسان در برابر رایانه: ماریون تینسلی و نبوغ بی‌پایان

دهه‌ها پیش از آنکه ماشین‌ها با تکیه بر سرعت پردازنده‌ها این راز را برملا کنند، یک انسان با تکیه بر درک شهودی و هوش سرشار به این قله از کمال نزدیک شده بود. دکتر ماریون تینسلی، استاد ریاضیات اهل فلوریدا، بی‌گمان بزرگ‌ترین بازیکن تاریخ چکرز به شمار می‌رود.

کارنامه رقابتی تینسلی شبیه به یک افسانه است. در طول ۴۵ سال حضور فعال در مسابقات رسمی و حرفه‌ای، تینسلی در میان هزاران بازی تنها ۹ بار شکست خورد^[1]. او دهه‌ها عنوان قهرمانی جهان را در اختیار داشت و تنها زمانی عنوان خود را کنار می‌گذاشت که انگیزه رقابتی‌اش فروکش می‌کرد. برای آزمودن چینوک در برابر حد نهایی هوش انسانی، جاناتان شیفر در سال ۱۹۹۲ میلادی مسابقه‌ای رسمی برای قهرمانی جهان با تینسلی ترتیب داد.

رویارویی سال ۱۹۹۲ یک نقطه عطف تاریخی میان شهود انسانی و محاسبه سیلیکونی بود. در طول ۳۹ مسابقه نفس‌گیر، تینسلی تسلط موقعیتی شگرفی نشان داد و چینوک را با ۴ برد در برابر ۲ باخت و ۳۳ تساوی شکست داد^[1]. این نخستین بار در تاریخ ورزش‌های فکری بود که یک نرم‌افزار در دیداری رسمی برای قهرمانی جهان به مصاف یک قهرمان انسان می‌رفت.

در سال ۱۹۹۴ میلادی مسابقه برگشت برگزار شد. پس از ۶ تساوی پیاپی، تینسلی به دلیل بیماری ناگهانی ناچار به کناره‌گیری شد و در سال ۱۹۹۵ درگذشت^[1]. پس از آن چینوک قهرمان جهان شناخته شد. بررسی‌های بعدی پژوهشگران روی بازی‌های تینسلی نشان داد که تصمیم‌های او با احکام جداول بی‌نقص پایانی چینوک تطابقی شگفت‌انگیز داشت. ذهن او هندسه پنهان بازی را با شهود ناب درک کرده بود.

نردبان پیچیدگی: از چهار در یک خط تا شطرنج

برای درک اهمیت علمی این حل محاسباتی، قرار دادن چکرز در کنار دیگر بازی‌های فکری پرطرفدار بسیار آموزنده است.

کلود شانون در سال ۱۹۵۰ میلادی در مقاله‌ای ماندگار پیچیدگی بازی شطرنج را ارزیابی کرد^[4]. شانون شمار وضعیت‌های قانونی شطرنج را در حدود ۱۰^۴۴ وضعیت و شمار شاخه‌های بازی‌های ممکن را دست‌کم ۱۰^۱۲۰ بازی برآورد کرد؛ این عدد امروزه با نام عدد شانون شهرت دارد^[4].

مقایسه ابعاد این بازی‌ها تصویر روشنی به دست می‌دهد:

• چهار در یک خط: در سال ۱۹۸۸ به صورت قوی حل شد^[2]. با تریلیون‌ها حالت، امروزه روی هر لپ‌تاپ معمولی ظرف چند ثانیه بررسی می‌شود.
• چکرز انگلیسی ۸×۸: در سال ۲۰۰۷ با فضایی حدود ۵ × ۱۰^۲۰ وضعیت به طور ضعیف حل شد^[1]. این کار نیازمند ۱۸ سال پردازش خوشه‌ای و پایگاه داده پایان بازی با ۳۹ تریلیون وضعیت بود.
• شطرنج: کاملاً حل‌نشده باقی مانده است. با ۱۰^۴۴ وضعیت و ۱۰^۱۲۰ مسیر گوناگون^[4]، شطرنج بسیار فراتر از توان پردازش کنونی بشر است. امروزه پایگاه‌های پایان بازی شطرنج تنها تا ۷ مهره را به طور کامل پوشش می‌دهند. گسترش پایگاه به ۸ مهره نیازمند پتابایت‌ها حافظه است و بازی کامل با ۳۲ مهره دور از دسترس باقی مانده است.
• چکرز بین‌المللی ۱۰×۱۰: حل‌نشده است. با صفحه صدخانه‌ای، فضای حالت این بازی نزدیک به ۱۰^۳۰ وضعیت تخمین زده می‌شود. حرکت شاه‌های پروازی و اجباری بودن زدن بیشترین تعداد مهره، درخت بازی را بسیار گسترده‌تر می‌کند.

چرا اثبات ریاضی از جذابیت چکرز نمی‌کاهد؟

هنگامی که خبر حل چکرز در سال ۲۰۰۷ در رسانه‌های جهان انتشار یافت، عده‌ای به نادرست از پایان چکرز سخن گفتند. اگر رایانه می‌داند بازی مساوی است، چه نیازی به نشستن پشت صفحه باقی می‌ماند؟

این نگرش حقیقت نبردهای انسانی را نادیده می‌گیرد. راه‌حل ریاضی شرح مواجهه دو خرد بی‌نقص است که طی پنجاه حرکت حتی کوچک‌ترین خطایی مرتکب نمی‌شوند. اما انسان‌ها رایانه‌های بی‌خطا نیستند. هیچ استادی نمی‌تواند ۳۹ تریلیون موقعیت را در ذهن بسپارد یا درختی از میلیون‌ها انشعاب را مرور کند.

هنر فداکاری و نبردهای پوزیسیونی

پشت صفحه، چکرز همچنان نبردی پرتنش و تاکتیکی است. قانون زدن اجباری قلب تپنده هیجان این بازی است: اگر مهره‌ای امکان گرفتن داشته باشد، بازیکن ناچار به زدن است. این قاعده زمینه فداکاری‌های شگفت‌انگیز را پدید می‌آورد؛ جایی که بازیکن مهره‌های خود را پیشکش می‌کند تا مهره حریف را به خانه‌ای آسیب‌پذیر بکشاند و با پرش‌های چندگانه ورق بازی را برگرداند.

در عمل ۳ عامل سرنوشت مسابقه را رقم می‌زند:

1. دقت در گشایش. اگرچه دقیق‌ترین مسیر به تساوی می‌رسد، راه‌های فرعی پر از تله‌های خطرناک هستند. یک اشتباه در آغاز بازی می‌تواند طی دو حرکت شکست را رقم بزند.
2. مهارت پوزیسیونی. کنترل خانه‌های مرکزی، محافظت از ردیف آخر و هدایت مهره‌ها نیازمند درک عمیق است. بازیکنانی که اصول استراتژی چکرز را می‌شناسند بر رقبای متکی بر محاسبات سطحی چیره می‌شوند.
3. دقت در پایان بازی. هنگام برابری تعداد مهره‌ها، اصل تقابل (اپوزیسیون) برنده را تعیین می‌کند. یک اشتباه می‌تواند بردی قطعی را به تساوی بدل کند، چنانچه در راهنمای آخر بازی چکرز بررسی کرده‌ایم.

به همین دلیل در مسابقات حرفه‌ای با قرعه‌کشی حرکات اولیه، بازیکنان را به وضعیت‌های ناشناخته هدایت می‌کنند. چکرز نمرده است؛ بلکه اثبات ریاضی نشان داد که این بازی چه توازن استوار و هندسه باشکوهی دارد.

ابعاد روان‌شناختی رقابت بر سر صفحه بازی

تساوی نظری در چکرز هرگز به معنای بازی خسته‌کننده یا بدون هیجان نیست. برعکس، زمانی که دو بازیکن زیر فشار زمان به تصمیم‌گیری می‌پردازند، هوشیاری روانی و تمرکز حواس نقشی حیاتی پیدا می‌کند. پیش‌بینی نقشه‌های پنهان رقیب، شناخت لحظه‌های حساس برای تعویض مهره‌ها و حفظ ساختار دفاعی نیازمند آمادگی فکری عمیقی است که تنها با تمرین مستمر حاصل می‌شود.

تجربه مسابقات ثابت کرده است که زیبایی چکرز دقیقاً در همین درگیری‌های فکری زنده است. در حالی که رایانه‌ها نتیجه نهایی را مشخص کرده‌اند، هنر پیاده‌سازی تاکتیک‌ها بر روی صفحه همچنان متعلق به انسان‌ها است.

چه به تازگی در حال یادگیری قوانین چکرز باشید، چه مشتاق بررسی انواع چکرز در سراسر جهان باشید و چه بخواهید به بازی آنلاین چکرز با رقبایی از سراسر دنیا بپردازید، صفحه بازی همچنان میدان پویای خلاقیت و ذهن انسان است. علم ایستگاه پایانی را نشان داد، اما مسیر بازی همواره به بازیکنان تعلق دارد.

پرسش‌های متداول دربارهٔ حل چکرز

آیا چکرز برای تمامی خطاهای عجیب حل شده است؟

خیر، چکرز انگلیسی به شکل ضعیف حل شده است نه قوی. این برهان استراتژی تضمین‌شده‌ای برای تساوی از وضعیت آغازین با ۲۴ مهره در ۳۲ خانه تیره ارائه می‌دهد^[1]. همچنین تمامی وضعیت‌های با ۱۰ مهره یا کمتر در پایگاه ۳۹ تریلیون وضعیتی محاسبه شده‌اند. اما وضعیت‌های آشفته با مهره‌های پرشمار که پس از اشتباهات پیاپی پیش می‌آیند، ثبت نشده‌اند.

آیا یک بازیکن انسان می‌تواند چینوک را شکست دهد؟

در برابر نسخه کامل چینوک که مجهز به کتاب گشایش و پایگاه پایان بازی ۱۰ مهره‌ای است، هیچ بازیکنی توان پیروزی ندارد. با توجه به اثبات تساوی، رایانه با محاسبات دقیق هرگز شکست نخواهد خورد. اگر بازیکن حریف نیز کاملاً بی‌نقص عمل کند، بازی مساوی می‌شود؛ و چنانچه انسان مرتکب کوچک‌ترین خطایی شود، برنامه با بهره‌گیری از آن پیروز می‌گردد.

آیا مهره تیره در چکرز انگلیسی برتری دارد؟

در چکرز انگلیسی نخستین حرکت را مهره‌های تیره انجام می‌دهند. اگرچه حق حرکت اول ابتکار عمل برای تسلط بر خانه‌های مرکزی ایجاد می‌کند، برهان شیفر نشان داد که این برتری برای پیروزی در برابر دفاع بدون اشتباه کافی نیست^[1]. با بازی بی‌نقص دو طرف، این برتری اولیه به آرامی خنثی می‌شود و بازی با نتیجه مساوی خاتمه می‌یابد.

منابع

1. Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P., & Sutphen, S. (2007). Checkers Is Solved. Science, 317(5844), 1518–1522.
2. Allis, L. V. (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. thesis, University of Limburg, Maastricht.
3. Boardgammon. “Checkers Rules: How to Play, Movement, and Captures.”
4. Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine, Ser. 7, 41(314), 256–275.
5. Boardgammon. “Checkers Crown: Play Online Checkers and Regional Draughts Variants.”
6. Boardgammon. “Play Checkers Online: Free Browser and Mobile Draughts.”
7. Boardgammon. “Checkers Variants: The Kinds of Draughts Played Around the World.”

غلطی دیدید یا جمله‌ای به گوشتان غریب آمد؟ به ما خبر بدهید