هرس آلفا-بتا چگونه عمق جستجوی هوش مصنوعی تخاصمی را دو برابر می‌کند؟

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

هزینه محاسباتی مینی‌مکس سرسام‌آور است. اگر یک بازی دارای ضریب انشعاب ۳۵ باشد (به این معنی که در هر نوبت ۳۵ حرکت قانونی ممکن وجود دارد، همان‌طور که در شطرنج معمول است)، پیش‌بینی تنها چهار حرکت جلوتر نیازمند ارزیابی بیش از ۱٫۵ میلیون موقعیت است.[1]

پیش‌بینی شش حرکت جلوتر، این رقم را از مرز ۱٫۸ میلیارد عبور می‌دهد. پیچیدگی زمانی این رویکرد جستجوی فراگیر برابر با O(b^d) است، که در آن b ضریب انشعاب و d عمق درخت جستجو است.[6]

هرس آلفا-بتا در این انفجار تصاعدی مداخله می‌کند، اما نه با تغییر تصمیم نهایی، بلکه با اثبات ریاضی این‌که کدام شاخه‌های آینده نیازی به کاوش ندارند.[4]

این الگوریتم هنگام پیمایش درخت بازی دو مقدار را ردیابی می‌کند: آلفا، حداقل امتیازی که بازیکن بیشینه‌ساز تضمین می‌کند به دست آورد، و بتا، حداکثر امتیازی که بازیکن کمینه‌ساز تضمین می‌کند واگذار کند.[5]

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

اگر هوش مصنوعی بداند که از قبل مسیر تضمین‌شده‌ای برای رسیدن به امتیاز ۵+ دارد، و شروع به کاوش شاخه جدیدی کند که در آن حریف می‌تواند امتیاز ۲+ را تحمیل کند، دیگر نیازی به دیدن بقیه آن شاخه ندارد. بازی بهینه حریف از قبل آن را نسبت به خط پایه ۵+ در جایگاه پایین‌تری قرار داده است.[2]

دستاوردهای کارایی حاصل از این میانبر منطقی بسیار عمیق است. در بدترین حالت، جایی که الگوریتم ابتدا بدترین حرکت‌های ممکن را ارزیابی می‌کند، هرس آلفا-بتا هیچ فایده‌ای ندارد و پیچیدگی زمانی همان O(b^d) باقی می‌ماند.[6]

با این حال، تحت مرتب‌سازی بهینه حرکت‌ها (جایی که بهترین حرکت‌ها ابتدا ارزیابی می‌شوند)، پیچیدگی زمانی به O(b^{d/2}) کاهش می‌یابد.[1][6]

این کاهش با ضریب b^{d/2} عملاً توان را نصف می‌کند. در عمل، هوش مصنوعی که قبلاً می‌توانست تا عمق ۴ حرکت را در یک محدودیت زمانی محاسباتی خاص جستجو کند، اکنون می‌تواند در همان زمان دقیق تا عمق ۸ حرکت را جستجو کند.[6]

در شطرنج، ضریب انشعاب مؤثر از حدود ۳۵ به حدود ۵٫۹ کاهش می‌یابد. همین ویژگی ریاضی بود که به رایانه‌های شطرنج‌باز اولیه، که نقطه اوج آن‌ها مسابقه دیپ بلو در سال ۱۹۹۷ بود، اجازه داد تا میلیون‌ها موقعیت را در ثانیه ارزیابی کرده و استادبزرگ‌های انسانی را به چالش بکشند.[1][4]

حداکثر کارایی نظری O(b^{d/2}) کاملاً به مرتب‌سازی حرکت‌ها وابسته است. اگر هوش مصنوعی حرکت‌ها را به‌طور تصادفی ارزیابی کند، کارایی هرس به‌شدت افت می‌کند.[5]

برای نزدیک شدن به این حد بهینه، موتورهای مدرن به روش‌های اکتشافی خاص دامنه متکی هستند (مانند ارزیابی زدن مهره‌ها یا کیش دادن در ابتدا) تا اطمینان حاصل کنند که امیدوارکننده‌ترین شاخه‌ها، محدوده‌های آلفا و بتای قدرتمندی را در همان ابتدای جستجو ایجاد می‌کنند.[7]

در حالی که هرس آلفا-بتا برای بازی‌های مجموع‌صفر دونفره به‌زیبایی حل شده است، تعمیم آن به محیط‌های چندنفره پیچیدگی‌های شدیدی را به همراه دارد. در یک بازی سه‌نفره، حرکتی که برای بازیکن ۱ بد است ممکن است برای بازیکن ۲ خوب، اما برای بازیکن ۳ فاجعه‌بار باشد.[3]

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

ماندگاری و اهمیت هرس آلفا-بتا در قطعیت ریاضی آن نهفته است. این الگوریتم یک راه‌حل را تقریب نمی‌زند یا در مورد یک احتمال حدس نمی‌زند؛ بلکه دقیقاً همان نتیجه جستجوی فراگیر را تضمین می‌کند، در حالی که از نظر ریاضی ثابت می‌کند بخش‌های وسیعی از آینده نامربوط هستند.[4][7]