اسمي ايغور فولكوف. أعمل في شركة استشارية كمطور جافا ، مهندس معماري ، قائد فريق ، مدير فني. أدوار مختلفة حسب الاحتياجات الحالية للمشروع. لفت الانتباه إلى المسابقات من mail.ru لفترة طويلة ، ولكن اتضح للمشاركة بنشاط في Paper IO.
هذه المرة ، اقترح المنظمون تنفيذ استراتيجية لإدارة الروبوتات على أساس اللعبة الشعبية. اقرأ المزيد عن القواعد هنا . يمكن العثور على رمز استراتيجيتي هنا ، وأمثلة من الألعاب على موقع البطولة .
في بداية المسابقة ، كما بدا لي ، كانت فكرة التنفيذ المنبثقة الأكثر شيوعًا هي استخدام MCTS . لذلك ، قضيت بعض الوقت في تجربة هذه الخوارزمية. وبدون معرفة كيفية استخدامها بفعالية لحل المشكلة ، قررت أن أبدأ بتوليد العديد من المسارات المستطيلة (مع اثنين ، ثم بثلاث دورات) وتقييمها اللاحق.
خوارزمية الاستراتيجية
يمكن تمثيل الخوارزمية عالية المستوى للاستراتيجية بالنقاط الست التالية:
- قراءة حالة العالم
- تحويل كائنات الرسالة إلى كائنات العمل
- تشكيل مجموعة من الطرق مستطيلة
- معدل كل من الطرق التي تم إنشاؤها
- اختيار أفضل طريق
- إرسال فريق
لم تتغير هذه الخوارزمية أثناء المنافسة. تم تعديل فقط طريقة تشكيل طرق السير وتقييمها.
تحتوي فئة SimpleStrategy على الإصدار الأولي من الاستراتيجية ، وفئة BestStrategy هي نسخة محسنة ، والتي احتلت المركز الثاني في المسابقة.
قراءة حالة العالم
تنتقل حالة العالم ككائن JSON عبر STDIN . لقد رأيت في pom.xml أنه يمكنك استخدام مكتبة Gson وأن مهمة قراءة حالة العالم قد تم تبسيطها إلى حد كبير. باستخدام مكتبة Gson ، أزال تسلسل سلسلة JSON من دفق الإدخال القياسي إلى مثيل لفئة الرسائل . الرمز في Main.java (الأسطر 44-49) .
إنشاء كائنات العمل
عادةً ما يكون استخدام كائنات النقل في رمز البرنامج الرئيسي غير مناسب للغاية ويعد خطأً من الناحية المعمارية. على سبيل المثال ، يمكن للمنظمين ، لسبب أو لآخر ، تغيير تنسيق الرسائل. لذلك ، من الضروري تحويل كائنات النقل إلى عمال ، والتي سيتم استخدامها في رمز البرنامج الرئيسي. تحافظ فئات Player و PlayerState على حالة الروبوت ، كما تساعد فئة الأدوات المساعدة MessagePlayer2PlayerConverter في إنشاء هذه الفئات بناءً على بيانات من رسالة النقل. تحتوي فئة المكافأة على معلومات حول مكافأة الخلية في الملعب. يوجد رمز إنشاء كائنات العمل في Main.java (الأسطر 61-74) .
في الإصدارات الأولى من الاستراتيجية ( SimpleStrategy ) ، تم تعيين المسار باستخدام فئات MovePlanWithScore و Move . تحريك Move يحدد اتجاه الحركة وعدد الخلايا التي يجب أن يتحرك الروبوت فيها في ذلك الاتجاه ، ويحتوي MovePlanWithScore على المسار المحدد بواسطة صفيف تحريك وتقدير لهذا المسار. يمكن أن تحتوي مجموعة من واحد إلى أربعة كائنات نقل . على الرغم من حقيقة أن الطرق المستطيلة التي لا تحتوي على أكثر من ثلاث لفات يتم أخذها بعين الاعتبار ، إلا أنه في الحقيقة يتم الحصول على مسار الروبوت في شكل خط مقطوع. يتم تحقيق ذلك عن طريق اختيار أفضل مسار مستطيل جديد في كل منعطف. تشكل وظيفة إنشاء المسار ، التي يتم تنفيذها على هيئة حلقات متداخلة ، قائمة من MovePlanWithScore لمزيد من التقييم.
لم يكن هذا التكوين لمسارات الروبوت فعالًا جدًا من حيث أداء التقييم اللاحق ، حيث كان من الضروري حساب نفس المسارات عدة مرات ، لكنه كان مفيدًا للغاية لفهم آليات اللعبة.
في الإصدارات الأحدث من الاستراتيجية ، بدأت BestStrategy في استخدام شجرة المسار. تعكس فئة MoveNode عقدة هذه الشجرة. تتشكل الشجرة بالكامل في بداية الاستراتيجية. انتبه إلى طريقة init لفئة MoveNode . إنه مشابه جدًا لإنشاء طرق من فئة SimpleStrategy . في الأساس ، لا يختلف المسار المطلوب كثيرًا عن الإصدار الأول.
في اعتقادي ، كان من الممكن تحسين تشكيل الطرق أكثر قليلاً بإضافة لمسة أخرى. ولكن لم يكن هناك وقت كافٍ للتحسين.
تقييم الطريق
أينما كان موقع الروبوت ، تم اختيار أفضل طريق ينتهي على أراضيها له دائمًا. لتقييم المسار ، قدمت مؤشرين: النتيجة والمخاطر. النتيجة - تعكس تقريبًا عدد النقاط التي تم تسجيلها لكل علامة في المسار ، والمخاطر - عدد علامات التجزئة التي لا تكفي لإكمال المسار (على سبيل المثال ، نظرًا لحقيقة أن الخصم يمكن أن ينتزع بواسطة الذيل). لم تظهر المخاطر على الفور. في الإصدار الأول ، إذا وجدت الروبوتات فجأة في منتصف المسار أنه لم يكن لديها وقت لإكمال المسار ، فقد "أصبح مجنونا" ، لأن جميع المسارات الخطرة كانت سيئة على قدم المساواة. من بين جميع المسارات التي تم النظر فيها ، يتم تحديد المسار الأكثر "أمانًا" مع الحد الأقصى لعدد النقاط لكل علامة في المسار.
لتقييم سلامة الطريق ، أقوم بحساب مصفوفة إمكانية الوصول: بالنسبة لكل خلية في ملعب اللعب ، أجد علامة يمكن أن يظهر عليها روبوت الخصم. أولا ، فقط علامة ، وبعد ذلك أضاف حساب طول الذيل. كما لم تؤخذ المكافآت التي يمكن الحصول عليها على طول الطريق في الاعتبار في الإصدارات الأولى من الاستراتيجية. تحسب فئة TimeMatrixBuilder مصفوفات القراد وأطوال الذيل للروبوتات المتنافسة. ثم يتم استخدام هذه المصفوفات لتقييم المخاطر. إذا كانت روبوتاتي موجودة على أراضيها وقت حساب الخطوة التالية - يتم تعيين الحد الأقصى لمستوى المخاطرة على طرق خطرة ، إذا كان روبوت السير بالفعل في منطقة أجنبية أو محايدة ، يتم تقييم المخاطرة على أنها الفرق بين علامات التجزئة لإكمال المسار (جاءت الروبوت إلى منطقته) والقراد عندما يمكن تهديد الخطر (على سبيل المثال ، يمكن أن بوت شخص آخر خطوة على الذيل).
في الإصدارات الأولى من الإستراتيجية ، تم اعتبار النتيجة فقط على أساس المنطقة التي تم الاستيلاء عليها وتم أخذ المكافآت في الاعتبار قليلاً. للعثور على الخلايا الملتقطة أستخدم خوارزمية متكررة . اشتكى العديد من المتسابقين من الغرابة والتعقيد الحسابي المفرط للخوارزمية التي يستخدمها المنظمون في Local Runner . سأفترض أن هذا قد تم عن قصد حتى لا يُمنح المشاركون في المسابقة حلول جاهزة.
غريب ، ولكن على الرغم من بدائية الإصدارات الأولى من الإستراتيجية ، فقد أظهرت نفسها بشكل جيد: المركز العاشر في صندوق الرمال. صحيح أنه في الجولة التمهيدية بدأ ينخفض بسرعة: قام المشاركون الآخرون بتحسين استراتيجياتهم.
بلدي بوت توفي في كثير من الأحيان. بادئ ذي بدء ، يرجع ذلك إلى حقيقة أنه تم بناء طريق إلى الأراضي التي استولت عليها الروبوتات المنافسين. تم إطالة المسار بشكل غير متوقع وتم القبض على روبوتي بواسطة الذيل. غالبًا مات بسبب تنبؤ غير صحيح بطول الذيل وسرعة روبوت الخصم. على سبيل المثال ، كان روبوت الخصم في حالة تباطؤ أمرًا خطيرًا ، حيث إن الاستراتيجية ، بحساب تقريبي ، افترضت أنه كان يجب عليه مغادرة الخلية بالفعل ، وكان لا يزال هناك. لمكافحة هذه المشكلات ، بدأت في حساب عدد أكبر من المؤشرات لكل خلية في حقل اللعب (فصول AnalyticsBuilder و CellDetails ).
عد خلايا الملعب
- ضع علامة يمكن أن يشغل فيها روبوت الخصم القفص (ضع علامة عند الذيل)
- ضع علامة عنده يمكن لروبوت الخصم دخول الخلية
- طول الذيل عند دخول القفص
- ضع علامة عنده يمكن لروبوت الخصم الخروج من القفص
- طول الذيل عند مغادرة القفص
- حدد أي خلية يمكن أن يتم التقاطها بواسطة روبوت الخصم
- ضع علامة على الخلية التي قد تكون هدفًا لالتقاط المنطقة
- ضع علامة على الخلية التي يمكن ضربها بمنشار
يقتصر عمق التحليلات على 10 خطوات. أعتقد أنه كان من الممكن تحقيق عمق أكبر من خلال التخلي عن حساب المنافسين الفرديين أو تقديم عمق عائم ، لكن لم يكن هناك وقت كافٍ للتحسين. بالإضافة إلى AnalyticsBuilder ، بدأ في استخدام SimpleTickMatrixBuilder إذا كان هناك نقص في التجسيد في AnalyticsBuilder . يتم استخدام نتائج التحليلات بواسطة BestStrategy .
لقد تحسنت أيضًا وظيفة التصنيف قليلاً:
- بدأت أخذ في الاعتبار المكافآت: عقوبة لأخذ مكافأة تباطؤ ومكافأة لأخذ مكافآت تسارع ورأيت. نتيجة لذلك ، بدأ الروبوت في تجنب المكافآت السيئة والتقاط مكافآت جيدة على طول الطريق.
- بدأ يأخذ في الاعتبار صراع الرؤوس. وأضاف بضع نقاط للاشتباك النصر. وكلما اصطدم ممكن ، وأقل نقاط.
- لتقليل احتمالية البيئة ، أضاف بضع نقاط لأخذ خلايا حدود الخصم.
- قلل من قيمة الخلايا الفارغة على الحدود: كلما كانت المسافة بعيدة عن المركز ، انخفضت القيمة. عندما شاهدت معارك النهائيات ، توصلت إلى استنتاج مفاده أنه من أجل الاستيلاء على خلية فارغة ، ليست هناك حاجة لتجميع نقاط على الإطلاق. يجب أن تعتمد قيمة الخلية الفارغة على القرب من مجموعات كبيرة من خلايا العدو. لسوء الحظ ، في النهاية لم يعد بالإمكان تعديل الإستراتيجية.
- نقاط إضافية للالتفاف على رئيس الروبوت المنافس. لست متأكدا إذا كان هذا ساعد بطريقة أو بأخرى. ربما مع أبسط الاستراتيجيات.
- لقد أضاف نقاطًا حتى للاستيلاء غير المجدي على الذيل (تمكنت روبوت الخصم من الاستيلاء على المنطقة في نفس العلامة التي صعد فيها روبوتي على ذيله). لست متأكدًا بالتأكيد ، لكنني أعتقد أن هذا منع روبوتات الخصم من الاستيلاء على أراضي شخص آخر وكان عليهم في كثير من الأحيان العودة إلى منطقتهم.
- في حالة اكتشاف احتمال الوفاة من الأسر ، زادت تكلفة الخلايا الحدودية في أراضي الخصم بشكل كبير.
تصحيح الاستراتيجية
تضمنت الإصدارات الأولى من الاستراتيجية عددًا كبيرًا من الأخطاء المطبعية والأخطاء: على ما يبدو ، نتيجة البرمجة الليلية. على سبيل المثال ، في فئة الخلية ، تم اعتبار الفهرس بشكل غير صحيح: بدلاً من this.index = x * Game.sizeY + y ، this.index = x * Game.width + y . في البداية حاولت الاعتماد فقط على الاختبارات ، لكن حدسي أشار إلى أنه بدون التصور وبدون لعب المباريات التي سبق لعبها ، سيكون من الصعب العثور على أخطاء في الشفرة وتحليل أسباب اتخاذ القرارات الخاطئة. نتيجة لذلك ، ظهر متخيل DebugWindow ، حيث يمكنك عرض الألعاب التي سبق لعبها خطوة بخطوة ، بالإضافة إلى بدء التصحيح على القراد المطلوب. الرمز ليس جميلًا جدًا ، مكتوبًا على عجل ، ولكنه ساعدني كثيرًا عند تصحيح الأخطاء. على سبيل المثال ، تم اكتشاف خطأ على الفور بحساب غير صحيح لمؤشر الخلية. عرض العديد من المتسابقين معلومات تصحيح الأخطاء في وحدة التحكم ، لكن بدا لي أنها غير كافية.
الأمثل
من أجل عدم إضاعة الوقت في إنشاء الكائنات وتشغيل GC ، حاولت إنشاء بعض الكائنات مسبقًا. هذه هي خلايا ساحة اللعب (فئة الخلية ). بالإضافة إلى كل خلية تحديد الجيران. إنشاء شجرة من المسارات المحتملة مقدما (فئة MoveNode ).
افترضت أنه يجب محاكاة العديد من السيناريوهات ، وفي هذه الحالة سوف تتدهور الحالة الحالية ويتعين استعادتها في كل مرة. لذلك ، للحفاظ على حالة العالم ، حاولت استخدام أكبر قدر ممكن من الهياكل المعبأة. لتخزين الأراضي المحتلة - BitSet (فئة PlayerTerritory ). يتم ترقيم كل خلية في حقل التشغيل ، ويتوافق رقم الخلية مع رقم البت في BitSet. لتخزين الذيل ، استخدمت BitSet مع ArrayDeque (فئة PlayerTail ).
صحيح ، لم أحصل على لعب سيناريوهات مختلفة بسبب ضيق الوقت. وحيث أن الوظيفة الرئيسية لحساب المسار أصبحت متكررة ويمكن تخزين الحالة بأكملها على المكدس ، فإن أحدث التحسينات لم تكن مفيدة للغاية بالنسبة لي.
أفكار غير محققة
عند تقييم مخاطر مسار روبوتي ، أخذت كل خصم في الاعتبار بشكل مستقل. في الواقع ، كل من المنافسين يخاف أن يموت. لذلك ، يجدر النظر في هذا في تقييم المخاطر. على الأقل ، كان لا بد من أخذ ذلك في الاعتبار في المباريات النهائية.
وهو ما يمثل الموت المستقبلي للخصم. يحدث في بعض الأحيان أن الروبوت يلتقط أراضي الخصم ، ويموت الخصم بشكل غير متوقع. إنه لأمر مخز ، لأنه نتيجة لذلك ، يمكنك التقاط خلايا فارغة فقط.
يمثل الخلايا الفارغة التي سيتم التقاطها في المستقبل القريب كدالة تقييم.
توصيات وشكرا
أوصي بأن يشارك جميع المطورين مشاركة نشطة في مسابقات AI Cups. هذا يطور التفكير ويساعد من خلال اللعبة على تعلم خوارزميات جديدة. وكما أوضحت تجربتي ، فإن الحماسة الصغيرة تكفي لشغل أحد الجوائز ، وحتى الرمز البسيط وليس الأمثل للغاية يمكن أن يحقق نتائج.
شكرا جزيلا للمنظمين. على الرغم من بعض المشاكل الفنية ، إلا أن المنافسة كانت مثيرة للاهتمام. أنا أتطلع إلى التالي!