CSE 415 Winter 2006: Assignment 3

CSE 415 Winter 2006: Game Playing

Code Due: Friday March 3rd, before class; email to Tyler at trobison@cs.washington.edu

Report Due: Friday March 3rd, in class

The tournament participation decision must be sent to Tyler by Feb. 24th

The purpose of this assignment is to try out the game playing techniques we have studied as well as adding your own ideas. You will be designing an agent to play the board game Kalah ( instructions here).

In addition to the assignment itself, you have the option of entering your agent in a tournament, set to take place after the submission date. The tournament is optional, but it will be a good chance to show off your agent, and participants will receive some extra credit, whether they win or not. If you are interested in the tournament, please email Tyler with your decision by Feb. 24th.

Requirements

You must use the 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; trying various heuristics, for instance. Your experimentation, and what you conclude from it, should be included in your report.
Your program should be interactive, so that you or others can play against it. Fancy interfaces are not required, though the program should at least 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.
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 alternative heuristic(s) you experimented with, and how well they worked.
- The details of your program design with justification.

Turn-in

Please turn in your report in class on March 3rd.
Please turn in your program/data/output electronically to Tyler at trobison@cs.washington.edu. Use a subject like 'CSE415 hw3 submission'.
Include all files needed to compile your program. Also include any additional data (files) you tested your program on. Please zip or tar them together.
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.

The Tournament

Click here to view the tournament ladder

Tyler will organize a Kalah tournament after the submission date, and participation is voluntary. This is mostly just for fun, but the winners will be recognized and there will be some 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 work as follows: Tyler will pair participants off and email them their opponent's email address. The players will be given around 2 days to meet, play their match, and report the outcome. Then, the winners will be paired off and the process will continue.

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. There are a few ways to implement a timing restriction, and it will vary based on the language used; email Tyler about this if you have any questions. Note: timing controls are only required if you want to enter the tournament.

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.