Minimax, Voronoi Territory, Draws

[grogers]

Originally, in order to work out the kins in my minimax algorithm I was using the exact same strategy as in brikbrik's guide - http://www.sifflez.org/misc/tronbot/index.html which is basically -
If we are separated from the opponent, fitness is count of reachable squares for us minus count of reachable squares for the opponent.
else, use a heuristic to decide the fitness. My heuristic was basically - prefer to wall hug, prefer positions close to the opponent in both distance and moves.

Tonight I tried the voronoi territory idea since it seemed to be more elegant than the heuristics I chose, but still get all the benefit of them (or perhaps better). My bot is currently mid-30's, this is definitely a strong evaluation function (especially for such a simple concept).

I especially like that this makes your bot aggressively fight for the center, which seems to do very well on maps that are open.

[iouri_]

I find Voronoi territory idea was a good starting place that led me to better heuristic move evaluation functions (and, for a few days, into top 10 - before everyone else improved their code).

A good improvement on it was after finding the squares that are closer to your bot to discard those squares that cannot be reached if other squares are reached - e.g if there are two dead-end corridors, the bot can go into only one of them. If this is evaluated a few moves deep, it can lead to never losing on maps such as Quadrant.

[JofferLamesch]

[gaundygojo]