مينيمكس

قيمة الحد الأقصى الأدنى هي أعلى قيمة يمكن للاعب أن يضمن الحصول عليها دون معرفة تحركات اللاعبين الآخرين؛ وبصورة مكافئة، هي أدنى قيمة يمكن للاعبين الآخرين إجبار اللاعب على الحصول عليها عندما يعرفون تحركاته. تعريفها الرسمي هو: ^{[ 3 ]}

${\displaystyle {\underline {v_{i}}}=\max _{a_{i}}\min _{a_{-i}}{v_{i}(a_{i},a_{-i})}}$

أين:

• يمثل i فهرس اللاعب محل الاهتمام.
• ${\displaystyle -i}$يشير إلى جميع اللاعبين الآخرين باستثناء اللاعب i .
• ${\displaystyle a_{i}}$هو الإجراء الذي اتخذه اللاعب i .
• ${\displaystyle a_{-i}}$يشير إلى الإجراءات التي اتخذها جميع اللاعبين الآخرين.
• ${\displaystyle v_{i}}$هي دالة القيمة للاعب i .

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

على سبيل المثال، لنفترض اللعبة التالية للاعبين، حيث يمكن للاعب الأول ("لاعب الصف") اختيار أي من ثلاث حركات، مُعَلَّمة بـ T أو M أو B ، ويمكن للاعب الثاني ("لاعب العمود") اختيار أي من حركتين، L أو R. وتُوضَّح نتيجة الجمع بين الحركتين في جدول العوائد.

${\displaystyle {\begin{array}{c|cc}\hline &L&R\\\hline T&3,1&2,-20\\M&5,0&-10,1\\B&-100,2&4,4\\\hline \end{array}}}$

(حيث يمثل الرقم الأول في كل خلية المبلغ المدفوع للاعب الصف، ويمثل الرقم الثاني المبلغ المدفوع للاعب العمود).

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

• يمكن للاعب الصف أن يلعب ورقة T ، مما يضمن له ربحًا لا يقل عن2 (يُعتبر لعب الخيار ب محفوفًا بالمخاطر لأنه قد يؤدي إلى ربح)-100 ، ويمكن أن يؤدي لعب M إلى عائد قدره-10 ). ومن ثم:${\displaystyle {\underline {v_{row}}}=2}$.
• يمكن للاعب العمود أن يلعب L ويحصل على عائد لا يقل عن0 (يعرضهم لعب R لخطر الإصابة${\displaystyle -20}$). لذلك:${\displaystyle {\underline {v_{col}}}=0}$.

إذا لعب كلا اللاعبين استراتيجيات الحد الأقصى الخاصة بهما${\displaystyle (T,L)}$متجه العائد هو${\displaystyle (3,1)}$.

قيمة الحد الأدنى الأقصى للاعب هي أصغر قيمة يمكن للاعبين الآخرين إجبار اللاعب على الحصول عليها، دون معرفة تحركاته؛ أو بعبارة أخرى، هي أكبر قيمة يمكن للاعب التأكد من الحصول عليها عندما يعرف تحركات اللاعبين الآخرين. تعريفها الرسمي هو: ^{[ 3 ]}

${\displaystyle {\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}}$

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

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

لكل لاعب i ، فإن القيمة القصوى الدنيا هي على الأكثر القيمة الدنيا القصوى:

${\displaystyle {\underline {v_{i}}}\leq {\overline {v_{i}}}}$

بشكل بديهي، في خوارزمية ماكسيمين، تأتي عملية التعظيم بعد عملية التصغير، لذلك يحاول اللاعب i تعظيم قيمته قبل معرفة ما سيفعله الآخرون؛ أما في خوارزمية مينيمكس، فتأتي عملية التعظيم قبل عملية التصغير، لذلك يكون اللاعب i في وضع أفضل بكثير - فهو يعظم قيمته بمعرفة ما فعله الآخرون.

هناك طريقة أخرى لفهم الترميز وهي القراءة من اليمين إلى اليسار: عندما نكتب

${\displaystyle {\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}=\min _{a_{-i}}{\Big (}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}{\Big )}}$

المجموعة الأولية من النتائج${\displaystyle \ v_{i}(a_{i},a_{-i})\ }$يعتمد على كليهما${\displaystyle \ {a_{i}}\ }$و${\displaystyle \ {a_{-i}}\ .}$نقوم أولاً بتهميش الآخرين${\displaystyle {a_{i}}}$من${\displaystyle v_{i}(a_{i},a_{-i})}$، من خلال تحقيق أقصى قدر من${\displaystyle \ {a_{i}}\ }$(لكل قيمة ممكنة لـ${\displaystyle {a_{-i}}}$) لإنتاج مجموعة من النتائج الهامشية${\displaystyle \ v'_{i}(a_{-i})\,,}$والذي يعتمد فقط على${\displaystyle \ {a_{-i}}\ .}$ثم نقوم بتقليلها إلى الحد الأدنى${\displaystyle \ {a_{-i}}\ }$على هذه النتائج. (والعكس صحيح بالنسبة للحد الأدنى الأقصى).

على الرغم من أن الأمر دائمًا هو${\displaystyle \ {\underline {v_{row}}}\leq {\overline {v_{row}}}\ }$و${\displaystyle \ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,}$متجه العائد الناتج عن لعب كلا اللاعبين لاستراتيجيات الحد الأدنى الأقصى الخاصة بهما،${\displaystyle \ (2,-20)\ }$في حالة${\displaystyle \ (T,R)\ }$أو${\displaystyle (-10,1)}$في حالة${\displaystyle \ (M,R)\,,}$لا يمكن تصنيفها بالمثل مقابل متجه العائد${\displaystyle \ (3,1)\ }$نتيجةً لتطبيق كلا اللاعبين لاستراتيجية الحد الأقصى الأدنى.

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

في سياق ألعاب المجموع الصفري، فإن نظرية المينيماكس تعادل ما يلي: ^{[ 4 ]}

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

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

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

بمعنى آخر،  تضمن استراتيجية اللاعب الأول له ربحًا قدره V بغض النظر عن  استراتيجية اللاعب الثاني، وبالمثل،  يضمن اللاعب الثاني لنفسه ربحًا قدره -V . يُطلق على هذه الاستراتيجية اسم "مينيماكس" لأن كل لاعب يُقلل من أقصى ربح ممكن للآخر - وبما أن اللعبة ذات مجموع صفري، فإنهم يُقللون أيضًا من أقصى خسارة ممكنة لأنفسهم (أي يُعظمون أدنى ربح ممكن). انظر أيضًا مثالًا على لعبة بدون قيمة .

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

بعض الخيارات يهيمن عليها خيارات أخرى ويمكن استبعادها: لن يختار أ الخيار أ3 لأن الخيار أ1 أو أ2 سينتج نتيجة أفضل، بغض النظر عما يختاره ب ؛ ولن يختار ب الخيار ب 3 لأن بعض الخلطات بين ب1 وب2 ستنتج نتيجة أفضل، بغض النظر عما يختاره أ .

يمكن للاعب أ تجنب دفع مبلغ متوقع يزيد عن 1/3 باختيار A1 باحتمالية 1/6 و A2 باحتمالية 5/6 : سيكون العائد المتوقع للاعب أ هو 3 × 1/6 - 1 × 5/6 = - + 1/3 في حالة اختيار اللاعب ب الخيار B1 ، و -2 × 1/6 + 0 × 5/6 = - + 1/3 في حالة اختيار اللاعب ب الخيار B2 .​ ​ ​​​​ وبالمثل، يمكن لـ B ضمان ربح متوقع لا يقل عن 1/3 ، بغض النظر عن اختيار A ، وذلك باستخدام استراتيجية عشوائية لاختيار B1 باحتمالية 1/3 و B2 باحتمالية 2/3 . لا يمكن تحسين استراتيجيات minimax المختلطة هذه ، وهي الآن مستقرة .

في نظرية الألعاب، غالباً ما يُفرّق بين مفهومي "ماكسيمين" و"مينيمكس". يُستخدم "مينيمكس" في ألعاب المحصلة الصفرية للدلالة على تقليل أقصى عائد للخصم. في لعبة المحصلة الصفرية ، يُعادل هذا تقليل أقصى خسارة للشخص نفسه، وتعظيم أدنى ربح له.

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

تُعدّ قيم المينيماكس ذات أهمية بالغة في نظرية الألعاب المتكررة . وتعتمد إحدى النظريات المركزية في هذه النظرية، وهي نظرية فولك ، على قيم المينيماكس.

خوارزمية مينيمكس ^{[ 5 ]} هي خوارزمية تكرارية لاختيار الحركة التالية في لعبة متعددة اللاعبين (n )، وعادةً ما تكون لعبة ثنائية اللاعبين. تُخصص قيمة لكل موضع أو حالة في اللعبة. تُحسب هذه القيمة باستخدام دالة تقييم الموضع ، وهي تُشير إلى مدى جودة وصول اللاعب إلى ذلك الموضع. بعد ذلك، يقوم اللاعب بالحركة التي تُعظم القيمة الدنيا للموضع الناتج عن الحركات التالية المُحتملة للخصم. إذا كانت Aعندما يحين دور اللاعب A في التحرك، فإنه يعطي قيمة لكل حركة قانونية يقوم بها.

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

يمكن توسيع نطاق هذا النهج إذا استطعنا توفير دالة تقييم استدلالية تُعطي قيمًا لحالات اللعبة غير النهائية دون النظر إلى جميع التسلسلات الكاملة اللاحقة الممكنة. عندئذٍ، يمكننا حصر خوارزمية المينيماكس في النظر إلى عدد محدد من النقلات المستقبلية. يُسمى هذا العدد "النظرة المستقبلية"، ويُقاس بـ " النقلات ". على سبيل المثال، نظر حاسوب الشطرنج " ديب بلو" (أول حاسوب يهزم بطل العالم آنذاك ، غاري كاسباروف  ) إلى 12 نقلة مستقبلية على الأقل، ثم طبق دالة التقييم الاستدلالية. ^{[ 6 ]}

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

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

يمكن تعديل خوارزمية minimax الساذجة بشكل بسيط لإرجاع التباين الرئيسي الكامل بالإضافة إلى درجة minimax.

يُعطى أدناه الكود الزائف لخوارزمية minimax ذات العمق المحدود.

تقوم الدالة minimax(node, depth, maximizingPlayer) بما يلي: إذا كان depth = 0 أو node عقدة طرفية، فإنها تُرجع القيمة التقريبية للعقدة. أما إذا كان maximizingPlayer، القيمة := −∞ لكل فرع من العقدة، قم بما يلي: القيمة := الحد الأقصى (القيمة، الحد الأدنى الأقصى (الفرع، العمق - 1، خطأ)) أعد القيمة وإلا (* تقليل حجم اللاعب *) القيمة := +∞ لكل فرع من العقدة، قم بما يلي: القيمة := الحد الأدنى (القيمة، الحد الأدنى الأقصى (الفرع، العمق - 1، صحيح)) القيمة المُعادة

(* الاستدعاء الأولي *) minimax(origin, depth, TRUE)

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

تتعامل خوارزمية Minimax مع اللاعبين (اللاعب الذي يسعى إلى تحقيق أقصى ربح واللاعب الذي يسعى إلى تقليل الربح) بشكل منفصل في شفرتها البرمجية. وذلك بناءً على الملاحظة التالية:${\displaystyle \ \max(a,b)=-\min(-a,-b)\ ,}$يمكن تبسيط خوارزمية minimax في كثير من الأحيان إلى خوارزمية negamax .

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

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

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

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

في نظرية القرار الإحصائي الكلاسيكية ، لدينا مُقدِّر${\displaystyle \ \delta \ }$ذلك يستخدم لتقدير المعلمة${\displaystyle \ \theta \in \Theta \ .}$نفترض أيضًا وجود دالة مخاطرة${\displaystyle \ R(\theta ,\delta )\ .}$يُحدد عادةً على أنه تكامل دالة الخسارة . في هذا الإطار،${\displaystyle \ {\tilde {\delta }}\ }$يُطلق عليه اسم minimax إذا كان يحقق الشروط التالية:

${\displaystyle \sup _{\theta }R(\theta ,{\tilde {\delta }})=\inf _{\delta }\ \sup _{\theta }\ R(\theta ,\delta )\ .}$

يُعدّ مُقدِّر بايز في وجود توزيع مسبق معيارًا بديلًا في إطار نظرية القرار.${\displaystyle \Pi \ .}$يكون المُقدِّر بايزيًا إذا قلل من متوسط ​​المخاطرة

${\displaystyle \int _{\Theta }R(\theta ,\delta )\ \operatorname {d} \Pi (\theta )\ .}$

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

علاوة على ذلك، لا يتطلب تحليل المينيماكس سوى القياس الترتيبي (أي مقارنة النتائج وترتيبها)، وليس القياسات الفاصلية (أي أن النتائج تتضمن "مدى التحسن أو التدهور")، ويعيد بيانات ترتيبية باستخدام النتائج المُنمذجة فقط: خلاصة تحليل المينيماكس هي: "هذه الاستراتيجية هي المينيماكس، لأن أسوأ حالة هي (النتيجة)، وهي أقل سوءًا من أي استراتيجية أخرى". قارن ذلك بتحليل القيمة المتوقعة، الذي تكون خلاصته على النحو التالي: "هذه الاستراتيجية تُعطي ℰ ( X ) = n ". بالتالي، يمكن استخدام المينيماكس مع البيانات الترتيبية، ويمكن أن يكون أكثر شفافية.