CSE 473 Assignment 4: Othello (Reversi)

List of team members due Nov 9 (by email to Ravi Kiran)

You must complete this assignment in a team with either one or two other students (maximum 3 per team). One member of each team must send an email to Ravi Kiran no later than midnight Thursday Nov 9 stating the members of the team. Send the email in the format:

-----------------------------------------------------------------------------
Subject : Othello Team

  Team-name member1 member2 member3
  ----------------------------------------------------------------------------
   member1, member2, member3 are email ids but without the @u.washington.edu or @cs.washington.edu suffixes.

If you are unable to find another team member, send an email to the instructor by Nov 9, and you will be assigned to a team.

Program printout and writeup due in class Monday Nov 20 (details described below)

Tournament will take place Nov 20 – Dec 1.

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

Assignment

Implement a program that plays Othello (also known as Reversi). 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 requirements, anything goes. You may use any programming language and run on any computer where you have compute cycles. For reliability 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.
• Your 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 allows games to be played at a convenient location for each team and enforces 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 both TAs. Pairings will be posted prior to each round.

Time: In order to compensate for groups using different machines to run their programs, we will define the amount of time allowed for a move 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 which has the highest score after two games wins, where the score is the total number of each player’s 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, you forfeit the game.

Tournament Tree

The tournament tree for Othello games can be found at this link : Tournament Tree

This will be updated as the games progress.

Scoring : Score is the total number of each player's pieces remaining on the board at the end of the game. You were asked to play 2 games but feel free to play a tie-breaker if required. The winning team should send the participating team names and scores (theirs and opponents) to Abhay.

Since we have odd number of pairs in Round-0, the winner from one of the pairings will have a free ride into Round-2 where it plays a game with the topmost loser in Round-1 (from among all teams which lose in Round-1, the team with the highest number of points). By random selection, the aforementioned pairing from Round-0 is {Wumpus1, Wumpus3}

The semi-final round is round-robin tournament where the semi-finalists will play each other. The top two teams enter the finals. The due dates for sending in the results are also given. Please send in the results of your games BY THE DUE DATE