التقليم ألفا-بيتا
Alpha-Beta Pruning
تحسين لخوارزمية الحد الأدنى والأقصى يتجاهل الفروع التي لا يمكن أن تغيّر القرار النهائي، فيعطي النتيجة نفسها بعدد أقل من المواقع.
الفكرة الأساسية
الاحتفاظ بحدّين α وβ لأفضل قيمة مضمونة لكل لاعب، وقطع البحث عندما يتجاوز أحدهما الآخر.
آلية العمل
أثناء البحث بالعمق أولاً تُحدَّث α عند عقد MAX وβ عند عقد MIN، ويُقطع الفرع عندما α ≥ β.
المعادلات
prune when alpha >= betaالمزايا
- النتيجة مطابقة لـ Minimax
- مع ترتيب جيد للحركات يتضاعف العمق الممكن تقريباً
القيود
- الكفاءة تعتمد على ترتيب الحركات
التعقيد الحسابي
O(b^(d/2)) في أفضل ترتيب، وO(b^d) في الأسوأ
التطبيقات العملية
محركات الشطرنج الكلاسيكية ومنها Deep Blue.
عناصر مرتبطة
تأثّر بـ
- خوارزمية الحدّ الأدنى والأقصى خوارزمية · 1928المصدر: An analysis of alpha-beta pruning
خريطة المعرفة لهذا العنصر
افتح بالحجم الكاملالمصادر والمراجع العلمية
- 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
يدعم: تحليل رياضي لكفاءة التقليم
