ملخص تقني: موازاة خوارزمية تقليل الندم المضاد للواقع (Counterfactual Regret Minimization)

بيان المشكلة

بينما تُعد الموازاة (Parallelization) حجر الزاوية في الذكاء الاصطناعي، حيث قللت بشكل جذري من أوقات التدريب للنماذج الكبيرة، إلا أن تطبيقها على حل الألعاب الحسابية لا يزال غير مستكشف نسبيًا. وعلى الرغم من النجاحات البارزة في حل ألعاب المعلومات الناقصة الكبيرة (مثل Cepheus وLibratus وPluribus) التي تعتمد على شكل من أشكال الموازاة، فإن الآليات المحددة لموازاة خوارزميات تقليل الندم المضاد للواقع (CFR) لم يتم تعميمها. غالبًا ما تعاني المحاولات الحالية، مثل تلك التي قام بها Reis وRudolf، من مشكلات في قابلية إعادة الإنتاج، أو تتطلب تدفق تحكم معقد لكل خيط معالجة (thread)، أو تؤدي إلى تعقيد عمل تربيعي دون المستوى الأمثل. كما تفتقر النهج السابقة المحددة لنطاق معين (مثل Cepheus) إلى العمومية. حدد المؤلفون الحاجة إلى إطار عمل عام ومستقل عن النطاق يمكنه تسريع خوارزميات CFR ومتغيراتها الجدولية دون التضحية بالخصائص الخوارژيتمية التي تجعلها فعالة.

المنهجية

يقترح المؤلفون إطار عمل موازاة عامًا يعيد صياغة نسخة "صيغة التسلسل" (sequence-form) من خوارزمية CFR كمتسلسلة من عمليات الجبر الخطي. يسمح هذا التحويل بتطبيق تقنيات قياسية ومحسنة للغاية لموازاة الجبر الخطي (تحديدًا على وحدات معالجة الرسومات - GPUs) على حل الألعاب.

النهج التقني الأساسي

1. إعادة صياغة CFR كجبر خطي:
   يقوم البحث بتحويل خطوات عبور الشجرة المتأصلة في CFR (من الأعلى إلى الأسفل لتحديث الاستراتيجية، ومن الأسفل إلى الأعلى لملاحظة المنفعة) إلى عمليات ضرب مصفوفات في متجهات. ويتم تحقيق ذلك باستخدام مصفوفات منطقية (مصفوفات مدخلاتها في المجموعة {0, 1}) للتوفيق بين تمثيلات البيانات المختلفة:

   • تمثيل التسلسل مقابل تمثيل العقد: تقوم المصفوفة المنطقية $A \in \mathbb{R}^{P \times \Sigma}$ بالتحويل بين المتجهات لكل عقدة ($\mathbb{R}^P$) ومتجهات كل تسلسل ($\mathbb{R}^\Sigma$).
   • التمثيل السلوكي: تتعامل المصفوفة المنطقية $B$ مع التحويل إلى التمثيل السلوكي ($\mathbb{R}^{\Sigma^+}$)، والذي يستبعد التسلسل الفارغ.
   • تجميع الإجراءات: تقوم المصفوفة المنطقية $C$ بتجميع القيم عبر الإجراءات المتاحة عند نقاط القرار، مما يتيح حسابات التنميط (L1-normalization) والتوقعات عبر ضرب المصفوفات.

2. عبور الشجرة الموازي:
   بدلاً من العبور العودي للشجرة (recursive tree traversal)، يقوم الخوارزم بفك مكونات عملية اتخاذ القرار ذات الصيغة التسلسلية (TFSDP) إلى هياكل مستويات. تمثل مصفوفات التجاور $L^{(d)}$ الحواف عند كل عمق $d$.

   • يتم إجراء العبور من الأعلى إلى الأسفل (لنشر الاستراتيجية) عن طريق تطبيق المصفوفات $L^{(1)}, L^{(2)}, \dots, L^{(k)}$ بالتتابع.
   • يتم إجراء العبور من الأسفل إلى الأعلى (لتراكم المنفعة) عن طريق تطبيق هذه المصفوفات بترتيب عكسي.
   • يتم تنفيذ هذه العمليات باستخدام ضرب المصفوفات المتجهة بنمط الصف المضغوط (CSR)، وهو فعال للغاية في الأجهزة المتوازية.

3. التكيف الخوارزمي:
   تم تصميم إطار العمل ليكون نمطيًا. يتم تعريف العمليات المتوازية الأساسية (NEXTSTRATEGY و OBSERVEUTILITY)، وتُنفذ متغيرات محددة من CFR عبر إضافة عمليات بسيطة لهذه الوظائف الأساسية:

   • CFR+: تضيف عملية "الأرضية" (flooring) إلى الندم.
   • CFR المخصم (DCFR): يطبق عوامل قياس تعتمد على الوقت على الندم الإيجابي والسلبي.
   • CFR التنبؤي (PCFR): يدمج متجه تنبؤ للندم اللحظي.

المساهمات الرئيسية

• إطار عمل عام: يقدم البحث إطار عمل مستقل عن النطاق يعامل CFR كجبر خطي، مما يجعله قابلًا للتطبيق على أي متغير جدولي لـ CFR (مثل CFR، CFR+، DCFR، PCFR، PCFR+).
• التحليل النظري: باستخدام نموذج "العمل-العمق" (work-depth model)، يثبت المؤلفون أن الخوارزمية المتوازية تحافظ على نفس تعقيد العمل الإجمالي ($W = \Theta(|P|)$) لخوارزمية تسلسل الصيغة لـ CFR المتسلسلة، مما يضمن عدم فقدان الكفاءة في غياب التوازي. كما أظهر أن العمق هو $D = \Theta(k \log B)$، حيث $k$ هو ارتفاع الشجرة و $B$ هو عامل التفرع.
• تنفيذ مفتوح المصدر: على عكس محاولات GPU السابقة، يوفر هذا العمل تنفيذًا مفتوح المصدر متوافقًا مع مكتبة OpenSpiel، مما يسهل قابلية إعادة الإنتاج والتكامل.
• القابلية للتوسع: يعمل النهج على تقسيم اللعبة بفعالية عند كل عمق بدلاً من مجرد حدود الألعاب الفرعية، مما قد يؤدي إلى توازي أعلى من البنى السابقة مثل Cepheus.

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

قيم المؤلفون تنفيذهم المعزز بواسطة وحدة معالجة الرسومات (GPU) مقابل تنفيذات Google DeepMind لـ OpenSpiel (بنسختي Python و C++) التي تعمل على المعالجات المركزية (CPUs) عبر سبع ألعاب مرجعية متفاوتة الأحجام (من Kuhn poker بـ 58 عقدة إلى Large Battleship بـ $5.2 \times 10^7$ عقدة).

• الألعاب الصغيرة: بالنسبة للألعاب الصغيرة (مثل Kuhn poker و Leduc poker)، تؤدي تكلفة الـ GPU الإضافية إلى تباطؤ مقارنة بتنفيذات الـ CPU.
• الألعاب الكبيرة: مع زيادة حجم اللعبة، يتفوق التنفيذ المتوازي بشكل كبير على خطوط الأساس للـ CPU.
  • بالنسبة لـ Small Battleship، تبلغ سرعة التسريع حوالي $2.1 \times 10^2$ مرة أسرع من تنفيذ OpenSpiel بـ C++.
  • بالنسبة لـ Medium Battleship، تصل سرعة التسريع إلى $1.2 \times 10^3$.
  • بالنسبة لـ Large Battleship، تبلغ سرعة التسريع $4.1 \times 10^3$.
  • إجمالًا، التنفيذ المعتمد على GPU أسرع بما يصل إلى 18,889 مرة من تنفيذ OpenSpiel بـ Python و 3,413 مرة من تنفيذه بـ C++.
• التقارب: تُظهر التجارب أن التنفيذ المتوازي يحقق نفس تقليل القابلية للاستغلال (exploitability reduction) عبر وقت التشغيل الفعلي، ولكن في جزء ضئيل من الوقت، حيث يصبح التسريع أكثر وضوحًا مع نمو حجم اللعبة.

الأهمية والادعاءات

يزعم البحث أنه بينما قد لا تزيد تقنية الموازاة هذه بالضرورة من حجم اللعبة التي يمكن حلها (من حيث سعة الذاكرة)، إلا أنها تقلل بشكل كبير من الوقت المطلوب لإيجاد الحل الأمثل.

• تسريع البحث: القيمة الأساسية هي تمكين الباحثين من اختبار الفرضيات، ومتغيرات CFR الجديدة، وأنظمة المعلمات الفائقة (hyperparameters) في أوقات استجابة أسرع بكثير.
• الإعدادات المتكررة: إطار العمل مفيد بشكل خاص للألعاب التي تُلعب في إعدادات متكررة (مثل البوكر مع أحجام رهانات متغيرة) حيث تكون أشجار الألعاب الفردية متشابهة، مما يسمح بإعادة الحل بسرعة.
• التوافق: يؤكد المؤلفون أن طريقتهم تحتفظ بالتوافق الكامل مع OpenSpiel، مما يسمح باستخدامها كمسرع مباشر لأبحاث نظرية الألعاب الحالية دون الحاجة إلى إعادة كتابة تعريفات الألعاب.
• التواضع: يذكر المؤلفون صراحة أن مساهمتهم ليست حصرية مع البنى السابقة (مثل تقسيم الألعاب الفرعية في Cepheus)؛ بل يمكن تعزيز تقنيتهم بتلك البنى لتحقيق مزيد من التوازي. كما يقرون بأنه بينما يقارنون بين GPU و CPU، فإن نتائجهم تسلط الضوء على إمكانات التوازي حتى في حالات الاستخدام العادية، رغم أنهم لا يدعون حل ألعاب كانت غير قابلة للحل سابقًا بسبب قيود الذاكرة.