Source Code Thread

[BlackWave]

My bot "colors" all contiguous areas of the map, and check if there are the same area adjacent to each player.
if yes, go to connected (try to find a win move) else got to maximize moves in an area.
In connected mode, it's very aggressive in the way that it spends 0.9 seconds going deep in move trying to find one that unconnects the players leaving me with more area than him. It iterates with all possible of my moves trying to find one that ALWAYS win, no matter what the opponent plays. (Win means unconnect with more area) It can go to a depth of 9 (18 if counting his moves). If no win play has been found, he just simulates all play with depth of 2 (for each move I make (NN to WW) he calculates all his possible moves) and plays the one that leaves me with more area. In case of two or more plays with same score, then choose the one that goes nearest (in straight line) to opponent.
In unconnected mode, makes and iterative on the number of plays trying to find the one which leaves me more area and less walls in my color. Usually, it goes to a deepness around 8/9.
I didn't had time to make "pretty" code, so I'm sorry for all the garbage in it.

[timwintle]

Here's mine - in python/cython/C - the main entry point is in the.py files, which import an extension module built from the .pyx, .h, and.c files. chamberNode.c/h are linked in, but I didn't have time to finish that.

I seem to have a bug or two given how badly I've done compared to others using almost the same technique (it was really frustrating bug hunting for hours and not finding anything ) - but here's what I was going for:

* if the bots are separated then generate a game tree (using only my moves) and choose the path that maximises area left at the end. I normally manage 15-25 levels deep.

* If the bots aren't separated, build the game tree for both players moves and assign scores to the nodes as such:
for most nodes:
min(score({their moves}))
or
max(score({my_moves}))

for deepest nodes:
-100 if we lose
+100 if we win
0 if we draw
delta := (my_area - their_area) (within the limit -100<delta<100)

If they were in the same section on that node then I used veronoi territory. If they were not, then I split the region into chambers, and for each chamber I used the checkerboard trick - this gave a better upper bound than flood-filling, but not as good as if I'd got the chamber graph working.

At each game state node I also pass back which move I've predicted they are going to make - and what their worst possible move would be (along with what score that would lead to).

I tried using this information to decide when it's worth picking a move that's not the best (i.e. when the move they would make - assuming I make the best move - is actually the worst move they could make if I did something else).

This last trick seems to have worked well against some bots, and really badly against others - I guess it depends on how similar our evaluations are - I'd have stored a hit ratio for the move predictions and decided when to take such a move based on that if I'd had time. In the end I commented it out a few minutes before the deadline over a very narrow empirical test,

[Fritzlein]

[dmj]

Here is my bot:

http://bitbucket.org/dmj111/tronbot/

I will try to clean the code up over time, but wanted to get it out there. The code uses alpha-beta minimax with Voronoi for the evaluation function. I did a bad job on trying to make it faster, so it only looks ahead 2-6 ply when both bots are in the open.

When separated, I use a iterative depth-first search to find the move that leaves the most reachable area, using cut points to find areas that will not longer be reachable. This can see much further ahead, since it ignores the opponent's choices. Something might still be wrong there, because the bot makes weird choices. I think it may be that it knows it will lose a square 20 moves ahead, so it just sacrifices one on move 1. Then, it still loses one 20 moves out because it makes the same type of decision.

I tried using the articulation points to improve the voronoi evaluation. Especially for maps like triangle and oval, my bot thinks it has a lot of territory, but will cut itself off when it approaches the opponent.

[Experiment Garden]

Here is the complete source code for my bots:

http://experimentgarden.blogspot.com/20 ... n-bot.html

[luv2run]

My ranking tended to hover around 70th - 90th in the last few days of the contest, for reference. It's pretty simple I think but did very well except on a few maps like the quadrant one.

It's written in Lua, which is a very readable language, and there are lots of comments.

http://gist.github.com/317677

Description:
The bot first runs a minimax which just checks several moves ahead to see if there is a sure win for us. If there is, we make that move.

It then checks if there is a path to the enemy.

If not, it hugs the walls. This is not the best survival mode but not horrible -- it just picks the square with the most surrounding walls, as long as we don't split the available space. If we must split the space, then we choose the side with more open space.


If the enemy and player can reach each other, the general strategy is to be able to control more space than your opponent. Given our square and our opponent's square, we run dijkstra's on each and obtain a map whose entries are the distances away from each player. We then count who controls the most squares (controlling a square means we can reach the square first). However, squares are weighted by type: deadends (surrounded by 3 walls) are worth practically nothing, while open spaces are worth the most and so on.

Depending on how big the map is, we either run this score count for each of our possible moves, or also include the enemy's possible moves, or look ahead one turn.

Comments? Thoughts?

[DjinnKahn]

[analyst74]

My C# source:



Strategy is pretty typical:
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 and
return final score as -
The whole Alpha Beta Pruning process is wrapped using a Iterative Deepening loop.

If 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.

[dhartmei]

[Fritzlein]

Very nice explanation, dhartmei. Are you by any chance a professional teacher?

Once I realized that the tree-of-chambers constrained the ending node as well as the starting node, I thought about searching in this fashion, but the already-implemented search plus eval seemed to be playing survival mode so well that it didn't seem worth tinkering with any more (especially given egregious errors in eval when the bots could still reach each other). Did you do any performance comparisons between the stretching rubber band and search, either for which filled more territory or for which ran faster?