تطوير الذكاء الاصطناعى باستخدام مثال لعبة Dicey Dungeons

لمدة شهر تقريبًا ، كنت أحل واحدة من أصعب المشكلات الفنية في لعبتي الجديدة ، Dicey Dungeons - الذكاء الاصطناعي المحسن للإصدار النهائي للعبة. لقد كان عملاً مثيراً للاهتمام إلى حدٍ ما ، وكان الكثير منه جديدًا بالنسبة لي ، لذلك قررت أن أكتب القليل عنه.

بادئ ذي بدء ، سأشرح لك: أنا لست خبيراً في نظرية أجهزة الكمبيوتر ، ولكن فقط أحد أولئك الذين درسوا البرمجة بما يكفي لإنشاء ألعاب فيديو ، وبعد ذلك تخرجت من التدريب ، ولم أتناول سوى ما أحتاج إليه. عادةً ما يمكنني حل مشاكلي بمفردي ، لكن من المرجح ألا يوافق مبرمج حقيقي على قراراتي.

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

حسنًا ، لنبدأ بشرح المهمة!

التحدي

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


مثال أكثر تعقيدًا: يحتوي Jack of all trades على مفتاح ربط ، والذي يتيح لك وضع زهرتين معًا (أي ، 3 + 2 سيعطي 5 ، و 4 + 5 سيعطي 6 و 3). لديه أيضًا مطرقة (Hammer) ، والتي تفرض تأثير "صدمة" على اللاعب ، إذا قمت بتطبيق ستة له ، ومطلق النار من البازلاء (Pea Shooter) ، الذي لا يلحق به أي ضرر كبير ، لكن له "عد تنازلي" ، هناك صالحة لعدة تحركات.


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


بالطبع ، هناك الكثير في اللعبة ، لكن للحصول على فكرة عامة ، هذا يكفي.

لذلك ، مهمتنا: كيفية الحصول على منظمة العفو الدولية لاختيار أفضل عمل لهذه الخطوة؟ كيف يمكن معرفة أي من المكعبات المحترقة التي سيتم إخمادها ، وأي المكعبات التي يجب استخدامها لتخفيف الصدمات ، وأيها يجب الاحتفاظ بها لأسلحة مهمة؟

كما فعل من قبل

لفترة طويلة ، كان لدى الذكاء الاصطناعي في Dicey Dungeons قاعدة واحدة فقط: نظر إلى جميع الأسلحة من اليسار إلى اليمين ، وحدد أفضل مكعب يمكن استخدامه عليه ، ثم استخدمه. هذا عمل رائع ، ولكن كانت هناك استثناءات. لذلك أضفت قواعد جديدة.

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

أضفت القاعدة بحكم لكل شيء يمكن أن أتخيله ، ونتيجة لذلك حصلت على الذكاء الاصطناعي الذي بدا أنه يعمل! في الحقيقة ، إنه لأمر مدهش كيف أظهر هذا التشابك بين القواعد المختلفة نفسه - منظمة العفو الدولية في Dicey Dungeons قد لا تتخذ دائمًا القرار الصائب ، لكنها كانت دائمًا مقبولة على الأقل. على الأقل لعبة ما زالت قيد التطوير.

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

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

لذلك قررت أن أبدأ من جديد.

الحل الكلاسيكي

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


تطبيق minimax كالتالي:

أولاً ، نقوم بإنشاء أبسط نسخة تجريدية من لعبتنا ، والتي تتوفر فيها جميع المعلومات اللازمة لنقطة زمنية محددة في اللعبة. سوف نسميها لوحة . في حالة الشطرنج ، هذه هي المواقف الحالية لجميع القطع. في حالة Dicey Dungeons ، هذه قائمة من النرد والأسلحة وتأثيرات الحالة.

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

ثم ، من هذه اللوحة التجريدية ، نحاكي جميع الحركات الممكنة التي يمكننا القيام بها ، والتي تعطينا لوحات تجريدية جديدة. ثم نقوم بمحاكاة إتمام جميع التحركات الممكنة على هذه اللوحات ، وما إلى ذلك ، بالعديد من الخطوات التي تريدها. فيما يلي توضيح ممتاز لحل مماثل من freecodecamp.org :


نقوم بإنشاء رسم بياني لجميع التحركات الممكنة التي يمكن أن يقوم بها اللاعبون ، وتطبيق دالة قيمة عليها لتقييم كيفية سير اللعبة.


وفي هذا ، يختلف Dicey Dungeons عن minimax: جاء minimax من النظرية الرياضية للألعاب ، وهو مصمم للعثور على أفضل سلسلة من الحركات في العالم حيث يسعى الخصم إلى زيادة نقاطه إلى الحد الأقصى. تسمى الخوارزمية ذلك لأنها تقلل من خسائر اللاعب عندما يلعب الخصم من أجل تحقيق أقصى قدر من المكاسب.

ولكن ماذا يحدث في ديسي زنزانات؟ في الواقع ، لا يهمني ما يفعله خصمي. لكي تكون اللعبة مثيرة ، يكفي الذكاء الاصطناعي أن يتخذ خطوات منطقية - لتحديد أفضل طريقة لتطبيق الزهر على الأسلحة ، حتى تكون المعركة عادلة. وبعبارة أخرى ، "الحد الأقصى" فقط هو المهم بالنسبة لي ، دون "المصغرة".

هذا يعني أنه لكي يقوم AI Dicey Dungeons بعمل جيد ، يكفي أن أقوم بإنشاء هذا الرسم البياني للحركات المحتملة والعثور على اللوحة التي حصلت على أعلى الدرجات ، ثم القيام بالتحركات المؤدية إلى هذه النقطة.

خطوة العدو سهلة

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


في الواقع ، لديها خياران فقط. ضع 1 على السيف العريض ، و 3 على الدرع ، أو قم بالعكس. من الواضح أنها تقرر أنه من الأفضل وضع 3 بدلاً من 1. ولكن لماذا؟ لأنها درست كل النتائج الممكنة:


إذا وضعت 1 على السيف ، فسنحصل على 438 نقطة. إذا وضعت 3 عليها ، فسنحصل على 558 نقطة. عظيم! لذلك ، أحصل على المزيد من النقاط عن طريق وضع السيف 3 ، تم حل المشكلة.

من أين تأتي هذه النظارات؟ يأخذ نظام التقييم في Dicey Dungeons في الاعتبار الجوانب التالية:

• الضرر: العامل الأكثر أهمية هو 100 نقطة لكل نقطة ضرر تعامل.
• السم: تأثير هام على الحالة يعتبره الذكاء الاصطناعى بنفس أهمية الضرر - 90 لكل سم.
• إنشاء تأثيرات حالة أخرى: على سبيل المثال ، الصدمة ، الحرق ، الضعف ، إلخ. كل منهم يكلف 50 نقطة.
• تأثيرات حالة المكافأة: تكلف إضافة تأثيرات إيجابية على اللاعب ، مثل الدفاع وما شابه ، 40 نقطة لكل منهما.
• استخدام الأسلحة: استخدام أي نوع من الأسلحة يكلف 10 نقاط ، لأنه إذا لم ينجح أي شيء آخر ، فعلى منظمة العفو الدولية فقط محاولة استخدام كل شيء.
• تخفيض العد التنازلي: لتفعيل بعض أنواع الأسلحة (على سبيل المثال ، ل Pea Shooter) ، المبلغ الإجمالي على الزهر يكفي فقط. لذلك ، يحصل الذكاء الاصطناعي على 10 نقاط لكل نقطة عد تنازلي.
• النقاط على النرد: تحصل الذكاء الاصطناعي على 5 نقاط لكل نقطة غير مستخدمة على النرد ، أي تكلف 1 نقاط و 6 تكلف 30 نقطة. يتم ذلك حتى لا تفضل منظمة العفو الدولية استخدام المكعبات التي لا تحتاج إلى استخدامها ، لذلك تصبح تحركاتها مشابهة جدًا لتلك التي في البشر.
• المدة: تفقد الذكاء الاصطناعى نقطة واحدة في كل دور ، لذلك فإن الحركات الطويلة لها قيمة أقل قليلاً من الحركات القصيرة يتم ذلك بحيث يكون هناك تحركان في حالة وجود تحركات تكون لهما قيمة متساوية ، فإن الخيار AI هو الأقصر.
• العلاج: لا تكلف سوى نقطة واحدة لنقطة صحية واحدة مستعادة ، لأنه على الرغم من أنني أريد أن أراعي منظمة العفو الدولية هذا الأمر ، إلا أنني لم أراقب حالتي الصحية حقًا. هناك دائما أشياء للقيام بها وأكثر أهمية!
• نقاط المكافأة: يمكن إضافتها إلى أي تحرك لإجبار منظمة العفو الدولية على فعل شيء ما لم يفعله أبدًا. تستخدم معتدلة جدا.

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

هذه الأرقام ليست مثالية - خذ على سبيل المثال المشكلات المفتوحة الحالية: 640 ، 642 ، 649 ، ولكن هذا ليس مهمًا جدًا. حتى الأرقام الدقيقة تقريبًا تكفي لتحفيز الذكاء الاصطناعي على فعل أكثر أو أقل بشكل صحيح.

تحركات أكثر صعوبة للعدو

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


شجرة قرارها اصعب "قليلاً":


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

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

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


سيد مفتاح. يقسم المكعب إلى قسمين.

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

لحسن الحظ ، لدى Dicey Dungeons حلاً رائعًا لكل من هاتين المشكلتين!

الحل الحديث

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


في الواقع ، بدلاً من إضافة كل حركة ممكنة إلى الرسم البياني ، تتحقق MCTS من تسلسل التحركات العشوائية ، ثم تتعقب تلك التي أثبتت أنها أفضل. بفضل صيغة تسمى Upper Confidence Bound ، يمكنه تحديد أي فروع لشجرة القرار هي "الواعدة":


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

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

تحتوي MCTS على ميزتين رائعتين مثاليتين لـ Dicey Dungeons:

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

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

مواضيع ذات صلة مثيرة للاهتمام

هذه هي الطريقة التي يقرر بها أعداء Dicey Dungeons كيف يقتلونك! أريد إضافة هذا النظام إلى الإصدار التالي من اللعبة v0.15!

من أين أتت الرسوم البيانية التي عرضتها ، بما في ذلك على twitter:


لقد قمت بإنشائها عن طريق كتابة مصدر لـ GraphML ، وهو تنسيق ملف رسم بياني مفتوح المصدر يمكن قراءته بواسطة العديد من الأدوات المختلفة. (اعتدت العيد الممتاز ، الذي أوصي به بشدة.)

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


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