I sow several tic-tac-toe games for arduino.
All of them were designed for GLCD library, and none was a "thinking" one, all were randomly chosen steps.
At first this game was designed for GLCD, but when I sow the TVOUT library, I knew this will be my first trail with it, converting the tic tac toe to output on TV.
You can see the setup in this photo:
I used Duemilanove board, the keyboard you see is also home made. The arduino is connected to the computer since I was in the middle of working on the code when I took the photo.
And in this photo you can see Its still easy to beat the game, but that is true when playing against humans as well, If you go for 3 corners no one can stop you from winning.
If you are interested in the code, just drop me a line.
I think I would like to add some sounds to it as well, which is available with the TVOUT library.
TVOUT - http://code.google.com/p/arduino-tvout/