Project 1: Othello

Phase I due: Thursday 20 Februrary

Implement an Othello playing program that performs heuristic minimax search to depth 4. The testing program will supply the MAXDEPTH argument of 4, but your program can be hardwired to assume that this is the depth. Turn in a zip file consisting of a single folder using the naming convention below (important). The folder should contain the source and compiled versions of your code, include an executable file named "play" as described below, and a project report. The report must be in pdf (preferred) or Microsoft Word format (.doc or .docx). The report should be at least 3 pages long and include the following information:

Grading:

Phase II due: Thursday 6 March

Modify your program so it uses the milliseconds per move parameter (TIMELIMIT1) to determine how much search to do before returning an answer. You will need to devise a cut-off strategy that relies on time. The Linux operating system call clock( ) can be used to check the time using a clock that advances according to the amount of time the process has been executing (as opposed to the actual time, which can be greater). For example, in C++, the following code snippet determines the amount of time that has passed since the opponent's last move was read:

#include <time.h>
clock_t start, now;
...
    // read opponents move
    scanf("%i %i", &opponentX, &opponentY);
    start = clock();
    ...
    now = clock();
    // units for clock() are CLOCKS_PER_SEC, units for timelimit1 are 1/1000 of a second
    time_passed = (now - start) * 1000 / CLOCKS_PER_SEC
...

Note that:

Grading:

Phase III (Optional) due: Thursday 20 March

Instead of being given a time limit per move (TIMELIMIT1), your program will be given a time budget for the entire game (TIMELIMIT2).

Grading:

Teams

Please contact your team partner. Email both the instructor and grad TA if it turns out your assigned partner is not actually taking the course for credit.

Programming Materials

Pseudocode for Heuristic MiniMax with Alpha-Beta Pruning

Specification

Player programs are a folder (directory) containing a main program named "play" and any necessary auxiliary files.The name of the folder is the team name, written using only lowercase letters and using a dash "-" in place of blanks. The team name is of the form

word-word-member-name-member-name

For example: screaming-banjos-tim-kopp-henry-kautz

The file play should be executable. It might invoke other files in the directory. For example, if your player is written in java and consists of the files foo.java and foo.class, then the file play would be the script:

#/bin/sh

java foo

When play is executed, it starts by reading a line from stdin. The line is of the form:

game COLOR DEPTHLIMIT TIMELIMIT1 TIMELIMIT2

COLOR is either the letter B or the letter W, and indicates whether the program makes the first play: B (black) means go first. The remaining arguments are integers. DEPTHLIMIT is the cutoff depth, or 0 if none. TIMELIMIT2 is the amout of CPU time in milliseconds(1/1000 sec) allowed for each move, or 0 if no limit. TIMELIMIT2 is the total time budget for the game, or 0 if no overall limit.

If COLOR is B, then the program must write a line (ending with the newline character) to stdout specifying its move.After printing its move, the program waits to read a line from stdin indicating the opponent's move. If COLOR is W, then the program waits to read a line from stdin specifying the opponents move, and then begins to work on its move.

Moves are specified by line consisting of two integers

X Y

indicating a position by its horizontal and vertical position. X and Y range from 1 to 8.

The tournament program determines when the game is over (all squares are filled) and who the winner is. When a player program believes that the game is over and it cannot move, it should wait by reading from stdin. If a line is able to be read (it should not, unless the program has a bug), it should print a line consisting of two zeros and loop back to read from stdin.

If a program takes longer than TIMELIMIT to print its move, or if it makes an illegal move, it immediately loses and the tournament program ends the game.

Tournament Program

The following details are subject to change, check back until this page indicates that it is finalized.

tournament program is supplied by instructors in the ???? directory on the instructional linux cluster for CS majors. It is invoked as follows:

tournament GUI BLACKPLAYER WHITEPLAYER DEPTHLIMIT TIMELIMIT TIMELIMIT2

GUI is one of the following strings:

gui Display the game graphically (using X windows and the DISPLAY environmental variable).
text Print a record of the game to stdout
none Nothing is printed except the final winner of the game

Each of BLACKPLAYER and WHITEPLAYER is either the flag -human or the name of a player program directory (including the path if not in the working directory). If a player is human the player either uses the gui to enter her moves, or in the case of text display types her moves as pairs of integers to stdin after receiving a prompt. TIMELIMITs are not enforced for human players. For program players, the tournament program runs them and interacts with them via stdin and stdout as described above.

At the end of the game, the tournament program prints a single line to stdout of the form:

winner COLOR ADVANTAGE REASON

where COLOR is either the letter B or W, ADVANTAGE is an integer equal to (# winner squares - # loser squares), and REASON is one of the following strings:

legal The game was played properly by both players
timeout The losing program exceeded the time limit on a move
illegal The losing program made an illegal move

Note that in the came of timeout or illegal, ADVANTAGE might be negative.