Project 1

Due 10/21

We are going to be creating a program that does mini-max search and alpha beta pruning to play the game connect four. Anyone not familiar with this game may look here. I've provided a basic connect four implementation here (though I don't promise it's fully correct. The first student to find a bug in it will get extra credit on their project). Your is to write a program that makes moves based on the mini-max algorithm.

You need to write the following two functions:

  1. move(connectFourBoard, depthLimit, alphaBetaPurningOn, heuristicFunction)
  2. moveRandomly(connectFourBoard)
Each of these functions should make a move on the connect four board provided. "move" should use the minmax algorith along with alpha beta pruning. It should return how many states were explored. It should explore depthLimit moves into the future. If alphaBetaPurningOn is true, it should attempt to do alpha beta pruning. The heuristicFunction should be a pointer to a heuristic function (which you will have to come up with on your own). The moveRandomly function should simply move randomly.

You should spend a little time trying to come up with clever heuristics, and you are welcome to use the internet to help you with this. Your minimax should usually beat the random player, and if you want to test how good a given heuristic is, play the two heuristics against each other 100 times or so. We'll have an in class tournament, with the best connect four program getting extra credit.

At the end, you should write a brief report describing what heuristics you tried, how often your mini-max beat the random player, and anything else you think would be of interest about this program (it can be about a page long).

To submit your project and report, use the command "submit cs471 proj1.py report.txt". You may submit additional files and have any other methods you like, but both move functions must be in the file proj1.py.