Home Lecture Notes Homework Resources Syllabus Jen's Home INFM 743: Development of Internet Applications

Midterm: Tic Tac Toe

In tic-tac-toe, player X and O take turns marking one square with their mark (X or O). A player wins if they get three of their marks in a row horizontally, vertically, or diagonally. If neither player has three in a row when the board is full, the game is a tie.

Your midterm project is to implement a web-based version of tic-tac-toe. A user will pick moves on the page, and you will make the computer's move using the method described below. You must use the method described below for your computer implementation.

There are lots of tic-tac-toe programs on the web. You may not use any other code either as the basis for your code, to help with parts of your code, nor may you take segments of it to use as your own. Do not consult other programs, in perl or in any other language. You may not use them for logic or for syntax. You must solve this problem entirely on your own and writing code entirely on your own. You may not work with other students, on the code or on the logic. This entire program from ideas to implementation in perl to the HTML must be written by you working alone with no collaboration.

Let the user make the first move. After they do, generate a new page with your move and theirs shown. Repeat for each move. If the game ends, either because you win or there is a tie, print out a message that says the result and do not allow the user to make another move.

You will be graded on your implementation of the algorithm, the effectiveness of game play (i.e. does it work like it should), as well as the quality of your web page. Make it look professional. Appearance will be a smaller part of your grade, but it will matter, so spend some time on the interface.

The Algorithm

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 (first trying the center, then moving from left to right, top to bottom).

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 tries to take the center square. If that is not available, it starts at the left top corner and moves across and then down until it finds an open square.

For this assignment, you must implement and use a subroutine to rotate the board. For a given pattern below.you should check it, rotate, check, rotate, etc. You may not enumerate all four orientations and check those.

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 | * 

Pattern #6 to check:

 * | O | * 
---+---+---
 * | ? | * 
---+---+---
 * | O | * 


Pattern #7 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 #8 to check:

 ? | X | X 
---+---+---
 * | * | * 
---+---+---
 * | * | * 

Pattern #9 to check:

 ? | * | * 
---+---+---
 X | * | * 
---+---+---
 X | * | * 

Pattern #10 to check:

 ? | * | * 
---+---+---
 * | X | * 
---+---+---
 * | * | X 

Pattern #11 to check:

 X | ? | X 
---+---+---
 * | * | * 
---+---+---
 * | * | * 

Pattern #12 to check:

 * | ? | * 
---+---+---
 * | X | * 
---+---+---
 * | X | * 


Pattern #13 to check:

 * | X | * 
---+---+---
 * | ? | * 
---+---+---
 * | X | * 


Pattern #14 to check:

 X | * | * 
---+---+---
 * | ? | * 
---+---+---
 * | * | X
The following patterns represent positions the computer must move to block the player from winning in two moves.

Pattern #15 to check:

    | ? | X     
 ---+---+---
    | O |   
 ---+---+---
  X |   |   

Pattern #16 to check:

 ? | X |   
---+---+---
 X | O | * 
---+---+---
   | * | * 

Pattern #17 to check:

 ? |   | X 
---+---+---
 X | O | * 
---+---+---
   | * | * 


Pattern #18 to check:

 * | * | X 
---+---+---
 * | O | 
---+---+---
   | X | ? 

Pattern #19 to check:

 ? |   | X 
---+---+---
   | O | * 
---+---+---
 X | * | * 

Pattern #20 to check:
 ? | * | * 
---+---+---
 * | X | * 
---+---+---
 * | * |   


Pattern #21 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 (check the middle first, and then the rest). If there are not empty squares, the game is over.

With this algorithm, the computer should never lose.

Turn this in by uploading *one* cgi file to the folder called midterm on the server.