خوارزمية Min Max في الذكاء الاصطناعي: المكونات والخصائص والمزايا والقيود

تعد خوارزمية min max في الذكاء الاصطناعي ، والمعروفة باسم minimax ، خوارزمية رجعية تستخدم في صنع القرار ونظرية الألعاب والذكاء الاصطناعي (AI). يتم استخدامه للعثور على الحركة المثلى للاعب ، بافتراض أن الخصم يلعب أيضًا على النحو الأمثل. تستخدم هذه الخوارزمية على أجهزة الكمبيوتر ثنائية اللاعبين أو الألعاب عبر الإنترنت مثل Chess و Tic-Tac-Toe و Checkers و Go وما إلى ذلك.

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

كيف يعمل؟

في خوارزمية min max في AI ، هناك لاعبان ، Maximiser و Minimiser. يلعب هذان اللاعبان اللعبة حيث يحاول المرء الحصول على أعلى درجة ممكنة أو أقصى فائدة بينما يحاول الخصم الحصول على أقل درجة أو أدنى فائدة.

تحتوي كل لوحة لعبة على درجة تقييم مخصصة لها ، لذلك سيحدد Maximiser القيمة القصوى ، وسيحدد Minimiser القيمة المصغرة مع التحركات العكسية. إذا كان لـ Maximiser اليد العليا ، فستكون نتيجة اللوحة قيمة موجبة ، وإذا كان Minimiser له اليد العليا ، فستكون نتيجة اللوحة قيمة سالبة.

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

انضم إلى دورات شهادة التعلم الآلي والذكاء الاصطناعي عبر الإنترنت من أفضل الجامعات في العالم. اربح درجة الماجستير أو PGP التنفيذي أو ACP لتتبع حياتك المهنية بشكل سريع.

تحطيم خوارزمية min max في AI

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

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

مصدر

شجرة اللعبة أعلاه عبارة عن بنية بيانات متداخلة تُستخدم لتقييم الحركات. هنا تكون العقدة الجذرية هي المستوى 0 ، والتي تتفرع إلى المستوى 1 أو العقد الأصلية ، والتي تتفرع إلى المستوى 2 أو العقد الفرعية. يمكن أن يستمر التفرع إلى مستويات عديدة ، مع وجود إمكانات المستويات اللانهائية. المستوى 0 يشبه الحالة الحالية للوحة ، بينما المستوى 1 هو جميع الحالات الممكنة للوحات اعتمادًا على الخطوة التالية.

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

ضع في اعتبارك مثالًا حيث توجد أربع حالات نهائية ويكون المسار للوصول إليها من الجذر إلى الأوراق الأربعة للشجرة. قيم الأوراق الأربعة هي 3 و 6 على اليسار و 4 و 7 على اليمين. حان دور Maximiser / Player 1 للقيام بخطوة. للتشغيل من خلال الخوارزمية ، يجب وضع افتراضات لكل خطوة.

إذا اختار اللاعب 1 أن يتجه إلى اليسار ، فيجب أن يختار Minimiser / Player 2 الأقل بين 3 و 6 ، وبالتالي سيختارون 3. بينما إذا اختار اللاعب 1 حقًا ، فسيختار اللاعب 2 4 ، وهو الحد الأدنى من القيمتين ، 4 و 7. إذن ، المستوى 1 يحتوي الآن على القيمتين 3 و 4.

نظرًا لأنه جاء دور Player 1 / Maximiser ، فعليهم اختيار الحد الأقصى من عقد المستوى 1. وبالتالي ، سيختارون 3. ثم الخيار الأمثل هو الذهاب يسارًا.

يمكن تحديد خطوات خوارزمية min max في الذكاء الاصطناعي على النحو التالي:

1. قم بإنشاء شجرة اللعبة بأكملها.
2. قم بتقييم الدرجات للعقد الطرفية بناءً على وظيفة التقييم.
3. التراجع من الورقة إلى العقد الجذرية:

بالنسبة لـ Maximizer ، اختر العقدة ذات الدرجة القصوى.

بالنسبة لـ Minimizer ، اختر العقدة ذات الحد الأدنى من النقاط.

4. في عقدة الجذر ، اختر العقدة ذات القيمة القصوى وحدد الحركة المعنية.

اقرأ أيضًا: أفكار مشروع التعلم الآلي

خصائص خوارزمية min max في AI

• الخوارزمية كاملة ، مما يعني أنه في شجرة بحث محدودة ، سيتم العثور على حل بالتأكيد.
• من الأفضل أن يلعب كلا اللاعبين بالشكل الأمثل.
• نظرًا لبحث Depth-First Search (DFS) لشجرة اللعبة ، فإن التعقيد الزمني للخوارزمية هو O (b m ) ، حيث b هو عامل التفرع و m هو أقصى عمق للشجرة.
• مثل DFS ، فإن التعقيد المكاني لهذه الخوارزمية هو O (bm).

مزايا

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

محددات

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

ولكن مع Alpha-Beta Pruning ، يمكن تحسين الخوارزمية.

خاتمة

تشرح هذه المقالة جميع جوانب خوارزمية min-max في AI. أولاً ، يتم تقديم مقدمة للنظرية بأمثلة عن مكان استخدامها ، وبعد ذلك يوجد وصف لكيفية عمل الخوارزمية في اللعبة.

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

إذا كنت مهتمًا بمعرفة المزيد عن التعلم الآلي ، فراجع برنامج IIIT-B & upGrad's Executive PG في التعلم الآلي والذكاء الاصطناعي المصمم للمهنيين العاملين ويقدم أكثر من 450 ساعة من التدريب الصارم ، وأكثر من 30 دراسة حالة ومهمة ، IIIT -ب حالة الخريجين ، 5+ مشاريع التخرج العملية العملية والمساعدة في العمل مع الشركات الكبرى.