خوارزمية

التقليم ألفا-بيتا

Alpha-Beta Pruning

استُخدمت في الخمسينيات والستينيات، وحُللت رياضياً عام 1975 موثّق جزئياً Partially Verified

تحسين لخوارزمية الحد الأدنى والأقصى يتجاهل الفروع التي لا يمكن أن تغيّر القرار النهائي، فيعطي النتيجة نفسها بعدد أقل من المواقع.

رسم توضيحي، وليس صورة أصلية

الفكرة الأساسية

الاحتفاظ بحدّين α وβ لأفضل قيمة مضمونة لكل لاعب، وقطع البحث عندما يتجاوز أحدهما الآخر.

آلية العمل

أثناء البحث بالعمق أولاً تُحدَّث α عند عقد MAX وβ عند عقد MIN، ويُقطع الفرع عندما α ≥ β.

المعادلات

prune when alpha >= beta

المزايا

  • النتيجة مطابقة لـ Minimax
  • مع ترتيب جيد للحركات يتضاعف العمق الممكن تقريباً

القيود

  • الكفاءة تعتمد على ترتيب الحركات

التعقيد الحسابي

O(b^(d/2)) في أفضل ترتيب، وO(b^d) في الأسوأ

التطبيقات العملية

محركات الشطرنج الكلاسيكية ومنها Deep Blue.

عناصر مرتبطة

يُستخدم في

خريطة المعرفة لهذا العنصر

افتح بالحجم الكامل

المصادر والمراجع العلمية

  1. Donald E. Knuth; Ronald W. Moore (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6(4):293-326. DOI: 10.1016/0004-3702(75)90019-3

    يدعم: تحليل رياضي لكفاءة التقليم

    مقالة محكّمة · جرى التحقق من بياناته الببليوغرافية عبر Crossref · صفحة المرجع