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.
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.