Game Playing Homework

This assignment is out of 75 points, and is worth 7.5 percent of your grade.

Your task in this assignment is to write a perfect Tic-Tac-Toe AI that interacts with a human or plays itself.

You are to implement the minimax algorithm (as seen in the book and the slides).

You may implement your program in whatever language you would like, as long as it runs on linux.gl. Be sure to include any compiling or running information as comments in your source code.

Your program should take one command line argument: "cvc", "cvp" or "pvc". If passed "cvc", the computer will play itself. If passed "cvp", the computer will play against a player and the computer will go first. If passed "pvc", the computer will play against a player and the player will go first. x goes first, o goes second.

The tic-tac-toe grid will be labeled with 9 letters, like such:

ABC
DEF
GHI

In your output, empty spaces should take their respective labels. Taken spots are to be marked with a lower-case "x" or a lower-case "o". Example:

xBo
DoF
GHx

The interface to the program will simply prompt the user to input his move as the empty space. For example:

xBo
DoF
GHx



Where would you like to move?

G



xBo
DoF
xHx

If the user inputs an incorrect or unavailable spot, re-prompt for input.

What to turn in: your source code, complete with in-line comments explaining what you are doing, a header comment that describes how to compile, and a separate text file containing sample output from one computer vs. computer game and one computer vs. player game.

Extra credit: For 4 points extra credit, implement this homework entirely in LISP.

Extra credit: for 5 points extra credit, add alpha-beta pruning to your algorithm.

Extra credit: For 8 points extra credit, in addition to tic-tac-toe, use your code to play connect-four perfectly. All the requirements for connect four are the same as the tic-tac-toe assignment, except you can implement the interface however you would like. Include this in a separate file.

Extra Credit: For 7 points extra credit, in addition to being able to play connect-four, make your alpha-beta pruning algorithm domain independent so that both tic-tac-toe and connect-four use the same code (via a header file, library, etc.). Much like how in homework 3, your BFS was implemented so that it worked for several domains, make your alpha-beta pruning algorithm work the same way.