Source Code Thread

[grogers]

http://github.com/grogers0/grogers-tron-ai

[Queue29]

I want to see the source of whoever had the high ranking Go bot.

[corey.abshire]

Here's mine.

http://github.com/coreyabshire/Tron

It uses minimax and all that, but it never got deep enough because I wasn't able to come up with a decent way to approximate the space around us instead of counting it all. I tried just deriving whether the space count would be a simple decrement on the space count for the prior state, or whether I needed to count again based on changes in the walls immediately around each player, but the logic for that ended up being too complicated and caused more problems than I thought it was worth.

My fill strategy had issues because it didn't orient itself towards articulation points properly. It basically followed the wall, but it used the same count spaces function to avoid obviously bad choices. Wall would be fine if it filled in an order that optimized before the articulation points. For some reason I just kept avoiding thinking that through.

Some of the other strategies I came up with never worked all that well in practice. I kept experimenting with a bunch of different ideas when I probably would have made it further by optimizing to get deeper in minimax. Oh well, it was fun anyway.

[jmcarthur]

There have been a few requests for me to reveal my source code, but I'd rather keep working on it a little bit longer and play it on dhartmei's server [1] a bit. I will open source it when I'm done with my little exercise. It will be a few days because I won't be able to work on it at all for a little while. I will post a link to the source once I have put it up.

[1] viewtopic.php?f=10&t=337

Edit: I changed my mind about posting the source code for the bot I had submitted. It's posted below.

[positron]

My messy Common Lisp is here:

Nothing special, just minimax with iterative deepening, using the voronoi territory idea for eval. I have attempted trivial monte-carlo for flood-filling but didn't get to spend too much time on that, as it looked like it was doing worse than a simple DFS.

[jmcarthur]

I changed my mind. I will continue to develop my new bot, but here is the source for the one that actually made it to the server before the deadline. My bot used plain vanilla UCT written in Haskell with no special heuristics and ranked around #130 before the deadline, I think. For a day or two it was in the top 50-100, but I stopped maintaining it when I got the idea I'm working on now. My pure UCT algorithm is in GameTree.hs, and it's agnostic to the game it's applied to as long as it's 2 player and minimax. The actual Tron-specific game tree is generated lazily in MyTronBot.hs, including what I guess is an unusual use of unsafeInterleaveST: lazily generating the Monte Carlo results for each node of the tree.

This bot space fills very very badly, though. I would have been much better off abandoning UCT after being separated from my opponent and using a dedicated space filling algorithm.

http://patch-tag.com/r/jmcarthur/uct-tr ... ent/pretty

[dhartmei]

Here's mine: .

Using a minimax tree with only four values (win, loss, draw, undecided), no pruning.
The weakness is chosing among undecided nodes, for which I only had simple Voronoi.
Stronger points are the space filling after separation: finding chambers (through articulations), and the way
to fill a chamber ("stretching rubber-band").

[iouri_]

Here's my code:



Rough description:
- When near to or separated from opponent, use iterative deepening to search through available moves. Score moves using tree-of-chambers approach detailed here: . Pick best move using minimax.
- When far from opponent (> 6 steps), for each available move, replay the game from that move forward using the above method (evaluating 1 step deep) until the opponents are separated or one/both opponents die. If the opponents are separated, the score for that path was the final move score using the tree-of-chambers approach. This allowed to find 'strategically good' moves that would become useful only 20+ steps later.

Most calculation results were stored between the MakeMove() function invocations to avoid recalculating the same thing. The side effect was that in open spaces on small maps the program would take up to 600MB memory.

[achan1058]

Here's my source. I use basic Voroniod Territory (attempting to add "enhancements" such as distance to squares controlled and etc gives worse results) with alpha-beta search. Because player 1 and 2 are not symmetric when player 1 goes first, I ensured that all terminal search nodes are on even depth (where both players make the same number of moves).

When opponents are separated, I simply move to the space that maximizes the remaining squares available, and tie break by maximizing distance. For some reason, trying to do a search on it makes it do some poor moves.

There's a big bunch of macros defined all over the place for me to test the "enhancements" that doesn't work, so I don't have to create multiple source files and forget to modify a bunch of them. Not good coding style, but I like it for a project like this.

[dutchflyboy]

As everyone is sending in his bot, here's mine. It has gotten in the top 10 once (just after upload, but still, great feeling). The rest of the time it floated between 50-100 (EDIT: in final ranking: 81st).

Short description:
- Bot can be in three states, "Hunt", "Eat" and "Survive" (I wasn't very inspired the day I wrote the skeleton).
- Hunt is when the bots are far away and the minimax encourages getting near to the enemy without wasting space
- Eat is at short distances (when minimax gets deep enough to make a valid strategy) and the evaluation function only considers squares. In both cases (Hunt and Eat) tie-brakes are done by trying to stay in a straight line, if this isn't possible, with a random number (add some variance).
- The survive function was a maxmax algorithm (I don't know how it should be called, it's minimax while ignoring the enemy) which tried to maximize the available space and tried to stick to walls (1 wall touched = 1/5 square, so it's only used as tie brake).
- The square count algorithm is a simple counter with a queue that counts all but one dead-end. No other optimizations where added. No pruning either (I tried adding alpha-beta, but it didn't add any speed improvement, so I probably did something wrong in the implementation).