CS 302: Introduction to Programming

Program 3, Spring 2013: Fox & Geese

P3 Announcements

Corrections, clarifications, and other announcements regarding this programming assignment will be found below.

Friday, March 22nd, 2013: Created an OFFLINE snapshot of P3 and Javadoc files, p3_offline.zip. After downloading and extracting the archived file, open the p3_offline.html file in your web browser. Be sure to check the online version as soon as possible and use that site when internet is available as the "offline" version will not be updated.
Monday, March 18th, 2013: Program 3 released. Create and join teams using Forms page before beginning to work together. Teams must be created and joined before 10pm on Friday, April 12th, 2013.

Make sure to check Piazza for other clarifications and hints.

Overview:

Assignment Goals:

Learn how classes organize code.
Learn how to instantiate classes and use objects.
Access members of another class.
Understand the difference between class (static or shared) members and instance (or non-static) members.
Implement a program that uses multiple classes.

There are many simple games that can be played on a checkers board. In this assignment, you will implement a common game known as Fox and Geese (or Fox and Hounds).

Game Rules:

The game is played by two players on a standard red-and-black checkerboard with 8 rows and 8 columns. One player controls a single piece (called the "fox"), and the other player controls four pieces (called "geese"). The game always begins with the fox on the top row and the geese on the bottom, as shown in the figure. The fox is the orange piece, and the geese are white.

The players alternate turns, and during each turn a player may move one of his pieces to an unoccupied, diagonally adjacent square. Pieces may only move to the black squares on the board; the red squares are never occupied. The fox may move in any direction: northeast (NE), northwest (NW), southeast (SE), or southwest (SW). The geese may only move upward; that is, they may only move northeast (NE) or northwest (NW).

This means that eventually the geese will have no more moves, since they can never backtrack. There is no jumping or capturing of pieces in this game. A piece may not move onto a square occupied by another piece.

The game is over once any of the following conditions becomes true:

The fox reaches the bottom edge of the board. In this case, the fox wins.
The geese have no legal moves left. In this case, the fox wins.
The fox has no legal moves left. In this case, the geese win. This case is shown in the figure.

In summary, the fox's goal is to break through the line of geese to reach the bottom of the board. The geese's goal is to trap the fox before this happens. The geese can trap the fox more easily against the edges of the board, since the fox has less freedom to maneuver there.

Getting Started:

To begin, you must download the skeleton code files and add them to your Eclipse project. To do this, create an Eclipse project as you have done in lab (we suggest you call this project "P3"). Download the following ZIP file and extract its contents (a bunch of .java files) into your Eclipse project folder.

`skeleton.zip`

Javadoc:

Next, check out the Javadoc pages which describe the skeleton code files you just downloaded:

Javadoc Pages

Your Task:

You are responsible for filling in the following classes in the skeleton. Make sure to read the descriptions in the comments carefully.

You must implement the methods EXACTLY as they appear in the Javadoc and program skeleton. By this we mean:

Do not change method names.

Do not add or remove parameters.

Do not change method return types.

Do not add additional public methods.

Implement all public methods and constructors in the skeleton.

Do not create public fields.

You may add additional private methods and fields as you feel are appropriate to complete the assignment.

Of course, you will need to change each method's body so that it works as described in the Javadoc and program skeleton. When grading, we will be testing the required methods individually to verify that they work as described.

Provided Main Classes

The skeleton you downloaded contains two pre-fabricated main classes for you to use when testing your program. The first (FoxAndGeese) will call your Game constructor to create and run a game with humans controlling both sides. The second (FoxAndGeeseAi) will call your Game constructor to create and run a game with a human controlling the fox and an AI controlling the geese. If you code your classes correctly, running either of these main classes will display the GameWindow in the starting game configuration. It will then permit the user to move their pieces in the proper turn order. If the game is being run with a goose AI, the user should not be allowed to select or move any goose pieces; these pieces should move automatically after each fox move is made. Once either your Game.hasFoxLost method or your Game.haveGeeseLost method return true, the GameWindow should display the game results. It will do this automatically as long as you make sure to call GameWindow.gameUpdated whenever the state of your Game has changed.

Note. You should not have to edit either of FoxAndGeese.java or FoxAndGeeseAi.java in order to make your program work. You will not be submitting these classes, so make sure your code (specifically your Game class and its constructors) works properly with these classes as provided. That being said, you are free to edit the two main classes we have given you to try out different configurations (especially different AIs).

Using the `GameWindow` Class

You will use the GameWindow class, which we have provided in its entirety, to display your game to the user as a Graphical User Interface (GUI). To display the GUI, create a GameWindow object and call its GameWindow.show method. To display your game's state on the window, call its GameWindow.gameUpdated method, passing the Game object to be displayed. In addition to displaying the state of a game to the user, the GameWindow can also receive user input in the form of clicks. Any time the user clicks on a square on the displayed board, the GameWindow object will call the Game.handleBoardClick on the Game being displayed. You will have to add code to the handleBoardClick method to properly respond to user clicks.

When the user first clicks on a square containing a game piece (fox or goose), your code should set the clicked piece to be "selected," so that calling Game.getSelectedPiece on your Game object will return that piece which was clicked. Only one piece can be selected at a time, and your Game object should make sure that a piece is selected only if that piece's side (fox or geese) has the current turn. Once you implement getSelectedPiece properly, the GameWindow will highlight the current selected piece (and all of its legal moves, as determined by your GamePiece.getLegalMoves method) with a blue outline. The way the user should be able to move a piece is by first clicking it to make it the selected piece and then by clicking a nearby square for the piece to move to. If the square that was clicked constitutes a legal move for the currently selected piece, then the piece should move and the turn should pass to the other player.

If the user clicks a piece controlled by the current player (i.e. if they click a fox while it is the fox's turn, or a goose while it is the geese's turn), that piece should become the selected piece. In particular, if a user clicks on an already selected piece, that piece should remain selected. If the user clicks on a square that does not contain a piece and is not a legal move for the currently selected piece (if there is a currently selected piece), then your code should deselect all pieces. When no piece is selected, your Game.getSelectedPiece method should return null.

Using the `Ai` Classes

One requirement for this assignment is that you code Game to be able to either pit one human against another human or to pit a human fox player against an AI-controlled goose player. We have provided three implementations of a goose AI of varying skill levels:

RandomGooseAi - Makes moves randomly. It's hard not to beat this AI.
ProgressiveGooseAi - Tries to move geese forward gradually, maintaining a mostly unbroken line as it advances. Easy to beat, but you at least have to know what you're doing.
CrazyGoodGooseAi - Provably unbeatable.

You should use the provided main class FoxAndGeeseAi to run your code with an AI to move the goose pieces. When your code is run in this way, the human player should not be allowed to move the goose pieces at all. Instead, whenever it is the geese's turn, you should call the Ai object's Ai.makeNextMove method. This will cause one of the goose pieces to be moved. The turn should then pass immediately back to the human player so that they can move the fox piece again. Note: since the geese always get the first move, the goose AI will always make a move before the human player is even presented with the GUI to make their move. Thus, it might look to the player like the geese didn't start in the correct starting positions, but this is not a problem.

You should make sure that these AIs work reasonably with your code. Specifically, you should make sure none of them crash when you try to play against them. If the AI crashes, that means you made a mistake in one of your classes.

Other Requirements

Once your program has detected an end-of-game condition, it should not allow the user to move pieces on the board. The only thing the user can do at this point is to close the window, causing the program to exit.

Development Milestones:

We suggest that you incrementally develop this program by following the milestones in the order listed below. This order will make it easy for you to check that each milestone is working properly before you move on to the next one. Don't move on to a new milestone until you can convince yourself that the current milestone is working correctly. The further along you get, the harder it will be to detect errors in code you developed early on. The percentages listed in ( )'s indicate what you'll earn in the "correctness of execution" portion of your grade (total of 75%) by correctly completing each milestone.

Note. In order to get any milestone working, you may have to edit classes not mentioned in the milestone description. For instance, you probably can't make a working Board class without implementing some parts of the Position class.

Hint. In addition to simply filling in the required methods, you will also need to add private fields to some classes, in order to store the state specific to instances of that class. Think carefully about what data should be stored in each class.

Milestone 1 (5%) - Show a GameWindow. Start by familiarizing yourself with the publicmethods of the GameWindow class. Then add enough code to Game (and any other classes as necessary) so that running either of the provided main classes displays a GameWindow containing an empty 8-by-8 checkerboard.

Milestone 2 (15%) - Initial Board. Fill in enough of the Board class (and any other classes as necessary) so that your GameWindow shows the foxes and geese in their correct starting positions when you start the program (again, using either of the provided main classes). Note that you will have to fill in the Game. getBoard method.

Milestone 3 (20%) - Piece Selection. Start implementing the Game.handleBoardClick method so that the user can click pieces and select them. Implement GamePiece.getLegalMoves so that each piece's legal moves are displayed when it is selected.

Milestone 4 (15%) - Moving and Turn Order. The geese should get the first turn when the game starts up. Revise your Game.handleBoardClick implementation so that if a piece is selected and one of its legal move destinations is clicked, the piece moves there and the turn passes to the other player. Don't worry about supporting AI players yet; just test with the FoxAndGeese main class.

Milestone 5 (10%) - Game End. Code the Game.haveGeeseLost and Game.hasFoxLost methods to detect the various game-ending conditions. Once you have done this, playing a game to completion should cause the GameWindow to display which side won. Make sure that, once this happens, the game does not allow the user to continue to move pieces on the board.

Milestone 6 (10%) - Goose AI Support. Implement the Game(Ai) constructor, which takes in an Ai object to make moves for the geese. When the Game is created with this constructor, the user should not be allowed to move the goose pieces at all. Instead, each time it is the geese's turn, the Ai should be invoked to move a goose piece.

Testing

You should test your program by running it frequently as you develop. It is a worthy goal to always have a compiling program so that you can run it and see what it does. If you follow the milestones outlined above, you should be able to verify whether you have completed each milestone by running your program and interacting with it.

When you think your program is ready, you should make sure to test your program with no goose AI (i.e. both sides controlled by the user) as well as with the 3 goose AI implementations we provide. If your program crashes in any of these cases, you have a problem and need to fix it.

Extra Credit (1%):

For the normal assignment, we provided several AI implementations for moving the goose pieces. In the extra credit part of the assignment, you will implement another AI for moving the fox piece. Begin by downloading the following additional skeleton code and adding it to your Eclipse project:

`skeleton-ec.zip`

This skeleton-ec.zip file contains the following classes:

RandomFoxAi - An example fox AI that moves the fox randomly around the board.
FoxAiEC - A skeleton class for you to fill in with your own fox AI implementation.
FoxAndGeeseEC - Another main class that can be used to match two AIs (one for the fox and one for the geese) against each other.

Once you have added these files to your Eclipse project, you will probably find that the FoxAndGeeseEC class doesn't compile; it tries to construct a GameEC instance, passing two Ai objects as arguments to the constructor. To make your project compile again, copy your existing Game class and name the new copy of it "GameEC". Add a new constructor to the GameEC class with the following constructor header:

public GameEC(Ai gooseAi, Ai foxAi) { ...

Then fill in the constructor (and make any other required additions to your GameEC class) to support the creation of GameECs where both sides are played by AIs. Note: You should make sure your other GameEC constructors still work too, allowing GameECs to be created where the user controls the fox or both the fox and the geese.

When you run a game with two AI players, you won't be able to see any of the intermediate steps of the game--the game will be over before your GUI window even has a chance to be displayed. That is OK. You will at least see the ending positions of all the pieces, as well as an indicator of which side won.

Once you run several games with two AI players (one ProgressiveGooseAi and one RandomFoxAi), you should notice that the fox loses a little more than half the time. This makes sense, since the fox AI player is moving randomly and not even focusing on reaching the bottom of the board. To receive full EC credit, you will need to implement your own fox AI that can beat the ProgressiveGooseAi in 9 out of 10 games. You should do this by filling in the FoxAiEC skeleton we have provided. You may use the various AI classes we have provided as a reference. To test your AI implementation, replace "new RandomFoxAi()" with "new FoxAiEC()" in FoxAndGeeseEC.java. This part of the EC assignment is your chance to be creative. Think about the kinds of moves a fox should try to make in order to achieve its goals. Don't make your AI overly complicated; it doesn't take much to improve on a random fox AI (and even the random fox AI was able to beat the ProgressiveGooseAi in a significant fraction of games!).

Important Note: Make sure your AI class can handle any legal board configuration. In other words, you may assume that the Board which gets passed to your AI's makeNextMoveImpl method has one fox and four geese and that the foxes and geese only occupy black squares on the board, but do not assume anything else about their positions or the number of legal moves available to any particular piece.

Submission:

Before handing in your program, check that you've done the following:

Did you verify that your program works correctly by following the information in the Testing section above? About 75% of your grade is based on your program working correctly and handling errors as described.
Did you turn in all necessary source files listed below? About 5% of your grade is based on submitting ALL source code files correctly.
Did you use good programming style by following the CS302 Style Guide? About 15% of your grade is based on good programming style.
Did you properly comment your program by following the CS302 Commenting Guide? About 5% of your grade is based on proper commenting. Note, we've provided most of your method header comments. But, it is still the students responsibility to ensure that they are complete and correct.
Are your program's source files named exactly as provided by the skeleton? Deductions will be made if you renamed any classes or changed any public methods headers from the skeleton.

Use the CS302 Forms Page to electronically submit and backup your work:

You may submit the files listed below as often as you wish at any time before the due date and time.
Previously submitted files are overwritten when you re-submit your work.
We suggest you use your handin directory to keep a backup of your most recent working copy as you develop your solution. Use the "List Files" form to download the files in your handin directory as a backup. They are downloaded as a zip file that you'll need to unzip to extract your files.
You can verify that you've submitted things correctly. Please do not ask your instructor to check for you. Use the "List Files" form to list and download what you've submitted to verify that the files with the desired contents are your handin directory.

Submit these files:

Board.java
Game.java
GamePiece.java
Position.java

You are not submitting any of the other files that were provided to you in the skeleton. You should not have edited any other files, and if you did, you should make sure your code still works with those files as they were provided to you.

If you did Extra Credit, submit these files in addition to the other files you submit:

FoxAiEC.java
GameEC.java

Make sure you did not put any EC-specific code into any other files. These two files, along with the non-EC files submitted earlier, should be enough for us to run your entire EC submission.

Menu