Computer Science 136 Data Structures and Advanced Programming Williams College Fall 2005

Short Answers

Complete the following problems from the book and turn them in as a text file lab8.txt at the start of lab.

Lab Program

This week's lab uses trees to play Hex-a-Pawn, a small chess-like game. You will build a tree representing all possible states that the game board can be in. You will then implement several different players that consult this tree to make moves as they play Hex-a-Pawn. The players include: a human player that asks the user for moves to make; a random player that picks possible moves at random; and a computer player that improves its strategy by learning from past mistakes. In the end, you will be able to run the different players against each other. The lab is outlined in Section 11.11 of Bailey.

• Before lab, copy the starter files from the cs136 shared area under labs/hexapawn on the Macs or FreeBSD systems. You should find HexBoard.java, HexMove.java, and Player.java. Familiarize yourself with these classes.
• A significant part of your task is to design and implement the GameTree class. This is a tree structure with potentially many children instead of just two. Think about the methods you will need in this class and how you can represent the structure. Bring a handwritten sketch of GameTree to lab so we can check on them before you get too far along.
• You can play a game of Hex-a-Pawn by running java HexBoard after compiling the starter files.
• To use your three Player classes as described in the book, implement the Hex-a-Pawn game as the main method of a class HexaPawn.java. This program should take four parameters. The first two specify the number of rows and columns the board should have. The third and fourth should be "human", "comp", or "random" to indicate what type of player should be used for the white and pieces, respectively.
• Gardner's original paper describing this game is under labs/hexapawn in the CS136 common area on cortland and the FreeBSD systems. Take a look, if you're interested. Notice the ad for a "comparator" on the third page.

Submission

When you're finished, create and submit a tar file lab8.tar that includes the following:

• Your well-documented source code for all Java files that you write. You do not need to submit source code for starter files, as you should not need to modify them.
• A README file that contains your answers to thought questions 1 and 2.

  For thought question 1, you should be able to generate trees for boards of size 3 ×4 and 4 ×3 quite easily. For 4 ×4 and 3 ×5, you will need to tell Java to allow your program to allocate more memory than it normally would be allowed to allocate.

  To do this, add the options -Xms1500m -Xmx1500m after the command java and before the name of your class when you run the program.