💇🏿 ☎️ ☹️ SEMrushからJSQAゲームの最終レベルに合格する方法 🕧 🚞 👨🏿‍⚕️

こんにちは私の名前はティムールです。SEMrushからQAゲームを書きました。オンラインでHeisenbugに参加したり、テスター向けのTelegramチャットでゲームの発表を見たりした場合は、このゲームについて聞いたことがあるかもしれません。つまり、QAゲームでは、難易度を上げてレベルを完了し、JavaScriptを使用してバグをキャッチする必要があります。

この記事では、7番目（最終的で最も難しい）レベルを分析し、ゲームの勝者の決定を共有します*。

*プレイヤーのための明確化。 QAゲームは6月と7月の2つのストリームで開始されました。常に最大ポイント数は最初のストリームからアレクサンダーによって獲得されたので、記事では彼の結果を分析します。残りのリーダーはリンクで見ることができます。

「内部」とは：ゲームのコードエディタにはAce.jsライブラリが使用され、構文の強調表示と自動補完が利用できます。 webWorkerは、クライアント側でコードを実行するために使用されます（この記事に触発されました）。バックエンドはPythonとFlaskで記述され、Herokuにデプロイされています。合計で、ゲームを書くのに約2か月かかりました。

QA Gameを書いたときは、まだAce.jsとwebWorkersの経験がなく、試してみるのも面白かったです。同様のゲームを作りたい場合は、次のことを検討することをお勧めします。

私が行ったように、クライアント側ではなくサーバー側でプレーヤーコードを実行する。
非同期バックエンドフレームワークを使用します。バックエンドがPythonの場合は、QuartまたはFastAPIをお勧めします）。

QAゲームレジェンド

ゲームでは、バグをテスト、検索、修正できるキャラクター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秒以内に可能な最大数のバグを修正して確認する必要があります。

RUNボタンは60回しか押すことができません。
120秒後、アルゴリズムは自動的に終了し、ポイントは付与されなくなります（検証はフロントエンドとバックエンドの両方で行われました）。
修正されたバグごとに100ポイントが付与され、修正および検証されたバグに対して150ポイントが付与されます。
RUNを開始するたびに、すべてのポイントがリセットされ、新しいバグがランダムに生成されます。

ポイントの最大数を取得するには、結果に影響を与える要因を分析する必要があります。

コードの簡略化。不要な構造をすべて削除し、明確なコードを記述して、ループの可能性をチェックする必要があります。多くの参加者は、コードのエラーのためにポイントを失い、無限の空のループにつながりました。
リクエストへの応答時間を短縮します。各SDKメソッドはサーバーにリクエストを送信し、平均して1つのリクエストに200〜400ミリ秒かかります。この数字を減らすには、適切なサーバーを見つけて、そこからクエリを実行する必要があります。
アルゴリズムの最適化。ほとんどの場合、バグを再現する手順を見つけるのにかかります（関数insearch_bug）。したがって、最小試行回数で解決策を見つけるために、アルゴリズムを最適化する方法を考える必要があります。
アルゴリズムの「並列化」。標準の起動は1つのスレッド（1つのwebWorker）で行われ、すべてのAPIメソッドは同期しています。アルゴリズムの「並列化」を試みることができます。また、一部のメソッドを非同期にすることが可能かどうかも確認できます（スポイラーアラート：一部は可能です）。

アルゴリズムの最適化

調査バグ（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」を受信したときに、最後の文字を置き換えて同じシーケンスを再チェックしない場合に高速化できます。代わりに、すぐに別の文字を文字列に追加し、結果で新しい行を確認する必要があります。

どういう意味ですか？このアルゴリズムを使用すると、invey_bug呼び出しの数を「節約」することができます（ただし、すべての場合に高速に動作するわけではありません）。

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 += ">";
        }
    }

結果を比較してみましょう：

正しい再生手順	find_steps関数でのsurvey_bugの呼び出し数	find_steps2関数でのinvey_bug呼び出しの数
>>	2	2
<<	4	6
<<<	6	五
>> << >>	8	7
<<<<<<	12	12

2番目のアルゴリズムが常に高速であるとは限らないことに注意することが重要ですが、ほとんどの場合、より少ないステップで解決策を見つけることができます。また、場合によっては、最初に文字>または<のどちらを置き換えるかが重要になります。ただし、選択した組み合わせのランダム性を考えると、これによって目立った増加は得られないと結論付けることができます。

おそらくあなたはより良いアルゴリズムを見つけることができますか？

バグに関する作業の実行を「並列化」する

これは2つの方法で行うことができます：

新しい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」を返す場合、バグはまだ修正されていません。
JSのSDKメソッドによって呼び出されるすべてのAPIメソッドを表示し、お気に入りのプログラミング言語で独自のスクリプトを作成します。このアプローチは、アクションの完全な自由、複数のスレッドでソリューションを簡単に実行する機能、サーバーから独自のスクリプトを実行する機能があり、ネットワーク要求の待ち時間が最小になるため、優れています。

非同期機能

すべてのSDK関数を分析した後、ゲームで使用される標準関数を書き直すだけで、fix_bug関数とverify_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人未満）。何度か試みた後、私のプログラムは11,000ポイントを超え、大幅に1位になりました。

しかし、解決策自体は非常に些細なことだったので、私は最初の場所に長く留まらないことに気づき、プログラムを改善する方法を考え始めました。

まず、作業速度に最も影響を与えるものを調べたところ、99％の時間がサーバーへのリクエストで占められていたことがわかりました。各リクエストには約110〜120ミリ秒かかりました。したがって、プログラムを加速するための3つの主なオプションがありました。

アルゴリズムを改善し、サーバーへのリクエスト数を減らします。
サーバーへの非同期要求の使用。
1つのリクエストの時間を短縮します。

問題の条件と元の同期APIを超えるため、2番目のオプションを拒否しました。

サーバーへのリクエスト数を減らす方法はいくつかありましたが、いずれもわずかな増加（合計で数十パーセント）しかありませんでした。

そこで、1回のリクエストの時間を短縮する方法を考え始めました。ゲームサーバーが展開されている場所を調べたところ、ダブリンのAWSにあることがわかりました（私の都市からダブリンに100ミリ秒以上pingを送信）。最初は、このデータセンターでサーバーを借りて、次のラックから直接プログラムを実行したいと思いました。しかし、私はドイツに無料のサーバーを持っていたので、最初にそこからプログラムを実行することにしました。

DE、VNC、Firefoxをインストールし、プログラムを起動しました。pingを低くすると、すぐにポイント数が2倍になりました。そして、他とのギャップが非常に大きかったので、それ以上結果を改善しないことにしました。

これが物語です。

参加者のよくある間違い

あとがきとして、参加者がより多くのポイントを獲得するのを妨げたいくつかの典型的な間違いを共有します。

すでに修正されたバグの同じリストを無限にループします。アルゴリズムがすでに修正されたバグを記憶せず、それらを数回修正すると、時間が無駄になります。
バグの再生ステップの選択によるループのエラー。その結果、サイクルは無限になりました。バグを再生するための最大行長は10文字でしたが、多くの寄稿者は再生ステップを探すときに100文字の制限を使用しました。
すべての参加者がアルゴリズムを数回実行しようとしたわけではありません。同じアルゴリズムを2〜3回実行すると、バグの分布やバグを再現するための他のシーケンスが異なるため、ポイントが少し増える可能性があります。

ゲームに関する質問にお答えし、第7レベルを解決するためのオプションを確認させていただきます。

SEMrushからJSQAゲームの最終レベルに合格する方法