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 move: you can extend from a piece of your own color by laying down a new piece of your color in an empty square next to that existing piece (horizontally, vertically, or diagonally), or you can jump: move a piece of your own color to an empty, non-adjacent square that is no more than two rows and no more than two columns distant. 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 play alternates until no more moves are possible, or until there have been 25 jumps with no intervening extends. You are allowed to skip a move (pass) only if you have at least one piece, 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, unless you have no pieces left). It is possible also to tie.

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). 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. No block may be placed in the four corner corner squares, since 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 for short). Manual players can talk to the program using either a textual interface, described in this section, or (for extra credit) a GUI.

At any given time, your program can be in one of several states:

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.

Commands to begin and end a game

Set-up commands

The following commands are valid only in set-up mode. They set various game parameters prior to the start of play.

Entering moves.

One can enter moves either in set-up state or in playing state. In set-up state, moves serve to manually set up a position on the playing board. 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. See Notation for move syntax.

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.

The following commands are valid in any state.

Output

When either player enters a winning move, the program should print a line saying either Red wins. Blue wins., or Draw., as appropriate. Use exactly those phrases, alone on their line. At that point, each program goes into finished state (maintaining the final state of the board so that the User may examine it). 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 passes.
 Blue passes.
 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 Your Program

Your job is to write a program to play Ataxx. 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 five moves of the current position. There will be a tournament at the end.

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).

Your Task

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 proj1 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 (that is part of the grade). The makefile we provide has convenient targets for running unit and integration tests, and a Python testing script for integration 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 five moves of a given position. It must not use more than 10 seconds to make any given move.

Our testing of your projects (but not our grading!) will be automated.

Advice

We've provided a program staff-ataxx on the instructional machines for seeing our solution in action. Be aware, however, that the staff-ataxx program does not define what you are supposed to do; this document does. If you find a discrepency between this specification and our program, tell us. Don't just assume that our program defines how your program is supposed to work.

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.

I suggest working first on the classes Board, which is supposed to represent the game board, and Command, which houses some command-parsing code. Next, implement the manual player. Then you can tackle writing a machine player. 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.