TicTacToe Bot (Part 2)

PART-2 : The TicTacToe Robot Controller

Now, that we have an algorithm working, what's next? Good question. Lets take a look again at the block diagram of our electronics:

 

Roughly based on the above I whipped together a Schematic:

Basically a Atmel (AVR) ATMega32, with a 2x16 Character LCD,  a Keypad Matrix,  and A set of headers for interfacing with the motion driving circuitry and sensors.

Step 1: Preparing the firmware.

This was main part, apparently porting the windows 'C#' code to plain 'C' wasn't all that simple, after all. Well it would have been , except:

So, I did a bit of optimization, and then some more, and then a LOT more. A poem would explain better:

"Till I had reduced each int to byte,

and byte to bit,

Till each hardware register was consumed,

Till each register could be used,

or Re-Used no more,

and Lo... I present to you the 'Optimized Code-Size'"

This I'm particularly proud of.

Anyway, the code is divided into 5 Files:

• main.c
• game.h
• game.c
• UserInterface.h
• UserInterface.c

Step 2: Preparing the hardware.

After getting the code "Out of the way", it was time to do what I really wanted to do this weekend. Time to get some Solder Iron Burns and some spit, wire and breadboards, together!!

Lets See what we need first. Hmmm....

-Solder Iron. Check.

-Bread Board. Check.

-LCD. Check.

-Microcontroller. Check

r step -Random Headers and Stuff. Check.

-Some Discreets. Check.

-Lots-a-Buttons. Check.

All clear. Lets go....

One Hour Later:

Everything assembled to my satisfaction, and ready for testing.

It Works!!! It Works!!!

Some random screens:

Scrolling Up and Down the Menu:

Preparing the Outer Box: (I wish I had taken my art and crafts class in High school seriously

Ooohhh the guts and wires.....

The Front Panel: (Before I got creative with a felt pen )

  AAaahhh Finished....

 

Still Works....

Under the hood: Easy Access to the Microcontroller, and I/O Headers. I know, I'm a genius.

  So, Thats it for now. What about the rest of the bot? Well the main part is over, I mean, the Code works on the Mega32, is now optimized, quite a bit, and I spent an entire long weekend (Long Weekend = Friday + Saturday + Sunday) on it, so it may be atleast another 3-4 weekends that this project will be on hold, so that I can work on other interesting projects. Nothing to be sad about... Next week, I'm working on Panasonic Servo based gantry (Ball Screw), with a Xilinx Spartan XC3S400. Nice....

 

If you like this post, leave a message, it always makes my day.

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.