ネオン・ライトサイクル対決

色分けはボロノイ図に見えますし、実際そうです。ただし測っているのは空いた升目を通る手数で、直線距離ではありません。軌跡が一本引かれた途端、二つの尺度は似ても似つかなくなります。22×22の升目を用意し、中央の列に沿って軌跡を引き、最後の行にだけ隙間を残してみてください。向かい側の二升先の升目は、44手の距離になります——下へ二十一、横へ二、また上へ二十一。見た目の二十二倍です。越えて見える壁も、回り込むしかない壁です。だから曲がった瞬間に重ね描きは引き直され、だからボロノイは飾りではなく選択肢の中の戦略として並んでいます。

ライトサイクルの対戦では、相手を攻撃することはできません。負けるのは、壁・光る軌跡・行き止まりに突っ込んだときだけです。本当の目的は、動き続けられるだけの空きスペースを確保し、保ち続けることにあります。実践的な教訓は、開けた中央を横切るのではなく、縁に沿って進みながら整然とスペースを埋めていくこと。そうすれば、相手より多くの逃げ道を残せます。

これほど小さな盤面なら簡単に「解ける」と思うかもしれませんが、一般には解けません。2012年、Tillmann Miltzow は、任意のグラフ上で Tron の勝者を決定する問題が PSPACE困難であることを証明しました。これは、多くのパズルの背後にある NP完全問題よりもさらに難しいと広く信じられているクラスです。だからこそこのツールは、真に最適な手を計算する代わりに、貧欲な回廊選択や 2-ply ミニマックスといったヒューリスティックに頑っています。