Gábor Melis' () blog - March 2010

Archive

Older posts

UCT

As promised my UCT implementation is released, albeit somewhat belatedly. It's in Micmac v0.0.1, see test/test-uct.lisp for an example. Now I only owe you Alpha-beta.

Google AI Challange 2010 Results

For what has been a fun ride the official results are now available. In the end, 11th out of 700 is not too bad and it's the highest ranking non-C++ entry by some margin.

I entered the contest a bit late with a rather specific approach in mind: UCT, an algorithm from the Monte Carlo tree search family. It has been rather successful in Go (and in Hex too, taking the crown from Six). So with UCT in mind, to serve as a baseline I implemented a quick minimax with a simple territory based evaluation function ... that everyone else in the competition seems to have invented independently. Trouble was looming because it was doing too well: with looking ahead only one move (not even considering moves of the opponent) it played a very nice positional game. That was the first sign that constructing a good evaluation function may not be as hard for Tron as it is for Go.

But with everyone else doing minimax, the plan was to keep silent and Monte Carlo to victory. As with most plans, it didn't quite work out. First, to my dismay, some contestants were attempting to do the same and kept advertising it on #googleai, second it turned out that UCT is not suited to the game of Tron. A totally random default policy kept cornering itself in a big area faster than another player could hit the wall at the end of a long dead end. That was worrisome, but fixable. After days of experimentation I finally gave up on it deciding that Tron is simply too tactical - or not fuzzy enough, if you prefer - for MC to work really well.

Read more