2025-11-16T22:28:12.942550

Reinforcing Competitive Multi-Agents for Playing 'So Long Sucker'

Sharan, Adak

This paper investigates the strategy game So Long Sucker (SLS) as a novel benchmark for multi-agent reinforcement learning (MARL). Unlike traditional board or video game testbeds, SLS is distinguished by its coalition formation, strategic deception, and dynamic elimination rules, making it a uniquely challenging environment for autonomous agents. We introduce the first publicly available computational framework for SLS, complete with a graphical user interface and benchmarking support for reinforcement learning algorithms. Using classical deep reinforcement learning methods (e.g., DQN, DDQN, and Dueling DQN), we train self-playing agents to learn the rules and basic strategies of SLS. Experimental results demonstrate that, although these agents achieve roughly half of the maximum attainable reward and consistently outperform random baselines, they require long training horizons (~2000 games) and still commit occasional illegal moves, highlighting both the promise and limitations of classical reinforcement learning. Our findings establish SLS as a negotiation-aware benchmark for MARL, opening avenues for future research that integrates game-theoretic reasoning, coalition-aware strategies, and advanced reinforcement learning architectures to better capture the social and adversarial dynamics of complex multi-agent games.

academic

تعزيز الوكلاء المتنافسين متعددي الأطراف للعب "So Long Sucker"

المعلومات الأساسية

معرّف الورقة: 2411.11057
العنوان: تعزيز الوكلاء المتنافسين متعددي الأطراف للعب "So Long Sucker"
المؤلفون: Medant Sharan (كلية الملك بلندن)، Chandranath Adak (معهد الهند للتكنولوجيا باتنا)
التصنيف: cs.AI
وقت النشر: نوفمبر 2024 (نسخة arXiv المسبقة)
رابط الورقة: https://arxiv.org/abs/2411.11057

الملخص

تقدم هذه الورقة لأول مرة لعبة الاستراتيجية "So Long Sucker" (SLS) إلى مجال التعلم المعزز متعدد الوكلاء (MARL) كمعيار جديد. بخلاف منصات الاختبار التقليدية للألعاب الرقمية أو الألعاب الفيديو، تتميز SLS بتشكيل التحالفات والخداع الاستراتيجي وقواعد الحذف الديناميكية، مما يوفر بيئة تحديات فريدة للوكلاء المستقلين. قام الباحثون ببناء أول إطار عمل حسابي متاح للعموم لـ SLS، يتضمن واجهة مستخدم رسومية ودعم معايير خوارزميات التعلم المعزز. من خلال تدريب الوكلاء على اللعب الذاتي باستخدام طرق التعلم المعزز العميق الكلاسيكية (DQN و DDQN و Dueling DQN)، تعلموا قواعد SLS والاستراتيجيات الأساسية. تُظهر النتائج التجريبية أنه على الرغم من أن هذه الوكلاء يمكنهم تحقيق حوالي نصف الحد الأقصى للمكافآت المتاحة والتفوق المستمر على خط الأساس العشوائي، إلا أنهم يحتاجون إلى فترات تدريب طويلة (حوالي 2000 لعبة) وقد ينفذون أحياناً إجراءات غير قانونية، مما يسلط الضوء على الإمكانيات والقيود المتأصلة في التعلم المعزز الكلاسيكي.

خلفية البحث والدافع

تعريف المشكلة

تركز معايير التعلم المعزز متعدد الوكلاء الحالية بشكل أساسي على الأهداف التعاونية البحتة (مثل مهام التنسيق) أو المنافسة الخصومية (مثل الألعاب ثنائية الأشخاص بمجموع صفري)، وتفتقر إلى بيئات مختلطة يمكنها التقاط ديناميكيات تشكيل التحالفات والخيانة في نفس الوقت. على الرغم من التطورات المحققة في مجالات مثل Go و StarCraft II و Diplomacy، لم توفر هذه المعايير بشكل كافٍ الديناميكيات المختلطة من التحالفات والخيانة الفريدة لـ SLS.

أهمية البحث

تعتبر SLS، وهي لعبة استراتيجية رباعية الأشخاص صممها Hausner و Nash و Shapley و Shubik، تدور حول تشكيل التحالفات والتحالفات المؤقتة والخيانة الحتمية. يعتمد الفوز ليس فقط على الإجراءات القانونية بل أيضاً على الدبلوماسية والانتهازية، مما يجعلها منصة اختبار فريدة لدراسة الثقة والتفاوض والمعضلات الاجتماعية.

قيود الطرق الموجودة

تفتقر معظم معايير MARL إلى الديناميكيات المختلطة من التحالفات والخيانة
عادة ما تعتمد الأعمال السابقة في الإعدادات الغنية اجتماعياً على قنوات اتصال صريحة أو قواعد تفاعل مصنوعة يدوياً
لم تتم دراسة SLS مسبقاً كمعيار حسابي

دافع البحث

من خلال تشكيل SLS كمتغير متسلسل قابل للتكرار واختبار خوارزميات DRL الأساسية، تضع هذه الورقة SLS كمنصة اختبار واعية بالتحالفات والخيانة لتقدم بحوث MARL.

المساهمات الأساسية

أول إطار عمل حسابي لـ SLS: تصميم وإطلاق أول إطار عمل حسابي متخصص لبحوث التعلم المعزز، مزود بواجهة مستخدم رسومية للتجارب
معايير خوارزميات DRL الكلاسيكية: اختبار خوارزميات DRL الكلاسيكية (DQN و DDQN و Dueling DQN) في SLS، مع تحليل قدرتها على اكتساب الكفاءة في اللعب القانوني والوعي الاستراتيجي الجزئي
معيار واعٍ بالتحالفات والخيانة: تأسيس SLS كمعيار واعٍ بالتحالفات والخيانة لـ MARL، مما يلهم الأبحاث المستقبلية التي تجمع بين DRL والاستدلال النظري للألعاب

شرح الطريقة

تعريف المهمة

تحويل SLS إلى بيئة MARL، باستخدام متغير بمجموع صفري من نسخة Hofstra المعممة. يتم تخصيص أربعة لاعبين بألوان فريدة، يبدأ كل منهم بـ 5 رقائق بنفس اللون، ويلعبون على لوحة بها ما يصل إلى 6 أكوام نشطة. شرط الفوز هو أن تكون آخر لاعب متبقٍ.

تشكيل التعلم المعزز

نمذجة SLS كعملية قرار ماركوفية (MDP):

فضاء الحالة S: مجموعة جميع حالات اللعبة الممكنة
فضاء الإجراء A: مجموعة جميع الإجراءات المتاحة للوكيل (مجموعة الحركات الصحيحة المنفصلة)
دالة الانتقال: p(s'|s,a) تمثل احتمالية الانتقال إلى s' بعد تنفيذ الإجراء a في الحالة s
دالة المكافأة: r(s,a,s') تخصص قيمة عددية لكل انتقال
السياسة: π(a|s) هي سياسة اختيار الوكيل للإجراء a في حالة معينة s

الهدف هو إيجاد السياسة المثلى π* لتعظيم العائد المتوقع المخصوم: $R_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}$

تمثيل الحالة

تشفر الحالة st جميع المعلومات اللازمة لوصف بيئة اللعبة: $s_t = (Board\ Configuration, Player\ Chips, Eliminated\ Chips, Current\ Player, Game\ Phase, Step\ Count)$

حجم فضاء الملاحظة هو: $obs\_size = (n_{rows} \times n_{players} \times n_{max\_pile}) + n_{players}^2 + (2 \times n_{players}) + 4 + 1$

فضاء الإجراء

فضاء إجراء منفصل A = {A₀, A₁, ..., A₉}، يتضمن:

A₀-A₅: إجراءات اختيار الكومة (صحيحة في مرحلة اختيار الكومة)
A₆-A₉: إجراءات قرار اللاعب/اللون (صحيحة في مراحل اختيار الرقائق واختيار اللاعب التالي وحذف الرقائق)

تصميم المكافأة

يتم تعريف إشارة المكافأة في الخطوة الزمنية t على النحو التالي: $r_t = \min\left(\wp, \frac{\wp}{(\alpha/n_c) \cdot t}\right)$

حيث α ∈ (0,1] هي معامل يتحكم في معدل التناقص، و℘ هي حجم المكافأة. تتلقى الإجراءات غير القانونية عقوبة مكافأة سالبة ثابتة (-℘)، بينما تحصل الإجراءات القانونية على مكافأة موجبة تصل إلى +℘، وتتناقص هذه القيمة مع عدد الخطوات لتعزيز الكفاءة.

الإعداد التجريبي

إعدادات اللعبة

عدد اللاعبين: 4 لاعبين
الرقائق الأولية: 5 رقائق بنفس اللون لكل لاعب
الحد الأقصى لعدد الأكوام: 6 أكوام نشطة
شرط الفوز: لعبة بمجموع صفري، هيكل المكافأة {0,0,0,ù}، ù ∈ N⁺

إعدادات التدريب

استخدام إعداد التعلم التراكمي المركزي، حيث تشترك جميع وكلاء اللاعبين الأربعة في شبكة تعلم مشتركة وذاكرة تشغيل مشتركة. معمارية الشبكة عبارة عن طبقتي إخفاء متصلة بالكامل بـ 64 وحدة عصبية (تفعيل ReLU)، متبوعة بطبقة إخراج خطية.

إعدادات المعاملات الفائقة

معامل الخصم γ = 0.95
معدل الاستكشاف الأولي ε₀ = 1.0
معدل تناقص الاستكشاف ε_decay = 0.995
الحد الأدنى لمعدل الاستكشاف ε_min = 0.01
معدل التعلم = 0.001
حجم الدفعة = 64
عدد جولات التدريب = 10,000 لعبة

مقاييس التقييم

متوسط وانحراف معياري للمكافآت المتراكمة
متوسط الخطوات لكل لعبة
نطاق المكافآت الحد الأدنى، الحد الأقصى
نطاق الخطوات الحد الأدنى، الحد الأقصى

الطرق المقارنة

DQN (شبكة Q العميقة)
DDQN (DQN المزدوج)
Dueling DQN
خط الأساس العشوائي

نتائج التجارب

النتائج الرئيسية

الوكيل	المكافأة (متوسط ± انحراف معياري)	نطاق المكافأة الحد الأدنى، الحد الأقصى	الخطوات (متوسط ± انحراف معياري)	نطاق الخطوات الحد الأدنى، الحد الأقصى
DQN	103.40 ± 42.31	-313.45, 189.24	61.16 ± 14.51	27, 162
DDQN	108.44 ± 44.95	-279.13, 191.38	61.23 ± 14.18	28, 165
Dueling DQN	102.06 ± 49.62	-319.76, 192.09	65.92 ± 15.94	28, 173
عشوائي	-8.78 ± 43.52	-419.26, 94.19	65.24 ± 17.76	29, 174

النتائج الرئيسية

الأداء: تفوق جميع وكلاء DRL بشكل مستمر على خط الأساس العشوائي، محققة حوالي نصف الحد الأقصى النظري للمكافآت (≈200)
خصائص التقارب: حقق DDQN أكثر التقارب استقراراً وأعلى متوسط مكافأة، مما يتحقق من فوائد التقدير المزدوج في تخفيف الإفراط في تقدير قيمة Q في الألعاب طويلة الأجل
ديناميكيات التعلم: أظهر الوكلاء في المراحل المبكرة من التدريب (<500 لعبة) تباين مكافآت كبير، وبعد حوالي 2000 لعبة أظهر جميع وكلاء DRL تقارباً أكثر سلاسة

تحليل منحنيات التعلم

ينقسم عملية التدريب إلى ثلاث مراحل:

مرحلة الاستكشاف (0-500 لعبة): تباين عالي، إجراءات غير قانونية متكررة
مرحلة التعلم (500-2000 لعبة): إتقان تدريجي للقواعد، ارتفاع تدريجي في المكافآت
مرحلة التقارب (>2000 لعبة): استقرار المكافآت في النطاق 100-120، مع انخفاضات استكشافية عرضية

الأعمال ذات الصلة

تطور معايير MARL

المعايير التقليدية: Go و StarCraft II تركز بشكل أساسي على المنافسة البحتة أو التعاون
الألعاب الاجتماعية: Diplomacy وغيرها تتضمن التفاوض لكنها تعتمد على الاتصال الصريح
تطبيقات نظرية الألعاب: تطبيق حل توازن ناش في الأنظمة متعددة الوكلاء

تطبيق التعلم المعزز العميق في الألعاب

سلسلة AlphaGo: اختراقات في الألعاب ذات المعلومات الكاملة
التعلم متعدد الوكلاء: التدريب على اللعب الذاتي وتنوع الاستراتيجيات
طرق دالة القيمة: تطبيق DQN ومتغيراته في فضاء الإجراء المنفصل

البحث المتعلق بـ SLS

تقدم هذه الورقة لأول مرة SLS كمعيار حسابي، مما يسد الفجوة في دراسة ديناميكيات تشكيل التحالفات والخيانة.

الخلاصة والمناقشة

الاستنتاجات الرئيسية

يمكن لطرق القيمة الكلاسيكية تعلم القواعد الأساسية لـ SLS والاستراتيجيات الجزئية، محققة أداء مستقرة لكن دون المستوى الأمثل
يعكس التباين العالي في المكافآت الحساسية تجاه التهيئة والاستكشاف
الإجراءات المرتبطة بالسياق تكشف عن قيود تقدير القيمة قصيرة الأجل
أصبحت SLS معيار MARL واعٍ بالتفاوض بنجاح

القيود

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

الاتجاهات المستقبلية

تحسينات المعمارية: دمج أطر actor-critic والإطارات الواعية بالتحالفات
تعزيز الاستراتيجية: تحسين الاستدلال طويل الأجل والامتثال للقواعد
الديناميكيات الاجتماعية: تطوير قدرات التفاوض والتحالف والخداع
التحليل النظري: دمج الاستدلال النظري للألعاب مع التعلم العميق

التقييم المتعمق

المميزات

معيار مبتكر: أول إدراج لـ SLS في MARL، سد فجوة مهمة في دراسة ديناميكيات التحالفات والخيانة
إطار عمل شامل: توفير إطار عمل حسابي كامل مع واجهة مستخدم رسومية، تعزيز البحث القابل للتكرار
تقييم منهجي: معايير شاملة لطرق DRL الكلاسيكية المتعددة
مساهمة نظرية: توضيح قواعد المتغير بمجموع صفري، معالجة عدم اكتمال التشكيل الأصلي

أوجه القصور

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

التأثير

القيمة الأكاديمية: توفير اتجاه بحثي جديد ومعيار للمجتمع الأكاديمي MARL
الأهمية العملية: سيعزز إطلاق الإطار مفتوح المصدر الأبحاث اللاحقة
المساهمة المنهجية: توضيح كيفية تحويل ألعاب استراتيجية معقدة إلى بيئات صديقة للتعلم الآلي
الإلهام من القيود: الكشف عن قيود RL الكلاسيكي في الألعاب الاجتماعية المعقدة، توجيه اتجاهات البحث المستقبلية

السيناريوهات المعمول بها

بحوث MARL: تطوير خوارزميات لديناميكيات تشكيل التحالفات والخيانة
تطبيقات نظرية الألعاب: نماذج حسابية للتفاوض متعدد الأطراف والاستدلال الاستراتيجي
الذكاء الاجتماعي: نمذجة سلوكيات الثقة والخداع والتعاون
أدوات تعليمية: عروض توضيحية تعليمية لنظرية الألعاب والأنظمة متعددة الوكلاء

المراجع

Hausner, M., Nash, J., Shapley, L., & Shubik, M. (1964). So Long Sucker- A Four-Person Game
Vinyals, O. et al. (2019). Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature
FAIR Team et al. (2022). Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science
Mnih, V. et al. (2015). Human-level control through deep reinforcement learning. Nature

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