البحث التنافسي والمينيماكس

يختلف البحث عن مسار عن لعب لعبة في نقطة حاسمة: ففي اللعبة يتحرّك شخص آخر بعدك، وهو يحاول أن يجعلك تخسر. فلا تستطيع تخطيط سلسلة أفعال ثابتة، لأن ردود خصمك ليست لك لتختارها. ويعالج البحث التنافسي ذلك بافتراض أن الخصم يلعب أفضل ما يمكن، وبحساب أفضل ردّ على ذلك.

أ. شجرة اللعبة

لاعبان، هما اصطلاحاً MAX (الذي يتحرّك أولاً ويعظّم) وMIN (الذي يصغّر الكمية نفسها). ولـشجرة اللعبة الوضعُ الابتدائي عند الجذر، وفرعٌ لكل نقلة قانونية، وطبقات متناوبة من عقد MAX وMIN، وأوضاع نهائية عند الأوراق تحمل منفعة - أي عائد MAX.

ولأن منفعة MIN هي سالب منفعة MAX، فهذه لعبة صفرية المجموع: ما يكسبه أحدهما يخسره الآخر بالضبط. وهذا ما يتيح لعدد واحد لكل ورقة أن يصف النتيجة لكليهما.

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

تُعرَّف قيمة العقدة تعريفاً عَودياً:

$$\textsc{Minimax}(s) = \begin{cases} \textsc{Utility}(s) & \text{if } s \text{ is terminal},\\[4pt] \max_{a} \textsc{Minimax}(\textsc{Result}(s, a)) & \text{if } s \text{ is a MAX node},\\[4pt] \min_{a} \textsc{Minimax}(\textsc{Result}(s, a)) & \text{if } s \text{ is a MIN node}. \end{cases}$$

يختار MAX أكبر قيمة بين الأبناء؛ ويختار MIN أصغرها. وتنتشر القيم من الأوراق صعوداً إلى الجذر، وأفضل نقلة لـMAX عند الجذر هي التي تؤدّي إلى الابن الذي تساوي قيمته قيمة الجذر.

ماذا يشتري الافتراض، وماذا يكلّف. يفترض المينيماكس أن الخصم يلعب لعباً أمثل. وأمام خصم أمثل تكون القيمة بالضبط ما يستطيع MAX ضمانه، فهي ضمانة حقيقية لأسوأ الحالات لا تنبّؤ. أما أمام خصم ضعيف فهي متحفّظة: إذ قد تتخلّى عن فخّ كان الخصم القابل للخطأ ليقع فيه.

ج. حلّ شجرة يدوياً

شجرة من ثلاث طبقات: الجذر MAX، وأبناؤه الثلاثة عقد MIN، لكلٍّ منها ثلاثة أبناء نهائيين.

طبقة MIN. تأخذ كل عقدة MIN أصغر قيم أبنائها:

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

الجذر. يأخذ MAX الأكبر:

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

فينبغي لـMAX أن ينتقل إلى $B$، ضامناً 3 على الأقل.

ولاحظ ضآلة أهمية قيم الأوراق الكبيرة. فالـ$12$ تحت $B$ والـ$14$ تحت $D$ لا تُنالان أبداً، لأن MIN لن يسمح بهما - إذ ينتقل MIN إلى $3$ و$2$ على الترتيب. ولا ينجو إلا أصغر قيم كل فرع.

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

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

وتُحمَل قيمتان أسفل البحث، وقد عرّفهما راسل ونورفيغ هكذا:

• $\alpha$ - قيمة أفضل خيار (الأعلى) وُجد حتى الآن عند أي نقطة اختيار على المسار بالنسبة إلى MAX؛
• $\beta$ - قيمة أفضل خيار (الأدنى) وُجد حتى الآن على المسار بالنسبة إلى MIN.

ويشذّب البحث الفروع المتبقّية عند عقدة حالما يُعلم أن قيمة العقدة أسوأ من $\alpha$ الحالية (بالنسبة إلى MAX) أو $\beta$ الحالية (بالنسبة إلى MIN).

هـ. تشذيب الشجرة، خطوةً خطوة

بتتبّع الشجرة نفسها من اليسار إلى اليمين:

العقدة $B$. افحص $3$ و$12$ و$8$. لا شيء يمكن تشذيبه - فهذا الفرع الأول ولا تملك MAX $\alpha$ بعد. و$B = 3$، فيضبط الجذر $\alpha = 3$: أي أن MAX يضمن 3 سلفاً.

العقدة $C$. افحص الورقة الأولى، $2$. و$C$ عقدة MIN، فقيمتها النهائية على الأكثر $2$ - إذ لا يستطيع MIN إلا النزول من هنا.

لكن MAX يملك 3 مضمونة في مكان آخر. ولن يُختار فرعٌ قيمته على الأكثر 2 على فرع قيمته 3، مهما كان محتوى الأوراق المتبقّية. فلا تُفحص الورقتان $4$ و$6$ أبداً. وهذا هو التشذيب.

العقدة $D$. افحص $14$: القيمة حتى الآن $14$، وما زالت فوق $\alpha = 3$، فلا تشذيب. افحص $5$: القيمة حتى الآن $5$، وما زالت فوق $3$. افحص $2$: القيمة $2$. و$D = 2$.

الجذر. $\max(3, 2, 2) = 3$ - الإجابة نفسها التي يعطيها المينيماكس الكامل.

فحص ألفا-بيتا 7 من الأوراق التسع، مشذّباً ابنَي $C$ الثاني والثالث.

يطبع تشغيله القيمة 3 بالطريقتين، وexamined: [3, 12, 8, 2, 14, 5, 2] (سبع أوراق)، والورقتين المشذّبتين.

و. لماذا يحسم ترتيب النقلات كل شيء

يتوقّف التشذيب على العثور على النقلات الجيدة مبكراً. فإن فُحصت أفضل نقلة لـMAX أولاً، ارتفعت $\alpha$ فوراً وشذّبت بقوة. وإن فُحصت أخيراً، فلا شيء نشذّب مقابله حتى النهاية.

ومع ترتيب مثالي، يفحص ألفا-بيتا نحو $O(b^{m/2})$ عقدة بدل $O(b^m)$ لمعامل تفرّع $b$ وعمق $m$. ويعني ذلك الأُسّ المنصَّف البحث بضعف العمق في الزمن نفسه - وهو الفرق بين برنامج هاوٍ وبرنامج خبير.

ويتطلّب الترتيب المثالي معرفة الإجابة سلفاً، ولذا تقاربه البرامج الحقيقية بقواعد استرشادية: جرّب الأسْر أولاً، جرّب النقلة التي كانت الأفضل عند العمق الأقلّ السابق، وهكذا.

ز. حين تكون الشجرة أكبر من ذلك على أي حال

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

ويُدخل هذا مشكلتين جديدتين تستحقّان التسمية. فـأثر الأفق هو النزوع إلى دفع خسارة محتومة إلى ما بعد عمق البحث بقليل، فتبدو متفادَاة وهي مجرّد خارج المرأى. ويجب تطبيق دالة التقييم عند أوضاع هادئة - إذ يعطي التوقّف في وسط تبادل تقديراً خاطئاً بشدّة، فيُمدّ البحث حتى تستقرّ الأمور.

وتاريخياً، تصوّر جون مكارثي بحث ألفا-بيتا عام 1956؛ وأثبت كنوث ومور صحّته وتعقيده الزمني عام 1975.

الخلاصات الأساسية

• يفترض البحث التنافسي خصماً أمثل، ما يجعل قيمة المينيماكس ضمانةَ أسوأ حالة.
• MAX يعظّم وMIN يصغّر، وتنتشر القيم من الأوراق إلى الجذر.
• شجرتنا: عقد MIN $3, 2, 2$؛ وقيمة الجذر $3$؛ وMAX يلعب نحو $B$.
• يعيد ألفا-بيتا القيمة ذاتها مع تخطّي فروع غير ذات صلة بالبرهان - 7 أوراق بدل 9 هنا.
• $\alpha$ أفضل ضمانة لـMAX حتى الآن، و$\beta$ أفضل ضمانة لـMIN؛ ويُقطع الفرع حالما يعجز عن تجاوزهما.
• ترتيب النقلات يحدّد المكسب؛ والترتيب المثالي ينصّف تقريباً أُسّ العمق الفعّال.

ما التالي

يفترض المينيماكس تعارضاً صارماً. ومعظم المواقف الاستراتيجية الحقيقية ليست صفرية المجموع - إذ قد يكسب اللاعبون جميعاً أو يخسرون جميعاً، ويحتاج «اللعب الأمثل» إلى إعادة تعريف. وذلك التعميم هو نظرية الألعاب وتوازن ناش.