In diesem Artikel werde ich das siebte (letzte und schwierigste) Level analysieren und die Entscheidung des Gewinners des Spiels * teilen.
* Klarstellung für Spieler. QA Game wurde in zwei Streams gestartet: im Juni und im Juli. Die maximale Punktzahl für die gesamte Zeit wurde von Alexander aus dem ersten Stream erzielt, daher werden wir im Artikel seine Ergebnisse analysieren. Der Rest der Führer kann unter dem Link gesehen werden .
Was ist "drin" ? Die Ace.js- Bibliothek wird für den Code-Editor im Spiel verwendet . Syntaxhervorhebung und automatische Vervollständigung sind darin verfügbar. webWorker wird verwendet, um Code auf der Clientseite auszuführen (wurde von diesem Artikel inspiriert ). Das Backend ist in Python & Flask geschrieben und auf Heroku bereitgestellt . Insgesamt dauerte es ungefähr 2 Monate, um das Spiel zu schreiben.
Als ich QA Game schrieb, hatte ich noch keine Erfahrung mit Ace.js & webWorkers und es war interessant, sie auszuprobieren. Wenn Sie ein ähnliches Spiel machen möchten, empfehle ich Ihnen, über Folgendes nachzudenken:
- durch Ausführen von Spielercode auf der Serverseite, nicht auf der Clientseite, wie ich es getan habe;
- Verwenden eines asynchronen Backend-Frameworks. Wenn sich das Backend in Python befindet, empfehle ich Quart oder FastAPI .
QA-Spiellegende
Im Spiel musst du den Charakter ZERO2 steuern, der in der Lage ist, Fehler zu testen, zu suchen und zu beheben. Die Steuerung erfolgt über JavaScript-Code, ZERO2 verfügt über ein eigenes SDK, das die Programmierung erheblich vereinfacht.
Um beispielsweise alle auf der Ebene verfügbaren Funktionen zu testen, müssen Sie den folgenden Code ausführen:
let result = scan();
for (f of result.features) {
smoke_test(f);
}Um alle beim Testen gefundenen Fehler zu beheben, gehen Sie wie folgt vor:
result = scan();
for (b of result.bugs) {
fix_bug(b);
}Jedes neue Level im Spiel enthält zusätzliche Funktionen und erfordert die Verwendung komplexerer Algorithmen. Eine detaillierte Analyse jedes einzelnen von ihnen wird auf GitHub veröffentlicht . In diesem Artikel werde ich Level 7 im Detail analysieren, da darauf festgelegt wurde, welcher der Spieler die maximale Punktzahl erhalten würde.
Wie bekomme ich maximale Punkte? Game Creator Version.
Auf Stufe 7 müssen die Spieler die maximal mögliche Anzahl von Fehlern in 120 Sekunden beheben und überprüfen, während:
- Die RUN-Taste kann nur 60 Mal gedrückt werden.
- Nach 120 Sekunden endet der Algorithmus automatisch, Punkte werden nicht mehr vergeben (die Validierung erfolgte sowohl im Front-End als auch im Back-End).
- Für jeden behobenen Fehler werden 100 Punkte vergeben, für einen korrigierten und verifizierten Fehler - 150 Punkte;
- Jedes Mal, wenn Sie RUN starten, werden alle Punkte zurückgesetzt und neue Fehler werden zufällig generiert.
Um die maximale Anzahl von Punkten zu erhalten, müssen Sie die Faktoren analysieren, die das Ergebnis beeinflussen:
- Vereinfachung des Codes . Es ist notwendig, alle unnötigen Konstruktionen zu entfernen und klaren Code zu schreiben, um zu prüfen, ob eine Schleife möglich ist. Viele Teilnehmer verloren Punkte aufgrund von Fehlern im Code, was zu endlosen leeren Schleifen führte.
- Reduzierung der Antwortzeit auf eine Anfrage . Jede SDK-Methode sendet eine Anforderung an den Server, und im Durchschnitt dauert eine Anforderung 200-400 ms. Um diese Zahl zu verringern, müssen Sie einen geeigneten Server finden und Abfragen von diesem ausführen.
- Algorithmusoptimierung . Meistens dauert es, die Schritte zum Reproduzieren des Fehlers zu finden (Funktion investigate_bug). Daher müssen Sie überlegen, wie Sie den Algorithmus optimieren können, um eine Lösung mit der minimalen Anzahl von Versuchen zu finden.
- "Parallelisierung" des Algorithmus . Der Standardstart erfolgt in einem Thread (einem WebWorker), und alle API-Methoden sind synchron. Sie können versuchen, den Algorithmus zu "parallelisieren". Sie können auch sehen, ob es möglich ist, einige der Methoden asynchron zu machen (Spoiler-Alarm: Einige können).
Algorithmusoptimierung
Die Funktion Investigate_Bug (Bug_ID, Schritte) gibt 0 zurück, wenn die angegebenen Wiedergabeschritte nicht korrekt sind, 1, wenn die angegebenen Wiedergabeschritte der Beginn einer korrekten Kombination von Schritten sind, und 100, wenn die angegebenen Schritte eine vollständige Kombination von Schritten zur Reproduktion des Fehlers sind.
Der Algorithmus zum Auswählen von Wiedergabeschritten kann folgendermaßen aussehen:
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);
}
}
};Diese Funktion kann beschleunigt werden, indem nicht dieselbe Sequenz erneut überprüft und das letzte Zeichen für eine bestimmte Sequenz ersetzt wird, wenn eine "0" empfangen wird. Stattdessen müssen Sie der Zeichenfolge sofort ein weiteres Zeichen hinzufügen und das Ergebnis auf eine neue Zeile überprüfen.
Was bedeutet das? Mit diesem Algorithmus ist es möglich, die Anzahl der Aufrufe von investigate_bug zu speichern (obwohl dies nicht in allen Fällen schneller funktioniert):
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 += ">";
}
}Vergleichen wir die Ergebnisse:
| Korrigieren Sie die Wiedergabeschritte | Anzahl der Aufrufe von Investigate_Bug in der Funktion find_steps | Die Anzahl der Investigate_Bug-Aufrufe in der Funktion find_steps2 |
|---|---|---|
| >> | 2 | 2 |
| << | 4 | 6 |
| <<< | 6 | fünf |
| >> << >> | 8 | 7 |
| <<<<<< | 12 | 12 |
Vielleicht können Sie einen besseren Algorithmus finden?
"Parallelisierung" der Ausführung von Arbeiten an Fehlern
Dies kann auf zwei Arten erfolgen:
- Erstellen Sie neue WebWorker und übergeben Sie ihnen in der Zeile JavaScript-Code:
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);
Bei diesem Ansatz bleibt nur das Problem der Synchronisierung verschiedener Streams miteinander zu lösen. Hier können Sie die Funktionseigenschaft fix_bug (bug_id) verwenden. Wenn die Funktion "0" zurückgibt, wurde der Fehler noch nicht behoben. - Zeigen Sie alle API-Methoden an, die von SDK-Methoden von JS aufgerufen werden, und erstellen Sie Ihr eigenes Skript in Ihrer bevorzugten Programmiersprache. Dieser Ansatz ist gut, da Sie vollständige Handlungsfreiheit haben, die Lösung problemlos in mehreren Threads ausführen können und Ihr eigenes Skript vom Server aus ausführen können, was eine minimale Latenz für Netzwerkanforderungen bedeutet.
Asynchrone Funktionen
Nachdem Sie alle SDK-Funktionen analysiert haben, konnten Sie feststellen, dass die Funktionen fix_bug und verify_fix asynchron gemacht werden können, indem Sie einfach die im Spiel verwendeten Standardfunktionen neu schreiben:
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());
}
Wie bekomme ich maximale Punkte? Gewinnerversion.
Alexander wurde der Gewinner mit 28.050 Punkten. Er erzählte, wie er es geschafft hatte, dann die Erzählung in der ersten Person.
Als ich zum Spiel kam, gab es noch wenige Teilnehmer (weniger als 10). Nach mehreren Versuchen erreichte mein Programm über 11.000 Punkte und belegte mit großem Abstand den ersten Platz.
Da die Lösung selbst jedoch ziemlich trivial war, wurde mir klar, dass ich nicht lange an erster Stelle bleiben würde, und ich begann darüber nachzudenken, wie ich das Programm verbessern könnte.
Zuerst habe ich mir angesehen, was die Arbeitsgeschwindigkeit am meisten beeinflusst. Es stellte sich heraus, dass 99% der Zeit mit Anfragen an den Server belegt waren. Jede Anfrage dauerte ungefähr 110-120 ms. Dementsprechend gab es drei Hauptoptionen zur Beschleunigung des Programms:
- Verbesserung des Algorithmus und Reduzierung der Anzahl der Anforderungen an den Server;
- Verwenden asynchroner Anforderungen an den Server;
- Verkürzung der Zeit einer Anfrage.
Ich habe die zweite Option abgelehnt, da sie über die Bedingungen des Problems und die ursprüngliche synchrone API hinausgehen würde.
Es gab verschiedene Möglichkeiten, die Anzahl der Anforderungen an den Server zu verringern, aber alle haben nur geringfügig zugenommen (insgesamt einige zehn Prozent).
Daher begann ich darüber nachzudenken, wie ich die Zeit einer Anfrage verkürzen könnte. Ich habe nachgesehen, wo der Spieleserver bereitgestellt wurde. Es stellte sich heraus, dass er sich in AWS in Dublin befand (Ping von meiner Stadt> 100 ms nach Dublin). Zuerst wollte ich einen Server in diesem Rechenzentrum mieten und das Programm direkt vom nächsten Rack ausführen. Da ich aber in Deutschland einen kostenlosen Server hatte, habe ich mich zunächst entschlossen, das Programm von dort aus auszuführen.
Ich habe DE, VNC und Firefox installiert, das Programm gestartet - und ein niedrigerer Ping erhöhte sofort die Anzahl der Punkte um das Zweifache. Und da der Abstand zum Rest sehr groß war, habe ich beschlossen, das Ergebnis nicht weiter zu verbessern.
Hier ist eine Geschichte.
Häufige Fehler der Teilnehmer
Als Nachwort werde ich einige typische Fehler nennen, die die Teilnehmer daran gehindert haben, mehr Punkte zu erhalten:
- Endlose Schleifen über dieselbe Liste bereits behobener Fehler. Wenn sich der Algorithmus nicht an die bereits behobenen Fehler erinnert und diese mehrmals behebt, wird Zeit verschwendet.
- Fehler in Schleifen mit Auswahl der Wiedergabeschritte für Fehler. Infolgedessen wurden die Zyklen endlos. Viele Teilnehmer verwendeten das Limit von 100 Zeichen, wenn sie nach Wiederholungsschritten suchten, obwohl die maximale Zeilenlänge für die Wiederholung von Fehlern 10 Zeichen betrug.
- Nicht alle Teilnehmer haben mehrmals versucht, ihre Algorithmen auszuführen. Wenn Sie denselben Algorithmus 2-3 Mal ausführen, können Sie aufgrund einer unterschiedlichen Verteilung von Fehlern und anderen Sequenzen zur Reproduktion von Fehlern etwas mehr Punkte erhalten.
Gerne beantworte ich Fragen zum Spiel und sehe Ihre Möglichkeiten zur Lösung des siebten Levels.