تصغير الأعظم

التعامل مع التحركات البديلة

من جهة ثانية، وكذلك يفضل استخدام قاعدة مفادها أنه إذا كانت نتيجة الحركة فوزًا مباشرًا لـ A فإنها تقيم بما لا نهاية موجبة وإذا كانت فوزًا مباشرًا لـB ، فإنها تقيم بلانهاية سالبة.  قيمة الحركة بالنسبة لـ A مقارنة بأي حركة أخرى هي الحد الأقصى للربح الناتج عن كل الردود المحتملة لـ B.  لهذا السبب، يُطلق على A اسم مشغل التعظيم ويُسمى B مشغل التصغير، ومن هنا جاءت تسمية الخوارزمية minimax.  وستقوم الخوارزمية بتعيين قيمة موجبة أو سالبة لكل وضعية بناءً على قيمة المراكز الرابحة أو الخاسرة النهائية التي يمكن أن تؤدي لها هذه الوضعية، ولكن غالبًا ما يكون هذا غير ممكنٍ الألعاب المعقدة مثل الشطرنج إلا إذا كانت قريبة من نهايتها، لصعوبة حساب كل الاحتمالات الممكنة، ولذلك تعطى الوضعيات قيمًا محدودة كتقديرات لدرجة الاعتقاد بأنها ستؤدي إلى فوز اللاعب أو خصمه.

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

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

من جهة ثانية، لذلك من غير العملي إجراء تحليل كامل للألعاب مثل الشطرنج باستخدام خوارزمية ميني ماكس.

من جهة ثانية، وترتبط القيمة بالوضعية الحالية في اللعبة، وتحسب هذه القيمة عن طريق وظيفة تقييم الوضعية وهي تعني مدى نجاح اللاعب في التحركات التي اوصلته إلى هذه الوضعية.

وعلى صعيد آخر، يقوم اللاعب دائمًا بالحركة التي يظن أنها سترفع من قيمة وضعيته بناءً على توقعه لحركات الخصم.  كما يجب عليه أن يقيم كل الحركات الممكنة له لأختيار أفضلها.

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

ومن جهة أخرى، إحدى الطرق الممكنة لتقييم هو تعيين قيمة عددية للحركة يضعها لللاعب فمثلا تقيم الحركة A بـ +1 والحركة B بـ -1.  وهذا قد يؤدي إلى نظرية اللعبة الاندماجية.

من جانب آخر، مينيماكس هي خوارزمية متكررة الخطوات لاختيار الخطوة التالية في لعبة متعددة اللاعبين، وعادة ما تكون من لاعبين اثنين فقط.

الخوارزمية

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

من جانب آخر، تساعد خوارزمية مينيماكس على العثور على أفضل حركة، من خلال حساب نتيجة الحركة في نهاية اللعبة.  على افتراض أن كلا اللاعبينِ يسعى في كل حركة إلى زيادة احتمال فوزه إلى أعلى حد وبالتالي تقليل احتمال الخسارة إلى أدنى حد ممكن.

في الفلسفة

من جانب آخر، في الفلسفة، أستعمل مصطلح ماكسمين في نظرية العدالة لجون راولز، حيث ذكرها في سياق مبدأ الاختلاف.  وعرّف بأنه المبدأ أو القاعدة التي تنص على وجوب ترتيب التفاوتات الاجتماعية والاقتصادية بحيث «تكون ذات فائدة أكبر لأفراد الطبقة الفقيرة»

• انظر كذلك
• نظرية الألعاب
• تقييم ألفا بيتا
• استمثال توافقي
• واحدة بواحدة

في نظرية القرار

كذلك، على عكس القرارات التي تستعمل الخوارزمية لحساب القيمة المتوقعة أو المنفعة المتوقعة، لا توضع أي تقييمات للاحتمالات المختلفة، المطلوب فقط هو تحليل كافة الاحتمالات بغض النظر عن النتائج التي ستؤدي اليها.  وبالتالي فهي تحسب كل التغييرات المحتملة في العقد.

في هذا الإطار، علاوة على ذلك، لا يتطلب الحد الأدنى إلا قياسًا ترتيبيًا (بمقارنة النتائج وترتيبها)، وليس قياسات الفترات (تتضمن هذه النتائج «ما هو أفضل أو أسوأ بكثير»)، وترتيب البيانات، باستخدام النماذج فقط ويعرف الحد الأدنى في هذه الحالة، بانه «الاستراتيجية التي تؤدي إلى نتيجة، أقل سوءًا من أي إستراتيجية أخرى»..

في العاب المجموع الصفري

وفي هذا الصدد، كل لعبة من شخصين، محصلتها صفر تحتوي على الكثير من الاستراتيجيات والاحتمالات، توجد قيمة V واستراتيجية مختلفة لكل لاعب، مثل

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

كذلك، في ألعاب المجموع الصفري التي يوجد فيها لاعبان فقط، يكون حل ميناماكس هو توازن ناش.

من جانب آخر، ومع ذلك، فإن هذا الحل غير مستقر، وصعب التطبيق لأن B إذا اعتقد أن A سيختار A2 ، فإنه سيختار B1 للحصول على نقطة؛ وإذا اعتقد "A" أن "B" سيختار B1 ، فإن "A" سيختار "A1" للحصول على 3 نقاط؛

في هذا الإطار، وبالمثل، سيحصل اللاعب بفضل إستراتيجيته على نتيجة قدرها V بغض النظر عن إستراتيجية اللاعب 2، وبالعكس.

ومن جهة أخرى، يمكن أن يتجنب اللاعب A الاضطرار الناتجة من إجراء حركة متوقعة باختيار A1 مع أحتمال نجاح يبلغ 1∕6 أو بإمكانه إجراء الحركة المتوقعة A2 مع احتمال نجاح يبلغ 5∕6: النتيجة المتوقعة لـ A ستكون 3 × (1∕6) - 1 × (5 ∕ 6) = −1∕3 إذا اختار B الحركة B1 و −2 × (1∕6) + 0 × (5∕6) = −1/3 في حالة اختار الحركة B2.  ولذلك، يمكن أن تضمن هذه الحركة لB مكسبًا متوقعًا لا يقل عن 1/3، بغض النظر عما سيختاره A ، باستخدام إستراتيجية عشوائية سيكون احتمال اختيار B1 هو 13 واحتمال اختيار B2 هو 2∕3.

من جانب آخر، لن يختار أي لاعب الخيارات التي تفيد الخصم أكثر منه ولذة: لن يختار A الحركة A3 لأن الحركتين A1 أو A2 سيحققان نتيجة أفضل، بغض النظر عما سيختاره اللاعب B ؛ وهذا الأخير لن يختار الحركة B3 لأن بعض النتائج من الحركتين B1 و B2 ستعطي نتيجة أفضل منها، هذا بغض النظر عما سيختاره اللاعب A.

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

ومن ناحية أخرى، يوضح الجدول نهاية الخطة للعبة محصلتها صفر، حيث يقوم اللاعبان A و B بحركات متزامنة.  افترض أن كل لاعب لديه ثلاثة اختيارات ويمثل الجدول نقاط المكافأة لـ A ا. نقاط المكافأة لـ B هي نفس القيم التي في الجدول مع عكس الإشارات (أي إذا كانت الاختيارات A1 و B1 فإن B سيخسر 3 نقاط لصالح A). وبسبب ذلك، يكون الخيار الأفضل لـ A هو A2 نظرًا لأن أسوأ نتيجة ممكنة هي خسارة نقطة، وأفضل خيار لـ B هو B2 نظرًا لأن أسوأ نتيجة ممكنة هي 0.

إضافةً إلى ذلك، وبناء على إستراتيجية اللاعب 2، فإن أفضل عائد ممكن للاعب 1 هو V وبالنظر إلى إستراتيجية اللاعب 1، فإن أفضل عائد ممكن للاعب 2 هو −V.

أمثلة

وفي هذا السياق، تقوم الخوارزمية بتقييم كل عقدة نهائية باستخدام وظيفة تقييم إرشادية، للحصول على القيم الموضحة. مع تقييم الحركات التي ستضمن فوز اللاعب بما لا نهاية موجب، كما تقيم الحركات التي ستؤدي إلى فوز خصمه بما لا نهاية سالبة، وفي المستوى الثالث تختار الخوارزمية، لكل عقدة، أصغر قيمة للعقدة الفرعية، وتعيينها لنفس العقدة (مثلًا، العقدة الموجودة على اليسار ستختار العقد الفرعية هي "10" و "+ ∞"، لذلك تقيم العقدة ب10).  الخطوة التالية، وفي المستوى الثاني، تختار الخوارزمية أكبر قيمة متوفرة في العقد الفرعية.  وتستمر الخوارزمية في تقييم الحد الأقصى والحد الأدنى لقيم العقد الفرعية بالتناوب حتى تصل إلى العقدة الرئيسية، حيث تختار الحركة ذات أكبر قيمة (ممثلة في الشكل بسهم أزرق).  لأنها الحركة التي يجب على اللاعب القيام بها لكي يضمن أقل خسارة ممكنة.

مدى الأعتماد عليها

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

في الألعاب البسيطة

علاوةً على ذلك، القيمة القصوى هي: أعلى قيمة يمكن للاعب أن يضمن الحصول عليها بغض النظر عن قرارات اللاعبين الآخرين، وأقل قيمة يمكن للاعبين الاخرين اجبار اللاعب على تلقيها، بعد معرفة قراره ويمكن توضيح ذلك بالمعادلة:

• بحيث:
• تمثل اللاعب الذي يراد جعله يربح في اللعبة
• تمثل جميع اللاعبين إلا اللاعب
• تمثل قرارات اللاعب

الفرق بين ماكس مين وميني ماكس

وفي هذا الصدد، يكمن الاختلاف في أن ميني ماكس يستعمل في ألعاب المجموع الصفري لتقليل الحد الأقصى لمكافأة الخصم.  وبما أن خسارة لاعب تساوي ربح باقي اللاعبين، فإن هذا سيؤدي للتقليل من الحد الأقصى للخسارة، وزيادة الحد الأدنى من الربح لللاعب.

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

في حالات الشك

ومن ناحية أخرى، كما تطورت الخوارزمية، لتستطسع التعامل مع الألعاب ثنائية اللاعبين التي يكون فيها الحظ، عاملاً مؤثرا.

من جانب آخر، امتد استخدام الخوارزمية ليشمل القرارات التي لا يوجد فيها أي خصم، أي عندما تعتمد عواقب القرار على أمور غير معروفة،  (مثلًا، يستلزم اتخاذ قرار التنقيب عن المعادن تكلفة ستضيع إذا لم تكن هناك معادن موجودة، ولكنها ستحقق مكاسب كبيرة إذا كانت في موقع التنقيب)، وباستخدام خوارزمية مشابهة لتلك التي ينص عليها قانون مورفي أو مقاومة الأشياء، يمكن اتباع نهج يقلل من الحد الأقصى للخسارة المتوقعة.

تمثل قرارات باقي اللاعبين

إضافةً إلى ذلك، يمكن أن يحصل اللاعب الايسر على درجة واحدة إذا لعب اللاعب الآخر T أو M ، وعلى 4 درجات إذا لعب اللاعب الآخر B لذا:

تمثل تقييم حركات اللاعب .

من جهة ثانية، المعادلة مشابهة لمعادلة القيمة القصوى ولكن مع عكس ترتيب الحد الأدنى والحد الاعلى.

وفي هذا السياق، يمكن للاعب الأيمن الحصول على قيمة قصوى قدرها 4 درجات (إذا لعب اللاعب الآخر R) أو 5 درجات (إذا لعب اللاعب الآخر L)، لذا: .

إذا لعب كلا اللاعبين أفضل حركة لديهما فستكون النتيجة هي.

ومن ناحية أخرى، القيمة الدنيا هي: أقل قيمة من الخسارة التي يمكن للاعبين الآخرين إجبار اللاعب على تلقيها بغض النظر عن القرار الذي سيتخذه ويمكن توضيح ذلك بالمعادلة:

من جهة ثانية، في الجدول يمكن للاعب الأيسر اختيار أي من الحركات الثلاث T أو M أو B الجهة اليسرى، ويمكن للاعب الأيمن اختيار أي من الحركتين، L أو R.الجهة اليمنى

علاوةً على ذلك، القيمة الدنيا لكل لاعب دائما ما تكون أكبر أو تساوي القيمة القصوى له أي أن:.

وعلى صعيد آخر، يمكن للخوارزمية أن تحسب القيمة القصوى لخسائر الاعب على أسوء الحالات عن طريق إيجاد اسوء إجراء محتمل للاعب، والتحقق من جميع الإجراءات الممكنة لباقي لاعبين واختيار اكثرها خسارة للاعب وتستمر العملية هكذا- هذه العملية تمنح اللاعب أقل قيمة- وكذلك يمكن إيجاد القيمة القصوى للربح بعكس العملية.

علاوةً على ذلك، في القيمة القصوى، يحاول اللاعب تحسين قيمة حركته قبل معرفة ما سيفعله الآخرون؛ اما في القيمة الدنيا، يعين اللاعب حركته بناء على حركات اللاعبين الاخرين، ولذلك يعد أفضل بكثير.

من هذا المثال يتضح ما يلي.

علاوةً على ذلك، يمكن للاعب الأيمن أن يلعب L ويحصل على نتيجة 0 على اسوء الأحوال (لعب R يعرضه لخطر الخسارة بمقدار 20 درجة).

ومن جهة أخرى، أفضل حركة يمكن للاعب الأيسر أن يلعبها هي الحركة T ، مما يجعله يخسر على اسوء الإحتمالات درجتين فقط (لأن الحركة B خطرة للغاية لأنها يمكن أن تؤدي إلى خسارة بقيمة 100 درجة، ويمكن أن تؤدي الحركة M إلى خسارة قدرها 10 درجات).