Mini ai cup 2 أو AgarIO تقريبًا - ما الذي يمكن فعله للفوز

مرحبا بالجميع! هذه المرة أريد أن أكتب عن كيف تمكنت من الفوز بمسابقة Mini AI Cup 2 . كما هو الحال في مقالتي الأخيرة ، لن يكون هناك أي تفاصيل تنفيذية. هذه المرة كانت المهمة أقل حجمًا ، ولكن مع ذلك كان هناك الكثير من الفروق الدقيقة والأشياء الصغيرة التي تؤثر على سلوك الروبوت. ونتيجة لذلك ، حتى بعد ما يقرب من ثلاثة أسابيع من العمل النشط في الروبوت ، كانت لا تزال هناك أفكار حول كيفية تحسين الاستراتيجية.



تحت قطع الكثير من صور متحركة وحركة المرور.

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

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

رابط للمصدر على جيثب .

اختيار الأداة

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

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

كما كان من قبل ، أردت حقًا تصحيح أي علامة في اللعبة - القدرة على تشغيل إستراتيجية في لحظة اعتباطية من اللعبة المختبرة. نظرًا لأن المصور الإضافي لا يمكنه حل هذه المشكلة ، بمساعدة زوج #ifdef (الذي قمت فيه أيضًا بتغليف أجزاء التعليمات البرمجية المسؤولة عن العرض) ، أضفت إلى كل علامة حفظ فئة السياق ، والتي تحتوي على جميع القيم الضرورية للمتغيرات من القراد السابق. في جوهره ، كان الحل مشابهًا لما استخدمته في Code Wizards ، لكن هذه المرة لم يكن النهج عفويًا. بعد محاكاة اللعبة بأكملها ، طُلب منك إدخال رقم علامة اللعبة ، والذي يجب إعادة تشغيله. تم الحصول على معلومات حول حالة المتغيرات قبل هذا القراد من المصفوفة ، وكذلك الخط الذي تلقته استراتيجية الإدخال ، مما سمح لي بلعب تحركات استراتيجيتي بأي ترتيب ضروري.

ابدأ

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

وبعد ذلك ... بدأت في معرفة الخيارات وكيفية تطويرها. الأفكار في ذلك الوقت:

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

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

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

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


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

كتابة محاكاة

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

كانت وظيفة التصنيف لكل علامة في تلك اللحظة هي +1 للطعام الذي أتناوله و -1 للطعام الذي يأكله العدو ، بالإضافة إلى قيم أكبر قليلاً لتناول طعام agarics لبعضهم البعض. في ثوابت تناول agarics أخرى ، كان هناك في البداية فرق بين أكل خصمي ، خصمي (وبالطبع ، غرامة كبيرة جدًا لأكل آخر agarika من قبل الخصم) ، بالإضافة إلى خصمين مختلفين لبعضهما البعض (بعد بضعة أيام أصبح المعامل الأخير 0). بالإضافة إلى ذلك ، السرعة الإجمالية لجميع القراد السابق للمحاكاة ، تم ضرب كل علامة في 1 + 1e-5 لتشجيع الروبوت الخاص بي على تنفيذ إجراءات أكثر فائدة على الأقل في وقت سابق على الأقل ، وفي نهاية المحاكاة ، تمت إضافة سرعة القراد الأخير كمكافأة ، أيضًا صغيرة جدًا . لمحاكاة حركة agarics ، تم تحديد النقاط على حافة الخريطة بخطوة 15 درجة من إحداثيات الوسط الحسابي لجميع agarics ، وتم اختيار نقطة ، عند محاكاة الحركة التي اتخذت لها وظيفة التقدير القيمة الأكبر. وبالفعل مع مثل هذه المحاكاة البدائية التي تبدو وتقييم بسيط في ذلك الوقت ، ترسخ البوت بثقة في أعلى 10.


خلال مساء الجمعة والسبت ، تمت إضافة محاكاة لدمج agarics ، ومحاكاة "تقويض" الفيروسات ، وتخمين TTF للخصم. كان TTF الخاص بالخصم قيمة محسوبة مثيرة للاهتمام إلى حد كبير ، وكان من الممكن أن نفهم في أي نقطة قام فيها الخصم بالانقسام أو وصل إلى الفيروس فقط من خلال التقاط لحظة الرحلة غير المنضبط ، والتي يمكن أن تستمر من عدد صغير جدًا من القراد مع لزوجة كبيرة وحتى الرحلة من خلال الخريطة بأكملها. نظرًا لأن التصادمات العنيفة يمكن أن تؤدي إلى زيادة طفيفة في سرعتها القصوى ، لحساب TTF الخاص بالخصم ، فقد تحققت من أن سرعته في قُرادتين متتاليتين تتوافق حقًا مع السرعة التي يمكنك من خلالها الحصول على قرادتين على التوالي في رحلة مجانية (في رحلة مجانية ، طار agarics بشكل مستقيم تمامًا ومع تباطؤ كل علامة تساوي بدقة اللزوجة). أدى هذا تقريبًا إلى القضاء تمامًا على إمكانية وجود نتائج إيجابية خاطئة. أيضًا ، أثناء اختبار هذا المنطق ، لاحظت أن TTF الأكبر يتوافق دائمًا مع معرف أكبر لـ agaric (والذي كنت مقتنعًا به لاحقًا عند نقل رمز الانفجار على الفيروس ومعالجة الانقسام ) ، وهو أمر يستحق أيضًا استخدامه.

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

في ذلك الوقت ، كان هذا كافياً ، وتم وضع "العمود الفقري" للاستراتيجية ، وبدت الاستراتيجية بدائية للغاية وقابلة للتوسيع. ولكن ما لاحظته حقًا هو استهلاك وحدة المعالجة المركزية واستقرار الرمز بشكل عام. لذلك ، تم تخصيص أمسيات جزء العمل التالي من الأسبوع بشكل أساسي لتحسين دقة المحاكاة (التي ساعدها المصور كثيرًا) ، وتثبيت الكود (valgrind) وبعض التحسينات لسرعة العمل.

دعنا نمضي قدما

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

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


تحولت فائدة ذاتية مختلفة تمامًا إلى أنها محاكاة مزدوجة للعدو مع TTFs مختلفة - الحد الأدنى والأقصى ممكن (في حالة أنني لا أعرف TTF لجميع agarics المرئي على الخريطة). وإذا كان بوتي في وقت سابق يعتقد أن مجموعة العدو من agarics ستصبح وحدة واحدة وتتحرك ببطء ، فقد اختار الآن أسوأ السيناريوهين ولم يخاطر بأن يكون قريبًا من العدو ، الذي يعرف عنه أقل مما يريد.

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


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

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

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


بالإضافة إلى ذلك ، تمت إضافة نقاط محاكاة الحركة إلى النقاط الموجودة على حافة الخريطة: إلى كل agarik من المنافسين وضمن دائرة نصف قطرها من إحداثيات الوسط الحسابي agariki كل 45 درجة. تم ضبط نصف القطر على متوسط ​​المسافة من إحداثيات الوسط الحسابي لغارياتي.

التحضير النهائي

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

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


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

بدلا من الاستنتاج

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