Writing a bot for a game as simple as tic-tac-toe is not that hard. As there are only 255,168 possible games, you can easily simulate all of them to search for good moves.

So the first thing the bot does is generating all possible game endings based on the current situation. The resulting situations can be stored in a so called Game Tree:

Before we can start implementing the actual artificial intelligence, we need to develop the basic game mechanics. The key element of Tic-tac-toe is obviously the game grid.

As the grid consists of 3x3 fields, we could go with a multidimensional array, where each field would store either a 0 (empty), 1 (X, player 1’s sign) or a 2 (O, player 2’s sign). But multidimensional arrays are difficult to serialize and you can’t do a simple pattern matching against them.

One of the things that always interested me is Artificial Intelligence. I never had a chance to learn anything about it, but now the time has come. I recently bought the book Artificial Intelligence: A Modern Approach which I’ll start reading during my flight to the USA.

In this blog series, I’d like to document the development of a simple tic-tac-toe program. Once finished, I’ll release the source code on GitHub.

The program will support three different players:

Human Player: This one is obvious ;)

Simulating AI: A AI simulating all possible moves to find the ones guaranteeing either a win or a tie.

Learning AI: This one is the most interesting one: The only thing it knows is that it plays a turn based game and it can place X’s (or O’s) on a 3x3 grid. It doesn’t know the rules and it doesn’t know any strategies. Instead it will try to win by analyze it’s moves when the game finished.

I’ll use Java (7) as programming language but the principles are useable in any other language as well.

I just extended my jQuery plugin HumanReadableFileSize.js to support replacing the (numerical) contents of elements with a human-readable file size. Here is an example of how it works:

1
2
3
4
5

<span class="filesize">54788455578</span> <!-- 51.03 GiB -->
<span class="filesize">2322</span> <!-- 2.27 KiB -->
<script type="text/javascript">
  $('.filesize').fileSize(2, true);
</script>

Hope it’s of some use to you.

As I mentioned in my first blog post, I currently use Amazon S3 to host this blog. In this blog post, I’d like to explain my setup and the deployment process.

1

 print 'Hello world!'

I finally managed to start my own blog. I will add random bits about ruby, software development in general, geek stuff but also personal thoughts. You can learn more about me and this blog in the about section of this website.

The blog is powered by Octopress, it’s using the darkstripes theme for the moment and it’s currently hosted at Amazon S3. I will try to build my own theme and setup a personal server when the time comes.