Acabou agora mais um contest do codinggame, fechei em 35 global e primeiro brasileiro.

https://www.codingame.com/leaderboards/global/challenge/code-vs-zombies/25917060f87223d9e663378f192e4c1216da532

O jogo era fazer uma IA matadora de zumbis. Você tem um campo 2D onde tem um punhado de humanos estáticos e um punhado de zumbis de velocidade 400 que sempre andam na direção do humano mais próximo. Você controla um herói com velocidade 1000 e shotgun de alcance 2000, o objetivo é matar todos os zumbis de modo que sobre pelo menos um humano vivo.

Tinha 24h para codar, eu nem esquentei em fazer nada complicado, escrevi direto um monte carlo tree search. A parte bacana desse método é que ele escala com o número de simulações, então você está basicamente transformando otimização inteira em otimização de código (quanto mais rápido, mais iterações nos 100ms por round do jogo).

Se fosse 48h minha próxima otimização seria tirar fora o O(h*z) para calcular o zumbi mais próximo de cada humano, e trocar por uma BSP, aí esse mesmo check poderia ser feito em O(n lg n + z lg n).

O próximo contest é em fevereiro, é bem divertido, recomendo a todos :)