پیچیدگی ترکیبیاتی، مجیک بیت‌بوردها و الگوریتم‌های جستجوی پیشرفته در موتورهای شطرنج
بازی شطرنج با فضای حالت تخمینی حدود ۱۰ به توان ۴۶ و پیچیدگی درخت بازی نزدیک به ۱۰ به توان ۱۲۰ (فرموله‌شده توسط کلود شانون در سال ۱۹۵۰)، نماد کلاسیک بهینه‌سازی الگوریتم‌های جستجو و ارزیابی موقعیت در علوم کامپیوتر است. طراحی یک انجین شطرنج فوق‌سریع که قادر به پیمایش عمق‌های بالای ۲۵ لایه (Ply) در کسری از ثانیه باشد، مستلزم بهره‌گیری از محاسبات موازی سخت‌افزاری در سطح بیت و حذف شاخه‌بندی‌های شرطی کند است.
۱. توپولوژی بیت‌بورد ۶۴ بیتی (64-Bit Bitboards)
موتورهای مدرن شطرنج به جای استفاده از آرایه‌های دوبعدی، موقعیت مهره‌ها را با اعداد صحیح بدون علامت ۶۴ بیتی (uint64) نمایش می‌دهند. هر بیت از خانه a1 (بیت ۰) تا h8 (بیت ۶۳) متناظر با یک خانه از صفحه است. این بازنمایی به انجین اجازه می‌دهد قوانین حرکتی، پوشش مهره‌ها و تقاطع خطوط دید را با دستورات تک‌سیکلی CPU (شامل AND، OR، XOR، NOT، POPCNT و TZCNT) محاسبه نماید.
۲. مجیک بیت‌بوردها (Magic Bitboards) و توابع هش کامل
بزرگ‌ترین گلوگاه محاسباتی در تولید حرکات شطرنج، تعیین مسیر حرکت مهره‌های لغزان (رخ، فیل و وزیر) است، زیرا امتداد حرکت آن‌ها توسط مهره‌های مانع مسدود می‌شود. برای حذف حلقه‌های تکرار پرهزینه، انجین‌های مدرن از مجیک بیت‌بوردها استفاده می‌کنند. با ضرب ماسک موانع در یک عدد جادویی ۶۴ بیتی و شیفت به راست، یک ایندکس متراکم و بدون تصادم به دست می‌آید که صفحه حمله را در زمان O(1) و با صفر انشعاب شرطی از حافظه بازیابی می‌کند.
۳. معماری وب توزیع‌شده و موتورهای بلادرنگ
در سیستم‌های بازی مدرن مبتنی بر وب، مانند معماری موتور بازی شطرنج آنلاین Boardgammon Chess، ترکیب بیت‌بوردهای ۶۴ بیتی با وب‌اسمبلی و هماهنگ‌سازی سرورمحور، امکان ارزیابی میلیون‌ها گره در ثانیه را مستقیماً در مرورگر کاربران فراهم می‌سازد.
نتیجه‌گیری: همگرایی بهینه‌سازی‌های بیتی سطح پایین، جستجوی PVS و هرس شاخه‌های تاکتیکی در جستجوی آرامش (Quiescence Search)، نمونه‌ای درخشان از کاربرد مهندسی نرم‌افزار در حل مسائل ترکیبیاتی عظیم است.
)
مشاهده نظرات بیشتر...