Project 2: Jump61B

Intro Video to Board.java

Intro Video to AI.java

Jump Testing Tips Part 1, Part 2, Slides

Play the game here!

(10/25 12am) We have made an update to the Project 2 autograder to ensure that your AI meets the requirements detailed in the spec. See @833 on Piazza for more info. (10/20 12pm) Despite what the comments in the AI.java file may indicate, this portion of the project is NOT optional. You are required to implement an AI in order to get a full score on this project. There is nothing to fetch/merge for this update,

## Background

The KJumpingCube game1 is a two-person board game. It is a pure strategy game, involving no element of chance. For this third project, you are to implement our version of this game, which we'll call jump61b, allowing a user to play against a computer or against another person, or to allow the computer to play itself. The tested interface is textual, but for extra credit, you can produce a GUI interface for the game.

## Rules of Jump61

The game board consists of an $N\times N$ array of squares, where $N>1$. At any time, each square may have one of three colors: red, blue, or white (neutral), and some number of spots (as on dice). Initially, all squares are white and have one spot.

For purposes of naming squares in this description, we'll use the following notation: $r:c$ refers to the square at row $r$ and column $c$, where $1 \le r,c\le N$. Rows are numbered from top to bottom (top row is row 1) and columns are numbered from the left. When entering commands, we replace the colon with a space (this being easier to type).

The neighbors of a square are the horizontally and vertically adjacent squares (diagonally adjacent squares are not neighbors). We say that a square is overfull if it contains more spots than it has neighbors. Thus, the four corner squares are overfull when they have more than two spots; other squares on the edge are overfull with more than three spots; and all others are overfull with more than four spots.

There are two players, whom we'll call Red and Blue. The players each move in turn, with Red going first. A move consists of adding one spot on any square that does not have the opponent's color (so Red may add a spot to either a red or white square). A spot placed on any square colors that square with the player's color.

Figure 1. Example of two moves. The board on the top is the starting position, and the board on the bottom is after red and blue have each made a move.

After the player has moved, we repeat the following steps until no square is overfull or either all squares are red or all blue:

• Pick an overfull square.
• For each neighbor of the overfull square, move one spot out of the square and into the neighbor (even if occupied by the opposing side).
• Give each of these neighboring squares the player's color (if they don't have it already).

The order in which this happens, as it turns out, does not usually matter—that is, the end result will be the same regardless of which overfull square's spots are removed first, with the exception that the winning position might differ. A player wins when all squares are the player's color.

For example, given the board on the top ($N=4$) in Figure 2, if Red adds a spot to square 2:1, we get the board on the bottom after all the spots stop jumping.

Figure 2. Example of one jump creating another overfull cell. Square 2:2 becomes overfull after we add a spot to square 2:1 and perform the first jump, so we must jump again for square 2:2.

The rules hold that the game is over as soon as one player's color covers the board. This is a slightly subtle point: it is easy to set up situations where the procedure given above for dealing with overfull squares loops infinitely, swapping spots around in an endless cycle, unless one is careful to stop as soon as a winning position appears. It is acceptable, in fact, for you to report winning positions in which the redistribution procedure described above is prematurely terminated, so that some squares remain overfull.

For example, if, on Red's move, the board is as on the top of Figure 3 and Red moves to 3:1, then the board will turn entirely red. You are allowed to stop the process of redistributing spots when all squares are red, even though, depending on the order in which you do things, you could end up with the board on the bottom in the figure.

Figure 3. The board on the top shows a position just before Red's last move (to 3:1). The board on the bottom is one possible stopping point for spot redistribution (all squares now being one color), even though the squares at 1:3 and 4:1 are still overfull.

The shared repository will contain skeleton files for this project, which you can merge into your repository as usual with

git fetch shared
git merge shared/proj2

Be sure to include tests of your program (that is part of the grade). The makefile we provide has a convenient target for running such tests. Our skeleton directory contains a couple of tests, but these do not constitute an adequate set of tests! To help with testing and debugging, we will provide our own version of the program, so that you can test your program against ours.

You will be completing the implementation of this game through Board.java, which represents the game board and the state of the game. Additionally, you will be completing an AI. Your AI must reliably find a win from any position in which a forced win is four or fewer moves away, for any board no larger than six squares on a side. Likewise, it should be able to put off defeat for at least four moves (again on boards up to six squares on a side) if there is not a forced win for the other side in that many moves. Simply moving at random won't satisfy these requirements. Your AI program will have limited time to move. Don't expect to get more than an average of roughly 15 seconds per move on the instructional servers.

You may add commands and other features to your program, as long as it otherwise meets this specification. If you do, be sure to update the output of the help command or of usage messages accordingly.

## Textual Input Language

Your program should respond to the following textual commands (you may add others). There is one command per line, but otherwise, whitespace may precede and follow command names and operands freely. Empty lines have no effect, and a command line whose first non-blank character is # is ignored as a comment. Extra arguments to a command (beyond those specified below) are ignored. An end-of-file indication on the command input should have the same effect as the quit command.

• new
Abandons the current game (if one is in progress), and clears the board to its initial configuration (all squares neutral with one spot, Red's move).
• quit
Exits the program.
• auto $P$
Causes player $P$ to be played by an automated player (an AI) henceforth. The value $P$ must be red (or r), or blue (or b). Ignore case—Red, RED, or R) also work. Initially, Blue is an automated player.
• manual $P$
Causes player $P$ to take moves entered by the user. The value of $P$ is as for the auto command. Initially, Red is a manual player.
• size $N$
Clears the board to its initial configuration, but with the size of the board at $N$ squares, where $2 \le N \le 10$. Initially, $N=6$.
• set $R$ $C$ $N$ $P$
This command is intended for setting up positions for testing and debugging. Put $N$ spots at row $R$ and column $C$. $P$ denotes the player, as for the auto command. $N$ must be positive and less than or equal to the number of neighboring squares. The player who is next to move is determined by the total number of spots on the board. Because Red always moves first, the player to move is chosen based on if the number of added spots is odd or even.

Edit 10/13 You do not need to deal with the case where $N == 0$

• dump
This command is especially for testing and debugging. It prints the board out in exactly the following format:

===
2r 1- 2r 2r 1- 2b
1- 1- 2r 1- 3r 1-
2r 3r 2r 3r 1- 2b
3r 1r 3r 2r 2r 2b
2b 4r 3r 1r 3r 2b
2b 2b 3b 2r 3b 1b
===

with the === markers at the left margin and other lines indented four spaces. Here, 1- indicates a neutral square (necessarily with one spot), $N$r indicates a red square with $N$ spots, and $N$b indicates a blue square with $N$ spots. Don't use the two === markers anywhere else in your output. This gives the autograder a way to determine the state of your game board at any point. It does not change any of the state of the program.

• seed $N$
If your program's automated players use pseudo-random numbers to choose moves, this command sets the random seed to $N$ (a long integer). This command has no effect if there is no random component to your automated players (or if you don't use them in a particular game). It doesn't matter exactly how you use $N$ as long as your automated player behaves identically each time it is seeded with $N$. In the absence of a seed command, do what you want to seed your generator.
• help
Print a brief summary of the commands.

## Entering Moves

To enter moves from the terminal (for a manual player), use a command of the form

• $R$ $C$
Adds a spot to the square at row $R$, column $C$, where $R$ and $C$ are integers in the range 1 to the current board size. Rows are numbered from the top, columns from the left. After the spot is added, spots are redistributed as indicated in the rules above. Like other commands, $R$ and $C$ may be surrounded by any amount of whitespace. Illegal moves must be rejected (they have no effect on the board; the program should tell the user that there is an error and request another move).

The first and then every other move is for the red player, the second and then every other is for blue, and the normal legality rules apply to all moves.

## Output

When either player enters a winning move, the program should print a line saying either of

 * Red wins.
* Blue wins.

(with asterisks and periods as shown) as appropriate. Use exactly those phrases.

When an AI plays, print out the moves that it makes using the same format as

 * 1 4

That is, an asterisk followed by the row and column of a move. Again, use exactly this format. Do not print this message for manual moves.

These outputs should each go on a separate line. Do not use * anywhere else in your output.

Finally, as indicated in the section on commands, the dump command must print out in exactly the format shown.

Otherwise, you are free to prompt for input however you want, and to print out whatever user-friendly output you wish (other than debugging output or Java exception tracebacks, that is). For example, you might want to print the game board out after each move is complete (this is distinct from printing the board in the special format required by dump).

When users enter erroneous input, you should print an error message, and the input should have no effect (and in particular, the user should be able to continue entering commands after an error). Make sure that any of this extra output you generate is distinct from the outputs that are required (otherwise, the testing software will flag your program as erroneous.) Regardless of whether users have made errors during a session, your program should always exit with code 0.

## Testing

Also see the Jump Testing Tips videos ( Part 1 , Part 2 , Slides)

As in previous assignments, the command make will compile your program and make check will run all your tests (both unit and integration tests). You can use the command make style to ensure your code meets the guidelines of our style guide. The command java jump61.Main must run your program. When testing your program, we will use the command

 java -ea jump61.Main 

to run it (the -ea insures that all assertions in your program are checked.)

You can find some individual unit tests in the BoardTest.java class. Remember, passing these tests do not ensure your project is correct. You should write more unit tests to assist with debugging and ensure correctness. Additionally, if you add another unit testing file (say, for the AI portion of the project), you can add the name of that file in UnitTest.java. When UnitTest.java is run, it will then run the tests in your new unit testing file in addition to the tests in BoardTest.java. See Project 1 for an example of this.

We will evaluate your project in part on the thoroughness of your testing. Our autograder script will run UnitTest in the JUnit framework, expecting it to pass.

For integration testing, make check will use a program we've provided (test-jump61), which you can find in the proj2/testing directory. This program allows you to run your program, supply it with input, and check the result, or to run two programs, and play them against each other (taking output like* 1 1 from one program and feeding its move to the other.) See the comments at the beginning of test-jump61 and the sample files in the skeleton testing directory for information on how to write your own tests.

Important: If you normally use "python" or "py" to run python commands instead of "python3", running make check on its own won't work. Instead, you should run make PYTHON=py check or make PYTHON=python check, depending on which executable you normally use.

Integration tests used in make check are stored under the proj2/testing folder. If you would like to run an integration test in IntelliJ so that you can use the debugger, use the following steps:

1. Navigate to the Main class in IntelliJ and open it.
2. Click on Run > Edit Configurations...
3. In the left sidebar of the pop-up window, under "Application", select Main.
4. For "Program arguments", put in --log testing/<test_file> where <test_file> is the name of the file of the integration test you would like to run.

For example, if you would like to run integration test 00-err-1.in, you should have testing/00-err-1.in as your program arguments. Now you can click Run > Run 'Main' or Run > Debug 'Main' to run and use the debugger on the integration tests. Remember to set a breakpoint if you're debugging!

## Checkpoint

There will be a required checkpoint due 10/25 at 11:59 PM PT. You can submit to the checkpoint by running

git tag proj2a-0     # Or proj2a-1, etc.
git push
git push --tags

The checkpoint is worth 4 points. The checkpoint grader will test the correctness of your Board.java class. It will run the provided unit tests, the integration tests you are given with the skeleton code, and some additional integration test to ensure the correctness of your Board.java. These integration tests will also be run on your final submission for Project 2.

The checkpoint grader will be available on Gradescope starting 10/13. For this checkpoint, the logs will always be shown. You will be able to submit once every 6 hours on autograder release. Starting October 21, you will be able to submit once every 3 hours. On October 25 at 9pm, you will have unlimited submissions.

While this checkpoint will not test your AI, you should begin working on the AI portion of this project before the checkpoint deadline. You will not be able to finish the AI portion in the time between the due date of the checkpoint and the project due date (10/28).

The due date for Project 2 is 10/28 at 11:59 PM PT. For Project 2, we will be grading for style, integration tests, and your tests for a total of 24 points. On Monday 10/18 morning, you will be able to submit once every 6 hours, and see limited grader output. Starting Monday, 10/25, you will see the full grader output. Starting Thursday, 10/28 (the due date), you will be able to submit once every 3 hours. In the final hour before the deadline, you will be able to submit 4 times to account for any last minute issues, and there are no restrictions on the grader after the deadline.

NOTE: You will not have unlimited submissions before the deadline for this project.

The autograder will be available for you to submit to it starting 10/18.

## Extra Credit

For extra credit (and please attempt this only after you have met the required conditions,) you can provide a graphical interface. We've set up the skeleton in such a way that you can use the simple strategy of having your GUI communicate with the rest of the program by writing the same commands you can enter by hand and interpreting the output from the program to get its moves. Your GUI must operate only when the program is executed with

  java jump61.Main --display

(or java -ea) so that the GUI is not initialized when the --display option is missing.

As usual, start immediately. The first thing you should do is play the game! You can either play the game online (there are many places you can do this, for example here) or use the command staff-jump61 --display with X11 forwarding enabled while ssh-ed into the instructional account.

Next, read the spec and skeleton thoroughly, and try and understand the intent of the skeleton code. We have deliberately included uses of various Java features in the skeleton in part to get you to explore them—to read the on-line documentation and think about how they might be useful.

Now that you are familiar with how the game works, you should start working on the project. Your job will be to change the FIXMEs located in Board.java and AI.java (the other FIXEMEs are for the extra credit). Upon opening up the skeleton code, you should note that when you run java jump61.Main that the textual interface is already handled for you, but it completely lacks the game logic.

We suggest working on the representation of the board first (the skeleton has a class Board, which is supposed to represent the game board and state of play.) You can access an introduction video to this portion of the project here. As you start to build up the game logic, run and write more unit tests to make sure your implementation is correct.

Once you have the game logic working with manual players, then you can tackle writing an automated player AI. You can access an introduction video to this portion of the project here. Start with something really simple (perhaps choosing a legal move at random) and introduce strategy only when you get the basic game-running machinery working properly.

We have provided a program staff-jump61 on the instructional machines with a solution we've developed. You can use it for ideas and sanity checks but it is NOT part of the specification! There might be errors in it for all we know (why, we might even have added a few just to mislead you.) Feel free to use it with test-jump61 to write tests of your program running against another.

1. KJumpingCube is distributed under the GNU Public License as part of the KDE project. Copyright 1999, 2000 by Matthias Kiefer. It was inspired by an old game on the Commodore 64.