مرحبا بالجميع اسمي عليا. قبل أسبوعين ، انتهت مسابقة أخرى في CodinGame - مسابقة برمجة الروبوتات للعبة. لقد انضممت إلى أفضل 300 من المتصدرين في العالم ، لذا أود أن أخبركم لماذا المسابقات رائعة ومشاركة أسراري. وسيشارك إيفان سبيسورك ، الذي حصل على قائمة أفضل 100 متسابق في نفس المنافسة ، الأسرار.
سوف تتعلم كيفية المنافسة بنجاح في مسابقات برمجة الذكاء الاصطناعي في اللعبة.
ما هي لعبة CodinGame؟
codingame.com عبارة عن منصة تعليمية للمطورين من جميع الأعمار ومستويات التدريب. يمكنك الكتابة بـ 26 لغة : من C # و Python إلى Bash و Haskell. أروع شيء هو أن المهام هناك ليست مملة وغير مفهومة ، ولكنها ألعاب حقيقية مع واجهة مستخدم رسومية جيدة:
المسابقة عبارة عن مسابقة مدتها 10 أيام تُعقد مرة كل شهرين. يمكن لأي شخص المشاركة ، ليس من الضروري أن تكون أحد المرشحين النهائيين لـ ACM ICPC. بالطبع ، للوصول إلى القمة ، تحتاج على الأقل إلى فهم الخوارزميات النموذجية للذكاء الاصطناعي للألعاب.
ولكن من أجل قضاء أمسيتين باهتمام ، فإن المعرفة الأساسية كافية. يوجد في كل مسابقة رمز جاهز لقراءة بيانات الإدخال. يبقى فقط لقراءة القواعد ، وكتابة متواضع إذا كان آخر - وفي المعركة!
كود كوتولو
"Cthulhu Code" هي المسابقة الأخيرة التي جرت في الفترة من 15 إلى 25 يونيو. لمعرفة المؤامرة والغرض ، يكفي الوصف:
PH'NGLUI MGLW'NAFH CTHULHU R'LYEH WGAH'NAGL FHTAGN
ما يمكن أن يكذب إلى الأبد لم يمت على الإطلاق. ويموت الموت في دهر غامض.
اكتشفت أنت وفريق الباحثين الخاص بك قبر Cthulhu. هذا هو أسوأ قرار في حياتك ، لأنه لم يكن مستعدًا للاستيقاظ وهو الآن جائع لموتك. لكن الشفرة متاهة حقيقية ، ولا تتذكر أين كان المخرج ... إذا كان لا يزال موجودًا!
أوه ... ويبدو أن Cthulhu لم يكن وحده ، والآن هو يرسل الأعماق لك.
حاول أن تبقى على قيد الحياة لفترة أطول ، ولكن تذكر أنك لن تستمر طويلا ...
القواعد
سأقول على الفور أنه بدلاً من قراءة وصف نصي للقواعد ، يمكنك مشاهدة مقطع فيديو لتحليل القواعد والتكتيكات الأساسية من Tinsane :
خلاف ذلك ، تابع القراءة.
الخريطة
في اللعبة ، يسير أربعة لاعبين على الخريطة التي تم إنشاؤها - بشكل أكثر دقة ، الرسم البياني للخلايا المتصلة ببعضها البعض. المزيد على الخريطة يديرون أتباع العدو ، هدفهم اللحاق بالركب وتخويفهم.
الشخصيات
- الباحث هو أحد اللاعبين. يذهب في أي اتجاه على خلية واحدة. لديها قوى خارقة ، ولكن المزيد عنها لاحقًا.
- فاندر هو وحش أخضر. يظهر على الخريطة كل 5 أدوار ، من النقاط المعروفة سابقًا. يفرز أكثر من 3-6 حركات ، ويبحث عن أقرب لاعب ويبدأ السعي. يذهب مربع واحد فقط لكل دور. إذا لم يقبض على أي شخص في خطوات N ، فإنه يختفي من الخريطة.
- المشرح - يشبه الموت بمنجل. تظهر بدلاً من اللاعب الذي انخفضت صحته إلى أقل من 200 نقطة ، وظل على الخريطة حتى نهاية المباراة. "يرى" لاعب إذا لم تكن هناك جدران بينهما. إذا لم يغيب الهدف في حركتين ، فإن الخطوة التالية تقفز إلى المكان الذي شوهد فيه اللاعب آخر مرة.
البقاء
إذا دخل المتجول أو المشرح الخلية مع اللاعب ، يفقد اللاعب 20 حالة صحية. أيضا ، يفقد اللاعبون قدرا معينا من الصحة في كل دور دون سبب. ولكن إذا كان هناك باحثون حيون في محيط خليتين ، فسيتم فقدان القليل من الصحة.
الباحثون القوى العظمى
- PLAN - يزيد من الصحة بمقدار نقطتين خلال 5 دورات. إذا كان الباحثون الآخرون يقعون في دائرة نصف قطر العمل ، فإن التأثير يمتد إليهم ، ويتلقى منشئ التأثير صحة +2 لكل منهما. يمكنك استخدام مرتين لكل لعبة.
- YELL - يخيف اللاعب في الخلية التالية. يتحول الإجراء المخطط له في المنعطف التالي إلى انتظار (سيقف اللاعب ثابتًا). من المفيد إذا كان المتجول يلاحق العدو ، وتريد استبداله.
- ضوء - يضيء الخلايا في دائرة نصف قطرها 5 ، يمكنك استخدام 3 مرات في اللعبة. يساعد على تخويف المتجولين: عندما يحسبون المسار إلى أقرب هدف ، تحسب كل خلية مضاءة على أنها 4.
نهاية اللعبة
يموت اللاعب إذا انخفضت صحته إلى الصفر. بعد 200 حركة ، يبدأ اللاعبون الباقون في فقدان صحتهم بشكل أسرع ، وتنتهي اللعبة على الفور تقريبًا.
يعطي مطورو المسابقة القواعد للاعبين ، لكن اللاعبين الناجحين يذهبون إلى Github ويقرأون شفرة الحكم .
التكتيكات
يجب أن أقول على الفور أنني لم أبدأ من الصفر. في 16 يونيو ، عقد Kontur مراكز برمجة في سبع مدن - اجتماعات لأولئك الذين يرغبون في مناقشة المسابقة والاستمتاع في بيئة ممتعة ( صورة ).
لقد اجتزت الاختبار في الجامعة ولم أحضر إلى المركز الرئيسي في ايكاترينبرج ، لكنني استفدت من المكافأة من المنظمين - مجموعة المبتدئين. وهي متوفرة بلغتين - C # و TypeScript ، وهي تنفذ بالفعل البنية التحتية بالكامل: منطق قراءة حالة اللعبة عند كل منعطف ، بالإضافة إلى الفئات التي تميز اللعبة نفسها (مثل الحالة والإجراءات المحتملة) ، وبعضها الإضافي (على سبيل المثال ، مؤقت مخصص) . تمكنت على الفور من كتابة الشيء الأكثر إثارة للاهتمام - دماغي بوت باحث.
أحد قادة المركز في يكاترينبورغ هو فانيا داشكيفيتش ( سبيسورك ). لقد كان يجلس في CodinGame منذ أكثر من عام ، وشارك في سبع مسابقات ، وفي خمس مرات حقق أفضل 100 لاعب في العالم:
اكتشفت من فانيا تفاصيل القرار ، والتي زودته بالمركز 64 في لوحة الصدارة العالمية ، وقارنت قراره بقراري.
[1] تعال إلى المحاور: هناك يمكنك الحصول على روابط لمجموعات بداية ، ومناقشة القواعد ، ووضع التكتيكات والتعرف على أشخاص مهمين.
هذا في بداية المسابقة ، أنه في النهاية ، تبدو خوارزمية اختيار الخطوة التالية متشابهة:
- إنشاء جميع الإجراءات المتاحة للبوت ؛
- تطبيقها على الوضع الحالي ؛
- تقييم نتائج هذه التحركات ؛
- اختر الأفضل.
إنشاء الإجراءات المتاحة
أولستيكا : بالفعل في هذه الخطوة ، بدأت في تطبيق الاستدلال - تخيلت نفسي في مكان هذا الباحث ، وقررت ما هو جيد وما هو ليس كذلك. هل يمكنني الذهاب إلى الخلية المجانية التالية؟ أضف مثل هذه الخطوة. لا يزال لدي خطة غير مستخدمة ، ولا يوجد واندرر أو سلاشر في مكان قريب سيهاجمني في المنعطف التالي؟ أضف.
وفقًا للمخطط نفسه ، وقع LIGHT و YELL في قائمة الإجراءات المحتملة ، لكن استخدامها قلل من مستوى أدني في لوحة الصدارة. لذلك ، ما زلت أزالتهم من التنفيذ النهائي.
[2] لا تخف من تضمين الخيال: بالنسبة للمبتدئين ، فإن الاستدلال البسيط واثنين من العوامل الشرطية كافية.
تطبيق السكتة الدماغية
تسمى عملية تطبيق الانتقال إلى حالة اللعبة محاكاة. يسمح لك وجود المحاكاة باستخدام تقنيات برمجة الذكاء الاصطناعي المتقدمة: الحد الأدنى ، والخوارزميات الجينية ، و Monte Carlo Tree Search وغيرها.
أولستيكا : هذه هي الخطوة التي تتعلق بـ "التحفيز". "نيدو" - لأنه بعد أن ذهبت ، يجب أن يذهب بقية اللاعبين ، يجب أن يذهب الأعداء أو يعودون. ومع ذلك ، كنت كسولًا جدًا لإجراء محاكاة كاملة لأربعة لاعبين وعدد كبير من الأعداء بمنطق غير تافه. لذلك ، غيرت صحتي فقط اعتمادًا على ما إذا كنت وحيدًا أم في مجموعة ، ولم أجد هذا المتجول.
Spaceorc : لقد كان نهجي المعتاد مؤخرًا خطوتين:
- يمكنك الوصول إلى المسرح بأي شكل من الأشكال عندما يفتح المنظمون جميع القواعد وإسقاط مصدر "الحكم" على Github ؛
- تأخذ الحكم والكتابة ، والنظر إليه ، محاكاة.
المحاكاة كاملة ، مع جميع الفروق الدقيقة ، لكنها غير فعالة. أراهن عادةً على سرعة البحث وعمقه ... لكن المحاكاة الكاملة تسمح لك بتشغيل العديد من التطابقات محليًا ومقارنة الاستراتيجيات المختلفة. لقد اختبرت المحاكاة الكاملة مع CodinGame - توقعت مواقف التوابع ، مع العلم كيف سقط المنافسون (أي الخطوة التالية) ، واكتشفت التناقضات. عندما كانت المحاكاة الكاملة جاهزة ، بدأت في كتابة واحدة سريعة - للقيام بذلك ببساطة ، امتلاك واحدة عاملة.
[3] هل تريد الوصول إلى القمة؟ سيكون عليك معرفة القواعد وكتابة محاكاة.
محاكاة الخصوم
spaceorc : كتب مونت كارلو تري Search ، لكنه لعب بشكل أسوأ لأنه لم يكن هناك الكثير من الوقت للفرز. بشكل عام ، جاءني هذا النهج أكثر أو أقل فقط في Ultimate Tic-Tac-Toe . لعب الخصوم بنفس الطريقة - محاكاة لكل حركة بالإضافة إلى النتيجة ، حركاتي - MCTS واللعب حتى النهاية. كان من الممكن بهذه الطريقة محاكاة حوالي 50 لعبة حتى النهاية في 50 مللي ثانية. هذا لا يكفي لـ MCTS ، لذلك قمت بقصها وعادت إلى الفكرة الأصلية.
ونتيجة لذلك ، أصبحت المحاكاة السريعة غير مكتملة:
- توقفت عن التفكير في التجوال أكثر من 8 خلايا مني ؛
- توقفوا عن وضع اللصوص ، لأنهم تفرخوا بالفعل في 5 حركات ، وهذا هو عمق بحثي تقريبًا.
ونتيجة لذلك ، ازداد عمق البحث. حاولت أيضًا محاكاة التحركات فقط (بدون YELL ، LIGHT ، PLAN) من خصمي ، لكن الأمر كان أسوأ.
دالة التقييم
تساعد وظيفة التقييم على اختيار أفضل التحركات المتاحة. يأخذ حالة اللعبة عند الدخول ، وعند الإخراج يعطي رقمًا مع تقدير - كلما كان أكبر ، كلما كانت حالة اللعبة أفضل للاعب الحالي.
أولستيكا : ما هي المعايير التي تم تضمينها في تقييمي:
- صحة الباحث الخاص بي ؛
- المتجولون:
- إذا كان من المحتمل أن يأتي إلى هنا الخطوة التالية ، فهذه خطوة سيئة ؛
- إذا كنت على نفس الخط معه ، كلما كان البعد عنه أفضل ،
- إذا كان يفترسني أيضًا ، فإن المسافة تكون أكثر أهمية.
- الخلايا الحرة حولها ، حتى لا تصطدم بطريق مسدود ؛
- باحثون آخرون ، من الأفضل البقاء على مقربة منهم ؛
- الخطة الحالية: إذا انخفضت صحتي إلى ما دون 230 ، فإن العلاج فكرة جيدة.
في مرحلة ما ، حاولت تقييم القطع المائلة ، ولكن عندما أزلتها ، تم ترقيتي إلى عشرات الأماكن في لوحة الصدارة. إذا عملت على تحسين منطقهم ، فربما سيفعلون المزيد من الخير.
نتيجة لذلك ، قد يكون تقييمي أصغر ، ولكن كما يقولون ، يعمل - لا تلمس.
Spaceorc : لقد حاولت التلاعب بوظائف التقييم ، لكنها لم تنجح بشكل جيد للغاية ... بشكل عام ، بعض الذين تبين أنهم أعلى مني بكثير في لوحة الصدارة لم يجتازوا الكثير على الإطلاق ، لكنهم توصلوا إلى ميزات جيدة للتقييم. لم أتعامل مع هذا. تضمنت وظيفتي التقييم النهائية:
- عدد النقاط (الجولة التي ماتت فيها + الصحة) ؛
- كرو
- المسافة إلى الباحثين الأجانب.
[4] التجربة: تغيير معاملات معلمات دالة التقييم ، وإضافة معلمات جديدة وحذف المعلمات القديمة.
اختيار أفضل حركة
نرتب التحركات بترتيب تنازلي ونأخذ الخطوة الأولى ونستخدمها.
التحسين
لا يكفي التنافس على مكان في المئات الأعلى للحصول على وظيفة تقييم جيدة ومحاكاة كاملة. كلما عمل الروبوت بوتيرة أسرع ، سيتم محاكاة المزيد من الألعاب في شريحة زمنية. كلما زاد عدد الألعاب ، زادت احتمالية أن تكون الخطوة الحالية هي الأمثل. كلما كانت الحركة مثلى ، زاد المكان في لوحة الصدارة.
أوليستيكا : استفدت من حقيقة أن الخريطة يمكن تمثيلها في شكل رسم بياني - لقد حسبت مقدماً أطوال جميع المسارات من خلية إلى أخرى ولم أقضي وقتًا في ذلك في كل مرة.
spaceorc: في CodinGame ، عملت المحاكاة بسرعة ، في 50 مللي ثانية ، قامت بعشرات الآلاف من الحركات. بسبب:
- أقنعة البت والرمز غير الآمن.
- Explorer - int و wanderer - int و slasher - int.
- تتناسب جميع الحالات القابلة للتغيير في 128 بايت ، لذلك يعمل كل شيء معها بسرعة كبيرة.
- الإحداثيات بايت ، لأن أكبر خريطة بها 222 خلية مجانية.
- يجب أن تكون قائمة الانتظار - var queue = stackalloc byte [255].
- الحساب المسبق للمسارات والمسافات وأشياء أخرى.
لقد كنت أفعل ذلك طوال الوقت مؤخرًا ، إنه جيد جدًا. بالمناسبة ، أكتب دائمًا الكثير من الاختبارات لمثل هذه المحاكاة ، والتي بدونها لا يمكن تصحيحها ببساطة.
[5] هل تريد التنافس على مكان في أفضل 100 - تخلص من التعليمات البرمجية غير الفعالة.
ما أدى إلى
أولستيكا : طوال المسابقة ، ظل بوتي ثابتًا في قائمة أفضل 300 لاعب. في مرحلة ما ، كنت حتى في المركز 84 في لوحة المتصدرين العالمية ، ولكن بعد ذلك طلبت نسخة جديدة ولم أعود ¯ \ (ツ) / ¯ بعد أن انتهيت من المركز 290 ، أنا سعيد جدًا لثلاثة أسباب:
- هذه هي المسابقة الأولى التي شاركت فيها بشكل كامل ، حيث كنت مشغولاً للغاية بالدراسات في الماضي.
- أحببت اللعبة نفسها - كان من الواضح كيف تلعب وماذا تفعل للفوز.
- أفضل 15٪ على مستوى العالم - يبدو ذلك رائعًا :)
كان من الواضح أنه للوصول إلى القمة ، تحتاج إلى إجراء محاكاة كاملة وسريعة. لكنني لم أرغب في القيام بذلك ، لذلك أضفت للتو معلمات إلى وظيفة التقييم وغيرت الثوابت السحرية.
Spaceorc : أنا راضٍ إلى حد ما عن النتيجة ، وذهبت إلى أفضل 100 ... ولكن مع ذلك كان عليّ أن أعمل أكثر في وظيفة التقييم ، فقد ظهر انحياز قوي تجاه المحاكاة. لقد تعبت قليلاً في النهاية ، لم يكن خيالي كافياً ...
في الختام
تحقق من CodinGame وجرب يدك! في تموز (يوليو) ، يعدون بمسابقة جديدة - تعالوا إلى المحاور ، سنقوم بترميز البوتات معًا.
روابط مفيدة:
UPD شكرا dbf على التعليق: تم تحميل كود Kutulu إلى متعددة اللاعبين . لذا يمكنك وضع المعرفة المكتسبة في المقالة موضع التنفيذ! :)