Topics in Artificial Intelligence 308-424A G. Dudek

Final Project

Due:

Dec. 1 AT 2:00 PM (electronic submission).
Paper report can be submitted until Dec. 4th.

* Note that the normal policy for
late assignments does not apply *
The final project must be submitted on time.

Bonus marks are available if you hand in a working, albeit incomplete, electronic version early.

Work is to be done independently. Please see the policy on due dates, cheating and inappropriate collaboration accessible via the class web page.

Check the FAQ for tips.

Introduction

The final project is worth a major portion of your mark.

You must implement, test and document a game-playing program. The game your program must play is called forward-drax (formerly known as "Greg's game"). Your game-playing program will use TCP communication to play the game via another program called the "game server". The details of the game and the server are fully documented in a separate set of documents:

• On the game itself. Note this description is probably not up to date!
• On the server and the associated protocol and library.

Objectives

You must satisfy the following objectives:

1. Your program should play the game well.
2. Your program should be based on creative and original thought.
3. Your should docuement your work in a report.

Report

The report must include the following required components:

• An explanation of how your program works, and it's rationale is (why it is the way it is).
• A brief description of the theoretical basis of the approach (about a half-page, in most cases; references to the text of other documents are appropriate but not absolutely necessary).
• A summary of the advantages of your approach.
• Proof that your program works (a summary or explanation of test data).
• A summary of the disadvantages of your approach, expected failure modes, or weaknesses of your program.

Implementation

Your implementation can be carried out in the programming language of your choice. The recommended languages are C and Java and libraries for these languages will be supplied to simplify your task.

We currently plan to hold a competition between all the programs submitted by students in the class. you can expect to recieve a failing grade on the project if you fail to submit a report, even if you have a good program. On the other hand, the report is merely meant to document the program, which is essential.

Before you start your implementation, you should play a few games of DRAX yourself win a friend. Note that a sample (bad) player has also been provided to serve as illustration of how to deal with the technicalities.

Project submission

Please signup now if you plan to complete the final project. (click on the word "signup".)

Submit your program electronically using the "handin" program.

Addenda

Check the FAQ for tips and recent news.

The natural progression for your efforts on your project is:

- Play a series of simple games by hand and via the server.
- Figure out how to encode a chess state.
- Write a successor function.
- Create an evaluation function.
- Connect to the server and verify your functionality.
- Encode a minimax algorithm (perhaps with fixed cutoff or iterative deepening).
- Insert alpha-beta pruning.
- Add whatever other heuristics you think may help.
- Devise ways to tune the heuristics, manually or, better yet, automatically.
- Test, revise, test, revise....

Test your code regularly (on linux). Use rapid prototyping: that is, each time you add a bit more functionality, get it running and check it out before you add much more.

The important thing for your writeup is to document everything. How well deep can you search with just minimax? What does alpha-beta buy you? How effective were your other heuristics? What blunders did your evaluation function do and how did you fix them (if you could)?

Evaluation: This was discussed at length in class. Is short, you will be graded on how well you satisfy the objectives stated above. There are many ways to do this.

Your mark will be based on the product of the report evaluation and the program evaluation. That means either one alone is essentially worthless.

The program will be evaluated based on how well it plays, how much insight of creativity went into it's development, and how complete its functionality is. The program will be marked using the following guidelines:

• Winnng program: top marks
• Original and reasonably successful (but non-winning) approach: top marks
• Non-functional programs: zero marks

Java for linux can be downloaded (for x86 or PPC). You should also check the pages on additional resources for the course.