There are various ways for a computer to intelligently play a game. Each has a model with advantages and disadvantages that can be studied through implementation in particular game. After researching the problem, we found that no attempt had been made to compare the performance of the models of rule-based system, Minimax, and agent systems on the same game. To explore these different models, we examined different implementations of a small game with computer players. Our ultimate goal was to evaluate the algorithms for their efficiency, ease of implementation, scalability, and sensible representation of the problem.

Tic-tac-toe was chosen due to the simplicity of its game tree. We were able to generate a pruned version of this tree manually as well as produce a program that generates the entire tree. The implementation of the game itself was made easy due to a number of implementations of tic-tac-toe already in existence, as well as the availability of object oriented programming. We began the study focused on a very basic interaction between human and computer in which the computer was "dumb" but very modular. We knew this would be important since we wished to change the computer’s capability, vary the strength of play and play them against each other.

We developed three separate methods the computer used to play tic-tac-toe. The first method we implemented was a rule-based system guided by hard coded rules based on human observations and analysis of the full game tree. The second method was based on the expansion of the game tree using the Minimax algorithm with alpha-beta pruning. The third method involved an agent-based version that was capable of breaking down the game into smaller specialized tasks.

In doing our research we assumed that each method was able to produce equivalent game play. Because of the simplicity of the game and the fact that we were able to map out all possible moves, we were able to determine this to be true for the various algorithms developed. Using the implementation adopted from Problem Solving with Java, we were able to play each implementation against the others. The degree of difficulty in implementation varied somewhat. The rule based system was most difficult (and may be impossible for more complicated games) due to the necessity to represent every relevant state of the game in hard code. The agent-based system was very large, but could be looked at in manageable pieces. The Minimax system was the easiest, except for the heuristic function, which may not be perfect even now.

The agent and minimax solutions exhibited malleable properties which where adaptable to different game situations with nominal recoding; the rule based solution did not offer much flexibility. The rules tended to intertwine too tightly to separate out into modules. Also, the complexity of the rules was significant and the amount of analysis required for tic-tac-toe was extensive, implying that rule-based solutions for more complex games would be impractically large.

The scalability among our implementations varies as well. Minimax will simply use any computing power it can to recurse the game tree up to a predetermined limit: the depth of the game tree to search. In the case of tic-tac-toe, the game tree was small enough where we could search it completely in reasonable time. The agent version is extremely well suited for parallel processing, where each thread could become a process on a separate CPU. Each agent, or thread, was responsible for one small decision so that when combined, culminated into an intelligent decision. Finally, it seemed that all algorithms sensibly represented the problem. This is most likely not the case with larger game systems as the complexity increases.

In the future, this research will be extended in several ways. First, there are other algorithms that could be implemented and compared to the existing systems. For example, how would a genetic algorithm or a neural network hold up against these systems? Also, the knowledge gained using the simple game of tic-tac-toe should be applied to other games. Is it possible to write a rule base for a game as complex as chess or is Minimax the only practical solution in this case? Finally, the knowledge gained about these algorithms could be generalized and applied to artificial intelligence as a whole.

Minsky, Marvin, The Society of Mind, Simon and Schuster, 1986

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

http://www.research.ibm.com/deepblue/meet/html/d.3.html, Copyright IBM Corporation, 1997 under the auspices of ACM

Koffman, Eliot and Ursula Wolz, Problem Solving with Java, Addison-Wesley, Reading, MA, 1999