CSE 150 Programming Assignment #3

Date assigned: May 12, 2007

Date due: 11:59:59 May 24, 2007

 

In this programming assignment, you will be asked to construct a program to play Checkers.

 

Logistics:

You can work alone or in groups of at most 3. Code must be submitted (with comments) by the due date. Use of Java for this assignment is required. A copy of your write up as a pdf should be included. Turn in the code using the turnin script.

 

Hard copies of write-ups are due at the beginning of class the following class, printed and stapled. Code should be included in the printout. Write-ups should include a brief description of the approach taken, answers to any questions posed, and sample output on some examples. See below for more details on the content of the write up.

 

Half of the points are based on the quality of the write-up, testing, and code. The other half are based on the performance of your code on a test set of problems and against other student’s submissions. Bonus points may be awarded at the TA's discretion for going above and beyond the HW's description.

 

Points will be deducted for not following these instructions. Note that no late programming assignments will be accepted!

 

Code:

In order to allow programs to compete against each other, we are providing some common code to manage game play. Essentially, your program will be given a board state and must return the move your program decides to take. Code is available here. Javadoc documentation is available here. Supplied code is currently beta. If updates occur, a notification will go out on the discussion board. If you find a bug, please report it to the TA.

 

Our Game class handles the generation of possible moves, and keeps track of the depth and number of expansions. For various parts of the assignment, you will either be limited by depth or by the number of total board states you’ve expanded. Some attempt has been made to enforce the required interface, but it may be possible to circumvent this; ANY CODE THAT BYPASSES THE REQUIRED INTERFACE WILL BE HEAVILY PENALIZED. If you have a question whether something is legal, ask.

 

Board: This class contains the basic state information, namely:

  1. The current board. This is an 8x8 integer array such with:
    1. 0 denoting an empty space
    2. 1 denoting one of player 1’s pieces
    3. 2 denoting one of player 1’s kings
    4. –1 denoting one of player 2’s pieces
    5. –2 denoting one of player 2’s kings
  2. The number of moves played
  3. Whose turn it is
  4. Methods to check for a winner

It also contains some additional functionality for move primitives, which you are not to use.

 

Solver: An interface that your classes must implement. It requires you to implement a method chooseMove.

 

Player: Sample code for game play. You’ll need to modify this (or create your own) to test your code.

 

RandomPlayer: A sample Solver that chooses moves at random. Used as a template, and to give you something to compare your methods against.

 

BoardManipulator: This class manipulates a Board to generate the possible successor states. It is used extensively by the Game class, but is NOT to be used directly by your program.

 

Game: This manages the game and the search functionality, providing all necessary functions and information not provided by the Board class. Namely:

  1. It will return the current board state
  2. It will expand the current board state
  3. It will return the number of possible moves
  4. It will expand any other Board state, up to the limits set. This is static and can be done from anywhere using: Game.expand(Board b). If a limit has been exceeded, will return null.
  5. It will execute a move. Your program will not actually do this, merely return the action you decide to take. Some wrapper function for testing will actually be executing the move (see Player). The function is provided to make your testing possible.
  6. It has methods to check for a winner.

 

Expansion returns a Vector of Boards. Since moves can be of near arbitrary length (for multiple jumps), actions themselves are simply an index into this Vector.

 

Essentially your program receives a Board and must return an integer representing an action which is an index into the Vector of Board states. Each solver you construct must implement the Solver interface and have a constructor taking no arguments.

 

Project specifics

  1. Write a Node class with whatever information you require.

 

  1. Write an evaluation function. As a simple first pass, you may want to simply sum up the board to provide a value for p1. Since p1’s pieces and kings are denoted 1 and 2, and p2’s pieces and kings are denoted –1 and –2, this will provide a coarse measure of who is ahead. For part 5, you may want to improve this method.

 

  1. Write a class MinimaxSolver which implements the Solver interface. Have it execute the Minimax algorithm. See how deeply you can reasonably search (say 1 second/move). You should have your program play against itself, but you may also want to add some functionality to allow a person to play it.

 

  1. Now write a class AlphaBetaSolver which implements the Solver interface to do Alpha-Beta pruning. Now see how deeply you can reasonably search (say 1 second/move).

 

  1. Now write your competitive Solver. We’re still ironing out the logistics of the best way to have programs compete, but for now name it based on some team/person specific name. It also must implement the Solver interface. Here you should do whatever it takes to improve your algorithm. But stay within the rules! Namely, you must not violate the interface provided or recreate the functionality of the existing code (i.e.  you can’t write your own successor function). We’re looking for clever evaluators and search techniques, not ways to game the system. Again, if you have a question about whether something is legal, ask. Also, make sure your method is reasonably quick – if you’re holding up the competition, you may end up being disqualified. More guidelines on what “reasonably quick” means will be forthcoming, but it shouldn’t take more than a second with reasonable limits. Be sure to describe what you did in your report.

 

 

You must do SOMETHING that makes your best algorithm do better than vanilla alpha-beta pruning with the sum-of-board evaluation. Beam search may be a good place to start, given the lack of limits on the number of evaluations.

 

 

The competitive solvers will compete against each other. This will be run in “look-limited” mode, where you can only expand up to a set number of game states each move. The exact limit will not necessarily be announced ahead of time, but will be at least 500 nodes. In addition to the points awarded to the winner, there may be an additional prize.

 

Write up:

Please describe the approach taken and how your program should be executed. What kind of testing did you do, and how did your methods fare? How deeply could you search? Qualitatively, how well does your program seem to play?

 

You should include a graph of the average time per move as a function of max depth for your three methods.

 

As described in the last assignment, the following is a good outline. Please use it.

 

1. Files submitted (with brief description of each)

2. How to run (including unpacking, compiling)

3. Approach (describe algorithm(s)), problems encountered, hurdles overcome)

4. Known bugs (hopefully empty! But better to report than for me to find.)

5. Extra credit (can be empty - just because it's here doesn't mean you'll get points, but won't get points if not listed)

6. Sample output (since you’re only returning a number, this should be output from your testing)

7. Testing (convince me (and yourself) it works! Be thorough.)

8. Answers to questions

9. Summary

 

 

Testing:

Most testing will be running your code against itself (or against a different algorithm). Be sure to show that your “best” algorithm can outperform vanilla alpha-beta pruning most of the time. You may want to introduce an interface so that you can play against it.

 

Grading:

As described, half your points will be based on the report you turn in and half on evaluation. Minimax, alpha-beta pruning, and an improved version are all worth ten points of evaluation, while the remaining 20 points will be based on how your improved version does in the competition.