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: an 8x8 array
which uses 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.
The function find-move 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)
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)
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 I included
in my code is 10x10, instead of 8x8. You should use the internal 8x8
portion for the Othello board, and leave the outer ring as zeros.
I found when writing my code that it was really convenient to represent
the board in this fashion, as in some situations I didn't have to have
special cases when writing my loops to handle the edges of the board.
Feel free to take advantage of this or not, as you wish.
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.