Sunday, April 20, 2008

TicTacToe Bot (Part 2)

PART-2 : The TicTacToe Robot Controller

IMG_0140

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

 block-diagram

Roughly based on the above I whipped together a Schematic:

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:

Error_mem

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'" smile_shades

new_mem

This I'm particularly proud of. clap

Anyway, the code is divided into 5 Files:

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

Program Structure

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....

IMG_0120

-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....thumbs_up

One Hour Later:

IMG_0121

Everything assembled to my satisfaction, and ready for testing. fingerscrossed

IMG_0122

It Works!!! It Works!!!

Some random screens:

IMG_0128

IMG_0130

Scrolling Up and Down the Menu:

IMG_0123

IMG_0124

IMG_0125

IMG_0126 IMG_0127

IMG_0131 IMG_0133 IMG_0134

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

IMG_0135

Ooohhh the guts and wires.....IMG_0136

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

IMG_0137  AAaahhh Finished.... clapthumbs_upbeer

IMG_0139

 

IMG_0140

Still Works....

IMG_0142

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

IMG_0138  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.smile_regular

Tuesday, April 15, 2008

TicTacToe Algorithm

 

Title

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.

 Play-0

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.

Play-1

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.

Play-2

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.

Play-3

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).

block-diagram

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.