ميني ماكس

ميني ماكس (بالإنجليزية: minimax)‏وتختصر أحيانا بMM كما تسمى بنقطة الاختيار هي خوارزمية رياضية مستخدمة في الذكاء الاصطناعي، ونظرية القرار، ونظرية الألعاب، والإحصاءات، والفلسفة وحساب الأحتمالات تقوم بحساب كافة الاحتمالات المتوفرة لأختيار أفضلها من ناحية المكسب، وتعمل الخوارزمية على تقييم كل الحالات التي يتخذ فيها اللاعبون حركات بديلة وتلك التي يقومون فيها بحركات متزامنة، كما توسعت هذه الخوارزمية لتشمل ألعابًا أكثر تعقيدًا كالشطرنج واتخاذ القرارات في حالات الشك بوجود حركات أفضل وطُبِقَت هذه النظرية في شطرنج الحاسوب

ويعني الأسم - إيجاد الحد الأعلى من الربح-. ووضع في الأصل من اجل تحليل نظرية المجموع الصفري في الألعاب.

أساسيات النظرية

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

القيمة القصوى هي: أعلى قيمة يمكن للاعب أن يضمن الحصول عليها بغض النظر عن قرارات اللاعبين الآخرين، وأقل قيمة يمكن للاعبين الاخرين اجبار اللاعب على تلقيها، بعد معرفة قراره ويمكن توضيح ذلك بالمعادلة: $\underset{\_}{v_i}={max}_{a_i}{min}_{a_{-i}}{v}_i(a_i,a_{-i})$ بحيث:

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

$a_{-i}$ تمثل قرارات باقي اللاعبين

• $v_i$ تمثل تقييم حركات اللاعب i.

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

	L	R
T	3,1	2,-20
M	5,0	-10,1
B	-100,2	4,4

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

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

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

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

إذا لعب كلا اللاعبين أفضل حركة لديهما $(T,L)$ فستكون النتيجة هي$(3,1)$.

القيمة الدنيا هي: أقل قيمة من الخسارة التي يمكن للاعبين الآخرين إجبار اللاعب على تلقيها بغض النظر عن القرار الذي سيتخذه ويمكن توضيح ذلك بالمعادلة: $\overline{v_i}={min}_{a_{-i}}{max}_{a_i}{v}_i(a_i,a_{-i})$

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

• يمكن للاعب الأيمن الحصول على قيمة قصوى قدرها 4 درجات (إذا لعب اللاعب الآخر R) أو 5 درجات (إذا لعب اللاعب الآخر L)، لذا: $\overline{v_{row}}=4$.
• يمكن أن يحصل اللاعب الايسر على درجة واحدة إذا لعب اللاعب الآخر T أو M ، وعلى 4 درجات إذا لعب اللاعب الآخر B لذا:$\overline{v_{col}}=1$

القيمة الدنيا لكل لاعب دائما ما تكون أكبر أو تساوي القيمة القصوى له أي أن:$\underset{\_}{v_i}\le \overline{v_i}$.

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

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

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

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

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

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

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

يمثل الجدول نقاط المكافئة بالنسبة لللاعب أ

	ب اختار B1	ب اختار B2	ب اختار B3
أ أختار A1	+3	−2	+2
أ اختار A2	−1	0	+4
أ أختار A3	−4	−3	+1

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

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

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

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

يمكن أن يتجنب اللاعب 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 بـ +1 والحركة B بـ -1.  وهذا قد يؤدي إلى نظرية اللعبة الاندماجية. 

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

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

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

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

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

أمثلة

مثال على شجرة مينيماكس

مثال تعليمي متحرك بسيط من استبدلت فيه القيم اللانهائية بقيم صغيرة للتبسيط.

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

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

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

في حالات الشك

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

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

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

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

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

في الفلسفة

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