Project 1 CSE 473 Fall 2009: Game Playing

Preliminary Details

Due: Friday November 13 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. The game is Kalah with the following rules:

• Each player has 6 holes and a Kalah as shown in the lecture slides.
• A turn consists of selecting one of your own holes, picking up all the stones, and distributing them in each consecutive hole, including your Kalah but not the opponent's Kalah, in counterclockwise direction.
• If your last stone lands in your own Kalah, you get an extra turn.
• If your last stone lands in your own empty hole, you take all the stones in the opponent's opposite hole and put them in your Kalah.
• If you run out of stones on your side, the opponent takes all the stones left on his side and puts them in his Kalah.

Requirements

• You will work in teams of 2-3 people, but those needing to work alone may do so.
• 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 be added for extra credit points. The program must 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. We will give you a simple interface and a skeleton of the control flow to plug in your own classes and methods.
• 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.
• You may program in Java or C++. Here is a Java skeleton and here is a C++ skeleton. 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 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 Lynn.

Since there is an advantage to going first, you will play 2 games, changing who goes first, and determine the victor based the total number of stones acquired, if each player wins one game.

Rules