Project Overview:
Overview: I broke this project down into a number of sub-goals to make it a bit easier to handle. This is why there are eight versions presented on the main page. Each version built upon the previous version. The most interesting versions, other than version 7 and version 8 which implement the minimax and alphabeta algorithms, are versions 3 and 6. In version 3 the computer randomly selects its next square which results in some pretty odd moves. The most challenging thing to do with this version is to try to produce a cat's game. While this is far from impossible, it's harder to force a cat's game with this version than would be expected. In version 6 I used a series of if statements (over 80 of them) to get the computer to play a perfect game of tic tac toe. I tried an early version of this with a group of seventh graders and they found some holes in my strategy and so I tried to fix the holes that they found. I think it is now flawless, but I'm not absolutely convinced of this.

One improvement I might make on versions 7 and 8, is when the computer makes the first move, to have it select its square randomly and to apply the minimax/alphabeta algorithm to all subsequent moves. This would make the game slightly more interesting and in some cases the human might have a chance. (I'll have to look into this.)


Originality: While I endeavored to produce an original version of tic tac toe, I was influenced by several sources especially in regards to the use of the minimax and alphabeta algorithms (see the links below). Coincidentally I started collecting tic tac toe applets almost a year ago before I knew I would be taking this couse and before the programming assignment was altered to include tic tac toe. The first versions of tic tac toe which I looked at carefully were the Sun version and the GNU version (see first two links below). Other games I have spent some time studying and will spend more time studying are Tetris, Othello, Pacman, Asteroids, and Missile Attack.

I spent a lot of time playing around with various variations of the minimax method and the evaluate method before I settled on the version presented here. The versions I settled on are far from original. In addition to trying out various experiments on variations of the main algorithms used in these applets, I also spent a lot of time diagraming tic tac toe game trees in an effort to understand what was happening. All in all this was a useful and engaging assignment and I only wish that I had the mental facilities to develop an entirely original version of the minimax algorithm.


References:

www.javasoft.com
www.uniqsys.com
www.people.cornell.edu
www.cs.cmu.edu
www.cs.uiowa.edu/~dtull
sis.bris.ac.uk
home.cc.umanitoba.ca
www.cs.caltech.edu/~bartok
home.clear.net.nz
www.cs.caltech.edu/~petrovic
www.cs.uiowa.edu/~cremer

BOOKS:

Neil Bartlett, Steve Simkin, and Chris Stranc, Cutting-Edge Java Game Programming, Coriolis Group Books, Scottsdale, 1996.

Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, Upper Saddle River, 1995.