كيفية تجاوز المستوى الأخير من لعبة JS QA Game من SEMrush

مرحبًا ، اسمي Timur وقد كتبت لعبة QA Game من SEMrush . ربما تكون قد سمعت عن هذه اللعبة إذا شاركت في Heisenbug عبر الإنترنت أو شاهدت إعلانات اللعبة في محادثات Telegram للمختبرين. باختصار ، في QA Game ، تحتاج إلى إكمال المستويات بصعوبة متزايدة والتقاط الأخطاء باستخدام JavaScript.



في هذا المقال ، سأحلل المستوى السابع (الأخير والأكثر صعوبة) وأشارك قرار الفائز باللعبة *.







* توضيح للاعبين. تم إطلاق لعبة QA Game على مرحلتين: في يونيو ويوليو. تم تسجيل أقصى عدد من النقاط طوال الوقت بواسطة Alexander من الدفق الأول ، لذلك سنقوم في المقالة بتحليل نتائجه. يمكن رؤية بقية القادة على الرابط .



ما هو "الداخل": تُستخدم مكتبة Ace.js لمحرر التعليمات البرمجية في اللعبة ؛ يتوفر فيها تمييز بناء الجملة والإكمال التلقائي ؛ يستخدم WebWorker لتنفيذ التعليمات البرمجية من جانب العميل (مستوحى من هذه المقالة ). الواجهة الخلفية مكتوبة بلغة Python & Flask ، المنشورة على Heroku . في المجموع ، استغرق الأمر حوالي شهرين لكتابة اللعبة.



عندما كتبت QA Game ، لم يكن لدي أي خبرة مع Ace.js & webWorkers حتى الآن ، وكان من الممتع تجربتها. إذا كنت ترغب في صنع لعبة مشابهة ، فإنني أنصحك بالتفكير في:

• عن طريق تنفيذ كود اللاعب من جانب الخادم ، وليس من جانب العميل ، كما فعلت ؛
• باستخدام إطار عمل خلفية غير متزامن. إذا كانت الواجهة الخلفية في Python ، فإنني أوصي باستخدام Quart أو FastAPI ).

سؤال وجواب لعبة أسطورة

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



على سبيل المثال ، لاختبار جميع الميزات المتوفرة على المستوى ، تحتاج إلى تشغيل الكود التالي:

let result = scan();
for (f of result.features) {
    smoke_test(f);
}

ثم لإصلاح جميع الأخطاء التي تم العثور عليها أثناء الاختبار ، مثل هذا:

result = scan();
for (b of result.bugs) {
    fix_bug(b);
}

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

كيف تحصل على أكبر عدد من النقاط؟ نسخة منشئ اللعبة.

في المستوى 7 ، يحتاج اللاعبون إلى الإصلاح والتحقق من أكبر عدد ممكن من الأخطاء في 120 ثانية ، بينما:

1. يمكن الضغط على زر RUN 60 مرة فقط ؛
2. بعد 120 ثانية ، تنتهي الخوارزمية تلقائيًا ، ولا يتم منح النقاط (تم التحقق من الصحة على كل من الواجهة الأمامية والخلفية) ؛
3. لكل خطأ تم إصلاحه ، يتم منح 100 نقطة ، للخلل المصحح والتحقق منه - 150 نقطة ؛
4. في كل مرة تبدأ فيها RUN ، تتم إعادة تعيين جميع النقاط ، ويتم إنشاء أخطاء جديدة بشكل عشوائي.

للحصول على أكبر عدد ممكن من النقاط ، تحتاج إلى تحليل العوامل التي تؤثر على النتيجة:

• تبسيط الكود . من الضروري إزالة جميع الإنشاءات غير الضرورية وكتابة رمز واضح ، والتحقق من إمكانية التكرار. خسر العديد من المشاركين نقاطًا بسبب أخطاء في الكود ، مما أدى إلى حلقات فارغة لا نهاية لها ؛
• تقليل وقت الاستجابة للطلب . تقدم كل طريقة SDK طلبًا إلى الخادم ، وفي المتوسط ​​، يستغرق طلب واحد 200-400 مللي ثانية. لتقليل هذا الرقم ، تحتاج إلى العثور على خادم مناسب وتنفيذ الاستعلامات منه ؛
• تحسين الخوارزمية . يستغرق الأمر معظم الوقت للعثور على خطوات إعادة إنتاج الخطأ (وظيفة Explore_bug). لذلك ، تحتاج إلى التفكير في كيفية تحسين الخوارزمية من أجل إيجاد حل بأقل عدد من المحاولات ؛
• "موازاة" الخوارزمية . يحدث الإطلاق القياسي في مؤشر ترابط واحد (عامل ويب واحد) ، وتكون جميع طرق واجهة برمجة التطبيقات متزامنة. يمكنك محاولة "موازنة" الخوارزمية. ويمكنك أيضًا معرفة ما إذا كان من الممكن جعل بعض الطرق غير متزامنة (تنبيه المفسد: يمكن لبعضها).

تحسين الخوارزمية

ترجع الدالة Explore_bug (bug_id، steps) القيمة 0 إذا كانت خطوات التشغيل المحددة غير صحيحة ، 1 إذا كانت خطوات التشغيل المحددة هي بداية مجموعة صحيحة من الخطوات ، و 100 إذا كانت الخطوات المحددة عبارة عن مجموعة كاملة من الخطوات لإعادة إنتاج الخطأ.



قد تبدو خوارزمية تحديد خطوات التشغيل كما يلي:

function find_steps(bug_id) {
    let path = '';
    let result = 0;
    while (result != 100) {
        path += '>';
        result = investigate_bug(bug_id, path);
        if (result === 0) {
            path = path.slice(0, -1);
            path += '<';
            result = investigate_bug(bug_id, path);
        }
    }
};

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



ماذا يعني؟ من الممكن "حفظ" عدد الاستدعاءات للتحقيق في الأخطاء باستخدام هذه الخوارزمية (على الرغم من أنها لن تعمل بشكل أسرع في جميع الحالات):

function find_steps2(bug_id) {
    let path = "";
    result = 0;
    prev_result = 0;  //    , 
                      //      0,   
                      //      
    while (result != 100) {
        result = investigate_bug(bug_id, path + ">");
        if (result === 0) {
            if (prev_result === 0) {
                result = investigate_bug(bug_id, path + "<");
                if (result > 0) {
                    prev_result = 1;
                    path += "<";
                } else {
                    //       0, 
                    //     path
                    //    100  1 
                    result = investigate_bug(bug_id, path);
                }
            } else {
                prev_result = 0;
                path += "<";
            }
        } else {
            prev_result = 1;
            path += ">";
        }
    }

لنقارن النتائج:

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



ربما يمكنك العثور على خوارزمية أفضل؟

"موازاة" تنفيذ العمل على الخلل

يمكن القيام بذلك بطريقتين:

1. قم بإنشاء WebWorkers جديدة ، وقم بتمرير شفرة JavaScript إليهم في السطر:
   
   
   
   

   let my_code = "console.log('Any JS code which you want to run');";
   let bb = new Blob([hidden_js + my_code], {
       type: 'text/javascript'
   });
   
   // convert the blob into a pseudo URL
   let bbURL = URL.createObjectURL(bb);
   
   // Prepare the worker to run the code
   let worker = new Worker(bbURL);

   
   
   باستخدام هذا النهج ، يبقى حل مشكلة مزامنة التدفقات المختلفة مع بعضها البعض فقط ، وهنا يمكنك استخدام خاصية دالة fix_bug (bug_id) - إذا كانت الوظيفة ترجع "0" ، فهذا يعني أن الخطأ لم يتم إصلاحه بعد.
2. اعرض جميع طرق API التي يتم استدعاؤها بواسطة طرق SDK من JS وقم بإنشاء البرنامج النصي الخاص بك بلغة البرمجة المفضلة لديك. هذا النهج جيد لأن لديك حرية كاملة في العمل ، والقدرة على تشغيل الحل بسهولة في العديد من سلاسل الرسائل ، والقدرة على تشغيل البرنامج النصي الخاص بك من الخادم ، والذي سيكون له حد أدنى من زمن الانتقال لطلبات الشبكة.

وظائف غير متزامنة

بعد تحليل جميع وظائف SDK ، يمكنك أن ترى أن وظيفتي fix_bug و check_fix يمكن جعلهما غير متزامنتين بمجرد إعادة كتابة الوظائف القياسية المستخدمة في اللعبة:

function verify_fix(bug, path) {
    let xhr = new XMLHttpRequest();
    //    - true - ,     
    xhr.open('POST', "https://qa.semrush-games.com/api/verify_fix", true);
    xhr.setRequestHeader("Content-Type", "application/x-www-form-urlencoded");
    xhr.send("bug=" + bug + "&path=" + path);
}

function fix_bug(bug, path) {
    var xhr = new XMLHttpRequest();
    xhr.open('POST', "https://qa.semrush-games.com/api/fix_bug", true);
    xhr.setRequestHeader("Content-Type", "application/x-www-form-urlencoded");

    xhr.onreadystatechange = function () {
        if (this.readyState === XMLHttpRequest.DONE && this.status === 200) {
            if (this.response.toString().length > 3) {
                //   ,    :
                verify_fix(bug, path);
            }
        }
    };
    xhr.send("bug=" + bug.toString());
}

كيف تحصل على أكبر عدد من النقاط؟ نسخة الفائز.

أصبح الإسكندر الفائز برصيد 28.050 نقطة. حكى كيف استطاع تحقيق ذلك ، ثم السرد بضمير المتكلم.



عندما انضممت إلى اللعبة ، كان لا يزال هناك عدد قليل من المشاركين (أقل من 10). بعد عدة محاولات ، حصل برنامجي على أكثر من 11000 نقطة واحتل المركز الأول بهامش كبير.



ولكن نظرًا لأن الحل نفسه كان تافهًا تمامًا ، فقد أدركت أنني لن أبقى في المقام الأول لفترة طويلة ، لذلك بدأت أفكر في كيفية تحسين البرنامج.



أولاً ، نظرت إلى أكثر ما يؤثر على سرعة العمل ، اتضح أن 99٪ من الوقت كانت مشغولة بالطلبات المرسلة إلى الخادم. استغرق كل طلب حوالي 110-120 مللي ثانية. وفقًا لذلك ، كان هناك 3 خيارات رئيسية لتسريع البرنامج:

• تحسين الخوارزمية وتقليل عدد الطلبات إلى الخادم ؛
• استخدام الطلبات غير المتزامنة إلى الخادم ؛
• تقصير وقت طلب واحد.

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



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



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



لقد قمت بتثبيت DE و VNC و Firefox وأطلقت البرنامج - وزاد اختبار ping المنخفض على الفور عدد النقاط المكتسبة بمقدار الضعف. وبما أن الفجوة عن البقية كانت كبيرة جدًا ، فقد قررت عدم تحسين النتيجة أكثر.



هذه قصة.

الأخطاء الشائعة للمشاركين

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

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

يسعدني الرد على الأسئلة المتعلقة باللعبة والاطلاع على خياراتك لحل المستوى السابع.