TicTacToe Algorithm

 

So, I've been thinking a while now, of constructing a robotic game playing machine. You know, the type which plays Chess, Checkers, Monopoly.... You name it. Sound big? It did so, to me too :P . So we start with some thing simpler. A TicTacToe playing bot, now, here is an Idea!! I thought about this one for some time, the Idea slowly matured in my mind, and I concluded: The first step was to design an algorithm to play a fairly intelligent game of TicTacToe with a human opponent. I have no real experience with writing any game AI, so this was nice and challenging, worthy of devoting a full Sunday to......

So the algorithm is fairly simple. I played about a hundred games with myself to try to think of my thought processes during the game, and to my fair surprise, I found that my thought process was entirely linear (I blame it on the damn C-Addiction ;) ). Honestly the thinking was simple:

1. Look for a place to make my own winning trio
2. If found: make a play there
3. If not found: look for opponents possible trio
4. If found: make mark there
5. If not found: make a mark, so that there is possibility of trio next time.
6. goto 1

Sounds about right, huh? So what was to do? I whipped together a list of conditional statements to do the job, and wrote a program in C# to test it out. The reason I used C# is: Since its entirely a 'C' compatible syntax, I should have no trouble porting my logic and code to CodeVision (AVR), which I intend to make a target for my TicTacToe Robot.

Lets explore the program a little:

In this example, the Human Player (A.K.A: me, lolz!!) has chosen 'X' to play. Human moves are highlighted in blue, the computers moves are highlighted in red.

 

If you see the image above carefully, you will notice the first move I made is the top left corner, and the computer responded with a mid-right 'O'.

Reason: the mid-right 'O' is unobstructed, in 2-directions, and the highest chances of success are currently in 2 directions. Ideally we should have 3-directions of obstruction free blocks, but with my corner move, there are none left.

Now, I played the dead-center position for 'X', and the computer responded by blocking the 'X' with a bottom corner-right-placed 'O'. There really was no other move. 'O' blocked the trio, AND, started creating a trio of its own. Here there is a flaw. If you haven't figured it out, you will, when you see the next move.

I responded then by placing the 'X' at the top-right corner, the only logical position to be in, really. I stopped the 'O' trio, and co-incidentally, created, what I call the 'Double-Move' in TicTacToe. I could now place a 'X' in 2 places to win, and 'O' has only one move to stop both (the aforementioned flaw, we have here :P)!! So it picks one of the two places to block me. It picks the bottom right corner. The reason for that is, If I somehow miss the trio that I am making, 'O' can place its mark on the bottom-mid and make its own trio. A trade-off.

Seems like I didn't miss the possible trio after all. Lol!

So where did my algorithm go wrong? One may argue, that I co-incidentally won, right? I respectfully disagree. Look back at play-1 by the computer. The computer should have foreseen the 'Double Move' back then. What we need is a multiple-pass algorithm, to foresee this kind flaw. If the algorithm runs multiple-congruence tests, we can determine, a depth-of-thought kind of scenario, where we determine, the shortest and most probable win. We score each win on the basis of no of moves, and the next move is always a step in that direction.

This may sound like overkill for a simple TicTacToe algorithm right? But, remember what the real reason for this algorithm is? We want to play several games, chess, checkers, .... who knows? Maybe twister, and other crazy party sex games too ;)?? lolz!

You can download my application, and try it for yourself from:

http://rapidshare.com/files/107704442/pub.zip.html

 

Despite its shortcoming(s?), I deem this algorithm ready for the TicTacToe robot. What next? Make this algorithm ready to run on an AVR, and prepare the robot (electronics et al).

A simplistic block diagram to explain roughly the direction in which I will be working.

Will keep posting updates here, So, Stay tuned..... :)

 

Leave a message if you like this article. It always makes my day.