- خوارزمية Mini-max هي خوارزمية عودية أو تراجعية تُستخدم في اتخاذ القرار ونظرية اللعبة. إنها توفر حركة مثالية للاعب بافتراض أن الخصم يلعب أيضًا على النحو الأمثل.
- تستخدم خوارزمية Mini-Max العودية للبحث في شجرة اللعبة.
- تُستخدم خوارزمية Min-Max في الغالب للعب الألعاب في الذكاء الاصطناعي. مثل لعبة الشطرنج، لعبة الداما، لعبة تيك تاك تو، لعبة غو، والعديد من ألعاب سحب اللاعبين. تحسب هذه الخوارزمية قرار الحد الأدنى للحالة الحالية.
- في هذه الخوارزمية، يلعب لاعبان اللعبة، أحدهما يسمى MAX والآخر يسمى MIN.
- يتقاتل كلا اللاعبين حيث يحصل اللاعب الخصم على الحد الأدنى من الفائدة بينما يحصل على أقصى فائدة.
- كلا اللاعبين في اللعبة خصمان لبعضهما البعض، حيث سيحدد MAX القيمة القصوى وسيحدد MIN القيمة المصغرة.
- تقوم خوارزمية minimax بتنفيذ خوارزمية بحث العمق أولاً لاستكشاف شجرة اللعبة الكاملة.
- تستمر خوارزمية الحد الأدنى وصولاً إلى العقدة الطرفية للشجرة، ثم تتراجع عن الشجرة باعتبارها التكرار.
الكود الزائف لخوارزمية MinMax:
function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva
المكالمة الأولية:
الحد الأدنى (العقدة، 3، صحيح)
عمل خوارزمية Min-Max:
- يمكن وصف عمل خوارزمية minimax بسهولة باستخدام مثال. أدناه أخذنا مثالاً على شجرة الألعاب التي تمثل لعبة ثنائية اللاعبين.
- في هذا المثال، هناك لاعبان أحدهما يسمى Maximizer والآخر يسمى Minimizer.
- سيحاول برنامج Maximizer الحصول على الحد الأقصى من النقاط الممكنة، وسيحاول Minimizer الحصول على أقل عدد ممكن من النقاط.
- تطبق هذه الخوارزمية DFS، لذلك في شجرة اللعبة هذه، يتعين علينا أن نقطع كل الطريق عبر الأوراق للوصول إلى العقد الطرفية.
- في العقدة الطرفية، يتم إعطاء القيم الطرفية لذلك سنقوم بمقارنة تلك القيمة وتتبع الشجرة حتى تحدث الحالة الأولية. فيما يلي الخطوات الرئيسية المتبعة في حل شجرة اللعبة للاعبين:
الخطوة 1: في الخطوة الأولى، تقوم الخوارزمية بإنشاء شجرة اللعبة بأكملها وتطبيق وظيفة الأداة المساعدة للحصول على قيم الأداة المساعدة للحالات الطرفية. في مخطط الشجرة أدناه، لنأخذ A هي الحالة الأولية للشجرة. لنفترض أن المكبر يأخذ المنعطف الأول الذي له القيمة الأولية لأسوأ حالة =- اللانهاية، وسيأخذ المصغر المنعطف التالي الذي له القيمة الأولية لأسوأ الحالة = +infinity.
الخطوة 2: الآن، أولاً نجد قيمة الأدوات المساعدة لـ Maximizer، قيمتها الأولية هي -∞، لذلك سنقوم بمقارنة كل قيمة في الحالة النهائية مع القيمة الأولية لـ Maximizer ونحدد قيم العقد الأعلى. سوف تجد الحد الأقصى بين الجميع.
- للعقدة D max(-1,- -∞) => max(-1,4)= 4
- بالنسبة للعقدة E max(2, -∞) => max(2, 6)= 6
- بالنسبة للعقدة F max(-3, -∞) => max(-3,-5) = -3
- بالنسبة للعقدة G max(0, -∞) = max(0, 7) = 7
الخطوه 3: في الخطوة التالية، حان دور المصغر، لذلك سيقارن قيمة جميع العقد بـ +∞، وسيجد 3بحث وتطويرقيم عقدة الطبقة.
- للعقدة B= دقيقة(4,6) = 4
- بالنسبة للعقدة C= دقيقة (-3، 7) = -3
الخطوة 4: الآن حان دور Maximizer، وسيقوم مرة أخرى باختيار الحد الأقصى لقيمة جميع العقد والعثور على الحد الأقصى لقيمة العقدة الجذرية. في شجرة اللعبة هذه، هناك 4 طبقات فقط، وبالتالي نصل فورًا إلى العقدة الجذرية، ولكن في الألعاب الحقيقية، سيكون هناك أكثر من 4 طبقات.
- للعقدة A max(4, -3)= 4
كان هذا هو سير العمل الكامل للعبة minimax ثنائية اللاعبين.
خصائص خوارزمية ميني ماكس:
حدود خوارزمية الحد الأدنى:
العيب الرئيسي لخوارزمية minimax هو أنها تصبح بطيئة للغاية بالنسبة للألعاب المعقدة مثل الشطرنج، وgo، وما إلى ذلك. هذا النوع من الألعاب له عامل تفرع كبير، ولدى اللاعب الكثير من الخيارات ليقررها. يمكن تحسين هذا القيد في خوارزمية minimax من خلال تشذيب ألفا بيتا والتي ناقشناها في الموضوع التالي.