If the only tool you have...

"If the only tool you have is a hammer, you will see every problem as a nail." - Abraham Maslow

This week, I've been experimenting with Monte Carlo methods for a Pentago AI player. I've written pattern-based AI players for Pentago before and (somewhere) I've got an unfinished implementation that uses Minimax as well.

I didn't really expect much from this little experimental player (it's only about 100 lines of Python code) but it has turned out to be "not too bad". Despite the fact that it only considers one game state at a time... maybe that says more about my other players though ;-)

I'll try to add MCTS (Monte Carlo Tree Search) during this week, maybe even UCT (Upper Confidence bounds applied to Trees) which ought to make the player quite a bit stronger.

Constructing an AI player for Pentago

I wrote my first AI player for Pentago a year and a half ago. It is a simple player which uses board patterns to decide where to place the next marble and which block to turn. I had no idea at the time that what I'd done was basically a very limited and modified implementation of the Markov Algorithm.

The player is simple but the implementation isn't trivial. Each pattern is expressed as a function returning either None or a tuple specifying where to place the next marble and optionally which block to turn.

Here is the function for placing the next marble:

>>> def placeMarker(self):
...   for method in [  self.winIfPossible,
...                    self.avoidImmediateLoss,
...                    self.blockThreeInARow,
...                    self.captureCenterPositions,
...                    self.blockFourInASquare,
...                    self.positionFourInASquare,
...                    self.positionThreeInARow,
...                    self.positionTwoInARow,
...                    self.any, ]:
...     p = method(self.game.getBoard())
...     if p is not None:
...       return p % 6, p / 6

There is also a method called rotateSquare performing similar work.

This player isn't very good but it isn't very bad either. It's remarkable how few patterns you actually need to get a "decent" player.

The problem with this implementation is that it takes a lot of effort to add a pattern. Once I learned about the Markov Algorithm I was able to re-structure the code such that adding a pattern is as easy as adding (for example) "???$*AA$???" to the Rules repository (I know that the example, and the whole pattern language, is a bit cryptic but I'll post about that some other time).

"???$*AA$???" can actually be used for both blockThreeInARow and positionTwoInARow (it all depends on who's turn it is). Using the Markov Algorithm requires *more* patterns to be described but since they're simpler it's a net win (in lines of code). To describe the winIfPossible pattern I need to specify it as three different patterns (because you can win horizontally, vertically and diagonally).

Of course, this type of player can never play better than I can (since I have to feed it patterns in order for it to improve). So my next move is to implement a Minimax player.

F/OSS Pentago?

As I've mentioned previously I'm interested in donating my pygame implementation of Pentago to OLPC. However, I want MindTwister (the company behind the game) to back it up, so most of last week (and this week) I've played the part of F/OSS Advocate.

I've suggested a dual-licensing scheme for them. Similar to what MySQL is using. And I've agreed to donate all of my Pentago related code to them provided that they also release it as GPL.

I really hope that they will decide in favor of it. I honestly believe that opening up is the best way forward. Of course, doing so will lead to lots and lots more work in building a community but that's the fun part...

Swedish Championship - Pentago

This weekend saw the first Swedish Championship of Pentago. Mariann Larsson is the first Swedish champion (more results here). It's a really good game. Damn, I wish I had spent the weekend in Stockholm, I definitely would have entered... maybe next year.

If you haven't tried Pentago yet there's an online version here. The page is in Swedish but if you click on "Pentago AI - Play" you go straight into a game. The rules are available in English here.