Artificial Intelligence - Methods and Applications (Fall 13)

Assignment 1: Othello

In this assignment, you will write an Othello engine, i.e., a program that computes moves for the game Othello (a.k.a. Reversi). More information on the game can be found here.

Deadline

December 2nd 2013, 12:00 (midday).

Working together

The assignment should be solved independently. Copying code from other students, the internet, or other sources is not allowed (the provided helper code excluded).

Programming language

Ideally, you should write your solutions in Java (1.5 or later). If you absolutely want to write your engine in another language, you will have to do slightly more work yourself (since you cannot use the provided helper code). Talk to the lecturer about specifications and what code should be handed in.

Assignment

Basically, you should write a program that takes an Othello positions and returns a recommended move for the player who has the move.

You will also have to implement a representation for the positions. In the helper code, the Java class OthelloPosition is provided. The code for this class is incomplete, however. You will have to fill in code at the places maked 'TODO' in the file.

The actual engine should take a position, use Alpha-Beta search with a sensible heuristic, and return a suggested move. The easiest way is to construct a class that implements the provided Java interface OthelloAlgorithm. This interface has a method evaluate that takes a position and returns an OthelloAction. It also has methods for setting the heuristic evaluation method (an implementation of the interface OthelloEvaluator) and one for setting the search depth.

The provided implementation of the position, and the way it is sent around in the code is not the most efficient way of doing things, but it is fairly easy to understand and work with. If you want to switch to a more efficient representation, feel free to do so.

Requirements: Your solution must use Alpha-Beta search and a sensible heuristic evaluation. It should be good enough to soundly beat a standard Alpha-Beta implementation that uses a naive heuristic (just counting how many black and white markers there are on the board).

Helper code

The following source files are avaliable:

Interface

To run your program, you should provide a shell script called othello which should be executable and be placed in your home directory at ~/edu/5DV122/lab1/.

The shell script should take two arguments, a description of the position and a time limit. The first argument should be an ascii string of length 65. The first character is W or B, and indicates which player is to move. The remaining characters should be E (for empty) O (for white markers), or X (for black markers). These 64 charachters describe the board, with the first character referring to the upper left hand corner, the second character referring to the second square from the left on the uppermost row, and so on. For example, the 10th charachter describes the second square from the left on the second row from the top.

The second parameter gives a number of seconds. This should guide the depth of your search. If the second parameter is 30, you should see to it that, when run on one of the PCs in MA316, your program replies and terminates within 30 seconds.

The shell script should write a move on standard out on the format (4,7), indicating that the move suggested is to place a marker on the fourth row from the top and the seventh column from the left. If the player who has the move has no legal move, the script should instead write pass on standard out.

What to hand in

You should hand in a complete and well-written report in the box marked Artificial Intelligence - Metoder och Verktyg on the fourth floor of the MIT building before the deadline.

The first page of the report must clearly show your name and CS user name. The report should provide a descirption of the structure of your solution and complete information on how to compile, run, and test your code. Describe how your code works on a level that does not omit interesting details.

All code necessary to run your solution should be placed in ~/edu/5DV122/lab1/. Make sure that permissions are set correctly.

Testing your program

Scripts and code for testing your program can be found in testcode.zip. On a linux machine, do the following.
  1. Unpack the zipfile in a directory (unzip testcode.zip)
  2. Unpack the jar file (jar xf HenrikOthello.jar)
  3. Make sure that the scripts 'othellostart' and 'othello' are executable. If not, write 'chmod 755 othellostart othello'.
  4. Run the 'othellostart' script with two parameters, indicating which programs should play against each other. For instance, if your home directory is '/home/abc123/' and you have placed your 'othello' script in ~/edu/5DV122/lab1/, then you can play Henrik's program against your own by writing './othellostart ./othello /home/abc123/edu/5DV122/lab1/othello'