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.

Computer Go reference bots

Interested in Computer Go? Then you probably already know about Don Dailey's excellent work on providing a number of Monte Carlo reference implementations. So far, he has managed to implement it in two three different languages (Java, C and some language called Vala).

The announcement is here and the Java bot is available here. It's not the prettiest Java code out there, but Don is a C programmer (I think) so he is excused. It was very interesting and educating to study the code. I've been reading a lot of the Monte Carlo Computer Go papers but I've always felt as if I've missed something fundamental since my understanding of how it works felt too... simple.

Now that I've seen the code I can say, with confidence, that it *is* quite simple. Implementing a Monte Carlo method, that is. Getting a decent (let alone, good) AI-player for 19x19 Go seems quite far from simple.

Cracking Go?

The October issue of IEEE Spectrum has a very interesting article about Go AI players and whether or not one can be created that will beat the best human players. The article is written by Feng-Hsiung Hsu. He was one of the people in the team behind Deep Blue, the chess-playing program that beat Garry Kasparov in 1997, so I guess he knows what he's talking about.

I was a bit disappointed though, after having read the article, since I got the feeling that the solution was more or less the Deep Blue program running on faster hardware and having been enhanced using null-move pruning and caching results of life-and-death analysis. It all sounds a bit... too simple. Life-and-death analysis is tricky business indeed and it doesn't help at all when he basically says that all the leading Go programmers today are too narrow minded in what they do and that their approach(es) won't ever lead to any decent Go AI players.

Until he provides some more details about this I'm going to have to agree with Luke Biewald that he himself may very well have underestimated the problem. It will however be very interesting to see what they come up with in the next few years in the research efforts that Microsoft (where he works) sponsor.

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.