الدرس 8 من 9
تلخيص درس تقليم ألفا-بيتا في شجرة اللعبة
الدرس باختصار
تتبّع خوارزمية MiniMax كل فروع شجرة اللعبة، وهذا مكلف. تقليم ألفا-بيتا (Alpha-Beta Pruning) يعطي القرار النهائي نفسه مع إهمال فروع لا تؤثر فيه. نتعلّم هنا كيف نتتبّعه خطوة خطوة بقيمتي ألفا وبيتا.
مصطلحات الدرس
كل مصطلحات الدرس بصفحة وحدة · راجعها ببطاقات
- MiniMax
- خوارزمية للألعاب بين لاعبين: MAX يرفع قيمة الاقتران وMIN يخفضها.
- التقليم (Pruning)
- استبعاد أجزاء من شجرة البحث لأنها لن تغيّر القرار النهائي.
- ألفا (α)
- أعلى قيمة ضمنها MAX حتى الآن على المسار.
- بيتا (β)
- أدنى قيمة ضمنها MIN حتى الآن على المسار.
أهم الأفكار
لماذا نقلّم؟
يزداد عدد حالات اللعبة بسرعة مع العمق، ويُفحص في MiniMax كامل الشجرة. لكن يمكن تقليل عدد الحالات التي نفحصها إلى النصف أو أكثر بعدم النظر إلى كل عقدة. فنستخدم التقليم للتخلّص من فروع لا تؤثر في القرار النهائي. ألفا-بيتا تزيل الفروع التي لا تؤثر في القرار النهائي لـ MAX ولا لـ MIN، فتقلّل زيارات العقد بصورة كبيرة وتحسّن الكفاءة دون تغيير صحة القرار.
مثال التقليم بالحساب
للشجرة التي جذرها MAX وفروعها: MINIMAX(root) = max( min(3,12,8), min(2,x,y), min(14,5,2) ). الفرع الأول يعطي 3. في الثاني نرى 2 أولًا فتكون القيمة أقل من أو تساوي 2 مهما كانت x وy، وبما أنها لا تتجاوز 2 فلن تتفوق على 3. فنكتب max(3, z, 2) حيث z ≤ 2 فالناتج 3. إذن قيمة الجذر مستقلة عن x وy، فلا حاجة إلى فحصهما.
ألفا وبيتا والقاعدة
نتتبّع الشجرة من اليسار إلى اليمين بالعمق أولًا، وننقل مع كل عقدة قيمتين: ألفا (أفضل قيمة أمكن لـ MAX ضمانها) وتبدأ من −∞، وبيتا (أفضل قيمة ل MIN) وتبدأ من +∞. في عقدة MAX نرفع ألفا إلى أكبر قيمة ابن، وفي عقدة MIN نخفض بيتا إلى أصغر قيمة ابن. القاعدة: إذا صار ألفا ≥ بيتا في عقدة توقفنا عن فحص بقية أبنائها (تقليم).
أمثلة محلولة
مثال 1: تقليم الفرع من الحساب
احسب MINIMAX(root) = max(min(3,12,8), min(2,x,y), min(14,5,2)) دون معرفة x وy.
اعرض الحل
- Min(3,12,8) = 3.
- في min(2,x,y) نرى 2 أولًا، فالقيمة z ≤ 2 مهما كانت x وy.
- Min(14,5,2) = 2. فنحسب max(3, z, 2) = 3 لأن z ≤ 2.
- x وy لا تؤثران في الجذر فنُقلّمهما.
الجواب: 3
اختبر حالك
1. قيمة MINIMAX للجذر في max(min(3,12,8), min(2,x,y), min(14,5,2)) تساوي:
2. متى نقلّم باقي أبناء عقدة في ألفا-بيتا؟
باقي الدرس للمسجّلين، ومجاناً
- مثالين محلولين كمان
- خطأين شائعين وكيف تتجنّبهم
- إجابات «اختبر حالك» مع الشرح
جاهز تتدرّب؟
1 سؤال على هالدرس، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.
تدرّب على 1 سؤال من هالدرس مجانًا