CSE 473 Fall 2005: Game Playing

Code Due: Wed November 23, before class; email to Tyler

Report Due: Wed November 23, in class

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.

Please send email to Tyler as to your choice of game and whether you wish to participate in a tournament by November 9.

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

• Please turn in your report in class on November 23.
• Please turn in your program/data/output electronically to Tyler at trobison@cs.washington.edu. Use a subject like 'CSE473 hw5 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.

Tournaments

Rules

Tournament links