Your goal is to create an agent that can accurately play Othello using a minimax strategy with alpha-beta pruning. If you're not familiar with the game, you can find the rules here. Submit a file called othello.lisp, which can have as many functions as you like: but it should have one in particular called find-move. This function should take the following parameters:
board: a Lisp 2-D array that contains an Othello board. It should be of precisely the form generated by calling the function (initalize-board 8), as found in /Accounts/courses/cs327/othello/othello_start.lisp. Use a 0 to indicate an empty space, a 1 for white, and a -1 for black.
player: indicates which player a turn should be made for. If player=1, your agent should move for the white player; if player=-1, your agent should move for the black player.
eval-function: this is a function that takes a board as a parameter, and returns the value of the board according to a particular evaluation function.
plys-ahead: indicates how many plys ahead your code should look in trying to find a solution.
The combination of a board, a player, an evaluation function, and a lookahead distance should completely determine what the next move will be. This will make your assignments easier to grade, but more importantly, will help us to run a fair tourney between programs.
The function (find-move board player eval-function plys-ahead) should return a list, containing row and column values where your agent chooses to go. If your agent decides to pass (or if no move is possible), return nil. Your return values should be indexed from 1, where (1 1) corresponds to the top-left of your board. For example, suppose that "board" contains the following pattern.
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . W B . . .
. . . B W . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Then the function call
(find-move board 1 sum-points
5)
might return the list (4 6),
which represents the following move:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . W W W . .
. . . B W . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Alternatively, from the same initial board, the function call
(find-move board -1
sum-points 5)
might return the list (4 3):
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . B B B . . .
. . . B W . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
... and so on.
To get you started, copy the file /Accounts/courses/cs327/othello/othello_start.lisp into your directory. It contains two functions that you may find useful: initialize-board, which is used to generate a starting Othello board, and print-board, which prints a board to the screen. Note that the board array is two units bigger in each dimensions than it should be. This is intentional; you should use the internal 8x8 portion for the Othello board, and leave the outer ring as zeros. It is general easier to code when you leave the outer ring empty. Chances are you will find this useful as well.
Students in the past have considered this to be one of the more
difficult assignments of the class. Start early! For full credit, your
should implement depth-limited depth-first-search, with alpha-beta
pruning.. Set partial goals and work your way there: some partial credit
will be given for a game that plays poorly or slowly but still manages
to play. Get it working without alpha-beta first.
After all the game playing agents have been submitted, we'll run a tournament to see which agents play the best. Indicate in program comments the name of your favorite evaluation function that you have constructed so that we can use it.