Your goal is to create an agent that can accurately play Othello (also known as Reversi) using a minimax strategy with alpha-beta pruning. Here are the rules, and you can play it online. Play a few games, especially if you haven't played Othello before.
To get started with your assignment, copy the files othelloBoard.py and othelloPlayers.py into your directory. othelloBoard.py contains everything necessary to get the Othello game moving. Use Python's help facility to see what what methods are in there that you might find useful. You should not modify othelloBoard.py in any way, but I am supplying the code in the event that you find it instructional to look at. To actually start up an Othello game, run python othelloBoard.py from a command prompt. The game allows for two players, each of which can be a human player or a computer player. You'll find a class for each of these players in othelloPlayers.py.
You need to submit code for following two functions/methods inside othelloPlayers.py:
Given a particular Othello board, return a heuristic value indicating the value of the board where a large positive number indicates a good position for white, and a large negative number indicates a good position for black. I have already given you code for the function heuristic, but it is very silly. You might need to experiment with this to come up with a good heuristic function. (You may not call the chooseMove function from within heuristic. Doing so would effectively not be calculating the heuristic on the current state, but would instead be looking ahead further.)
Given an Othello board, return a tuple (row,column) indicating the move that the computer chooses to make. Note that rows and columns start at 1, not 0, in order to make the game more playable for non-programmers.
You should use minimax search with alpha-beta pruning, and your code should use the above heuristic method. The number of plies is stored as in instance variable in the ComputerPlayer class. For example, a value of 1 for plies means that you should consider all possible moves you might make, and merely choose the one that gets you the best heuristic value. We will test your code by supplying our own heuristic function to see if your chooseMove method gives the same answer as ours does. Therefore, code this up carefully keeping that in mind, and make sure that you use self.plies as the number of plies to work with. Similarly, make sure that you do not call your heuristic function directly; rather, use the heuristic function that was initialized in the constructor for your ComputerPlayer object (e.g., use self.heuristic).
Anytime that you need to break a tie (perhaps two moves have the same heuristic value), you should choose the one that occurs on the lowest numbered row. If more than one move satisfies this criterion, choose the move on the lowest numbered column. In order for us to determine if your alpha-beta pruning is successfully pruning away the right number of nodes, you should print out a count of the number of times the heuristic function was called. You should print this out right before you return the answer from chooseMove, and the count should reflect the number of times heuristic was called just during this particular call to chooseMove.
Part 1: Turn in some attempt at a heuristic function. This is not your final one, and not the one we will ultimately grade for some form of correctness, but turn in something. This is to motivate you to get started on the assignment. You may want to code up a non-pruning version of chooseMove to run against the heuristic, but at this stage, this is up to you.
Part 2: Turn in a good heuristic function, and chooseMove as implemented with alpha-beta pruning.
Here is how the assignment will be graded.
After all the game playing agents have been submitted, if we can we'll run a tournament on the heuristic functions to see which agents play the best. Let me know if you'd be interested in volunteering to run the tournament.