First it checks to see if two bots are seperated.
If two bots are connected, it will use Minimax/Alpha Beta Pruning to determine the best move it should take. The evaluation functions is as follows:
1, if I win: +1000; opponent wins: -1000
2, if disconnected, and I have more open spots: +800; opponent has more open spots: -800; same: 0; Open spots is determined by flood fill.
3, if still connected,
find articulation points and divide map into zones
find the largest zones
use breadth first algorithm to divide the zones into spots I can reach first
return final score as spots I can reach first - spots enemy can reach first
The whole Alpha Beta Pruning process is wrapped using a Iterative Deepening loop.
When two bots are seperated, simply use a breadth first algorithm to determine how many open spots are left after each move using flood fill. Then choose the move that leaves the most spots open, in case two moves are equally good, hug the wall.
It is written in C#, and can be found here: http://github.com/analyst74/Tron-Bot
Update: here is a great write up about the challenge and many related links http://www.benzedrine.cx/tron/
Posts
