Duelo de Motos de Luz Neon

A divisão colorida parece um diagrama de Voronoi, e é — mas a distância que ela mede são movimentos por células livres, não a linha reta. Assim que um rastro é deixado, as duas medidas deixam de se parecer. Pegue uma grade de 22×22, trace um rastro pela coluna central e deixe uma única brecha na última linha: a célula duas casas do outro lado fica a 44 movimentos — vinte e um para baixo, dois para o lado, vinte e um de volta para cima. Vinte e duas vezes mais longe do que parece. Um muro por cima do qual se vê continua sendo um muro que se precisa contornar. É por isso que a camada se redesenha no instante em que uma moto vira, e por isso Voronoi está na lista como estratégia, não como enfeite.

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.