Duelo de Motos de Luz Neon

Num duelo de motos de luz, ninguém ataca ninguém: você só perde ao bater numa parede, num rastro luminoso ou num beco sem saída. O verdadeiro objetivo é conquistar e manter espaço livre suficiente para continuar em movimento. A lição prática: cole-se às bordas e preencha o espaço em varreduras organizadas, em vez de cortar pelo centro aberto, o que lhe deixa menos rotas de fuga do que ao seu rival.

Você poderia supor que uma grade tão pequena se "resolve" facilmente, mas em geral não é o caso. Em 2012, Tillmann Miltzow provou que decidir o vencedor de Tron em grafos arbitrários é PSPACE-difícil — uma classe que se acredita ser ainda mais difícil que os problemas NP-completos por trás da maioria dos quebra-cabeças. É exatamente por isso que esta ferramenta se apoia em heurísticas como corredores gulosos e minimax de 2-ply, em vez de calcular a jogada realmente ótima.