CSE 473 Fall 2007: Assignment 5

CSE 473 Fall 2007: Game Playing

Due: Mon November 26 11:59pm

The purpose of this assignment is to try out the game playing techniques we have studied as well as adding your own ideas. You may choose to do either Kalah with these rules or Othello on an 8 X 8 board with the standard rules.

Kalah Tournament Tree

Requirements

You must use minimax search with alpha-beta pruning as the basic algorithm.
You must design your own heuristic function and justify it in the report you turn in.
You should experiment with different strategies for more efficient or better search from the book or of your own design.
Your program should be interactive, so that you or others can play against it. Fancy interfaces are not required, but can count for extra credit points. At the least the program should display the current state of the game, allow the opponent to enter a move, do a search to determine its own move, display the move it is making and then display the new state of the game.
You should play against the game yourself, trying out your different variants and different max levels of search, and report on the results.
You should report on how long it takes to make a move at the search depths 3, 4, and 5 (and more if you wish) and mention your CPU speed. Timing restrictions are only for the tournament.
Your report should include the following:
- A brief description of the rules of the game.
- The definition of your heuristic function and its justification. Illustrate how it works with example moves it chose and explain why it chose them in terms of the function.
- The details of your program design with justification.
- Some screen shots of samples of your program playing against you including comparison of how it plays and how long it takes with different max search depths and other variants you introduce.

Turn-in Details

Turn in both program and report Here.
Include all files needed to compile your program. Also include any additional data (files) you tested your program on.
Please comment each method separately, describing its arguments, return value (if any), and, most importantly, its purpose. Also comment any important regions of code within a method; important loops or calculations that require explanation.
As with the previous programming assignments, you may program in Java, C++, Lisp or a Lisp variant. You'll need to be able to call a timing function in order to participate in the tournament.
Please include, in a text file with the code, a description of how to compile and use it. It doesn't need to be lengthy; 'To compile, type javac *.java' is sufficient for many cases.

Tournaments

The TAs will organize a Kalah tournament and an Othello tournament. This is mostly just for fun, but the winners will be recognized and there will be some small extra credit for participating.
The tournament requires having your program calculate moves in a certain amount of time, as described below. This functionality is only necessary if you want to participate in the tournament.

The tournament will be held after the due date, and participants will be assigned an opponent and a deadline by which the game must be completed; you will have to meet, play the game, and report the results to Deepak.

The order of turns can be decided in a couple of ways:
1) The issue of who goes first in each game can be decided by a coin-toss; your program should be able to play with either ordering.
2) You can play 2 games, changing who goes first, and determine the victor based the total number of stones acquired, if each player wins one game.
The choice is between you and your opponent; come to a decision before the game starts to keep things fair.

Rules

Time: In order to compensate for people using different machines to run their program, we will define move length in terms of processor speed. Each player gets 30 /(speed in GHz) seconds to move. If you wrote a multithreaded implementation, and are running on a multi processor machine, you must multiply the number of processors by the speed. For example, on a 1 GHz machine, you will get 30 seconds. So you should have some means to enter in the computer's speed and have the program return an answer in the allotted time.

Memory/Disk Space: Go to town. There are no limits other than you may not use another machine's CPU (no servers). Network disk access is OK, however, if the network goes down, you will have to forfeit the game; using the network is not recommended.