VORONOI TERRITORY:
My bot is playing a simple strategy that currently puts it among the top 20 bots. It uses minimax (see brikbrik's post) without pruning, etc. It simply looks two moves deep and chooses the highest scoring move using its board evaluation function. Usually there are no more than 81 boards to evaluate. (Exception: beginning a game where bots can move in 4 directions).
The evaluation function is simple. Partition the board into squares OUR bot can reach first and squares THEIR bot can reach first. I think of this as a Voronoi partition of the board. The score is simply count(OUR squares) - count(THEIR squares).
GO FOR THE DRAW:
Should your bot go for a draw? I think a perfect bot would draw against a perfect bot in every (symmetric board) game. If your bot avoids the draw by avoiding collisions your bot is making a suboptimal choice and will lose against a perfect (or a good enough) bot. My bot chooses a draw over a suboptimal move.
PROS:
Intuitively, this strategy should excel at open-field battle.
CONS: This strategy fills space poorly and so does poorly in the end-game. Here is a game where I "win" by going for the draw and then I lose by having a poor space-filling algorithm (the 2-level deep voronoi territory algorithm performs poorly here.) http://csclub.uwaterloo.ca/contest/visu ... id=3537348
CONS: This strategy splits territory unnecessarily when choosing between equally ranked moves,even before the end game. See this game, where it could have stayed against the wall and won: http://csclub.uwaterloo.ca/contest/visu ... id=3563386
Do you use an evaluation function like mine?
Do you use a single evaluation function for the whole game or a hybrid approach?
How many levels deep do you go? This is a chance for all you C/C++ programmers to brag!

How can I make my bot better?
Cheers! Discuss!