Duel de motos lumineuses néon

Le partage coloré ressemble à un diagramme de Voronoï, et c’en est un — mais la distance qu’il mesure compte les déplacements par cases libres, pas la ligne droite. Dès qu’une traînée est posée, les deux mesures divergent complètement. Prenez une grille de 22×22, tracez une traînée le long de la colonne centrale et laissez un seul passage sur la dernière rangée : la case située deux carreaux en face est à 44 déplacements — vingt et un vers le bas, deux de côté, vingt et un vers le haut. Vingt-deux fois plus loin qu’il n’y paraît. Un mur par-dessus lequel on voit reste un mur qu’il faut contourner. C’est pourquoi la couche se redessine dès qu’une moto tourne, et pourquoi Voronoï figure dans la liste comme stratégie et non comme décor.

Dans un duel de motos-lumière, personne n'attaque personne : on ne perd qu'en fonçant dans un mur, une traînée lumineuse ou une impasse. Le véritable objectif est de conquérir et de conserver assez d'espace libre pour continuer à avancer. La leçon pratique : longez les bords et remplissez l'espace par balayages ordonnés, plutôt que de couper par le centre ouvert, ce qui vous laisse moins d'issues qu'à votre adversaire.

On pourrait croire qu'une grille aussi petite se "résout" facilement, mais ce n'est pas le cas en général. En 2012, Tillmann Miltzow a démontré que déterminer le vainqueur de Tron sur des graphes arbitraires est PSPACE-difficile — une classe que l'on croit encore plus ardue que les problèmes NP-complets qui sous-tendent la plupart des casse-tête. C'est précisément pourquoi cet outil s'appuie sur des heuristiques comme les couloirs gloutons et le minimax 2-ply au lieu de calculer le coup vraiment optimal.