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.

2 kommentarer:

woolfel sa...

good old minimax algorithm. since you have a rule engine, you could implement the rules in your engine and then use it to play. I'm guessing you're already using your rule engine to do that. A fellow open source friend started to write his own chess game last year. good luck with that. it should be a lot of fun.

Johan Lindberg sa...

Yes, you're quite right. I do use my pyRete engine to construct AI players.

Actually my first implementation sparked my interest in Rete (I was convinced there must be a better way than Markov :-). However, I really feel that using a Rete implementation is overkill for the simple pattern matching Pentago player I've described.

Playing other games like Chess or Go is of course another matter and I'm really hoping that pyRete will prove useful enough for constructing a "decent" Go player some time.

Of course in the really, really long run. I'm hoping to implement a Neural Network Go player but that's mostly my hubris talking...