كيف توقفت عن الخوف وكتبت بوت لعبة

أو البرمجة الديناميكية القديمة الجيدة بدون هذه الشبكات العصبية.

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


شاشة اللعبة من خادم مشروع Codenjoy

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

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

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

سيتم إعطاء جميع الأمثلة من اللعبة في عرض مبسط ، والذي تم استخدامه في سجلات البرنامج:

جزء من النظرية

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

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

• إحداثيات اللاعب
• إحداثيات جميع الثقوب التي اخترقها جميع اللاعبين
• إحداثيات كل الذهب على الخريطة (أو إحداثيات الذهب الذي تم تناوله مؤخرًا)
• إحداثيات جميع اللاعبين الآخرين

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

وبالتالي ، فإن الحالة الحالية للعبة هي:

• إحداثيات اللاعب
• إحداثيات جميع الحفر

تصرفات اللاعب تغير الحالة بطريقة مفهومة:

• تغير أوامر الحركة أحد الإحداثيات المقابلة
• يضيف فريق حفر الحفرة حفرة جديدة
• إن سقوط لاعب بدون دعم يقلل الإحداثيات العمودية
• إن تقاعس اللاعب الواقف عن الدعم لا يغير الحالة

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

من أجل البساطة ، سنحتفظ بتقرير الوقت عن الخطوة الحالية ، أي الحركة الحالية هي t = 0.
نشير إلى حالة اللعبة خلال ر$$$x^t$.
الكثير من$$ ستشير إلى جميع الإجراءات الصحيحة للبوت (في حالة معينة ، ولكن من أجل البساطة لن نكتب فهرس الحالة) ، من خلال $$نشير إلى إجراء محدد على الدورة t (نحذف المؤشر).
حالة$$$x^t$ تحت تأثير $$يذهب إلى الدولة $$$x^{t+1}_a$.

الفوز عندما يكون العمل في حالة$$$x^t$ نشير إلى أنه $$$P(x^t, x^{t+1}_a)$. عند حسابه ، نفترض أنه إذا أكلنا الذهب ، فإنه يساوي G = 100 ، إذا ماتوا ، ثم D = -100500 ، وإلا 0.

دعنا$$$F(x^t)$هذه هي دالة العائد للعبة المثالية لبوت موجود في الحالة س في الوقت ر. ثم نحتاج فقط إلى العثور على إجراء يزيد$$$F(x^0)$.

الآن نكتب الصيغة الأولى ، وهي مهمة جدًا وفي نفس الوقت تقريبًا صحيحة:

$$

$$F(x^0) = \max_{a \in A} F(x^1_a) + P(x^0, x^1_a)$$

أو لنقطة اعتباطية في الوقت المناسب

$$

$$F(x^t) = \max_{a \in A} F(x^{t+1}_a) + P(x^t, x^{t+1}_a)$$

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

يبدو أن المشكلة قد تم حلها ، ولكننا هنا نواجه مشكلة أنه إذا كان علينا في كل خطوة أن نفرز من خلال 6 إجراءات للاعبين ، عندها في الخطوة N من العودية ، علينا أن نفرز من خلال 6 خيارات N ، والتي لـ N = 8 هي بالفعل عدد لائق جدًا ~ 1.6 مليون حالة. من ناحية أخرى ، لدينا معالجات gigahertz الدقيقة التي ليس لديها ما تفعله ، ويبدو أنها ستتعامل تمامًا مع المهمة ، وسنقتصر عمق البحث عليها مع 8 حركات بالضبط.

وهكذا ، فإن أفق التخطيط لدينا هو 8 حركات ، ولكن من أين نحصل على القيم$$$F(x^9)$؟؟؟ وهنا نخرج بفكرة أننا قادرون على تحليل آفاق المركز بطريقة أو بأخرى ، وتخصيصه بعض القيمة بناءً على اعتباراتهم العليا. اسمحوا ان$$$F(x^9)=S(x^9)$أين $$$S(x)$هذه هي وظيفة الاستراتيجية ، في أبسط نسخة هي مجرد مصفوفة نختار منها القيمة وفقًا للإحداثيات الهندسية للبوت. يمكننا القول أن التحركات الثمانية الأولى كانت تكتيكًا ، ثم تبدأ الاستراتيجية. في الواقع ، لا أحد يقيدنا في اختيار استراتيجية ، وسوف نتعامل معها لاحقًا ، ولكن في الوقت الحالي ، حتى لا نصبح مثل بومة من نكتة عن الأرانب والقنافذ ، سننتقل إلى التكتيكات.

مخطط عام

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

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

• روبوت يقف في مكانه لفترة طويلة
• المشي المستمر من اليسار إلى اليمين
• قلة الدخل لفترة طويلة

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



يمكن لخصومك تجميد وإغلاق طريقك القصير إلى الذهب المرغوب - سنتعامل مع كل هذا لاحقًا.

محاربة التسويف

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

• خطوة يسار - خطوة يمين - خطوة يمين
• خطوة إلى اليمين - تقاعس - تقاعس
• تقاعس - تقاعس - خطوة يمين

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

$$

$$F(x^0) = \max_{a \in A} F(x^1_a)*E + P(x^0, x^1_a)$$

قمنا بضرب المكاسب المستقبلية في الخطوة التالية في "معامل التضخم" E ، والذي يجب اختياره بأقل من 1. يمكننا أن نجرب بأمان قيم 0.95 أو 0.9. ولكن لا تختره صغيرًا جدًا ، على سبيل المثال ، بقيمة E = 0.5 ، سيجلب الذهب الذي يتم تناوله في الحركة الثامنة 0.39 نقطة فقط.

وهكذا ، أعادنا اكتشاف مبدأ "لا تؤجل حتى اليوم ما يمكنك أن تأكله اليوم".

سلامة

إن جمع الذهب أمر جيد بالتأكيد ، لكنك ما زلت بحاجة إلى التفكير في الأمن. لدينا مهمتان:

• علم البوت لحفر الثقوب إذا كان الوحش في وضع مناسب
• تعليم الروبوت أن يهرب من الوحوش

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

إذا بدأوا في الاقتراب منا ، فسيبدأ البوت نفسه في الهروب منهم ، لأنه سيتم تغريمه لكونه قريبًا جدًا منهم (نوع من العزلة الذاتية). وهكذا ، نقدم قاعدتين:

• إذا وصلنا إلى الوحش على مسافة d و d <= 3 ، فسيتم فرض غرامة قدرها 100،500 * (4-d) / 4 علينا
• إذا اقترب الوحش بما فيه الكفاية ، فهو على نفس الخط معنا وهناك فجوة بيننا ، عندها نحصل على بعض الربح P

مفهوم "اقترب من الوحش على مسافة د" سنفتح بعد ذلك بقليل ، ولكن الآن ، دعنا ننتقل إلى الاستراتيجية.

نذهب حول الرسوم البيانية

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



في الخطوة الأولى ، نختار جميع الخلايا التي يمكننا من خلالها الوصول إلى الذهب في خطوة واحدة ونعينها إلى 1. في الخطوة الثانية ، نختار جميع الخلايا التي نقع منها في خلايا في خطوة واحدة ونعينها إلى 2. تظهر الصورة الحالة لـ 3 خطوات. الآن دعنا نحاول كتابة كل شيء بشكل رسمي ، في شكل مناسب للبرمجة.

سنحتاج إلى:

• مسافة المصفوفة الرقمية ثنائية الأبعاد [س ، ص] ، التي سنخزن فيها النتيجة. في البداية ، بالنسبة لإحداثيات الذهب ، يحتوي على 0 للنقاط المتبقية -1.
• صفيف oldBorder ، الذي سنقوم فيه بتخزين النقاط التي سننتقل منها ، يحتوي في البداية على نقطة واحدة بإحداثيات ذهبية
• Array newBorder ، حيث سنقوم بتخزين النقاط الموجودة في الخطوة الحالية

1. لكل نقطة p من oldBorder نجد جميع النقاط p_a التي يمكننا من خلالها الوصول إلى p في خطوة واحدة (بتعبير أدق ، نتخذ فقط جميع الخطوات الممكنة من p في الاتجاه المعاكس ، على سبيل المثال ، التحليق لأعلى في غياب الدعم) والمسافة [p_a] = - 1
2. نضع كل هذه النقطة p_a في المصفوفة newBorder ، على مسافة [p_a] نكتب رقم التكرار
3. بعد الانتهاء من جميع النقاط:
4. قم بتبديل صفائف oldBorder و newBorder ، وبعد ذلك نقوم بمسح newBorder
5. إذا كان oldBorder فارغًا ، فأنهي الخوارزمية ، وإلا انتقل إلى الخطوة 1.

نفس الشيء في الكود الزائف:

iter=1;
newBorder.clear();
distance.fill(-1);
distance[gold]=0;
oldBorder.push(gold);

while(oldBorder.isNotEmpty()) {
  for (p: oldBorder){
    for (p_a: backMove(p)) {
      if (distance[p_a]==-1) {
         newBorder.push(p_a);
         distance[p_a]=iter;
      }
    }
  }
  Swap(newBorder, oldBorder);
  newBorder.clear();
  iter++;
}

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

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

قمت بتكملة الصورة بالأرقام ، بما في ذلك مراعاة حفر حفرة والقفز إليها:



ما الذي يذكرنا به هذا؟



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

1. لكل ذهب ، نقوم ببناء خريطة المسافة ونجد المسافة إلى اللاعب.
2. اختر الذهب الأقرب للاعب وأخذ بطاقته لحساب الاستراتيجية
3. لكل خلية من الخارطة ، حدد د المسافة بينها وبين الذهب ، ثم القيمة الاستراتيجية
   

   $$

   $$S(x) = \begin{cases} 0 & \text{ $d < 0$,}\\ G_s E_s^d & \text{ $d \geq0$ } \end{cases}$$

أين $$$G_s$هذه بعض القيمة الخيالية للذهب ، ومن المستحسن أن يتم تقييمه عدة مرات أقل من الحاضر ، و $$$E_s$هذا معامل تضخم <1 ، لأنه كلما زاد الذهب الخيالي ، كلما كان أرخص. نسبة المعاملين E و$$$E_s$يشكل مشكلة الألفية التي لم تحل ويترك مجالا للإبداع.

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

قبل الانتقال إلى استراتيجيات أكثر إثارة للاهتمام ، سنقوم بإجراء تحسين آخر. في اللعبة ، تسحب الجاذبية اللاعب إلى أسفل ، ويمكنه فقط صعود الدرج. لذا ، يجب تقييم الذهب الأعلى. إذا تم الإبلاغ عن الارتفاع من الخط العلوي لأسفل ، فيمكنك مضاعفة قيمة الذهب (بإحداثيات y الرأسية) في$$$E_h^y$. لمعامل$$$E_h$ تم صياغة المصطلح الجديد "معدل التضخم الرأسي" ، على الأقل لا يستخدمه الاقتصاديون ويعكس الجوهر بشكل جيد.

استراتيجيات التعقيد

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

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

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

تختلف الاستراتيجية مع التكتيكات

هنا يأتي روبوتنا إلى الذهب تحت الأرض:



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



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

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

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

$$

$$p_{new}(x^0,x^1_a) = p(x^0,x^1_a) + (S(x^1_a) – S(x^0)).$$

قيمة الدالة الهدف على الأخيرة تساوي صفر بشكل عام: $$$F(x^9) =0$. نظرًا لأن المكاسب يتم استهلاكها مع كل حركة من خلال الضرب في معامل ، فإن هذا سيجعل مكاسبنا الآلية مكاسب إستراتيجية أسرع ويزيل المشكلة الملحوظة.

استراتيجية غير مجربة

لم أختبر هذه الاستراتيجية عمليًا ، لكنها تبدو واعدة.

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

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

التحسينات النهائية

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

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

ميزات التنفيذ

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

كود المصدر وخادم اللعبة

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

يمكنك بدء الخادم بالسطر التالي:

call mvn -DMAVEN_OPTS=-Xmx1024m -Dmaven.test.skip=true clean jetty:run-war -Dcontext=another-context -Ploderunner

المشروع نفسه فضولي للغاية ، ويوفر الألعاب لكل ذوق.

استنتاج

إذا كنت قد قرأت كل هذا حتى النهاية دون التحضير الأولي وفهمت كل شيء ، فأنت زميل نادر.