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/

Hi!

ReplyDeleteYou should definitely also check out the [SSCAI] Tournament (and maybe even blog about it). It's a second year of an AI bot tournament in StarCraft with 24/7 LIVE Streams. Bots can be coded in C++ or JAVA, deadline is in December, and there are some Achievements that can be earned now.

Link: http://sscaitournament.com/