Tic-Tac-Toe (to death!)
(or, "How Many Tic-Tac-Toe Games does the World Need, Anyway?")
1.1 Introduction
A while back I decided to assign my assembly language class a simple project, so I had them write a Tic-Tac-Toe game. The class quickly divided into two groups - those who couldn't figure out an algorithm for the game, and those who were having a hard time implementing the algorithm in assembly language. When the due date arrived, those who managed to complete the project had typically written about 1,000 lines of sparsely commented code[1]. Of course, the students were complaining about the excessive size of this project.
Another problem with this project is that the students were collaborating a little too closely. I wound up with a class full of projects, most of which used the exact same algorithm (and, dare I say, a few too many of them used many of the same exact machine instruction sequences). When I began griping about this to the class, I got that all-too-familiar complaint "But there's only one way to do this!" Along with some additional complaints about how much work this project was and how unfair it was that I expected them to figure this out all on their own. Nevermind that I'd successfully given the assignment in the past without all these problems and whining.
In any case, I decided to show that with a little thought and experience, there were a multitude of different ways one could write the Tic-Tac-Toe program, most of which were much smaller than the shortest (working) program submitted in that class. For the purposes of the class, I devised two solution using bitmaps. Shortly after the class was over I implemented a third solution using regular expressions. I've also designed (and as time permits will implement) versions based on look-up tables[2], context-free grammars, and a heuristic search. I am contemplating designs using AI techniques like neural nets and genetic programming.
The purpose of this exercise is not to produce the "best" Tic-Tac-Toe game in the world. Rather, it is to point out that there are many solutions to a problem that a typical student might believe there to be only one solution for (i.e., the one solution the student has already seen). One could not expect CS 13 students (many of whom have only taken one other programming course) to understand concepts like Context Free Grammars and neural nets.
1.2 Basic User Interface
These implementations of the Tic-Tac-Toe game all use the same basic user interface. They present the user with a display that looks something like the following:
0 | 1 | 2 | |
---+---+--- ---+---+---
3 | 4 | 5 | |
---+---+--- ---+---+---
6 | 7 | 8 | |
Your move:
The left-hand Tic-Tac-Toe (TTT) board lists the player's possible moves (the player is always X). The right-hand TTT board displays the current game board. Immediately below the game boards the program will prompt the user for their next move. The user must enter a single digit in the range 0..8. The computer verifies that the user has entered a valid move, makes its move, checks to see if the game is over, and then redisplays the boards. For example, if the user chose move four above, the computer would move to square zero and display the following:
| 1 | 2 O | |
---+---+--- ---+---+---
3 | | 5 | X |
---+---+--- ---+---+---
6 | 7 | 8 | |
Your move:
Note that the computer will not allow the user to move into squares zero or four since these two squares are already occupied.
The game is over when the computer wins or when all squares on the game board are filled.
1.3 Algorithms
Although most of these TTT implementations are different, they all use the same basic algorithm; they search for certain patterns on the board and react accordingly when they discover a specific pattern. These programs do make a couple of assumptions. First, they assume the computer can never lose (which is true if the program is written correctly). They also assume that the player and the computer trade off turns (this means that the computer need only consider a small number of configurations early in the game). Finally, these algorithms all use the fact that the TTT game board is symmetrical. That is, the algorithm really only computes the computer's moves for the following three squares:
* | * |
---+---+---
| * |
---+---+---
| |
If the computer determines that it needs to move into one of these squares, then it takes the move and allows the player to make his/her move. If these squares are already occupied, or there isn't an important move in any of these squares, the computer rotates the board 90 degrees counter-clockwise and tries these same three positions (on the new board) again. After rotating the board four times, the computer winds up with the original configuration. If this occurs, and the board isn't completely filled, the computer takes the first available position on the game board.
When making a move, the computer first checks to see if it can win by putting an "O" into one of these three squares. If it cannot win, it checks to see if it has to block X from winning on the next move by putting an "O" into one of these three squares. If neither of these two conditions holds, the computer checks to see if it has to move into one of these squares to block X from winning in two moves. If it can't win and doesn't need to block X on the next one or two moves, the computer chooses an arbitrary location for its move.
To see if the computer can win, it checks for one of the following patterns. The computer checks them in the following order.
Note: an "X", "O", or space appear in a square below means that character must be present. A "*" means that anything may appear in the square. "?" denotes the position (that must currently contain a blank) where the computer will put an "O" if the pattern matches.
Pattern #1 to check:
? | O | O
---+---+---
* | * | *
---+---+---
* | * | *
Pattern #2 to check:
? | * | *
---+---+---
O | * | *
---+---+---
O | * | *
Pattern #3 to check:
? | * | *
---+---+---
* | O | *
---+---+---
* | * | O
Pattern #4 to check:
O | ? | O
---+---+---
* | * | *
---+---+---
* | * | *
Pattern #5 to check:
* | ? | *
---+---+---
* | O | *
---+---+---
* | O | *
The following patterns check to see if the computer needs to block the player from winning on the next move.
Pattern #6 to check:
? | X | X
---+---+---
* | * | *
---+---+---
* | * | *
Pattern #7 to check:
? | * | *
---+---+---
X | * | *
---+---+---
X | * | *
Pattern #8 to check:
? | * | *
---+---+---
* | X | *
---+---+---
* | * | X
Pattern #9 to check:
X | ? | X
---+---+---
* | * | *
---+---+---
* | * | *
Pattern #10 to check:
* | ? | *
---+---+---
* | X | *
---+---+---
* | X | *
The following patterns represent positions the computer must move to block the player from winning in two moves.
Pattern #11 to check:
| ? | X
---+---+---
| O |
---+---+---
X | |
Pattern #12 to check:
? | X |
---+---+---
X | O | *
---+---+---
| * | *
Pattern #13 to check:
? | | X
---+---+---
X | O | *
---+---+---
| * | *
Pattern #14 to check:
? | | X
---+---+---
| O | *
---+---+---
X | * | *
Pattern #15 to check:
* | ? | *
---+---+---
* | X | *
---+---+---
* | | *
Pattern #16 to check:
? | * | *
---+---+---
* | X | *
---+---+---
* | * |
If the computer cannot match one of the above patterns, it rotates the board 90 degrees and tries again. After rotating the board four times without finding a match, the computer locates the first empty square and moves there. If there are not empty squares, the game is over.
The following documents describe the implementation details for each of the current versions of the TTT program:
TTT1.ASM - A Tic-Tac-Toe program using bitmap pattern matching.
TTT2.ASM - Another Tic-Tac-Toe program using bitmap pattern matching.
TTT3.ASM - A Tic-Tac-Toe program using regular expression pattern matching.
[1] I should point out that these students were using the UCR Standard Library. The line counts would have been higher if they'd had to write the I/O code themselves.
[2] I have nixed the idea of implementing the Tic-Tac-Toe game with a straight lookup table since the table would need 19,683 16-bit entries.
Number of Web Site Hits since Dec 1, 1999:
