Intro Video to AI.java (coming soon!)
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
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
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 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
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).
Exits the program.
- auto $P$
Causes player $P$ to be played by an automated player (an AI) henceforth. The value $P$ must be
b). Ignore case—
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
autocommand. 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
autocommand. $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$
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 ===
===markers at the left margin and other lines indented four spaces. Here,
1-indicates a neutral square (necessarily with one spot), $N$
rindicates a red square with $N$ spots, and $N$
bindicates 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
seedcommand, do what you want to seed your generator.
Print a brief summary of the commands.
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.
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
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
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.
As in previous assignments, the command
compile your program and
make check will run all your tests
(both unit and integration tests). You can use the command
style to ensure your code meets the guidelines of our style guide.
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
You can find some individual unit tests in the
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 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
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
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
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:
- Navigate to the Main class in IntelliJ and open it.
- Click on Run > Edit Configurations...
- In the left sidebar of the pop-up window, under "Application", select Main.
- For "Program arguments", put in
<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
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!
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
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
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. The submission details will be released with the autograder.
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. The scoring and submission details will be released alongside the autograder.
Checking in your code (adding, committing and pushing) and pushing tags will submit your code to the autograder on Gradescope. You can see your score and details about your submission there.
The autograder will be available for you to submit to it starting 10/18.
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
java -ea) so that the GUI is not initialized when
--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
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
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
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 (coming soon). 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.
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.