بازی چکرز انگلیسی ۸×۸ (English Draughts) یکی از درخشان‌ترین دستاوردهای هوش مصنوعی و ترکیبیات محاسباتی در تاریخ نظریه بازی‌ها به شمار می‌رود. در سال ۲۰۰۷، پروفسور جاناتان شفر (Jonathan Schaeffer) و تیم تحقیقاتی دانشگاه آلبرتا پس از ۱۸ سال پردازش محاسباتی مداوم با پروژه Chinook، اثبات کردند که بازی چکرز با بازی بی‌نقص هر دو طرف همواره به تساوی (Draw) می‌انجامد. این پروژه چکرز را به بزرگ‌ترین بازی استراتژیک تخته‌ای تبدیل کرد که تا به امروز به طور کامل حل (Solved) شده است.

۱. فضای حالت و پیچیدگی ترکیبیاتی

فضای حالت بازی چکرز شامل دقیقاً 5.002 × 10^20 موقعیت قانونی است. اگرچه این رقم در مقایسه با عدد شانون در شطرنج (10^120) یا بازی گو (10^360) کوچک‌تر به نظر می‌رسد، اما همچنان فراتر از توان هرگونه پیمایش مستقیم است. نقطه عطف حل این بازی، تکیه بر تحلیل پس‌رونده (Retrograde Analysis) و پایگاه داده‌های پایان‌بازی (Endgame Tablebases) با ظرفیت ۳۹ تریلیون وضعیت بود.

۲. نمایش کم‌حجم ۳۲ بیتی در معماری پردازنده

یکی از ظرافت‌های مهندسی در طراحی موتورهای چکرز، استفاده از تقارن صفحه و خانه‌های فعال است. از آنجا که مهره‌های چکرز تنها بر روی ۳۲ خانه تیره حرکت می‌کنند، کل تخته را می‌توان با یک عدد صحیح ۳۲ بیتی (uint32) مدل‌سازی نمود. وضعیت کامل بازی با چهار رجیستر ۳۲ بیتی ذخیره می‌شود:

  • black_men: بیت‌های فعال مهره‌های عادی سیاه
  • black_kings: بیت‌های فعال شاه‌های سیاه
  • white_men: بیت‌های فعال مهره‌های عادی سفید
  • white_kings: بیت‌های فعال شاه‌های سفید

این ساختار به موتور اجازه می‌دهد تا با استفاده از عملیات شیفت منطقی (Bitwise Shift) و محاسبات موازی در سطح کلمه (SWAR)، تمام حرکات ممکن قطری را بدون استفاده از حلقه‌های شرطی و تنها در چند کلاک پردازنده تولید کند.

۳. دینامیک پرش اجباری و کاهش ضریب انشعاب

قانون بنیادین «پرش اجباری» (Mandatory Capture) ویژگی متمایزی است که فاکتور انشعاب (Branching Factor) را در چکرز کنترل می‌کند. در حالی که میانگین گزینه‌های حرکتی در بازی حدود ۸ تا ۱۰ است، در وضعیت‌هایی که پرش اجباری وجود دارد، ضریب انشعاب به طور چشمگیری افت کرده و به ۱٫۲ تا ۲ می‌رسد. این امر به الگوریتم هرس آلفا-بتا اجازه می‌دهد تا عمق درخت بازی را با سرعت بسیار بالایی واکاوی کند.

۴. پایگاه داده‌های رتروگرید Chinook

تحلیل پس‌رونده از وضعیت‌های پایانی (صفحات با ۲ یا ۳ مهره که نتیجه برد، باخت یا مساوی آن‌ها بدیهی است) آغاز می‌شود و به صورت معکوس به سمت موقعیت‌های با مهره‌های بیشتر گسترش می‌یابد. تیم شفر توانست تمام وضعیت‌های تا ۱۰ مهره را به طور کامل ایندکس و فشرده‌سازی کند. هنگامی که جستجوی پیش‌رونده درخت بازی به وضعیتی با ۱۰ مهره یا کمتر می‌رسد، مقدار دقیق نظری بازی بدون نیاز به هیچ‌گونه جستجوی بیشتر مستقیماً از حافظه با پیچیدگی O(1) استخراج می‌شود.

۵. پلتفرم‌های مدرن و استقرار وب‌اسمبلی

امروزه با بهره‌گیری از تکنولوژی‌های مدرن وب نظیر WebAssembly و بوم‌های رندرینگ دوبعدی با کارایی بالا، این هوش مصنوعی پیشرفته مستقیماً درون مرورگر اجرا می‌شود. علاقه‌مندان به بررسی عملی این الگوریتم‌ها و تجربه مسابقات آنلاین استاندارد می‌توانند از پلتفرم تحت وب چکرز کراون (Checkers Crown) بازدید نمایند؛ سامانه‌ای که با تکیه بر پایگاه‌های داده پایان‌بازی و موتورهای سبک کلاینت‌محور، بازی چکرز کلاسیک ۸×۸ را با بالاترین استانداردهای فنی ارائه می‌دهد.