في أوائل الخريف ، تم الانتهاء من المنافسة لكتابة الروبوتات Mini AI Cup # 3 (المعروف أيضًا باسم Mad Cars) ، حيث كان على المشاركين القتال على السيارات. جادل المشاركون كثيرًا حول ما سيعمل وما لا ينجح ، وتم التعبير عن الأفكار واختبارها من لو بسيط إلى تدريب الشبكات العصبية ، ولكن الرجال اتخذوا أفضل الأماكن مع ما يسمى "المحاكاة". دعنا نحاول معرفة ما هي ، ومقارنة الحلول للأماكن الأولى والثالثة والرابعة ومناقشة الحلول الممكنة الأخرى.

تنويه

تمت كتابة المقالة بالتعاون مع Alexei Dichkovsky (Commandos) و Vladimir Kiselev (Valdemar) .

بالنسبة لأولئك الذين يرغبون فقط في القراءة عن قرارات الفائزين ، أنصحك بالبدء فورًا بعنصر "المحاكاة".

بيان المشكلة

هذه المرة ، كانت آليات العالم تشبه إلى حد كبير لعبة Drive Ahead للأجهزة المحمولة: تم منح اللاعبين سيارة مع زر موجود عليها ؛ المهمة هي الضغط على زر العدو أسرع مما يفعل. إذا لم يفز أحد في 600 لعبة ، فإن البطاقة تبدأ في الغرق في كومة من القمامة ، والتي يمكن أيضًا الضغط على زر. وبعبارة أخرى ، تحتاج إلى حماية الزر الخاص بك من الأعداء والعالم من حولك وأكوام القمامة (بشكل حيوي ، نعم). تم منح كل لاعب 5 أرواح ، استمرت اللعبة من 5 إلى 9 جولات ، في حين أن شخصًا ما لم ينه حياته. عقدت كل جولة على خريطة عشوائية وسيارات ، نفس الشيء لكلا المشاركين. في المجموع كان هناك 6 بطاقات مختلفة و 3 أنواع من السيارات - ما مجموعه 18 مجموعة مختلفة.

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

يمكن العثور على قواعد أكثر اكتمالا هنا . وشاهد مباريات النهائيات هنا .

وصف الحل العام

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

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

عند اختيار خوارزمية ، يجب مراعاة:

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

في هذه المسابقة ، أعطت علامة واحدة حوالي 10-13 مللي ثانية (دقيقتان طوال المباراة). خلال هذا الوقت ، كان على البوت قراءة البيانات ، واتخاذ قرار وإرسال أمر للتحرك. كان هذا كافيا لتحفيز حوالي 500-1000 حركة. كرر على جميع الولايات. قد تبدو أبسط خوارزمية البحث وكأنها مقارنة بين ثلاثة خيارات للحركة: "50 علامة تنطلق يسارًا" ، "50 علامة تنطلق إلى اليمين" ، "50 نقرة تنقر نقرة توقف". وبغض النظر عن مدى بساطتها ، فهي ليست بعيدة جدًا عن قرار الفائز.

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

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

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

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

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

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

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

ملاحظة
فيما يتعلق بالعدد المحدود من الإجراءات المحتملة ، تجدر الإشارة إلى أنه يُسمح أحيانًا بتعديل بعض المعلمات "بسلاسة". على سبيل المثال ، ليس فقط دفع إلى الأمام ، ولكن مع بعض نسبة القوة. في هذه الحالة ، يمكن تحقيق "دقة" عدد الاستنتاجات بسهولة باستخدام عدة قيم ، على سبيل المثال ، 0٪ ، 25٪ ، 50٪ ، 75٪ و 100٪. في أغلب الأحيان ، يكفي اثنان فقط: "تشغيل كامل" و "إيقاف تشغيل كامل".

محاكاة

في هذه المسابقة ، استخدمنا محرك فيزياء السنجاب الجاهز. كانت توقعات المنظمين أنه عجوز ، ومُختبر للوقت ولديه العديد من الأغلفة بحيث يمكن للجميع تضمينها في قرارهم ...

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

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

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

خوارزمية البحث عن الخصم والتنبؤ به

من هذه النقطة ، يبدأ وصف منفصل للحلول. سيتم وصف الخوارزميات نيابة عن مؤلفها.

فلاديمير كيسيليف (فالديمار) المركز الرابع

تم استخدام بحث عشوائي (مونتي كارلو) للبحث في مساحة الحل. الخوارزمية هي كما يلي:

1. نقوم بتهيئة الجينوم - سلسلة من الإجراءات (يسار ، يمين ، توقف) لـ 60 علامة - بيانات عشوائية.
2. خذ أفضل الجينوم الموجود
3. تغيير أحد الإجراءات بشكل عشوائي
4. باستخدام وظيفة التقييم نحصل على رقم - مؤشر على مدى جودة الجينوم الجديد
5. إذا حصلت على حل أفضل ، فقم بتحديث الحل الأفضل.
6. كرر مرة أخرى من الخطوة 2

أنتج جهاز المحاكاة الخاص بي ~ 100 ألف محاكاة للعالم في ثانية واحدة ، مع الأخذ في الاعتبار أن هناك متوسط ​​12 مللي ثانية لكل علامة ، نحصل على 1200 إجراء لكل علامة. أي أنه في علامة واحدة نتمكن من المرور بالدورة الكاملة حوالي 20 مرة.

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

وتجدر الإشارة إلى التقنيات التي حسنت بشكل كبير جودة الخوارزمية:

• ننفذ التهيئة العشوائية فقط على العلامة الأولى ، وبقية الوقت نعيد استخدام أفضل حل تم العثور عليه بنقل حركة واحدة (يتم نقل الإجراء على العلامة الثانية إلى الخطوة الأولى ، وما إلى ذلك ، تتم إضافة إجراء عشوائي إلى النهاية). يؤدي ذلك إلى تحسين جودة البحث بشكل كبير ، لأنه بخلاف ذلك "تنسى" الخوارزمية ما كانت ستفعله في العلامة الأخيرة وتؤدي إلى اهتزازات لا معنى لها في اتجاهات مختلفة.
• في بداية الدورة ، نقوم بإجراء تغييرات أكثر كثافة (نغير الجينوم 2 أو 3 مرات بدلاً من واحد) على أمل كسر الحد الأقصى المحلي (تشابه درجة الحرارة في طريقة محاكاة الصلب).
  تم تحديد الكثافة يدويًا: أول 30 تكرارًا تقوم بعمل 3 طفرات ، و 10 التالية 2 ، ثم 1.
• مهم جدا هو التنبؤ بأعمال الأعداء. على حساب الوقت للبحث عن حل خاص بنا ، نطلق بحثًا عشوائيًا من جانب الخصم ، بمعدل 20 تكرارًا ، ثم 50 لأنفسنا ، باستخدام معلومات حول التحركات المثالية للخصم.
  يتم إعادة استخدام أفضل قرار للخصم أيضًا في الخطوة التالية مع تعويض. في الوقت نفسه ، عند البحث عن حل للعدو ، يتم استخدام الجينوم من الخطوة الأخيرة كأفعالي المقصودة.

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

• الساحة المحلية - إطلاق العديد من المباريات مقابل النسخة السابقة ؛
• متخيل لسلوك التصحيح ؛
• برنامج نصي لجمع إحصائيات عن التطابقات من الموقع - يسمح لك بفهم الخرائط والآلات التي تحدث الهزيمة في أغلب الأحيان.

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

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

الكسندر كيسيليف (مرتيدو) المركز الثالث

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

نقوم بتشفير الحل بمصفوفة من 40 رقمًا ، حيث تتوافق -1 و 0 و 1 مع حركات و و .

في بداية كل جولة ، قمت بحساب الوقت الذي قضيته بالفعل في اللعبة بأكملها ، وقمت بحساب حد زمني جديد بناءً على عدد الجولات التي ستظل كذلك ، وكل جولة افترضتها كانت 1200 علامة. T.O. في البداية ، حاولت ألا أنفق أكثر من 11 مللي ثانية لكل دور ، ولكن يمكنني "التجول" قليلاً في النهاية ، إذا كانت الجولات السابقة أسرع من 1200 علامة.

فالديمار:
ومن المثير للاهتمام أن هذه الشريحة زادت من سوء اللعبة بالنسبة لي. اتضح أنه من الأفضل دائمًا إنفاق 20-30 مللي ثانية من 11 أولاً ، و 60 في النهاية

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

كان البحث عن الحل نفسه هو نفسه لنفسه وللمنافس:

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

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

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

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

1. تم اختيار فريق عشوائي
2. لطول الحل بالكامل (40 حركة)
   
   1. نكتب الأمر الحالي في الخلية
   2. باحتمال 10٪ نغير الفريق الحالي إلى عشوائي

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

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

Valdemar:
1 , , .

Commandos:
— - .
— , . , … , . " ”. -.

(Commandos) 1

( ), n m . 3^2=9 . m + n 40 .

:

 |----------- n  -----------|---------- m  --------| |   ...   |   ...   | 

: , , . ( ).

n m , . , .

:

1. , ( , ):
   
   • , , , .
   • , , . . . , , , .
   • . ; ( ).
2. n m . , .1, , . - ( ) , — , ;
3. . , — . , ( ).

Valdemar:
, 2 . . , .

mortido:
! , . . , 2 , 40-60 . , 3 .
n + m == const ?

. n + m != const , . , . - .

(Valdemar) 4

, . , ( , , ..) [0..1].
. : , .
, , : , .

, :

• — 70 180 ( : ).
  , .
• 0..500
• — [2pi, pi/4] [0, 1]
• — , ( ), ( , , )
• — , , , .
  , , .
• — . .
• Y — .

, 2 , .

.

:

• “” ,
• “ ” , , .

mortido:
, .. , .

Commandos:
, . -

(mortido) 3

, chipmunk. . , , , , . .

3 .

, ( , , ):

• . , , ( , );
• , — , ; , 1 ;
• ;
• ( , );
• ( “+”, “-”);
  - ( “+”, “-”); , , , ;
  30 , , ( );
• , .

, , (, , )

Valdemar:
. , “ , , ” , ( ..) .

, , . .

Commandos:
, , “”… ? , “” .

(Commandos) 1

SquaredWheelsBuggy , .. , . Buggy , , ( /).
:

1. ;
2. ; — , , 1 0; .. ;
3. . ; 10 ( );
4. ( , );
5. (, );
6. — - , ;
7. / ; , — ; .

1-5 , . 2 “ ”.

Valdemar:
, . , .

mortido:
, 10 .

IF'

(Valdemar) 4

, if'. 3 , , . , , -.
: , “” — , - , ( , ) — .

:

• . , .
• — , .
• . “ ” .
  , , .
  , , .

, : . , , if' .

mortido:
, . .

Commandos:
if'. , , … , , .

(mortido) 3

- .

3 . . . “”, . , , .

, “” . . , , , - . . , , .. .

, , , , , . … . - — , ( , ).

Valdemar:
, . . “” , if'. , — .

, + . , .

Commandos:
… , - — , , . , , .

(Commandos) 1

. (, , ). ( ) /.

pill carcass map , , ( ). island map, , .

island hole buggy. / , , ( ). — . , , . SquaredWheelBuggy . , , , . , … , , .

(Pill map, Bus) , ( / 100% ).

pill hubble map. , ( ), . .

— , ...

, . , . ( ).

Valdemar:
, — . , .

mortido:
, “” .

Valdemar:
. , . ( ) .
. “”, , , , :)
, mailru , .

mortido:
: , … , , ( ). , 3 , , … .

Commandos:
- , . , , , . … . — , .
— ++. . , . 1 -.

, . , . , , .

Mail.Ru Group .

Valdemar
mortido