I built a robot that plays a perfect game of tic-tac-toe or noughts and crosses.
It uses an algorithm from an article in the 1971 issue of Radio Electronics by Don Lancaster called Tic-Tac-Tronix. The catch is the computer always goes first and plays the same corner square. Here is a link to the Tic-Tac-Tronix article in PDF form on Don Lancasters website. It's about halfway down the page - http://www.tinaja.com/glair01.asp
Movement is done using 3 servos. The computer play pieces are plastic beads. Input of the human player is through 9 switches, made from brass sheet, closed by a conductive play piece (fishing sinker). The switches are read by placing a high on one side with a 4017 decade counter and reading the pin3 input. Diodes keep the high and low outputs of the 4017 from shorting. Pin3 has a 10k pulldown resistor.
It uses 253 of the 256 available bytes. The flow chart in the Tic-Tac-Tronix article is implemented using lookup tables. I have included a serial version of the program that can be run in the simulator. It's what I used to debug the play code before I started adding the robot hardware. I have the schematics and code available. Here's a link to the robot on letsmakerobots.com.