logo

بحث عدائي

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

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

أنواع الألعاب في الذكاء الاصطناعي:

حتمية تحركات الفرصة
معلومات مثالية الشطرنج، لعبة الداما، اذهب، عطيل لعبة الطاولة والاحتكار
معلومات غير كاملة البوارج، العمياء، تيك تاك تو الجسر، البوكر، الخربشة، الحرب النووية
    معلومات مثالية:اللعبة التي تحتوي على المعلومات المثالية هي تلك التي يمكن للوكلاء من خلالها الاطلاع على اللوحة الكاملة. يمتلك الوكلاء جميع المعلومات حول اللعبة، ويمكنهم أيضًا رؤية تحركات بعضهم البعض. ومن الأمثلة على ذلك الشطرنج، لعبة الداما، الذهاب، الخ.معلومات غير كاملة:إذا لم يكن لدى الوكلاء في إحدى الألعاب جميع المعلومات حول اللعبة وليسوا على دراية بما يحدث، فإن هذا النوع من الألعاب يُسمى باللعبة ذات المعلومات غير الكاملة، مثل tic-tac-toe، وBattleship، وblind، وBridge، وما إلى ذلك.الألعاب الحتمية:الألعاب الحتمية هي تلك الألعاب التي تتبع نمطًا صارمًا ومجموعة من القواعد للألعاب، ولا توجد عشوائية مرتبطة بها. ومن الأمثلة على ذلك الشطرنج، لعبة الداما، الذهاب، تيك تاك تو، الخ.الألعاب غير الحتمية:الألعاب غير الحتمية هي تلك الألعاب التي تحتوي على العديد من الأحداث غير المتوقعة ولها عامل الصدفة أو الحظ. يتم تقديم عامل الصدفة أو الحظ هذا إما عن طريق النرد أو البطاقات. هذه عشوائية، ولم يتم إصلاح كل استجابة عمل. تسمى هذه الألعاب أيضًا بالألعاب العشوائية.
    على سبيل المثال: لعبة الطاولة، الاحتكار، البوكر، إلخ.

ملاحظة: في هذا الموضوع، سنناقش الألعاب الحتمية، والبيئة التي يمكن ملاحظتها بالكامل، والمجموع الصفري، وأين يتصرف كل وكيل بالتناوب.

لعبة محصلتها صفر

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

لعبة محصلتها صفر: التفكير المدمج

تتضمن لعبة المحصلة الصفرية تفكيرًا مضمنًا يحاول فيه أحد العملاء أو اللاعبين اكتشاف ما يلي:

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

يحاول كل لاعب معرفة رد فعل خصمه على أفعاله. يتطلب هذا تفكيرًا مضمنًا أو تفكيرًا رجعيًا لحل مشكلات اللعبة في الذكاء الاصطناعي.

إضفاء الطابع الرسمي على المشكلة:

يمكن تعريف اللعبة بأنها نوع من البحث في الذكاء الاصطناعي والذي يمكن إضفاء الطابع الرسمي عليه من العناصر التالية:

    الحالة الأولية:وهو يحدد كيفية إعداد اللعبة في البداية.اللاعب (اللاعبين):يحدد اللاعب الذي انتقل في مساحة الدولة.أجراءات):تقوم بإرجاع مجموعة التحركات القانونية في مساحة الدولة.النتيجة (النتائج، أ):وهو النموذج الانتقالي الذي يحدد نتيجة التحركات في فضاء الحالة.اختبار (اختبارات) المحطة الطرفية:يكون الاختبار النهائي صحيحًا إذا انتهت اللعبة، وإلا فهو خطأ على أي حال. الحالة التي تنتهي فيها اللعبة تسمى الحالات النهائية.المنفعة (الأدوات، ع):توفر وظيفة الأداة المساعدة القيمة الرقمية النهائية للعبة التي تنتهي بالحالات الطرفية s للاعب p. وتسمى أيضًا وظيفة الدفع. بالنسبة للشطرنج، النتائج هي الفوز أو الخسارة أو التعادل وقيم المردود هي +1، 0، ½. وبالنسبة لـ tic-tac-toe، تكون قيم المنفعة هي +1 و-1 و0.

شجرة اللعبة:

شجرة اللعبة هي شجرة حيث عقد الشجرة هي حالات اللعبة وحواف الشجرة هي حركات اللاعبين. تتضمن شجرة اللعبة الحالة الأولية ووظيفة الإجراءات ووظيفة النتيجة.

مثال: شجرة ألعاب تيك تاك تو:

يوضح الشكل التالي جزءًا من شجرة اللعبة للعبة 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 الانتقال إلى حالة القيمة الدنيا ثم:

بحث عدائي