Connect Four Embedded, Too

And here is the Connect Four player available for you to play against (on Mac OS X and Windows). Again, let me know if you manage to beat it.

Tic Tac Toe Embedded

I managed to put together a simple interactive application for the Tic Tac Toe player, and embed it here. Unfortunately it only supports Mac OS X and Windows, so apologies if you are viewing this from some other operating system.

Let me know if you manage to win! :)

Does it play Connect Four? Yes, it does.

Based on how well my Monte Carlo Tree Search agent played Tic Tac Toe, I wanted to move onto Connect Four.

Because the algorithm is domain independent I merely had to add the logic to list valid moves and determine a win, loss or draw outcome. One half-hour commute later and I had it playing Connect Four!

And it plays well, in fact really really well. Despite me trying my very best and with help from my wife, who happens to beat most of our family and friends at this game, we cannot beat the AI, when it plays first. Connect Four has been fully solved by MinMax searches and it can be shown that the first player can always force a move. This is exactly what my MCTS agent does. It will setup various potential win cases at the higher level slots and then eventually force you into playing moves that will allow it to win.


The other nice thing about the playing style you get from MCTS is that even if you play the same moves against it, due to its random sampling of the search tree, it will typically come up with slightly varied responses - ultimately leading to a win of course! :)

What's next? I'm currently deciding on whether to move onto 9x9 Go, some other intermediate step, or perhaps spend a bit of time making simple web-based GUIs for the Tic Tac Toe and Connect 4 agents, as my current UI is a bit lacking...see insert :)

Monte Carlo Tree Seach

Recently I have made great progress on my AI project, so today I will attempt to wake this sleepy blog from hibernation.

While I had heard about the success of Monte Carlo Tree Search applied to Go and other games a few years ago, it was only about a month ago that I became aware that in its basic form the algorithm is domain independent. It is therefore very suitable for my goal of making general game playing AI that doesn't need to be taught the rules of the games played.

For the necessary background knowledge and a great introduction to the algorithm and its variations, "A Survey of Monte Carlo Tree Search Methods" is a great resource. This paper also includes pseudo-code for the basic algorithm.

In essence, MCTS plays thousands of games to completion taking random moves to get there. The resulting win, loss or draw of each game then informs the algorithm which parts of the search tree to explore further. This combination of random moves and statistical analysis makes the algorithm applicable to a large range of domains and also means it scales well to harder problems - the more CPU time you give it, the better the result will be.

Because the algorithm plays the games to completion, it only needs to be informed about which moves are valid for each turn and whether the game resulted in a win, loss or draw at the end. No other domain-specific knowledge is required.

Is this the end of my genetic programming approach? Quite the opposite, I will be exploring combining the two approaches in the near future.

To try out MCTS, I implemented the basic algorithm and applied it to Tic Tac Toe. After a couple of hours of coding I was ready to play against it...and...it plays extremely well! If the agent starts, it appears impossible to win against it. It sets up clever double win strategies so the best a human opponent can hope for is a draw. I was very impressed!

It is time to move on to the slightly more complex game of Connect 4...