المينيماكس وتشذيب ألفا-بيتا

في لعبة بلاعبين صفرية المجموع تامّة المعلومات، يعرف اللاعبان كل شيء، ومكسب أحدهما خسارة الآخر. فـMAX يريد منفعة نهائية كبيرة؛ وMIN يريدها صغيرة. وللّعب الأمثل أمام خصم كامل تعريف دقيق، ويُحسب من أسفل إلى أعلى.

قيمة المينيماكس

$$\text{MINIMAX}(s) = \begin{cases} \text{UTILITY}(s) & \text{if } s \text{ is terminal},\\ \max_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if MAX moves at } s,\\ \min_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if MIN moves at } s. \end{cases}$$

اقرأها افتراضاً عن الخصم: إذ يفترض MAX أن MIN سيردّ دائماً بأسوأ نقلة لـMAX. والقيمة هي ما يستطيع MAX ضمانه حتى أمام لعب كامل - حدٌّ أدنى لا يمكن أن تُجادَل عنه، لا تنبّؤ بما سيفعله خصم ضعيف.

مثال محلول

الشجرة المعيارية من طبقتين. جذرٌ MAX له ثلاثة أبناء MIN، وأوراقهم

$$B: (3, 12, 8) , \qquad C: (2, 4, 6) , \qquad D: (14, 5, 2) .$$

رجّع عقد MIN. يأخذ كلٌّ منها أصغر أوراقه:

$$B = \min(3,12,8) = 3 , \quad C = \min(2,4,6) = 2 , \quad D = \min(14,5,2) = 2 .$$

رجّع جذر MAX. يأخذ أكبر أبنائه:

$$\text{root} = \max(3, 2, 2) = 3 .$$

فقيمة المينيماكس $\mathbf{3}$، والنقلة المثلى هي التي تؤدّي إلى $B$.

ولاحظ المطبّ في العقدة $D$: فهي تحوي أكبر ورقة في الشجرة كلها، $14$. ومع ذلك قيمتها $2$، لأن MAX لا يختار أي ورقة من $D$ تُبلَغ - بل MIN يختار، وسيأخذ $2$. فالفرع يساوي ما يسمح به خصمك، لا ما يحتويه.

تشذيب ألفا-بيتا

يفحص المينيماكس كل عقدة، وهو $O(b^m)$ وميؤوس منه في الألعاب الحقيقية. لكنك لا تحتاج رؤية كل عقدة لتعرف قيمة الجذر.

لنفترض أن MAX أثبت سلفاً أن $B$ يضمن $3$. والآن افحص $C$ فتجد أن ورقتها الأولى $2$. والعقدة $C$ عقدة MIN، فقيمتها النهائية على الأكثر $2$ - إذ يستطيع MIN دائماً أخذ تلك الـ$2$، ولا تستطيع الأوراق التالية إلا خفضها. ولأن $2 < 3$، لن يختار MAX $C$ أبداً. فأوراق $C$ المتبقّية لا تستطيع تغيير قيمة الجذر، ومن ثم لا حاجة إلى فحصها إطلاقاً.

وتلك هي الفكرة كلها، متتبَّعةً بحدّين: $\alpha$، أفضل قيمة يضمنها MAX سلفاً، و$\beta$، أفضل ما يضمنه MIN سلفاً.

ما يغيّره التشذيب. مطبَّقاً على شجرة مينيماكس معيارية، يعيد ألفا-بيتا النقلة نفسها التي يعيدها المينيماكس، مع تشذيب فروع لا يمكن أن تؤثّر في القرار النهائي. فهو دقيق لا تقريبي: القيمة متطابقة، والمختلف هو العمل فحسب. ومن يصفه بأنه تقريب أسرع فقد أساء فهمه.

ترتيب النقلات

يتوقّف التشذيب كلياً على فحص النقلات الجيدة مبكراً. فإن بُحثت أفضل نقلة أولاً، ارتفعت $\alpha$ فوراً وقُطعت الفروع اللاحقة سريعاً. ومع ترتيب مثالي يهبط معامل التفرّع الفعّال من $b$ إلى نحو $\sqrt{b}$، فيتيح للبحث أن يمضي أعمق بنحو الضعف في الزمن نفسه. ومع ترتيب أسوأ الحالات لا يُشذَّب شيء وتكون قد دفعت كلفة المينيماكس كاملة.

ولهذا تستثمر المحرّكات الحقيقية بكثافة في قواعد الترتيب الاسترشادية قبل تعميق البحث.

قبل الاختبار

كن قادراً على ترجيع القيم في شجرة صغيرة، وعلى القول إن ألفا-بيتا يعيد القيمة ذاتها بفحص عقد أقل، وعلى تفسير لماذا تساوي $D$ قيمة $2$ رغم احتوائها على $14$. انظر البحث التنافسي والمينيماكس.