حل محاسباتی چکرز، توپولوژی بیت‌بوردهای ۳۲ بیتی و پایگاه داده‌های رتروگرید Chinook

بازی چکرز انگلیسی (۸×۸) یکی از بزرگ‌ترین دستاوردهای نظریه محاسباتی بازی‌ها محسوب می‌شود. در سال ۲۰۰۷، تیم تحقیقاتی دانشگاه آلبرتا به سرپرستی دکتر جاناتان شفر با انتشار مقاله تاریخی خود در ژورنال ساینس اعلام کرد که بازی چکرز به صورت ضعیف حل (Weakly Solved) شده است؛ به این معنا که بازی بی‌نقص از نقطه شروع توسط هر دو بازیکن قطعاً به تساوی ختم می‌گردد. اثبات این ادعا نیازمند پیمایش فضای حالتی با کاردینالیتی ۵ در ۱۰ به توان ۲۰ موقعیت بود.

۱. توپولوژی فشرده بیت‌بورد ۳۲ بیتی

از آنجا که مهره‌های چکرز منحصراً روی ۳۲ خانه تیره صفحه شطرنجی جابه‌جا می‌شوند، کل موقعیت بازی را می‌توان در رجیسترهای ۳۲ بیتی بازنمایی کرد. این ساختار اجازه می‌دهد حرکات مورب پیاده‌ها با شیفت‌های ثابت (+۴ و +۳ برای ردیف‌های زوج و فرد) و زنجیره پرش‌های اجباری با ماسک‌های بیتی موازی (Bitwise AND/OR) بدون نیاز به حلقه‌های کند پردازش شوند.

۲. تحلیل رو به عقب (Retrograde Analysis) و حل پایان‌بازی

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

۳. پیاده‌سازی مدرن در مرورگرهای وب

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

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