Due date: Thursday, March 20, 2008.

Problem. In this homework we're going to implement a function playing the game of Othello. Thursday, March 20, we'll organize a competition between the programs in the form of a tournament. Any program ready by 4pm will be allowed to compete. Any program entering the competition receives 1 extra credit point for every game won and the champion gets 5 more extra credit points.

Programs that fail to give a legal move at any point are disqualified, unless no such move exists. Programs that result in an error or do not compile will also be disqualified. Programs that crash for whatever reason, like going over the maximum recursion depth, are also disqualified.

Any method to determine the next move is acceptable as long as the move it returns is legal. There are two restrictions:
(1) the answer must be provided within 3 minutes,
(2) you can import external modules as long as they are written by you, part of the standard Python library as installed in our labs, or written by you in C++ and compiled into Python modules.

Working programs can be turned in for full credit till midnight but they can't compete for the extra credit.

Download the following file:
othello.py

In this program you'll have to complete 3 functions:

dir_move: You must complete this function with the 5 remaining cases for the direction of movement - see the global variable directions.

reverse_line_dir: You must write this function that reverses all the pieces of the opponent on a line in the specified direction from a cell adjacent to the position (i j) up to the next piece belonging to the current player. You can follow the model of the function find_opp_dir in which before the indexes i1 and j1 move to the next position, the content of the b[i1][j1] is reversed.

next_move: This is the main function in this homework. It takes the current configuration of the board "b" and the player for whom to make the move, "who". It must return a legal move for this player in the form oftwo elements, i, j. If no legal moves are available, it should return -1, -1.

Note. You must make a copy of the board before moving anything in it, otherwise the board configuration will be lost for trying any other moves. This function should not change the parameter b. The function copy_board can be used for this purpose. If you're scanning all positions on the board to detect legal moves (those for which the function move returns True), do not copy the board for every position. That would use a lot of extra memory. Make a copy of the board, then make another copy again only after you found a legal position and you stored the result (either position and score, or the whole board if you need to expand the tree further). You don't want to copy an array of 64 elements 64 times!

Example. Here is a working version of the minmax and alpha-beta algorithms for the Loves Me /Loves Me Not game without a limit for the depth of the tree. You can use it whichever way you want (including not at all) for the Othello program.
loves_me_not.py

Here is a script that lets you play the game against the algorithm:
loves_me_game.py

Turn in: Python module(s) by email.