Project 2: Ataxx

Background

Ataxx is a two-person game played with red and blue pieces on a 7-by-7 board. As illustrated below, there are two possible kinds of moves:

In either case, all opposing pieces that are next to the previously empty destination square are replaced by pieces of your color. Here is an example of a starting position (in the middle) and two possible moves with the same piece. Squares marked $\times$ show red's other possible jumps with that piece:

Possible Moves
Figure 1. Extends and jumps.

At the beginning of the game, we start with pieces in all four corners:

Initial Position
Figure 2. Initial position.

The red player goes first, and the two players alternate until there are no more moves possible or until there have been 25 consecutive jumps between both players. You are allowed to skip a move (we will call this a pass) only if you have at least one piece on the board, but no legal move. The winner is the player who has the most pieces at the end of the game; thus, you don't automatically lose just because you can't move. The one exception to this condition is if you have no pieces left on the board. In this case, you have no way of winning, so you will automatically lose. It is possible also to tie, when both sides end up with the same number of pieces on the board and:

Notation

We'll denote columns with letters a--g from the left and rows with numerals 1--7 from the bottom, as shown in Figure 2. An ordinary move consists of two positions separated by a hyphen in the format $c_0r_0-c_1r_1$ (e.g., g1-f2). The first position gives a piece owned by the current player, and the second gives an empty square to which the piece jumps or extends. A single hyphen denotes a case where one player has no move and must pass (it is only legal when there is no other legal move).

Blocks

To make things even more interesting, you can place a set of blocks symmetrically about the center of the board before playing. These are pre-filled squares that may never be moved to (the blocks themselves never move). Setting blocks is only possible at the start of the game. The illustration below is an example of a starting configuration with 10 blocks. Each block is always reflected across the middle row and the middle column. In other words, there is symmetry both horizontally and vertically for any block that is placed. No block may be placed in the four corner squares, since the initial configuration has pieces there.

For example, the configuration below may be described by listing three squares: "b2", "c3", and "c4"; reflecting these three gives in addition "f2", "e3", "e4", "b6", "c5", "f6", and "e5". Alternatively, the same configuration may be described as "f2", "c3", and "e4".

Blocks
Figure 3. Blocks.

Textual Input Language

The players (we'll simply call them Red and Blue) can each be either a manual player, entering moves as input, or an automated player (we'll call it an AI). Manual players can talk to the program using either a textual interface, described in this section, or (for extra credit) a GUI.

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 everything from a # character to the end of a line is ignored as a comment.

The Commands:

Starting and Ending Games

Commands to Set Parameters

The following commands set various game parameters.

Entering and Undoing Moves

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.

Your program must reject illegal moves from any player (they have no effect on the board; the program should tell the user that there is an error and request another move). An AI must not make illegal moves.

Miscellaneous Commands

Optional (Helpful) Commands To Add

You might (optionally) consider a couple of other useful commands that you will find in the staff solution. These may be useful in debugging and improving the overall experience of the game:

Output

When either player enters a winning move, the program should print one of the lines

 * Red wins.
 * Blue wins.
 * Draw.

as appropriate. Use exactly those phrases, alone on their line. Don't use these phrases in any other situation.

Whenever a player is an AI, it should print out each move that it makes, using one of the formats

 * Red moves -.
 * Blue moves -.
 * Red moves C0R0-C1R1.
 * Blue moves C0R0-C1R1.

(replacing C0R0-C1R1 with an actual move, of course.) Again, use exactly those phrases, alone on their line.

Other than this, you may produce any additional user-friendly output you choose, subject to a few restrictions:

Running the Program

As usual, you'll run the program with the command

java -ea ataxx.Main

Your AIs must make only legal moves. They are required to be somewhat smart: they should be able to find a forced win that is within four moves of the current position. A forced win is a situation where you maneuver the opponent into a position in which they have no choice other than to make losing moves; in other words, you force your opponent into losing the game. Your AI should be able to look up to 4 moves ahead and find a forced win, if one is available. Finally, there will be an (optional) tournament at the end of the project so that you can challenge your AI against AIs that other 61B students came up with!

We've provided an executable staff-ataxx in cs61b-software, which allows you to run the staff's solution and AI. You can run staff-ataxx as follows:

staff-ataxx

After running the above line, you can begin entering the textual input commands in the terminal to play the game. If you'd like to run the staff solution with the GUI enabled, you can use:

staff-ataxx --display

To get this executable, cd into your cs61b-software directory and run

git pull origin master

Be aware, however, that the staff-ataxx program does not define what you are supposed to do; this document does. If you find a discrepancy between this specification and our program, tell us. Please don't assume that our program defines how your program is supposed to work.

Testing

Check out these testing videos for some explanations about the Ataxx testing framework!

As with Projects 0 and 1, the command

make unit

will run all the unit tests, and the command

make acceptance

will run all the acceptance tests. If you try this on the skeleton, you'll see that, unsurprisingly, it fails all these tests, giving you an indication of what needs to be changed. The unit and acceptance tests provided with the skeleton are nowhere near comprehensive. Passing the unit and acceptance tests included with the skeleton is not an indication that your code is correct, you should write additional tests to ensure correctness. Use the IntelliJ debugger to assist in passing these test cases.

Usually, you will want to use the command make check for testing, which runs both the unit and acceptance tests. By the time you finish the project, make check should report no errors. If your python command is python rather than python3 you will need to use make PYTHON=python check to run the acceptance tests.

Important: For information on the testing commands you can use in an acceptance test, refer to the comments in the test-ataxx file that was given as part of the skeleton.

Furthermore, to run individual acceptance tests, you can run the following from the proj2 directory:

python3 testing/tester.py --show=1 testing/<testX>.in

where <testX>.in is an input file (e.g test01-1.in). The --show=1 option here shows error output for the test that you are running. Finally, you can also run the above command with the --keep option:

python3 testing/tester.py --show=1 --keep testing/<testX>.in

This will create two new files in the proj2 directory:

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

  1. Navigate to the Main file 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 testing/<test_file> where <test_file> is the name of the file of the acceptance test you would like to run.

For example, if you would like to run acceptance test test01-1.in, you should have testing/test01-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 acceptance tests. Remember to set a breakpoint if you're debugging!

Some tests play two programs against each other (the tests with a testX-2.in file). When running these tests, you'll have to pass both files as arguments.

Your Task

Your job is to write a program that allows you to play a game of Ataxx, and also an AI that you can play the game against. This will involve editing the functions/locations labeled FIXME in Move.java, Board.java, and AI.java.

To obtain the skeleton files (and set up an initial entry for your project in the repository), you can use the usual command sequence:

git fetch shared
git merge shared/proj2 -m "Get proj2 skeleton"

from your Git working directory. Should we update the skeleton, you can use exactly the same sequence to update your project with the same changes.

Be sure to include tests of your program (this is part of the grade, see Grading Details). The makefile we provide has convenient targets for running unit and acceptance tests, and a Python testing script for acceptance testing. See the testing/README file for a description of the specification language used by this script. Our skeleton directory contains some trivial tests, but these do not constitute an adequate set of tests! Make up your tests ahead of time and update your makefile to run them. To help with testing and debugging, we will provide our own version of the program, so that you can test your program against ours (we'll be on the lookout for illegal moves). More details will follow.

Your AI should be able to find a forced win that is within four moves of a given position. It must not use more than 10 seconds to make any given move.

Some Notes and Hints About the Skeleton

  1. The _notifier instance variable and the announce() method that you see used throughout Board.java is a mechanism for the GUI (see the Extra Credit section). If you aren't working on the GUI, you can ignore this mechanism entirely.
  2. Our usage of the EXTENDED_SIDE class constant may confuse you; if you don't understand the motivation for it, please read the lengthy comment above the _board instance variable at the bottom of Board.java.
  3. The unrecordedSet() method in Board.java is a way for us to set the PieceColor of a square without marking the action as a move that can be undone. The set() method is supposed to set a square and mark the move as "undoable"; this may pose a problem when we'd like to make certain changes to the board that aren't supposed to be undone by a player.
  4. You shouldn't be calling the Move constructor (it's private!) whenever you need to create a new Move object; instead, use the factory static method Move.move() to get a Move object containing the move that you'd like to represent. This method is optimized (see the Javadoc comment above the method) in order for your AIs to run even faster, so you should use it whenever needed.

  5. You'll likely find that you'll need to do some character arithmetic while completing this project. Since chars are just integers underneath the hood, we can do addition with them as follows:

       'a' + 3 = 'd'
   'g' - 4 = 'c'
   '1' + 5 = '6'
   'b'++ is equivalent to 'c'

  6. "Linearized indices" is just a fancy way of stating that we converted the standard 2D array indexing with a row and column index into 1D array indexing. As a visual example, in the 3x3 table below we translate square (0, 0) to index 0, square (1, 0) to index 1, square (2, 0) to index 2, so on and so forth. Then, we can store all the squares in the Board as a 1D array and refer to each square by its new 1D index.

    0 1 2
    3 4 5
    6 7 8

Advice

You are not required to use any part of our skeleton as long as your program behaves as described in this document. However, don't throw anything away without understanding it; there's something to learn from our code even if you choose not to use it.

We suggest working first on the classes Move and Board, which allow you to make moves and interact with the board. Then you can tackle writing a machine player in AI.java. For the AI, start with something really simple (perhaps choosing a legal move at random) and introduce strategy only when you get everything working properly. Random play will not reliably satisfy the requirement of finding forced wins, so you will eventually have to do a real search.

Checkpoint Grading Details

By Friday, 3/18 at 11:59PM you must have completed the following deliverables in order to receive 4 points. The checkpoint is not extra credit, and will be factored into your final project grade.

  1. Pass all unit tests in MoveTest.java.
  2. Pass all unit tests in BoardTest.java.
  3. Pass acceptance tests 1-4 (a correct Move and Board implementation will be able to pass these 4).

You will be able to submit to the checkpoint autograder by committing it and tagging it as follows (the tag is proj2a not proj2):

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

On release, you will only be able to submit to the checkpoint autograder once every 6 hours, and full error logs will be displayed. Starting Monday 3/14, you will be able to submit once every 3 hours. Finally, starting at 9:00PM PST on 3/18, you will be able to submit as many times as you want.

Grading Details

Project 2 is due 4/1 at 11:59 PM PT. The project is worth 24 points (the total score for this project is 28 points, with the checkpoint included). Your score on Gradescope will be your final score for the assignment.

The release date of the full Project 2 autograder will be announced soon. The tests included in the skeleton code are not the full suite of tests that will be run on your submission. The intention is that you write tests for your code, and do not rely on autograder submissions to debug problems. To encourage this, you will only be able to submit to the autograder once every 6 hours, and limited error output will be displayed.

Starting 3/18, the autograder will show more information about why you are failing some tests, and what the tests that you are failing contain. Starting on 4/1, you will be able to submit to the grader once every 3 hours, and in the last hour before the deadline, you will be able to submit 4 times to account for any technical difficulties or Git issues. Starting 4/2 (this is after the official project deadline!), you will be able to submit as many times as you want.

As a warning, you will not be able to complete the project if you wait to start or test your code 3 days before the deadline You should plan to start early, and write your own extensive tests for this assignment. You will be required to write and pass at least 1 extra acceptance test on top of the ones given to you.

Extra Credit

Due to high demand for course resources, we will not provide help in Office Hours or answer Gitbugs for questions on the extra credit.

Extra credit grading details will be released on Piazza closer to the assignment deadline.

For extra credit, you can provide a GUI (after all, what computer board game is complete without a GUI?). By default, the command shown above should not use a GUI. Instead, you indicate explicitly that you want it:

java -ea ataxx.Main --display

If you choose not to implement a GUI, make sure that your program terminates with an error exit code of 2 when given the --display parameter. Otherwise, your program should exit with exit code 0, as usual, even if someone entered invalid commands during a session (and simply print error messages in response to the errors).

We do not recommend doing the extra credit before finishing the main part of the assignment.