Neste artigo, irei analisar o sétimo (final e mais difícil) nível e compartilhar a decisão do vencedor do jogo *.
* Esclarecimento para jogadores. O jogo QA foi lançado em 2 fluxos: em junho e em julho. O número máximo de pontos para todo o tempo foi marcado por Alexander na primeira corrente, portanto, no artigo analisamos seus resultados. O restante dos líderes pode ser visto no link .
O que está "dentro": a biblioteca Ace.js é usada para o editor de código no jogo ; o realce de sintaxe e o preenchimento automático estão disponíveis nela; webWorker é usado para executar código no lado do cliente (foi inspirado neste artigo ). O back-end é escrito em Python e Flask, implantado no Heroku . No total, demorou cerca de 2 meses para escrever o jogo.
Quando escrevi o QA Game, ainda não tinha experiência com Ace.js e webWorkers e foi interessante experimentá-los. Se você quiser fazer um jogo semelhante, eu o aconselho a pensar sobre:
- executando o código do player no lado do servidor, não no lado do cliente, como eu fiz;
- usando uma estrutura de back-end assíncrona. Se o back-end estiver em Python, recomendo Quart ou FastAPI ).
Lenda do jogo QA
No jogo, você precisa controlar o personagem ZERO2, que é capaz de testar, pesquisar e corrigir bugs. O controle ocorre usando código JavaScript, ZERO2 possui seu próprio SDK, o que simplifica muito a programação.
Por exemplo, para testar todos os recursos disponíveis no nível, você precisa executar o seguinte código:
let result = scan();
for (f of result.features) {
smoke_test(f);
}E então, para corrigir todos os bugs encontrados durante os testes, isto é:
result = scan();
for (b of result.bugs) {
fix_bug(b);
}Cada novo nível do jogo contém funções adicionais e requer o uso de algoritmos mais complexos; uma análise detalhada de cada um deles é publicada no GitHub . Neste artigo irei analisar detalhadamente o 7º nível, pois foi nele que se determinou qual dos jogadores receberia o máximo de pontos.
Como obter o máximo de pontos? Versão do criador do jogo.
No nível 7, os jogadores precisam corrigir e verificar o número máximo possível de bugs em 120 segundos, enquanto:
- O botão RUN só pode ser pressionado 60 vezes;
- Após 120 segundos, o algoritmo termina automaticamente, os pontos não são mais concedidos (a validação foi tanto no front-end quanto no back-end);
- Para cada bug corrigido, são atribuídos 100 pontos, para um bug corrigido e verificado - 150 pontos;
- Cada vez que você inicia o RUN, todos os pontos são zerados e novos bugs são gerados aleatoriamente.
Para obter o número máximo de pontos, você precisa analisar os fatores que afetam o resultado:
- Simplificação do código . É necessário remover todas as construções desnecessárias e escrever um código claro, verificando a possibilidade de loop. Muitos participantes perderam pontos devido a erros no código, levando a infinitos loops vazios;
- Reduzindo o tempo de resposta a uma solicitação . Cada método SDK faz uma solicitação ao servidor e, em média, uma solicitação leva de 200 a 400 ms. Para reduzir esse número, você precisa encontrar um servidor adequado e executar consultas a partir dele;
- Otimização de algoritmos . Na maioria das vezes, leva para encontrar as etapas para reproduzir o bug (função investig_bug). Portanto, é preciso pensar em como otimizar o algoritmo para encontrar uma solução no mínimo de tentativas;
- "Paralelização" do algoritmo . O lançamento padrão acontece em um thread (um webWorker) e todos os métodos de API são síncronos. Você pode tentar "paralelizar" o algoritmo. E você também pode ver se é possível tornar alguns dos métodos assíncronos (alerta de spoiler: alguns podem).
Otimização de algoritmo
A função investig_bug (bug_id, steps) retorna 0 se as etapas de reprodução especificadas não estiverem corretas, 1 se as etapas de reprodução especificadas forem o início de uma combinação correta de etapas e 100 se as etapas especificadas forem uma combinação completa de etapas para reproduzir o bug.
O algoritmo para selecionar as etapas de reprodução pode ser assim:
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);
}
}
};Esta função pode ser acelerada se, para uma determinada sequência, ao receber um "0", não verifique novamente a mesma sequência, substituindo o último caractere. Em vez disso, você precisa adicionar imediatamente outro caractere à string e verificar se há uma nova linha no resultado.
O que isso significa? É possível “salvar” o número de chamadas de investigue_ug usando este algoritmo (embora não funcione mais rápido em todos os casos):
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 += ">";
}
}Vamos comparar os resultados:
| Passos de reprodução corretos | Número de chamadas de research_bug na função find_steps | Número de chamadas de research_bug na função find_steps2 |
|---|---|---|
| >> | 2 | 2 |
| << | 4 | 6 |
| <<< | 6 | cinco |
| >> << >> | 8 | 7 |
| <<<<<< | 12 | 12 |
Talvez você possa encontrar um algoritmo melhor?
"Paralelizando" a execução de trabalhos sobre bugs
Isso pode ser feito de duas maneiras:
- Crie novos webWorkers e passe o código JavaScript para eles em linha:
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);
Com essa abordagem, resta apenas resolver o problema de sincronizar fluxos diferentes entre si, e aqui você pode usar a propriedade da função fix_bug (bug_id) - se a função retornar "0", o bug ainda não foi corrigido. - Visualize todos os métodos de API que são chamados por métodos SDK de JS e faça seu próprio script em sua linguagem de programação favorita. Essa abordagem é boa porque você tem total liberdade de ação, a capacidade de executar facilmente a solução em vários threads, a capacidade de executar seu próprio script a partir do servidor, que terá uma latência mínima para solicitações de rede.
Funções assíncronas
Após analisar todas as funções do SDK, você pode ver que as funções fix_bug e verify_fix podem se tornar assíncronas simplesmente reescrevendo as funções padrão que são usadas no jogo:
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());
}
Como obter o máximo de pontos? Versão vencedora.
Alexandre se tornou o vencedor com 28.050 pontos. Ele contou como conseguiu fazer isso, depois a narração na primeira pessoa.
Quando entrei no jogo, ainda havia poucos participantes (menos de 10). Depois de várias tentativas, meu programa conseguiu mais de 11.000 pontos e ficou em primeiro lugar por uma ampla margem.
Mas como a solução em si era bem trivial, percebi que não ficaria no primeiro lugar por muito tempo, então comecei a pensar em como melhorar o programa.
Primeiro, olhei o que mais afeta a velocidade de trabalho, descobri que 99% do tempo era ocupado por solicitações ao servidor. Cada solicitação demorou aproximadamente 110-120 ms. Assim, havia 3 opções principais para acelerar o programa:
- Melhorar o algoritmo e reduzir o número de requisições ao servidor;
- Usando solicitações assíncronas para o servidor;
- Reduzindo o tempo de um pedido.
Recusei a segunda opção, pois iria além das condições do problema e da API síncrona original.
Havia várias maneiras de reduzir o número de solicitações ao servidor, mas todas deram apenas um pequeno aumento (algumas dezenas de por cento no total).
Portanto, comecei a pensar em como reduzir o tempo de um pedido. Eu olhei onde o servidor do jogo foi implantado, descobri que ele estava no AWS em Dublin (ping para Dublin da minha cidade> 100ms). No início, eu queria alugar um servidor neste data center e executar o programa diretamente do próximo rack. Mas como eu tinha um servidor gratuito na Alemanha, decidi primeiro executar o programa de lá.
Eu instalei DE, VNC, Firefox, lancei o programa - e um ping mais baixo imediatamente aumentou o número de pontos ganhos em 2 vezes. E como a diferença em relação ao resto era muito grande, decidi não melhorar mais o resultado.
Aqui está uma história.
Erros comuns dos participantes
Posteriormente, compartilharei alguns erros típicos que impediram os participantes de obter mais pontos:
- Loops infinitos sobre a mesma lista de bugs já corrigidos. Se o algoritmo não lembra dos bugs já corrigidos e os corrige várias vezes, tempo é perdido;
- Erros em loops com seleção de etapas de reprodução para bugs. Como resultado, os ciclos se tornaram intermináveis. Muitos contribuidores usaram o limite de 100 caracteres ao procurar etapas de repetição, embora o comprimento máximo da linha para repetir bugs fosse de 10 caracteres;
- Nem todos os participantes tentaram executar seus algoritmos várias vezes e, se você executar o mesmo algoritmo 2 a 3 vezes, poderá obter um pouco mais de pontos devido a uma distribuição diferente de bugs e outras sequências para reproduzir bugs.
Terei o maior prazer em responder a perguntas sobre o jogo e ver suas opções para resolver o sétimo nível.