بحث عن السكون

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
الموسوعة الحرة

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

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

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

تأثير الأفق

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

الشفرة الزائفة

يوضح هذا الكود الزائف المفهوم خوارزميًا:

دالة quiescence_search(node, (اختياري) depth) تقوم بما يلي: إذا كانت العقدة هادئة أو كانت عقدة طرفية أو كان العمق يساوي صفرًا، فإنها تُرجع القيمة المُقدَّرة للعقدة. وإلا ، فإنها ( تبحث بشكل متكرر عن أبناء العقدة باستخدام quiescence_search) تُرجع القيمة المُقدَّرة للأبناء. تقوم الدالة normal_search(node, depth) بما يلي: إذا كانت node عقدة طرفية، تُرجع القيمة المُقدَّرة للعقدة. أما إذا كانت depth = 0 ، فإذا بدت العقدة هادئة ، تُرجع القيمة المُقدَّرة للعقدة . وإلا، تُرجع القيمة المُقدَّرة من الدالة quiescence_search(node, reasonable_depth_value). وإلا ، (يتم البحث بشكل متكرر عن أبناء العقدة باستخدام normal_search) تُرجع القيمة المُقدَّرة للأبناء.

مراجع