CSE 473 Assignment 4: Othello

List of team members due April 18 (by email to Ravi Kiran)

You must complete this assignment in a team with with either one or two other students. One member of each team must send an email to TA Ravi Kiran no later than midnight Monday April 17th stating the members of the team.

Program listings and writeup due in class April 28 (hardcopy as described below)

Tournament will take place April 29 - May 30.

Special prizes awarded to the 1st, 2nd, and 3rd place teams!

Assignment

Implement a program that plays Othello. Your program must:

• Play legally
• Be capable of playing first (white) or second (black)
• Be able to return the best move found with a specified number of seconds (typically between 15 and 30 seconds, see below)
• Employ a reasonable board evaluation function

Beyond these requirement, anything goes. You may use any programming language and run on any computer where you have compute cycles. For reliablity and ease of playing in the tournament it would be best if your final program ran on a team-member's laptop, but this is not a hard requirement.

Writeup Guidelines

Please discuss the following:

• Representation of the Othello game state.
• Generation of the next ply in the search tree.
• Board evaluation heuristic: why is it good?
• Methods for maximizing your search space over a fixed time period.
• Anything not mentioned above that makes your program cool.

In addition, for the discussion of the utility evaluation heuristic, please provide three board configurations, the computed utility value for each, and written description of why the computed utility value was appropriate for the given board configuration. Something to the effect of "The utility for this board configuration is high because I control three corners and I am about to capture a number of the other players pieces." You can pick whichever board configurations you'd like, but ideally we'd like to see configurations with good utility, bad utility and something in-between.

Please additionally attach a copy of your source code printed in two-column landscape mode, both front and back so that we might save some paper. CSE printers are all duplex capable. Take advantage of this fact. Linux users might want to check out "lpr -Z duplex" when printing.

The Tournament

Once the programs have been implemented, we will send out a listing of Othello team brackets. To keep things simple, games will be played using an agreed upon on-line service such as Yahoo Games or an Othello software game. This both allows for games to be played at a convenient location for each team and enforcement of the rules in a consistent manner. You may play any where / time that both teams agree upon. One person should email the results of the round to Ravi Kiran. Pairings will be posted prior to each round

Time: In order to compensate for groups using different machines to run their program, we will define move length in terms of processor speed. Each player gets 30/(speed in GHz) seconds to move. For example, if the processor speed is 1 GHz, you get 30 seconds per move, but if it is 2 GHz, you get 15 seconds per move. If your program runs on more than one processor, use the highest processor speed. (However, if you write a multi-threaded program that runs on multiple processors, you do not need to divide the time by the number of processors.)

Rounds: Rounds will consist of two games. The team who has the highest score after two rounds wins, where score is the total number of each players pieces remaining on the board at the end of the game. Each team will go first once.

Illegal moves / crashes: If your program attempts to make an illegal move, or otherwise crashes, the game will be restarted. If your program fails again, your must forfeit the round.