خوارزمية جديدة تجد توازن ناش في 5600 لعبة بدقة 1e-5

يُعدّ حساب توازن ناش في ألعاب المجموع العام من المسائل المزعجة منذ زمن طويل، على تقاطع نظرية الألعاب وتعلّم الآلة. وتكاد تغيب الخوارزميات العامة التي تأتي بضمان تقارب عالمي. في الورقة arXiv:2609.16158 يقترح هونغبو سون طريقة تسدّ جزءًا كبيرًا من هذه الفجوة. تحل الخوارزمية ألعابًا تعسفية لـ m لاعبين و n إجراءً بأي دقة مطلوبة، وترث التقارب الخطي العالمي. وفي 5600 حالة مولّدة عشوائيًا انخفضت الفجوة إلى أقل من 1e-5 في جميع الحالات.

من سمبلكس واحد إلى حاصل ضرب السمبلكسات

يقوم العمل على إطار تتبّع المسار على الحزم الليفية (fiber bundle) الذي وصفه المؤلف في ورقته السابقة arXiv:2606.00778. كان ذلك الإطار يحل المتباينات التغايرية منتهية الأبعاد على سمبلكس، أي مجموعة التوزيعات الاحتمالية على مجموعة من الخيارات. وهذا لا يكفي للألعاب. ففي لعبة متعددة المشاركين يملك كل لاعب توزيعه الخاص على الإجراءات، فتتحول المنطقة المسموح بها إلى حاصل ضرب سمبلكسات.

الطريق المباشر هو إعادة إثبات جميع خصائص التقارب للمنطقة الجديدة، لكن سون اختار طريقًا آخر. فقد بنى متباينة تغايرية مكافئة على سمبلكس واحد، وأقام تماثلًا بين الحزم الليفية للإطارين. ثم أضاف حجة تمديد المقاطع (slice-extension) التي تنقل جميع الضمانات من العمل الأصلي. لا حاجة إلى نظرية تقارب جديدة، لأن النظرية القديمة تعمل عبر التكافؤ الهندسي.

الكائن الناتج حزمة ليفية مركّبة. وبحسب المؤلف، تتيح هذه الحزمة القفز على امتداد الطبقات لتجاوز النقاط المنفردة. وعند هذه النقاط تحديدًا تتوقف الضمانات المعتادة لطرق تتبّع المسار عن العمل.

ما الذي تضمنه الطريقة بالضبط

للتقارب الخطي العالمي هنا شكلان، والفرق بينهما جوهري:

• في التوازنات غير المنفردة يُوجد الحل بدقة تامة؛
• في التوازنات المنفردة تتحقق أي دقة محددة مسبقًا.

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

اختبار على 5600 لعبة

يقوم الجزء التجريبي على مقارنة التكوينات القصوى. تغطي الأبعاد المدى من لعبة بلاعبَين لكل منهما 128 إجراءً، إلى لعبة بـ128 لاعبًا لكل منهم إجراءان. وتختلف بنية هذه الأنماط:

• 2 لاعبين × 128 إجراءً: عدد قليل من المشاركين وفضاء استراتيجيات واسع؛
• 128 لاعبًا × إجراءان: عدد هائل من المشاركين باختيار ثنائي، ويتزايد فيه العدد الإجمالي لتركيبات الإجراءات أُسّيًا؛
• تكوينات وسيطة بين هذين القطبين؛
• 5600 حالة عشوائية في المجموع، ومعيار النجاح فجوة أقل من 1e-5.

بلغت الخوارزمية هذا العتبة في كل حالة. ويُستنتج من النتائج المعلنة أن السلسلة لم تشهد إخفاقات ولا حلقات مفرغة ولا تشغيلات فاشلة. وهذه إشارة قوية في الألعاب العشوائية، مع أن الحالات العشوائية لا تغني عن المسائل المهيكلة مثل تجريدات البوكر أو آليات الأسواق.

لماذا يهم هذا مهندسي الذكاء الاصطناعي

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

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

حصلت الورقة حتى الآن على صوتين متواضعين فقط في Hugging Face Daily Papers، لكن موضوعها من النوع الذي نادرًا ما يتصدر العناوين، ويحسم باستمرار ما إذا كان النظام متعدد الوكلاء سيتصرف بصورة يمكن التنبؤ بها.