💻 computer science

An ASP-based approach to Solving General Stochastic Two-Player Games

تقدم هذه الورقة البرمجة المنطقية لتعيين المجموعات العشوائية (SQASP) كأول نهج قائم على برمجة تعيين المجموعات (ASP) لحل ألعاب لغة وصف الألعاب العامة (GDL) ذات لاعبين بنظام تبادل الأدوار مع وجود عدم يقين، مما يثبت تنافسيتها مع البحث الأمامي في الألعاب العشوائية الصغيرة وإمكاناتها في تقييم نهاية اللعبة.

المؤلفون الأصليون: Yifan He, Michael Thielscher

نُشر 2026-05-25

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Yifan He, Michael Thielscher

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تحاول تعليم كمبيوتر كيف يلعب لعبة لوحية. عادةً ما تكون هذه الألعاب مثل الشطرنج: تقوم بحركة، ثم يقوم خصمك بحركة، وتتغير اللوحة بطريقة يمكن التنبؤ بها. ولكن ماذا لو تضمنت اللعبة أيضًا "ورقة رابحة" (Wild Card)؟ ماذا لو كان بعد حركتك، يقرر رمي نرد سحري ما إذا كانت حركتك ستنجح، أو إذا كان هناك لاعب ثالث غير مرئي (لنسمّه "العشوائي") سيضع عائقًا في طريقك؟

هذه الورقة البحثية تتحدث عن تعليم الحواسيب كيفية حل هذه الألعاب الملتوية وغير المتوقعة. لقد قام المؤلفان، ييفان هي ومايكل ثيلشير، ببناء مجموعة أدوات رياضية جديدة لتحديد أفضل استراتيجية ممكنة عندما يكون الحظ متدخلًا.

إليك تفصيل نهجهم باستخدام تشبيهات بسيطة:

1. المشكلة: اللاعب "العشوائي"

في نظرية الألعاب القياسية، تبرع الحواسيب في حساب الحركة المثالية ضد خصم ذكي. ولكن عندما تضيف العشوائية (مثل رمي النرد أو سحب البطاقات)، تصبح الرياضيات معقدة.

الطريقة القديمة: كانت برامج الكمبيوتر السابقة قادرة على التعامل مع الألعاب التي تضم لاعبين ذكيين (مثل الشطرنج) أو الألعاب التي تضم لاعبًا واحدًا وعنصرًا عشوائيًا (مثل سوليتير). لكنها لم تستطع التعامل مع لعبة تضم لاعبين ذكيين وعنصرًا عشوائيًا في آن واحد.
الهدف: أراد المؤلفان حل "ألعاب اللاعبين الاثنين العشوائية العامة". فكر في الأمر كلعبة "إكس-أو" (Tic-Tac-Toe) حيث توجد في كل مرة تحاول فيها وضع علامة (X)، فرصة بنسبة 30% أن تتحول المربع إلى (O)، أو احتمال 50% أن يتم حظر حركتك تمامًا.

2. الأداة الجديدة: SQASP (المخطط السحري)

اخترع المؤلفان لغة جديدة تسمى البرمجة المنطقية الإجابية العشوائية (SQASP).

التشبيه: تخيل أنك مهندس معماري يصمم منزلاً. لديك مخطط (قواعد اللعبة). في الماضي، كنت تستطيع فقط تصميم منازل لنوعين محددين من البناة: أحدهما عبقري استراتيجي (الخصم) والآخر روبوت يتبع قواعد صارمة.
الابتكار: SQASP يشبه نوعًا جديدًا من المخططات التي يمكنها وصف موقع بناء حيث لديك استراتيجي عبقري، وروبوت، ومقامر يعملون جميعًا معًا.
- العبقري (اللاعب X) يريد الفوز.
- الخصم (اللاعب O) يريد منع اللاعب X من الفوز.
- المقامر (العشوائي) يرمي عملة معدنية ليقرر ما سيحدث بعد ذلك.
يسمح SQASP للكمبيوتر بأن يسأل: "ما هي أعلى نسبة ممكنة للفوز لدي، بافتراض أن خصمي يلعب ببراعة لمنعي، وأن المقامر سيفعل ما يشاء؟"

3. المترجم: تحويل المخططات إلى لغز

الحواسيب لا تتحدث لغة "المخططات"، بل تتحدث لغة "الألغاز المنطقية".

العملية: بنى المؤلفان مترجمًا (أداة تسمى sqasp2xssat). يأخذ هذا المترجم مخطط SQASP الفخم ويحوله إلى لغز منطقي ضخم يسمى الإرضاء العشوائي الممتد (XSSAT).
الاستعارة: تخيل أن SQASP هو وصفة معقدة لكعكة. المترجم هو آلة تحول تلك الوصفة إلى لغز "سودوكو" ضخم متعدد الطبقات. بمجرد حل اللغز، تخبرك الإجابة بالاحتمالية الدقيقة للفوز في اللعبة.
المحلل (Solver): استخدموا محللاً موجودًا بالفعل (SharpSSAT) لفك شفرة هذا "السودوكو". إذا قال المحلل "نعم، يمكن حل هذا اللغز"، فهذا يعني أن اللاعب لديه استراتيجية فوز. وإذا حسب نسبة 67%، فهذه هي أفضل نتيجة ممكنة.

4. خدعة "إزاحة المكممات" (Quantifier Shifting)

اختبرت الورقة أيضًا تقنية تحسين محددة تسمى إزاحة المكممات.

التشبيه: تخيل أنك تنظم بطولة.
- الطريقة (أ) (الأساس): تسرد كل حركة لكل لاعب، ثم تتحقق مما إذا كانت الحركات قانونية، ثم تتحقق مما إذا كانت اللعبة قد انتهت.
- الطريقة (ب) (الإزاحة): تتحقق مما إذا كانت الحركات قانونية قبل حتى أن تسرد الحركات. يبدو هذا أسرع لأنك لا تضيع الوقت في التخطيط لحركات غير قانونية.
النتيجة: في الألعاب التي تضم لاعبين ذكيين (الألعاب الحتمية)، تعتبر خدعة "الإزاحة" هذه دفعة هائلة للسرعة. ومع ذلك، وجد المؤلفون أنه في الألعاب التي تضم "المقامر" (الألعاب العشوائية)، لم تحدث هذه الخدعة فرقًا كبيرًا.
لماذا؟ المحلل الذي استخدموه (SharpSSAT) ذكي جدًا؛ فهو يمتلك "محققًا" داخليًا (يسمى انتشار الوحدة - unit propagation) يستطيع اكتشاف الحركات غير القانونية من تلقاء نفسه، بغض النظر عن الترتيب الذي قدمت به التعليمات. لذا، لم يكن إعادة الترتيب الفاخر ضروريًا لهذا المحلل تحديدًا.

5. النتائج: كيف كان الأداء؟

اختبر الفريق نظامهم على تنويعات من ألعاب كلاسيكية مثل إكس-أو (Tic-Tac-Toe)، وكونكت-4 (Connect-4)، ونيم (Nim)، ولكن مع إضافة اللاعب "العشوائي".

الأداء: كانت طريقتهم الجديدة منافسة لطرق "البحث الأمامي" القياسية (التي تشبه قيام الكمبيوتر بلعب اللعبة ملايين المرات في ذهنه ليرى ما سيحدث).
العقبة: نجحت الطريقة بشكل رائع في اللوحات الصغيرة (مثل 3x3 أو 4x4). ومع ذلك، عندما أصبحت اللعبة كبيرة جدًا (مثل كومة مكونة من 100 قطعة في لعبة Nim)، أصبح اللغز المنطقي ضخمًا جدًا بحيث لا يستطيع الكمبيوتر حله في وقت معقول.
الخلاصة: هذا الأسلوب ممتاز لـ تقييم النهايات (Endgame Evaluation). إذا كانت اللعبة قد اقتربت من النهاية، يمكن لهذا النظام أن يخبر ذكاءً اصطناعيًا عامًا يلعب اللعبة: "مهلاً، إذا قمت بهذه الحركة، فلديك فرصة 99% للفوز"، مما يساعده في اتخاذ القرار النهائي.

ملخص

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

ما لم يدّعوه:

لم يدّعوا أن هذا يعمل في الألعاب التي لا يمكنك فيها رؤية اللوحة كاملة (مثل البوكر أو Krieg-Tic-Tac-Toe). فقد ذكروا صراحة أن طريقتهم مخصصة للألعاب التي يرى فيها الجميع اللوحة كاملة (المعلومات الكاملة).
لم يدّعوا أن هذا سيحل محل جميع طرق الذكاء الاصطناዊ الأخرى فورًا؛ بل أشاروا إلى أنه بديل لسيناريوهات محددة، خاصة في نهايات الألعاب.

ملخص تقني: نهج قائم على ASP لحل ألعاب اللاعبين اثنين العشوائية العامة

بيان المشكلة

تهدف أنظمة ألعاب اللعب العام (GGP) إلى لعب ألعاب استراتيجية بناءً على أوصاف وقت التشغيل دون معرفة مسبقة بالقواعد. وتعد لغة وصف الألعاب (GDL) وامتدادها GDL-II المعايير الرسمية لتحديد مثل هذه الألعاب، حيث تدعم GDL-II العشوائية (stochasticity) وعدم القابلية للملاحظة الجزئية. وبينما تم تطبيق برمجة المجموعات المستقرة (ASP) بنجاح لحل ألعاب GDL الحتمية ذات اللاعب الواحد أو اللاعبين اثنين، تفتقر أطر عمل ASP الحالية إلى القدرة على التعبير عن السلوكيات التنافسية (minimax) والعشوائية في آن واحد. وبناءً على ذلك، توجد فجوة في استخدام طرق تعتمد على ASP لحل ألعاب GDL ذات الدور المتناوب للاعبين اثنين والتي تنطوي على عدم اليقين.

المنهجية

يقترح المؤلفون نهجًا جديدًا لحل ألعاب GDL العشوائية للاعبين اثنين من خلال تقديم لغة جديدة ومحلل يعتمد على الترجمة.

1. برمجة المجموعات المستقرة الكمية العشوائية (SQASP)

لسد الفجوة بين ASP وحل الألعاب العشوائية، يقدم البحث لغة SQASP، وهي لغة توسع QASP (البرمجة المنطقية الكمية) باستخدام مكممات الاحتمالية.

الصيغة (Syntax): يأخذ برنامج SQASP الشكل $Q_1.x_1 \dots Q_n.x_n \ P$ ، حيث $P$ هو برنامج منطقي عادي، ويمكن أن تكون المكممات $Q_i$ وجودية ( $\exists$ )، أو شاملة ( $\forall$ )، أو احتمالية ( $\mathcal{R}_{p}$ ).
الدلالات (Semantics): يتم تعريف الاحتمال الأقصى لاستيفاء برنامج SQASP بشكل عودي. يقوم المكمم الاحتمالي $\mathcal{R}_{p}$ بتعيين احتمال $p$ لكون المتغير صحيحًا، ويحسب القيمة المتوقعة بناءً على احتمالات الصيغ الفرعية.
الترجمة: ينفذ المؤلفون أداة، sqasp2xssat ، تقوم بترجمة برامج SQASP إلى صيغ الرضا العشوائي الممتد (XSSAT). وتوسع XSSAT صيغ القيم المنطقية الكمية (QBF) بإضافة مكممات الاحتمالية. وتستفيد الترجمة من الأدوات الموجودة (مثل lp2sat) لتحويل البرنامج المنطقي $P$ إلى صيغة CNF يمثل نموذجها (models) المجموعات المستقرة لـ $P$ .

2. ترميز ألعاب GDL في SQASP

المساهمة الجوهرية هي بناء برنامج SQASP $\Psi$ بحيث يساوي أقصى احتمال استيفاء لللاعب $x$ ضمن $n$ من الخطوات ( $P_x^w(S_0, n)$ ). تتم عملية الترميز عبر مرحلتين رئيسيتين:

الأساس التعاوني (Cooperative Baseline): أولاً، يتم بناء برنامج منطقي $P_c$ بافتراض أن جميع اللاعبين (بما في ذلك الخصم $o$ واللاعب العشوائي $r$ ) يتعاونون للوصول إلى حالة نهائية يفوز فيها $x$ . يضمن هذا تقدم اللعبة بشكل صحيح، والإنهاء في غضون $n$ من الخطوات، وتحقيق حالة الهدف.
النمذجة التنافسية والعشوائية: يتم بعد ذلك توسيع البرنامج لالتقاط سلوكيات محددة لكل من الخصم والبيئة:
- اللاعب التنافسي ( $o$ ): يتم نمذجته باستخدام التكميم الشامل ( $\forall$ ) عبر متغيرات القرار (dec_o). وهذا يجبر المحلل على اعتبار السيناريو الأسوأ حيث يقلل الخصم من احتمالية فوز $x$ . يستخدم الترميز تمثيلًا لوغاريتميًا للأفعال لتقليل عدد القواعد.
- اللاعب العشوائي ( $r$ ): يتم نمذجته باستخدام مكممات الاحتمالية ( $\mathcal{R}_{1/i}$ ). يضمن الترميز أنه إذا لم تنتهِ اللعبة، فإن اللاعب العشوائي يختار بالضبط فعلًا قانونيًا واحدًا بشكل موحد من بين الحركات القانونية المتاحة. ويتم تحقيق ذلك من خلال عد الأفعال القانونية وتطبيق قيود الاحتمالية على متغيرات القرار (dec_r).

3. استراتيجيات التكميم

يبحث البحث في استراتيجيتين للتكميم لصيغة XSSAT الناتجة:

الطريقة الأساسية ( $Q_b$ ): توضع جميع الذرات غير الاختيارية (مثل legal و terminal) في الكتلة الوجودية الأكثر داخلية، متبعةً ترتيبًا زمنيًا صارمًا لذرات الاختيار.
الطريقة القائمة على التبعية ( $Q_d$ ): مستوحاة من التقنيات المستخدمة في الألعاب الحتمية، تعمل هذه الطريقة على إزاحة الذرات غير الاختيارية لتظهر في أقرب وقت ممكن في البادئة الكمية، مباشرة بعد ذرات الاختيار التي تعتمد عليها. يهدف هذا إلى تقليل مساحة البحث عن طريق تثبيت قيم مثل legal قبل التفرع على does.

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

أول محلل قائم على ASP للألعاب العشوائية في GDL: يقدم البحث أول نهج لحل ألعاب GDL ذات الدور المتناوب، العشوائية، للاعبين اثنين باستخدام ASP.
لغة SQASP: تقديم لغة البرمجة المنطقية الكمية العشوائية، التي توحد الاستدلال التنافسي والعشوائي ضمن إطار عمل برمجة منطقية.
محلل يعتمد على الترجمة: تطوير sqasp2xssat ، الذي يحول برامج SQASP إلى صيغ XSSAT، مما يسمح باستخدام محلالات XSSAT الموجودة (تحديدًا SharpSSAT) لحل الألعاب.
الصحة النظرية: يقدم المؤلفون براهين رسمية (النظرية 2 و 3) تثبت التكافؤ بين أقصى احتمالية فوز في لعبة GDL وأقصى احتمال استيفاء لصيغة SQASP/XSSAT الناتجة.

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

قام المؤلفون بتقييم نهجهم على متغيرات عشوائية من ألعاب Tic-Tac-Toe و Connect-4 و Nim، مقارنين الطريقة القائمة على SQASP (باستخدام كل من التكميم $Q_b$ و $Q_d$ ) مع محلل البحث الأمامي Expected Minimax (EMM).

الأداء: يعد النهج القائم على ASP منافسًا للبحث الأمامي في الألعاب العشوائية الصغيرة. في كثير من الحالات (مثل Tic-Tac-Toe و Connect-3)، يحسب محلل ASP احتمالات الفوز بشكل مشابه لـ EMM، وغالبًا في أطر زمنية مماثلة.
إزاحة المكمم: من المثير للدهشة أن التكميم القائم على التبعية ( $Q_d$ ) لم يحقق تحسينات كبيرة في الأداء مقارنة بالطريقة الأساسية ( $Q_b$ ) عند استخدام محلل SharpSSAT. ويعزو المؤلفون ذلك إلى آلية انتشار الوحدة (unit propagation) الداخلية في SharpSSAT، والتي يمكنها اشتقاق قيم الذرات (مثل legal) بغض النظر عن ترتيب المكمم، مما يخفف الحاجة إلى الإزاحة الصريحة.
حدود القابلية للتوسع: يواجه النهج صعوبة مع مساحات الحالة الكبيرة، مثل لعبة Nim العشوائية مع أحجام أكوام كبيرة. تصبح صيغ XSSAT الناتجة كبيرة جدًا (أكثر من مليون بند) بحيث يصعب على المحلات الحالية التعامل معها بكفاءة، بينما يتوسع EMM بشكل جيد بفضل البرمجة الديناميكية وجداول التحويل (transposition tables).

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

يدعي البحث أن النهج المقترح القائم على ASP يوفر بديلًا قابلًا للتطبيق لـ تقييم نهاية اللعبة (endgame evaluation) في أنظمة ألعاب اللعب العام. ومن خلال توسيع التطبيق الناجح لـ ASP في الألعاب الحتمية إلى المجال العشوائي، يوضح العمل أن البرمجة المنطقية يمكنها التعامل بفعالية مع عدم اليقين والاستدلال التنافسي.

يشير المؤلفون بتواضع إلى أنه بينما لا يهيمن النهج على البحث الأمامي في جميع الحالات (خاصة في الألعاب ذات مساحات الحالة الكبيرة جدًا أو الهياكل المحددة مثل Nim)، فإنه ينجح في تعميم النتائج السابقة للألعاب الحتمية لتشمل العشوائية. كما حددوا التوسع إلى عدم القابلية للملاحظة الجزئية (مثل Poker و Krieg-Tic-Tac-Toe) كاتجاه حرج للعمل المستقبلي، مع الإقرار بأن الطريقة الحالية محدودة بألعاب المعلومات الكاملة.