Navigation
- Background
- Blocks
- Notation
- Textual Input Language
- Commands to begin and end a game
- Set-up commands
- Entering moves.
- Miscellaneous commands.
- Output
- Running Your Program
- Your Task
- Advice
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:
At the beginning of the game, we start with pieces in all four corners:
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".
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 commandauto 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, andX
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 thedump
command. - Do not output any lines containing the words "passes", "wins", "Draw", or "moves", except in the specified cases described above.
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.