بحث الخصومة هو بحث، حيث نقوم بفحص المشكلة التي تنشأ عندما نحاول التخطيط مسبقًا للعالم ويخطط عملاء آخرون ضدنا.
إيبكنفيغ لأوبونتو
- لقد قمنا في المواضيع السابقة بدراسة استراتيجيات البحث التي ترتبط فقط بعامل واحد يهدف إلى إيجاد الحل والذي غالباً ما يتم التعبير عنه في شكل سلسلة من الإجراءات.
- ولكن، قد تكون هناك بعض المواقف التي يبحث فيها أكثر من وكيل عن الحل في نفس مساحة البحث، ويحدث هذا الموقف عادةً أثناء اللعب.
- تسمى البيئة التي بها أكثر من عامل بيئة متعددة الوكيل حيث يكون كل وكيل خصمًا لوكيل آخر ويلعب ضد بعضهم البعض. يحتاج كل وكيل إلى النظر في تصرفات الوكيل الآخر وتأثير هذا الإجراء على أدائه.
- لذا، عمليات البحث التي يحاول فيها لاعبان أو أكثر بأهداف متعارضة استكشاف نفس مساحة البحث للحل، تسمى عمليات البحث العدائية، والمعروفة غالبًا باسم الألعاب .
- تم تصميم الألعاب على أنها مشكلة بحث ووظيفة تقييم إرشادي، وهما العاملان الرئيسيان اللذان يساعدان في تصميم الألعاب وحلها في الذكاء الاصطناعي.
أنواع الألعاب في الذكاء الاصطناعي:
حتمية | تحركات الفرصة | |
---|---|---|
معلومات مثالية | الشطرنج، لعبة الداما، اذهب، عطيل | لعبة الطاولة والاحتكار |
معلومات غير كاملة | البوارج، العمياء، تيك تاك تو | الجسر، البوكر، الخربشة، الحرب النووية |
على سبيل المثال: لعبة الطاولة، الاحتكار، البوكر، إلخ.
ملاحظة: في هذا الموضوع، سنناقش الألعاب الحتمية، والبيئة التي يمكن ملاحظتها بالكامل، والمجموع الصفري، وأين يتصرف كل وكيل بالتناوب.
لعبة محصلتها صفر
- الألعاب ذات المحصلة الصفرية هي عبارة عن بحث عدائي يتضمن منافسة خالصة.
- في لعبة المجموع الصفري، يتم موازنة مكسب أو خسارة منفعة كل وكيل تمامًا مع خسائر أو مكاسب منفعة وكيل آخر.
- يحاول أحد اللاعبين في اللعبة تعظيم قيمة واحدة، بينما يحاول لاعب آخر تقليلها.
- تسمى كل حركة يقوم بها لاعب واحد في اللعبة بالطبقة.
- تعتبر لعبة الشطرنج وتيك تاك تو من الأمثلة على لعبة محصلتها صفر.
لعبة محصلتها صفر: التفكير المدمج
تتضمن لعبة المحصلة الصفرية تفكيرًا مضمنًا يحاول فيه أحد العملاء أو اللاعبين اكتشاف ما يلي:
- ما يجب القيام به.
- كيفية تحديد هذه الخطوة
- يحتاج إلى التفكير في خصمه أيضًا
- يفكر الخصم أيضًا في ما يجب فعله
يحاول كل لاعب معرفة رد فعل خصمه على أفعاله. يتطلب هذا تفكيرًا مضمنًا أو تفكيرًا رجعيًا لحل مشكلات اللعبة في الذكاء الاصطناعي.
إضفاء الطابع الرسمي على المشكلة:
يمكن تعريف اللعبة بأنها نوع من البحث في الذكاء الاصطناعي والذي يمكن إضفاء الطابع الرسمي عليه من العناصر التالية:
شجرة اللعبة:
شجرة اللعبة هي شجرة حيث عقد الشجرة هي حالات اللعبة وحواف الشجرة هي حركات اللاعبين. تتضمن شجرة اللعبة الحالة الأولية ووظيفة الإجراءات ووظيفة النتيجة.
مثال: شجرة ألعاب تيك تاك تو:
يوضح الشكل التالي جزءًا من شجرة اللعبة للعبة tic-tac-toe. وفيما يلي بعض النقاط الرئيسية للعبة:
- هناك لاعبان MAX وMIN.
- لدى اللاعبين دور بديل ويبدأون بـ MAX.
- يقوم MAX بتعظيم نتيجة شجرة اللعبة
- MIN يقلل من النتيجة.
شرح المثال:
- من الحالة الأولية، لدى ماكس 9 حركات محتملة عندما يبدأ أولاً. MAX مكان x و MIN مكان o، ويلعب كلا اللاعبين بالتناوب حتى نصل إلى عقدة ورقية حيث يكون لدى لاعب واحد ثلاثة على التوالي أو يتم ملء جميع المربعات.
- سيقوم كلا اللاعبين بحساب كل عقدة، الحد الأدنى، قيمة الحد الأدنى التي تعد أفضل فائدة يمكن تحقيقها ضد الخصم الأمثل.
- لنفترض أن كلا اللاعبين يدركان جيدًا لعبة tic-tac-toe ويلعبان أفضل لعبة. يبذل كل لاعب قصارى جهده لمنع لاعب آخر من الفوز. مين يتصرف ضد ماكس في اللعبة.
- لذا، في شجرة اللعبة، لدينا طبقة Max، وطبقة MIN، وكل طبقة تسمى باسم رقائق . Max place x، ثم يضع MIN o لمنع Max من الفوز، وتستمر هذه اللعبة حتى العقدة الطرفية.
- في هذا إما أن يفوز MIN، أو MAX، أو يتم التعادل. شجرة اللعبة هذه هي مساحة البحث الكاملة عن احتمالات أن يلعب MIN وMAX لعبة tic-tac-toe ويتناوبان.
ومن ثم فإن البحث الخصومي عن إجراء الحد الأدنى يعمل على النحو التالي:
- ويهدف إلى إيجاد الإستراتيجية المثالية لـ MAX للفوز باللعبة.
- وهو يتبع نهج البحث العمق الأول.
- في شجرة اللعبة، يمكن أن تظهر العقدة الورقية المثالية في أي عمق للشجرة.
- قم بنشر قيم الحد الأدنى إلى الشجرة حتى يتم اكتشاف العقدة الطرفية.
في شجرة ألعاب معينة، يمكن تحديد الإستراتيجية المثالية من الحد الأدنى لقيمة كل عقدة، والتي يمكن كتابتها كـ MINIMAX(n). يفضل MAX الانتقال إلى حالة القيمة القصوى ويفضل MIN الانتقال إلى حالة القيمة الدنيا ثم: