Programming Assignment 3

Shortest Games

Data Structures and Algorithms, Spring 2011

Due Date

This assignment is due by 11:30 p.m. on Wednesday, 13 April.

See the assignment turn-in page (last modified on 2010 February 23) for instructions on turning in your assignment.

The absolute deadline for turning-in Assignment 3 is Saturday, 16 April at 11:30 p.m. It is not possible to turn-in Assignment 3 after the absolute deadline.

Background

A game, such as tic-tac-toe or go, consists of a board representing the state of a game, and a set of moves which transforms one board to the next. A game tree is a tree in which each node represents a board in a game. The children of a node n represent the result of all possible legal moves made from the board at n. The root node represents the game's initial board.

The Problem

Write the method shortestGame() that accepts a game and returns a shortest sequence of boards that leads to a winning game starting from the initial board.

shortestGame() is defined in the interface

/export/home/class/cs-503/pa3/GameAnalysis.java

The Game interface used in shortestGame does not need an implementation. The Game interface has already been implemented, and is part of the jar file.

Implementing

Once you’ve got your implementation far enough along, you can try it out using the jar file
/export/home/class/cs-503/pa3/pa3.jar
by typing 

$ java -classpath jar-path/pa3.jar:. main class-name

where jar-path is the path to pa3.jar and class-name is the name of the class implementing the GameAnalysis interface. For example, if the class QuickestGame implements GameAnalysis and you’re using pa3.jar in the public class directory, you would type 

$ java -classpath /export/home/class/cs-503/pa3/pa3.jar:. main QuickestGame

This page last modified on 2010 November 27.