البحث التنافسي ولعب الألعاب
البحث التنافسي هو دراسة اتخاذ القرار في البيئات التنافسية، حيث يجب على الوكيل اختيار حركات في شجرة اللعبة ضد خصم يحاول تحقيق نتيجة معاكسة.
Definition
يحسب البحث التنافسي حركة للاعب من خلال استكشاف شجرة اللعبة التي يتناوب فيها اللاعبون الأدوار، باستخدام مبدأ المينيماكس (كل لاعب يحسن افتراضًا أن الخصم يلعب بشكل أمثل) جنبًا إلى جنب مع التقليم والتقييم الاستدلالي للتعامل مع الأشجار الكبيرة.
Scope
يغطي هذا الموضوع البحث في الألعاب ثنائية اللاعبين، ذات المجموع الصفري، والمعلومات الكاملة: قاعدة قرار المينيماكس (minimax)، وتقليم ألفا-بيتا (alpha-beta pruning) الذي يسمح للمينيماكس بتجاوز الفروع غير ذات الصلة بشكل مؤكد، ودوال التقييم (evaluation functions) والبحث محدود العمق (depth-limited search) للألعاب الكبيرة جدًا بحيث لا يمكن حلها بدقة، وبحث شجرة مونت كارلو (Monte Carlo tree search) للألعاب ذات عوامل التفرع الكبيرة جدًا. يتناول هذا الموضوع كيفية نمذجة أشجار اللعبة وكيف تجبر القيود الحسابية على استخدام قطع استدلالي (heuristic cut-offs). لا يغطي هذا الموضوع تحليل التوازن العام لنظرية الألعاب للحوافز متعددة الوكلاء، والذي يتم تناوله ضمن أنظمة الوكلاء المتعددين.
Core questions
- كيف تحدد قاعدة المينيماكس الحركة المثلى ضد خصم أمثل؟
- كيف يزيل تقليم ألفا-بيتا الفروع دون التأثير على قيمة المينيماكس؟
- كيف تُستخدم دوال التقييم لقطع البحث عند عمق ثابت في الألعاب الكبيرة؟
- متى يكون بحث شجرة مونت كارلو مفضلاً على المينيماكس محدود العمق؟
Key concepts
- شجرة اللعبة
- قيمة المينيماكس
- تقليم ألفا-بيتا
- دالة التقييم (الاستدلالية)
- البحث محدود العمق وتأثير الأفق
- ألعاب المجموع الصفري والمعلومات الكاملة
- بحث شجرة مونت كارلو
- ترتيب الحركات
Key theories
- قاعدة قرار المينيماكس
- في لعبة ثنائية اللاعبين ذات مجموع صفري، يختار كل لاعب الحركة التي تزيد من الحد الأدنى لنتائجه المضمونة؛ يؤدي نشر قيم الحد الأقصى/الأدنى هذه إلى أعلى شجرة اللعبة إلى الحركة المثلى عند الجذر.
- تقليم ألفا-بيتا
- من خلال تتبع أفضل القيم المضمونة بالفعل للاعبين الذين يسعون للتعظيم والتقليل، يثبت بحث ألفا-بيتا أن بعض الأشجار الفرعية لا يمكن أن تؤثر على القرار النهائي ويتجاوزها، ويعيد قيمة المينيماكس الدقيقة بينما في أفضل الحالات يضاعف تقريبًا العمق الذي يمكن الوصول إليه في وقت معين.
- بحث شجرة مونت كارلو
- عندما تكون عوامل التفرع كبيرة جدًا بحيث لا تسمح بالبحث الشامل، يبني بحث شجرة مونت كارلو شجرة غير متماثلة موجهة بواسطة عمليات تشغيل عشوائية وقاعدة اختيار توازن بين الاستكشاف والاستغلال، وهي طريقة أحدثت تحولًا في اللعب الحاسوبي في ألعاب مثل Go.
Clinical relevance
أنتج البحث التنافسي أنظمة ذكاء اصطناعي رائدة، من محركات الشطرنج التي تستخدم بحث ألفا-بيتا إلى برامج Go القائمة على بحث شجرة مونت كارلو، وتُستخدم نفس التقنيات في التفاوض الآلي، والألعاب الأمنية، وأي بيئة تُنمذج كمنافسة بين أطراف تسعى للتحسين.
History
صاغت ورقة شانون عام 1950 شطرنج الكمبيوتر كبحث مينيماكس مع دالة تقييم، وقدمت نظرية مينيماكس لفون نيومان الأساس النظري للألعاب. تم تطوير تقليم ألفا-بيتا خلال الخمسينيات والستينيات وتم تحليله بدقة بواسطة كنوث ومور (1975). دفع بحث شجرة مونت كارلو، الذي تم إضفاء الطابع الرسمي عليه في العقد الأول من القرن الحادي والعشرين، القفزة التالية في قوة لعب الألعاب، خاصة في لعبة Go.
Key figures
- Claude E. Shannon
- John von Neumann
- Arthur Samuel
- Donald E. Knuth
- Ronald W. Moore
Related topics
Seminal works
- shannon1950
- knuth1975
- browne2012
Frequently asked questions
- هل يغير تقليم ألفا-بيتا الحركة التي سيختارها المينيماكس؟
- لا. يعيد تقليم ألفا-بيتا نفس القيمة والحركة تمامًا مثل المينيماكس الكامل؛ إنه يتجنب فقط استكشاف الفروع التي لا يمكن أن تؤثر على النتيجة بشكل مؤكد. فائدته هي السرعة، ومع ترتيب جيد للحركات يمكنه البحث بعمق مضاعف تقريبًا في نفس الوقت.
- لماذا يُستخدم بحث شجرة مونت كارلو بدلاً من المينيماكس في ألعاب مثل Go؟
- تتميز لعبة Go بعامل تفرع هائل وتفتقر إلى دالة تقييم بسيطة ودقيقة، لذا فإن المينيماكس ذو العمق الثابت غير فعال. بدلاً من ذلك، يقدر بحث شجرة مونت كارلو جودة الحركة من خلال العديد من عمليات اللعب العشوائية وينمي الشجرة بشكل انتقائي نحو الخطوط الواعدة، وهو ما يتناسب بشكل أفضل بكثير في مثل هذه الألعاب.