Gábor Melis' () blog - LISP

It hasn't been a year yet since I first promised that alpha-beta snippet and it is already added to micmac in all its 35 line glory. The good thing about not rushing it out the door is that it saw more a bit more use. For a tutorialish tic-tac-toe example see test/test-game-theory.lisp.

The logging code in the example produces output suitable for cut and pasting into an org-mode buffer and exploring it by TABbing into subtrees to answer the perpetual 'What the hell was it thinking?!' question.

While I seem to be unable to make my mind up on a good interface to alpha-beta with a few bells and whistles, I added a Nash equilibrium finder to Micmac that's becoming less statistics oriented. This was one of the many things in Planet Wars that never really made it.

Let's consider the Matching pennies game. The row player wins iff the two pennies show the same side. The payoff matrix is:

 |       | Heads | Tails |
 +-------+-------+-------+
 | Heads |     1 |    -1 |
 | Tails |    -1 |     1 |

Read more

I can't believe I won.

I can't believe I won decisively at all.

The lead in the last month or so was an indicator of having good chances, but there was a huge shuffling of ranks in the last week and some last minute casualties.

Read more

First, is it possible to get something as simple as RESOLVE-BATTLE wrong? Apparently, yes. That's what one gets for trying to port Python code that's pretty foreign in the sense of being far from the way I'd write it.

More importantly, I found out the hard way that sbcl 1.0.11 that's still on the official servers has a number of bugs in its timer implementation making WITH-TIMEOUT unreliable. Also, it can trigger timeouts recursively eventually exceeding the maximum interrupt nesting depth. Well, "found out" is not the right way to put it as we did fix most of these bugs ages ago.

In the new starter package (v0.8 in git, latest tarball), you'll find timer.lisp that's simply backported almost verbatim from sbcl 1.0.41 to sbcl 1.0.11. Seems to work for me, but I also had to lower the timeout to 0.8 from 0.98 because the main server is extremely slow.

Read more

Released v0.6 (git, latest tarball). The way the server compiles lisp submissions was fixed and this revealed a problem where MyBot.lisp redirected *STANDARD-OUTPUT* to *ERROR-OUTPUT* causing the server to think compilation failed.

The Google AI Challange is back with a new game that's supposed to be much harder than Tron was this spring. The branching factor of the game tree is enormous which only means that straight minimax is out of question this time around. Whether some cleverness can bring the game within reach of conventional algorithms remains to be seen.

Anyway, I'm adding yet another starter package (latest tarball) to the lot. It is based heavily on aerique's. Highlights compared to his version:

• no excessive use of specials (*INPUT*, *FLEETS*, etc)
• player class to support different types of players
• MyBot.lisp split into several files
• it uses asdf (more convenient development)
• made it easier to run tests with executables (./MyBot) or when starting a fresh sbcl (./bin/run-bot.sh)

Read more

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.

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

Tron is a fun little game of boxing out the opponent and avoiding crashing into a wall first. The rules are simple so the barrier to entry into this contest is low. Thanks to aeruiqe who made to Common Lisp starter pack it took as little as a few hours to get a very bare bones algorithm going. It's doing surprisingly well: it is number 23 on the leaderboard at the moment with 43 wins, 2 losses and 9 draws.

From a failed experiment today I salvaged Micmac, a statistical library wannabe, that for now only has Metropolis-Hastings MCMC and Metropolis Coupled MCMC implemented. The code doesn't weigh much but I think it gets the API right. In other news MGL v0.0.6 was released.