Preliminary

This assignment is inspired by the TAI Game Playing Championship held for many years by prof. Jan Eric Larsson from the EIT department at LTH.

In short:

Your task in this assignment consists in writing a program playing a full Reversi game.

In detail:

The rules of reversi can be found e.g. in http://en.wikipedia.org/wiki/Reversi. This version will be sufficient for our purposes. We will be playing according to the modern, so called Othello rules, i.e. diagonal beginning 2x2 and no limit of disks for players.

Two example sites (there are more, of course) giving you the possibility to get acquainted with the game interactively are http://www.samsoft.org.uk/reversi/ and http://www.haxx.se/home/games/othello/index.shtml, but there are lots more interesting resources on the web, of course.

In order to get the assignment passed, your program must:

1. Play a full game, from the beginning to an end, against a human opponent;
2. It should be able to play as either the dark or the white player (selectable option before the actual game begins);
3. In every game situation suggest a legal move, or admit there is no such move. When the game is finished, it should announce the result and gracefully exit;
4. Implement at least the classical mini-max adversarial search algorithm, with the alpha-beta pruning introduced;
5. Provide a response within a given, user-predefinable time limit;
6. Run on the LTH student Linux system, e.g., on the machine login.student.lth.se (it will be tested there). Any exceptions to this need to be agreed upon in advance!

Moreover, the program must come with a reasonable description (i.e. the submitted report) regarding its design (where in your code the alfa-beta pruning can be found, what kind of extensions or heuristics have you used, what is the evaluation function you have used and why is it reasonable, how is the game represented, etc.), usage (how can one run it in order to test it) and where can it be found on the student computer system, i.e., the access path.

(IMPORTANT NOTES: The path quoted must include your username //e.g., ~/TAI/a1/myprog is NOT GOOD! Why? Use the output of pwd command to provide the path info.// and you have to make sure it is accessible for the person evaluating your submission. Check the Linux chmod command for that purpose, please. The code should be accessible both for reading /i.e., the source has to have the right permissions/ and running /i.e., executable/ without any additional demands like, e.g., compilation or usage of some particular IDE /read Eclipse/.) Please, typeset and format your report consistently, using Latex for instance.

You may consult the code in the textbook code repository (or any other implementations), but the code you hand in must be primarily your work. You do not need to provide all or any code printout in the report - the code is available in your solution directory anyway - but only comments on its interesting parts.

The deadline for this assignment is Thursday, 28th February, by which you MUST file in your working solution to the assignment, fulfilling requirements 1-6.

Important remark: Remember that the time frame allotted to this assignment is approximately five days of your work, so please don't overdo it: a decent program will suffice to get a pass. You are expected to write a simple program that uses a well-known adversarial search algorithm, provide it with some evaluation functions for guiding the search, limit its search depth depending on time flow, and finally present the game in a simple manner.

If you decide to use someone else's code (e.g. some library found on the web), please mention it both in the code and in your report: it is a matter of academic honesty. Lund University is committed to fighting every case of dishonesty or plagiarism.

The report should be sent to edap01@cs.lth.se as an attachment to a mail message with the following subject line:

Assignment 1 by username

where username is your user name in the student computer system, like ada09jam or ja1234ma-s .

The resulting programs should remain accessible until you have been notified of the result, e.g., on the notice board and/or web or by e-mail. You may expect that your report and implementation will be examined within two weeks. If your report or implementation is unsatisfactory you will be given one chance to make the corrections and then to hand it in within a week after you have been notified (on the notice board and/or web or by e-mail).

Please send any requests for clarification to Jacek.Malec@cs.lth.se or visit him personally at his office, preferably on Wednesdays after the lecture, between 15.30 and 16.30.