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.