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:

Figure 1. Extends and jumps.

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

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

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:

• set-up state, meaning that no game is in progress is moving, and pieces may be placed on the board to set up a position (this is the initial state);
• playing state, where players are entering moves and the game is not yet over; or
• finished state, where one or the other player has won and no more moves are possible.

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

• clear Abandons the current game (if one is in progress), clears the board to its initial configuration, and places the program in the set-up state. Abandoning a game implies that you resign. This command is valid in any state.
• start Valid only in set-up state. Enters playing state. Red and Blue alternate moves. If there have been moves made during the set-up state, then play picks up at the point where these moves leave off (so, for example, if there was one set-up move made before start, then Blue will move first). In the (unusual) case where the set-up moves have already won the game, start puts the program in finished state.
• quit Abandons any current game (as for clear) and exits the program. Valid in any state. The end of input has the same effect.

## Set-up commands

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

• auto C Sets up the program so that player C (Red or Blue) is an AI. Initially, and after a clear command, Red is a manual player and Blue is an AI. Thus, the command auto Red causes both Red and Blue to be AIs, so that the start command causes the machine to play a game against itself.
• manual C Sets up the program so that player C (Red or Blue) is a manual player. Thus, the command manual Blue causes both Red and Blue to be manual players (who presumably alternate entering moves on a terminal).
• block CR Sets a block at square CR and all reflections of that square around the middle row and middle column, as described in Blocks. It is an error to place a block (or one of its reflections) on a previously set up piece. Blocks may not be placed after a piece move, until the board is again cleared. In case of any errors, the command has no effect.
• seed N If your program's AIs 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(s) behave(s) identically in response to any given sequence of moves. In the absence of a seed command, do what you want to seed your generator.

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

• help Print a brief summary of the commands.
• dump This command is especially for testing and debugging. It prints the board out in exactly the following format:

===
r - - - - - b
- - - - - - -
- - X - X - -
- - - - - - -
- - X - X - -
- - - - - - -
b - - - - - r
===

Here, - indicates an empty square, r indicates a red square, b indicates a blue square, and X indicates a block. Don't use === 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.

• load file Reads the given file and in effect substitutes its contents for the load command itself.

## 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:

• Any input prompts you print must end in a colon (":").
• Do not use the "===" marker except in the specified output from the dump command.
• Do not output any lines containing the words "passes", "wins", "Draw", or "moves", except in the specified cases described above.

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

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.

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