Your goal is to create an agent that can accurately play Othello using a minimax strategy with alpha-beta pruning. Here are the rules, as well as an online version of the game. Play a few games online, especially if you haven't played Othello before.
To get started with your assignment, copy the file 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 generally easier to code when you leave the outer ring empty, as you will have to do fewer special cases for the edges. Remember this technique; you may find it useful in other contexts.
This is a sizeable assignment, so I will ask you to turn in pieces of the code as you go.
Part 1: Turn in (at least) a function called make-move, which should be invoked as follows:
(make-move old-board row col color)
where:
Part 2: Turn in (at least) functions called board-value and play-othello which should be invoked as follows:
(board-value board)
returns a numerical value associated with the board position. This is the heuristic that you will use in creating the minimax algorithm. Explain in documentation the heuristic that you use, and why it makes sense. (It's ok if you change this in later submissions if you find something that works better.) The black player will be trying to maximize this value, and the white player will be trying to minimize this value.
(play-othello)
allows the user to play a simple game of Othello against the computer. The human player will always be black, and will play first. This function displays a brand new game board, prompts the player to make a move, and makes the move if legal. If the move is not legal, the computer prompts the player to try again. The user should also have the option of passing. In order to make the grader's life easier, you should all use the same format for entering moves: prompt the user first to enter the row number, then the column number. For example, your program running might look like:
. . . . . . . . . . . . . . . . . . . . . . . . . . . W B . . . . . . B W . . . . . . . . . . . . . . . . . . . . . . . . . . . Black's turn. Row? 4 Column? 3 . . . . . . . . . . . . . . . . . . . . . . . . . . B B B . . . . . . W W . . . . . . W . . . . . . . . . . . . . . . . . . . . White's turn. [and so on]
A user may pass by entering in 0 for both the row and the column.
The white player should then move. At this stage, that move can be anywhere legal (it doesn't have to be a good move), or pass if it cannot find a good move. The players should alternate back and forth until they both pass. You don't need to test to see if the game is complete based on the board unless you wish to. You should look ahead to part 3, which requires you to create a function called find-move. You don't need to have this capability present yet, but as you will, you may want to plan for it in writing your code.
A player is only allowed to pass if there are no legal moves. You may assume that players are playing legally in this respect: you do not need to test if a player's pass is legal, though you are welcome to do so if you wish.
Part 3: Turn in the above plus a function called find-move, which should be invoked as follows:
(find-move board player plies-ahead)
where:
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.
plies-ahead: indicates how many plies ahead your code should look in trying to find a solution. A value of 0 means you should not look ahead at all, i.e. you should just consider all legal moves and choose the one that maximizes your heuristic.
It is important that you follow this standard, as this will help us to grade your assignment as well as to attempt a fair tourney between programs. Make sure that find-move uses the board-value function to determine the value of a particular arrangement of the board. To test your find-move function, we will use our own board-value function.
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 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 5)
might return the list (4 3):
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . B B B . . .
. . . B W . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
... and so on.
For full credit, your should implement depth-limited depth-first-search, with alpha-beta pruning. Set partial goals and work your way there: partial credit will be given for a game that plays poorly or slowly but still manages to play. Most of the credit will be granted without alpha-beta pruning: that's the icing on the cake.
Update your play-othello code to take advantage of your find-move function.
After all the game playing agents have been submitted, if we can we'll run a tournament to see which agents play the best. Let me know if you'd be interested in volunteering to run the tournament.