Midterm: Tic Tac Toe

In tic-tac-toe, player X and O take turns marking one square in a 3X3 board 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 perl-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 must be written by you working alone with no collaboration. Basically, this midterm is a test of your problem solving abilities.

Let the user make the first move. After they do, display an updated board 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, and the effectiveness of game play (i.e. does it work like it should).

The Interface

We are writing this just in perl, so there won't be any beautiful interfaces. Here's what mine looks like: 


 0 | 1 | 2 
---+---+---
 3 | 4 | 5 
---+---+---
 6 | 7 | 8 

Pick a space: 4

 O | 1 | 2 
---+---+---
 3 | X | 5 
---+---+---
 6 | 7 | 8 

Pick a space: 1

 O | X | 2 
---+---+---
 3 | X | 5 
---+---+---
 6 | O | 8 

Pick a space:
Yours doesn't have to look like that, but there should be an easy way for a player to see the board and pick a space.

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 AI to work fully, 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* perl file to the folder. Use "midterm" as the assignment name in your file name.

Grading

  • 5 points for getting a working tic-tac-toe game going. The computer can move randomly or take any available space. Nothing intelligent needs to happen
  • 3 points for the computer making a winning move if possible (patterns 1-7)
  • 1 point for the computer blocking a win from x (patterns 8-14)
  • 1 point for fully working AI (all patterns)
Note: as discussed in class, you can implement this without the board rotation and patterns described above. They work better, but I will accept alternatives.