بحث شجرة مونت كارلو: مراجعة للعيوب والمزايا والقيود في الألعاب متعددة اللاعبين المعقدة
João Luis Almeida Santos, Andrei Camilotto, Djonatan Bonelli, Eduardo Fiorentin, Felipe Grando
ملخص
اكتسبت MCTS بروزًا بعد نجاحاتها في لعبة Go والشطرنج والشوغي، لكن معظم الدراسات تركز على الألعاب الثنائية ذات المعلومات الكاملة. تحلل هذه الورقة MCTS في الألعاب الرقمية وألعاب الطاولة متعددة اللاعبين، والتي غالبًا ما تتسم بمعلومات غير كاملة. استنادًا إلى 18 ورقة مختارة من 22 مسترجعة من IEEE Xplore وHAL Science Ouverte وGoogle Scholar (2013–2025)، تحدد الدراسة ثلاث قيود هيكلية متكررة: الهضاب الحسابية، والنقاط العمياء في التفكير التكتيكي، والمقايضات في نمذجة الخصم.
1. مقدمة
تعد خوارزمية بحث شجرة مونت كارلو (MCTS) عائلة من خوارزميات البحث التي تبني شجرة قرار على أربع مراحل: الاختيار، والتوسيع، والمحاكاة، والانتشار العكسي. وبدلاً من اشتراط دالة تقييم كاملة لكل حالة، تقدّر الطريقة جودة الإجراءات من خلال محاكاات عديدة، مما يوازن بين استكشاف البدائل النادر زيارتها واستغلال الإجراءات المعروفة. وقد أسهمت هذه الخاصية في تحقيق نتائج معبّرة في ألعاب مثل الغو والشطرنج والشوغي، لا سيما في بيئات اللاعبين الاثنين ذات المعلومات الكاملة (BROWNE et al., 2012).
غير أن الألعاب الرقمية وألعاب الطاولة المعاصرة تطرح ظروفاً أكثر تعقيداً: عدة خصوم، ومعلومات مخفية، وعشوائية، وفضاءات إجراءات واسعة، وقرارات في الزمن الحقيقي. وفي هذه الحالات، لا تؤدي محاكاة إضافية واحدة دائماً إلى قرار أفضل. فزيادة عدد اللاعبين توسّع شجرة البحث وتجعل نمذجة ردود الخصوم أمراً صعباً. ويمكن للمعلومات غير الكاملة أن تسبب اندماج الاستراتيجيات عندما تُعالَج الحالات المخفية بشكل غير ملائم، بينما يقلل ضغط الوقت من الميزانية الحسابية المتاحة. وعلى الرغم من التطبيق المتزايد لخوارزمية MCTS في هذه السيناريوهات، لا يزال الأدبيات مجزأً ومركّزاً على الألعاب الكلاسيكية.
2. الأهداف
كان الهدف العام لهذا العمل هو تحديد القيود المتكررة لخوارزمية MCTS في الألعاب الرقمية وألعاب الطاولة متعددة اللاعبين وتنظيمها، لا سيما في البيئات ذات المعلومات غير الكاملة والعشوائية وقيود الوقت.
أما الأهداف المحددة، فقد سعى العمل إلى جمع الاستراتيجيات التي تخفف هذه القيود وتحديد الفجوات البحثية التي يمكن أن توجّه الدراسات المستقبلية وتفضي إلى تقييمات أكثر قابلية للمقارنة والتكرار.
3. المنهجية
أُجريت مراجعة أدبيات للدراسات المنشورة بين عامي 2013 و2025، مع عمليات بحث في قواعد بيانات IEEE Xplore وHAL Science Ouverte وGoogle Scholar. وقد جمعت استراتيجيات البحث بين المصطلحين "Monte Carlo Tree Search" و"MCTS" وتعبيرات مرتبطة بالألعاب الرقمية وألعاب الطاولة والألعاب متعددة اللاعبين. وقد نظر الفرز في الأعمال التي تناول عنوانها أو ملخصها خوارزمية MCTS أو أحد متغيراتها المباشرة أو طريقة هجينة مطبقة على ألعاب تنافسية أو تعاونية. واستُبعدت الدراسات الخارجة عن النطاق، والوثائق التي تعذّر الوصول إلى نصها الكامل، والأعمال التي لم يكن نطاقها متوافقاً مع أهداف المراجعة.
أسفرت عمليات البحث عن 24 سجلاً، اثنان منها مكرران بين الاستعلامات، مما أدى إلى 22 عملاً فريداً يحتمل أن يكون ذا صلة (17 بالإنكليزية وخمسة بالفرنسية). وبعد الفرز، اختيرت 18 دراسة للتحليل الكامل واستُبعدت أربع. وقد جمعت المدونة النهائية 13 دراسة من IEEE Xplore وثلاثاً من HAL واثنتين عُثر عليهما عبر Google Scholar، وكان من بين الدراسات المختارة 15 نصاً بالإنكليزية وثلاثة بالفرنسية. وقد صُنّفت الأعمال حسب نوع اللعبة والخوارزمية المستخدمة وقيود البيئة والنتائج المبلّغ عنها واستراتيجيات التخفيف. ونُظّم التحليل الموضوعي في ثلاث فئات بنيوية للقيود، وهي حدود الأداء والنقاط العمياء التكتيكية والمقايضات في نمذجة الخصوم، ومضاعِفَين يعتمدان على المجال، وهما المعلومات غير الكاملة والقرارات في الزمن الحقيقي.
4. النتائج والمناقشة
تشير الدراسات المحللة إلى أن خوارزمية MCTS تعمل بأكثر اتساق في الألعاب ذات الحالات المحددة جيداً وعامل التفرع المعتدل والميزانية الحسابية الكافية لعدد كبير من المحاكاات. ومن بين الأعمال الـ18 المختارة، تناولت ثمانية ألعاباً رقمية، وبحثت ستة في ألعاب الطاولة أو الألعاب اللوحية، وحللت الأعمال المتبقية ألعاب الورق وبيئات اللعب العام أو تطبيقات ذات صلة. واستُخدمت خوارزميات قائمة على MCTS في 14 دراسة، غالباً بالاقتران مع الشبكات العصبية وتجريدات فضاء الإجراءات وسياسات المحاكاة وتقنيات ضبط المعاملات.
يتعلق القيد الأول المحدد بأداء البحث. فعلى الرغم من أن زيادة عدد المحاكاات تحسّن عادة جودة القرار، تميل المكاسب الحدية إلى التضاؤل عندما تبدأ المحاكاات الجديدة في إعادة زيارة مسارات سبق استكشافها بما يكفي. وتُظهر النتائج المحققة في الغو وألعاب الاستراتيجية في الزمن الحقيقي وألعاب الطاولة أن مضاعفة الميزانية الحسابية قد تنتج فوائد محدودة أو معدومة بعد نقطة معينة. وبالإضافة إلى ذلك، تُظهر الدراسات المتعلقة بعمق المهارة أن هذا الحد يعتمد على تعقيد اللعبة وعلى تهيئة الوكيل معاً. وتشمل استراتيجيات التخفيف تجريد فضاء الإجراءات وتبسيط المحاكاات والضبط التلقائي للسياسات وثوابت الاستكشاف واستراتيجيات التوسيع من خلال خوارزمية N-Tuple Bandit التطورية (NTBEA) (GOODMAN; PEREZ-LIEBANA; LUCAS, 2024).
يتوافق القيد الثاني مع النقاط العمياء في الاستدلال التكتيكي. فبما أن خوارزمية MCTS تقدّر القيمة المتوسطة للاستمرارات المُعيّنة، فقد تفشل الخوارزمية في المواقف التي تتطلب التعرف على تسلسلات تكتيكية محددة أو تهديدات طويلة الأمد أو تهيئات نادرة. وفي الغو، توضح حالات مثل السلالم والسيميائي سيناريوهات قد لا يتعرف فيها البحث على بنية تكتيكية واضحة للاعبين ذوي الخبرة.
يتعلق القيد الثالث بنمذجة الخصوم. ففي الألعاب التي تضم ثلاثة مشاركين أو أكثر، يجب أن تمثل عملية البحث ليس فقط قرارات اللاعب عند جذر الشجرة، بل أيضاً الردود المحتملة لكل خصم. وتميل النماذج التي تحتفظ ببنى مستقلة لكل خصم إلى تمثيل السلوك الاستراتيجي بشكل أفضل، وإن كانت تزيد التكلفة الحسابية زيادة كبيرة. وفي المقابل، تقلل الأساليب المبسطة، مثل Paranoid Search والسياسات المعممة، من هذه التكلفة لكنها قد تفشل في تمثيل سلوكيات ذات صلة. ويشير الأدبيات إلى أن الأساليب القائمة على التركيز الانتقائي وتعميم ردود الخصوم وتفكيك الشجرة بدائل واعدة، وإن كانت لا تزال قليلة التقييم في الألعاب ذات العدد الكبير من المشاركين (BAIER; KAISERS, 2020).
تزيد المعلومات غير الكاملة من حدة هذه القيود. ففي ألعاب الورق وبوكيمون وغيرها من البيئات ذات الحالات المخفية، قد يتسبب التحويل الحتمي، الذي يقوم على افتراض تهيئة ممكنة واحدة للمعلومات المجهولة والبحث كما لو كانت صحيحة، في اندماج استراتيجيات غير متوافقة. وتقلل خوارزمية Information Set MCTS، وهي تنويع من بحث شجرة مونت كارلو مصمم للتعامل مع عدم اليقين، من هذه المشكلة عبر تجميع الحالات التي لا يستطيع اللاعب تمييزها، مع الحفاظ فقط على المعلومات المتاحة فعلاً في لحظة القرار (COWLING; POWLEY; WHITEHOUSE, 2012). ومع ذلك، لا تزال العشوائية المتأصلة في البيئة والحاجة إلى استنتاج سلوك الخصوم تحدّان من موثوقية التقديرات المنتجة.
في البيئات الزمنية الحقيقية، مثل ألعاب الاستراتيجية وألعاب MOBA وألعاب إطلاق النار من منظور الشخص الأول، تصبح قيود الوقت عاملاً حاسماً. إذ يجب على MCTS اختيار الإجراءات في فترات قصيرة جداً مع إدارة فضاءات إجراءات توافقية ووحدات متعددة وملاحظات جزئية. وفي هذا السياق، تظهر التجريدات الهرمية والإجراءات الكلية وتقليم الإجراءات والسياسات المستمدة من التعلم المراقب أو التعلم المعزز كاستراتيجيات متكررة (ONTAÑÓN, 2013). وفي بعض الحالات، قد تؤدي أساليب بديلة أداءً أفضل. فخوارزمية Rolling Horizon التطورية (RHEA)، على سبيل المثال، تطوّر تسلسلات إجراءات قصيرة وتعيد التخطيط باستمرار، مما يجعلها مناسبة بشكل خاص للألعاب التعاونية والبيئات شديدة العشوائية التي تتغير فيها شجرة البحث بسرعة (SFIKAS; LIAPIS, 2022).
حُددت أيضاً تطبيقات لخوارزمية MCTS تعتمد بدرجة أقل على القرارات في الزمن الحقيقي، مثل الموازنة التلقائية واختبار اللعب ودعم تصميم الألعاب. وفي هذه السيناريوهات، يتوقف وقت المعالجة عن كونه قيداً حاسماً، مما يسمح باستكشاف تهيئات مختلفة على نطاق واسع وتحديد الاختلالات وتقييم بدائل التصميم. وعلى الرغم من أن معظم الدراسات تبلغ عن نتائج مؤيدة للأساليب المقترحة، لاحظت بعض الأعمال أداءً أدنى لخوارزمية MCTS مقارنة بتقنيات منافسة، كما في لعبتي Kingdomino وPandemic.
5. الخاتمة
حددت المراجعة أيضاً خمس فرص ذات صلة للبحث المستقبلي: (i) اعتماد وتوحيد معايير مرجعية مشتركة للألعاب متعددة اللاعبين ذات المعلومات غير الكاملة؛ (ii) التقييم المنهجي لتقنيات نمذجة الخصوم في الألعاب ذات العدد الأكبر من المشاركين؛ (iii) التحقيق في العلاقة بين التعقيد المدرك من اللاعبين البشر والعُمق الفعلي للبحث؛ (iv) دراسة السلاسل التنافسية من أفضل ثلاث وأفضل خمس مباريات، مع مراعاة سجل الاختيارات والحظر؛ و(v) توسيع تطبيقات MCTS في الموازنة التلقائية واختبار اللعب والتوليد الإجرائي للمحتوى.
المراجع
- [1]Baier, H.; Kaisers, M. (2020). Guiding multiplayer MCTS by focusing on yourself. In: IEEE Conference on Games (CoG), 550–557.
- [2]Browne, C. B. et al. (2012). A survey of Monte Carlo Tree Search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43.
- [3]Cowling, P. I.; Powley, E. J.; Whitehouse, D. (2012). Information set Monte Carlo tree search. IEEE Transactions on Computational Intelligence and AI in Games, 4(2), 120–143.
- [4]Goodman, J.; Perez-Liebana, D.; Lucas, S. (2024). Skill depth in tabletop board games. In: 2024 IEEE Conference on Games (CoG), 1–8.
- [5]Ontañón, S. (2013). The combinatorial multi-armed bandit problem and its application to real-time strategy games. In: Proceedings of the Ninth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 58–64.
- [6]Sfikas, K.; Liapis, A. (2022). Playing against the board: Rolling horizon evolutionary algorithms against Pandemic. IEEE Transactions on Games, 14(3), 339–349.