Janzert's Tron Bots, Information Page
Here is the source code for the two Tron bots I developed over the course of the 2010 Google AI competition. The first (crUTCh) is a plain UTC bot with random playouts and the second (crAB) is an alpha-beta searcher with Voronoi territory and 2-connectivity trees. These are my first non-trivial C++ programs in over 12 years and are completely uncommented so don't expect the source to be terribly pretty.
crUTCh - First is crutch. This bot actually started off in Java, but after experiencing a number of problems with timeouts on the contest servers I ported it over to C++. I don't think there is muchspecial about this bot. The only things that might be different than some of the other UTC bots in the contest are that it does include a transposition table and bitboard representation for the maps (see below in crab's description for more details). This achieved a rank in the teens fairly early in the contest (~2/10) and when accidently resubmitted on 2/25 was down around 129th.
After developing crutch I was ready to leave it be and not work further on the contest. But I happened to mention the contest to Fritz Juhnke who encouraged me to continue. He also has a background in mathematics and immediately had quite a few ideas from graph theory. So with his encouragement and supplying the graph theory knowledge for development, crAB was born.
crAB - crAB is an alpha-beta searcher using iterative deepening, a transpostion table and bitboard representation. With Voronoi territory and 2-connected chambers used for evaluation.
The transposition table uses two entries for each slot. One entry uses a greater depth replacement strategy and the other is an always replace entry. Only one slot is probed per lookup.
The bitboard representation uses a 64bit integer to represent each column of the map. So there is a hard limit on the height of maps at 64 squares, although the width is theoretically unlimited
Territory in the open game (when the players are not separated by walls) is done with Voronoi territory (basically whichever player can reach a square first claims it). In the end game territory is simply whatever area is reachable by each player. Value for the territory is then assigned by establishing an upper bound of the maximum area fillable. This is found by first building a tree of all the 2-connected "chambers" within the territory and then backing up the largest "checkerboard" score from the leaves to the root of the tree.
If during the search the two players are found to be separated by walls, two separate searches are then done for each player with the depth remaining. Also if at the beginning of a turn the players are separated search is restricted to just the bot itself and the opponent is ignored completely.
Since the evaluation only uses the value and bound (upper or exact) from the tree these values are cached and reused if the same area (as determined by its zobrist hash) is evaluated again. This gave a fairly substantial speed improvement right at the end of the contest.
On my local computer (an Athlon 64 X2 2.4Ghz) the bot can usually see ahead ~7 moves with 30k nodes searched per turn at the beginning of an open 15x15 map. Usually towards the end of the open game it will be searching to a depth of around 20 moves. Once the endgame starts it will initially see about 40 moves deep and find the longest path 70-150 moves away. (The node count is incremented every time the alpha-beta or endgame search function is called)
For anyone who enjoyed this contest I would encourage you to check out the Arimaa Challenge. The goal there is to develop a program that can beat the best human players. Tournaments are held once a year to choose the best computer players and pit it against the humans.
