توقع الحد الأدنى

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

في طريقة مينيمكس التقليدية ، تتناوب مستويات الشجرة بين الحد الأقصى والحد الأدنى حتى الوصول إلى الحد الأقصى لعمق الشجرة. أما في شجرة إكسبكتيمينيمكس، فتتداخل عقد "الاحتمال" مع عقد الحد الأقصى والحد الأدنى. وبدلاً من أخذ الحد الأقصى أو الأدنى لقيم المنفعة لأبنائها، تأخذ عقد الاحتمال متوسطًا مرجحًا، حيث يمثل الوزن احتمال الوصول إلى ذلك الابن. ^{[ 1 ]}

يعتمد التداخل على اللعبة. يتم تقييم كل "دور" في اللعبة كعقدة "قصوى" (تمثل دور اللاعب الذي يتحكم به الذكاء الاصطناعي)، أو عقدة "دنيا" (تمثل دور الخصم الأمثل المحتمل)، أو عقدة "احتمالية" (تمثل تأثيرًا عشوائيًا أو لاعبًا عشوائيًا). ^{[ 1 ]}

على سبيل المثال، لنفترض لعبة تتكون كل جولة فيها من رمية نرد واحدة، ثم قرارات يتخذها أولاً اللاعب الذي يتحكم به الذكاء الاصطناعي، ثم خصم ذكي آخر. يتناوب ترتيب العقد في هذه اللعبة بين "الفرصة" و"الحد الأقصى" ثم "الحد الأدنى". ^{[ 1 ]}

خوارزمية expectiminimax هي نوع من خوارزمية minimax وقد اقترحها دونالد ميتشي لأول مرة في عام 1966. ^{[ 2 ]} يتم تقديم رمزها الزائف أدناه.

دالة expectiminimax(node, depth) تُرجع القيمة التقريبية للعقدة node إذا كان الخصم سيلعب عندها، وذلك في حال كانت node عقدة طرفية أو كان depth = 0.  // القيمة المُعادة للعقدة الفرعية ذات القيمة الدنيا ليكن α := +∞ لكل ابن من أبناء العقدة α := min(α, expectiminimax(child, depth-1)) وإلا إذا كنا سنلعب عند العقدة // القيمة المُعادة للعقدة الفرعية ذات القيمة القصوى ليكن α := -∞ لكل ابن من أبناء العقدة α := max(α, expectiminimax(child, depth-1)) وإلا إذا حدث حدث عشوائي عند العقدة // إرجاع المتوسط ​​المرجح لقيم جميع العقد الفرعية ليكن α := 0 لكل ابن من أبناء العقدة α := α + (الاحتمالية[الفرع] × توقع الحد الأدنى الأقصى(الفرع، العمق-1)) إرجاع α

لاحظ أنه بالنسبة للعقد العشوائية، يجب أن تكون هناك احتمالية معروفة للوصول إلى كل عقدة فرعية. (في معظم ألعاب الحظ، تكون العقد الفرعية متساوية الوزن، مما يعني أن القيمة المُعادة يمكن أن تكون ببساطة متوسط ​​جميع قيم العقد الفرعية).

يُعد بحث Expectimax أحد المتغيرات الموصوفة في كتاب Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability (2005) من تأليف توم إيفريت وماركوس هوتر .

كان بروس بالارد أول من طور تقنية تُسمى *-minimax، تُتيح تقليم ألفا-بيتا في أشجار expectiminimax. ^{[ 3 ] [ 4 ]} تكمن مشكلة دمج تقليم ألفا-بيتا في خوارزمية expectiminimax في أن درجات أبناء عقدة الاحتمال قد تتجاوز حد ألفا أو بيتا لعقدة الأصل، حتى لو لم تتجاوز القيمة المرجحة لكل ابن هذا الحد. مع ذلك، من الممكن تحديد حد لدرجات أبناء عقدة الاحتمال، وبالتالي تحديد حد لدرجة عقدة الاحتمال نفسها.

إذا كانت عملية البحث التكراري القياسية على وشك أن تُحسب النتيجة${\displaystyle i}$الابن رقم 1 لعقدة احتمالية مع${\displaystyle N}$الأطفال الذين لديهم احتمالية متساوية، وقد حسبت تلك الدراسة النتائج${\displaystyle v_{1},v_{2},\ldots ,v_{i-1}}$للعقد الفرعية من 1 إلى${\displaystyle i-1}$بافتراض الحصول على أدنى درجة ممكنة${\displaystyle L}$وأعلى درجة ممكنة${\displaystyle U}$بالنسبة لكل طفل لم يتم البحث عنه، تكون حدود درجة عقدة الاحتمال كما يلي:

${\displaystyle {\text{score}}\leq {\frac {1}{n}}\left((v_{1}+\ldots +v_{i-1})+v_{i}+U\times (ni)\right)}$

${\displaystyle {\text{score}}\geq {\frac {1}{n}}\left((v_{1}+\ldots +v_{i-1})+v_{i}+L\times (ni)\right)}$

إذا تم تحديد حد ألفا و/أو بيتا في حساب نقاط عقدة الاحتمال، فيمكن استخدام هذه الحدود لقطع البحث عن${\displaystyle i}$الطفل رقم 1. يمكن إعادة ترتيب المعادلات أعلاه لإيجاد قيمة جديدة لـ α و β من شأنها أن توقف البحث إذا تسببت في تجاوز عقدة الاحتمال لحدود α و β الخاصة بها:

${\displaystyle \alpha _{i}=N\times \alpha -\left(v_{1}+\ldots +v_{i-1}\right)+U\times (ni)}$

${\displaystyle \beta _{i}=N\times \beta -\left(v_{1}+\ldots +v_{i-1}\right)+L\times (ni)}$

فيما يلي الشفرة الزائفة لتوسيع خوارزمية expectiminimax مع تقليم ألفا-بيتا المقاوم للفشل بهذه الطريقة:

دالة *-minimax(node, depth, α, β) إذا كانت node عقدة طرفية أو depth = 0، تُرجع القيمة التقريبية للعقدة. إذا كانت node عقدة قصوى أو دنيا، تُرجع قيمة minimax للعقدة. let N = numSuccessors(node) // حساب α، β للأطفال ليكن A = N * (α - U) + U، وليكن B = N * (β - L) + L، وليكن المجموع = 0 لكل ابن من أبناء العقدة // حصر نطاق العناصر الفرعية α و β ضمن نطاق صالح ليكن AX = max(A, L) وليكن BX = min(B, U) // ابحث عن الطفل باستخدام قيم القطع الجديدة let score = *-minimax(child, depth - 1, AX, BX) // تحقق من شروط القطع α و β إذا كانت النتيجة أقل من أو تساوي A، فأرجع α. إذا كانت النتيجة أكبر من أو تساوي B، فأرجع β. المجموع += النتيجة // اضبط قيمتي α و β للطفل التالي أ += يو - في B += L - v // لم يحدث قطع، يتم إرجاع النتيجة مجموع الإرجاع / N

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

• مينيمكس
• تقليم ألفا-بيتا
• نيغاماكس
• القيمة المتوقعة