Wednesday, March 14, 2007

Zen and Tic Tac Toe (Part 1)

AI Koan: Sussman attains enlightment

In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6.
What are you doing?", asked Minsky.
"I am training a randomly wired neural net to play Tic-Tac-Toe.", Sussman replied.
"Why is the net wired randomly?", asked Minsky.
"I do not want it to have any preconceptions of how to play", Sussman said.
Minsky shut his eyes.
"Why do you close your eyes?", Sussman asked his teacher.
"So that the room will be empty."
At that moment, Sussman was enlightened.

Tic-Tac-Toe is my current favorite in the search for the perfect task to demonstrate good programming practices. I believe it can be used to demonstrate the vast range of solutions that are available for many similar problems, and it should also be a good example of the range of quality in solutions.

Tic-Tac-Toe has a special personal significance to me as it figured in the first piece of hardware that I ever designed in 1969, and it was the first program that I ever wrote using my first personal computer in 1978.

In 1969, I was a sophomore in high school trying to come up with a decent entry for a science fair. I had recently learned to make electric relays using wire, nails, and tin cans, and I decided that it might be possible to wire up nine of these relays to switches and lights in such a way as to play a fair game of Tic-Tac-Toe. I worked for months on the wiring diagram until I came up with what I thought was a solution. Unfortunately, the relays kept sticking and I could never get the thing to work. I never learned whether my solution would have worked if I had access to better hardware.

Later, in 1978, I had bought a Radio Shack TRS-80 microcomputer that had an excellent chess program that I liked. Unfortunately, or perhaps fortunately, the game cassette tape deteriorated after a few months and I was left with no use for the computer. I decided that I would have to learn to program chess myself, so I got out the manual and, quickly getting over my delusions of grandeur, I settled for programming Tic-Tac-Toe. Hundreds of lines of code and about ten hours later, I had a working version of the game that met all of my requirements. I was hooked on programming, but obviously had a lot to learn, since the program was incredibly more complex than my teenage relay machine.

All of these years later, I have decided to revisit the problem of the Tic-Tac-Toe machine with 9 relays and determine if it is indeed possible to construct such an elegant solution to the problem. I will also endeavor to discover if the solution will carry over to software implementation as well, or if it is only possible in dedicated hardware.


1 comment:

rp said...

I have used Tic Tac Toe to explain web progamming. It worked very well, and the game is popular, too - the search engines still play it every day!