Quick links:
Contents:
Note: Some 6.170 students have acquired Repetitive Strain Injuries (RSI) over the course of the final project in the past. Don't let it happen to you. It hurts. Please read the MIT web site about RSI before embarking on the final project.
Your final project is to design, document, build, and test a program that plays Antichess.
Antichess is a variant of chess in which the goal is to either lose all of your pieces (except your king) or checkmate your opponent.
Antichess is played between two opponents by moving pieces on a square board. The board is composed of 64 equal squares. The eight vertical lines of squares are called columns. The eight horizontal lines of squares are called rows. The squares are colored black and white alternately. The lines of squares of the same color, touching corner to corner, are called diagonals. The chessboard is placed between the players in such a way that the near corner to the right of each player is white. The columns are labeled a to h from left to right. The rows are numbered 1 to 8 from bottom to top.
At the beginning of the game, one player ("white") has 16 white pieces, and the other ("black") has 16 black pieces. The white player pieces are: one King (e1), one Queen (d1), two bishops (c1 and f1), two knights (b1 and g1), two rooks (a1 and h1), and eight pawns (row 2). The black player pieces are: one King (e8), one Queen (d8), two bishops (c8 and f8), two knights (b8 and g8), two rooks (a8 and h8), and eight pawns (row 7). The initial position of the pieces on the chessboard is shown to the right.
A move is defined by the following rules:
A player's moves are limited by the following fact: A player is forced to capture an opponent's piece whenever possible. If a player can take several of the opponent's pieces, he/she is free to choose which piece to take. This limitation does not exists in regular chess. The only exception to this rule is being in check.
All the pieces move exactly as they do in standard chess. An excellent description of how each piece moves and captures is at http://www.princeton.edu/~jedwards/cif/chess.html. The exceptions in this semester's version of antichess are:
In short, each move of player A must observe the following:
The king is in check when the square it occupies is attackable by one or more of the opponent's pieces; in this case, the latter is/are said to be checking the king. A player may not make a move which leaves his king on a square attackable by any of his opponent's pieces; e.g., the player cannot move the king into check. Check must be resolved by the move immediately following. If any check cannot be parried, the king is said to be checkmated or mated.
It is the foremost obligation of each player to move the king out of a check. This overrides the rule that you must take an opponent's piece. For example, in the figure below to the left, it is black's turn and black must move its king out of check even though it can take white's bishop on c6 with its rook.
If it is possible for a player to remove the king from check as well take a piece of the opponent, then the player must do so. For example, suppose the black player's king is under check from white's rook. Further, suppose black has two choices to move away from check — remove the check with or without taking a white piece. In that case, black must take white's piece and remove the check. In the figure below to the right, black's king must take the white bishop with the king in the next move (it cannot simply move the king away from check without taking the bishop).
|
|
We shall play antichess with time restrictions, as is often the case in chess games. Each player is allocated a fixed amount of time T to make all the moves, e.g., 5 minutes. There is a clock for each player that is set to T minutes at the start of the game. If it is player A's turn to move, A's clock counts down until the move is made. While it is B's turn to move, A's clock is suspended, and B's clock runs down. If a player's clock runs down to zero while the game is in progress, the player loses. This ensures that the game is over in less than 2*T minutes, because by then at least one of the clocks has run down to zero.
Player A wins the game against player B if:
If player A checkmates player B and on the same turn takes the last of player B's non-king pieces, player A wins (ie, the checkmate prevails).
The game is stalemated if the king of the player who has the move is not in check, and this player cannot make any legal move. In the example on the right, black is stalemated on their turn, since neither their pawns nor king can move. In antichess, the stalemated player loses their turn, and the opposing player may continue to take turns until the stalemate is broken or the game is won.
Each team may enter its Antichess implementation into a class contest for one or more of the following awards:
Your A.I. player must be written in pure Java; we will compile all submissions from source and run them on a computer and JVM of our choosing. In other words, you should focus on high-level algorithmic optimizations, not low-level ones such as choice of bytecode or Java implementation.
Judging will be done initially by the TAs and final judgments will be made by the lecturers. Winners will be announced at the last class on Dec 12.
You'll do your project in phases, with the following milestones:
| Phase | Deliverables | Due date |
|---|---|---|
| Preliminary Design | Preliminary design document | 11/14/07 |
| Preliminary Release | Source code, specifications, unit tests | 11/27/07 |
| Final Release | Final design document, source code, specifications, unit tests, user manual, webstart packaging | 12/10/07 |
In addition, there will be weekly meetings with your TA between Nov 1 and Dec 10, with a progress document due at each.
Each team will receive a single grade for the final project.
The Final Project Grading, Deliverables, and Schedule document has more information about these stages, how they are graded, and what is required at each. You should be sure to read through this document now, so that you are not caught unprepared by what is expected.
The following additional requirements apply to the Antichess project:
The preliminary and final design documents must discuss, among other issues:
At the preliminary release deadline, we will ask you to demonstrate some specific Antichess functionality.
Your GUI should be reasonably easy to use and understand.
At the final release deadline, we will require you to meet the full requirements for Antichess as detailed in Appendix 1. In addition, you will need to meet the requirements for the amendment that we will give later.
See the Final Project Tools document for information on tools that may help make your work faster, more efficent, and more enjoyable.
We are providing you with images for various chess pieces. They are available in the directory /mit/6.170/www/psets/antichess/images.
In addition we provide you with a Specification and an interface to implement for machine players.
The most important issues when you design, build, and test your system are correctness and clarity. It is better to have a program that follows the rules and that implements your desired algorithm than it is to write one that quickly does the wrong thing. If you focus upon speed, you are more likely to encounter serious correctness problems. Similarly, good abstraction and an understandable design are more important than speed -- both in the real world, and because we will be grading on those real-world issues We will grade your submission primarily based on good modularity, documentation, abstraction, and other standard, important software engineering principles, not on less-important principles such as speed. If you want to sacrifice the former for the latter, you will sacrifice your grade as well. In any event, it is a false dichotomy: the best submissions do well on both, for a better design is more likely to be fast and is certain to permit you to apply optimizations easier.
Within the constraints of correctness and clarity, a faster implementation will perform better in the competition. This section discusses some speed-related issues. You should also see Bloch's Effective Java.
If you wish to optimize, you should focus on high-level issues such as representations and algorithms, which may give you orders of magnitude more speed increase than low-level optimizations can. Are you repeating computation? Are you needlessly creating objects? Does a more efficient algorithm exist? Even more importantly for Antichess, does a better static evaluation function exist?
When thinking about speed, you should never bother with low-level issues like whether to inline a particular procedure or whether i+=1 is faster than i=i+1. The first reason is that a good JIT already does a good job at such optimizations; it can be far more effective working at the machine code level than you can at the source level. The second reason is that you are likely to get these wrong; one reason that many modern compilers lack an inlining directive is that experience has shown that programmers' intuitions about inlining are wrong more often than they are right. The third reason is that such tiny performance improvements are unlikely to make a real difference: a couple of percent won't matter either way in the competition (or in most real-world environments).
In order to discourage counterproductive optimizations, and for other reasons, we require you to submit source in pure Java. We will compile it with a compiler of our choice and run it on a JIT of our choice. Both will be state-of-the-art tools, so you don't have to worry about low-level optimizations. Use of a uniform compiler will ensure fair comparison across students: we don't want to test a student's infrastructure or toolset, but the code.
More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason — including blind stupidity. — William A. Wulf
We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. — Donald E. Knuth
We follow two rules in the matter of optimization: Rule 1. Don't do it. Rule 2 (for experts only). Don't do it yet — that is, not until you have a perfectly clear and unoptimized solution. — M. A. Jackson
Your antichess game should be packaged with the JAWS tool, and be playable as a stand-alone application.
The basic mode of your game will be to have a human play against a machine player. Your application should use Java Swing (or SWT, if you choose) to provide a graphical user interface for this form of play.
You must implement the AiPlayerFactory interface from antichess.mit.edu. The web site contains further specifications and packaging instructions. Your A.I. must be playable in the Antichess.net client.
We have provided a jar file of the net.antichess.ai package in
antichess-ai.jar.
Note that AiPlayerFactory provides means for your A.I. to "learn" from its opponents by persisting state across games.
We highly encourage students to register on antichess.mit.edu and upload their A.I. players early. This way, students can prevent last minute packaging panic and test their A.I.s with other teams in scrimmages.
Our referee will use the information about what has changed on the board, plus its knowledge of the current state, to display the status of the game. It will check each response for legality, it will keep track of the time left for each player, and it will display the status of the game. We will provide our own referee that does these things. We will use this referee in the tournament. You will not implement the referee in this problem set; only your Antichess machine player. Of course, in a human-computer game, your program has to provide functionalities very similar to the referee (e.g. checking for illegal moves, displaying status, etc.).
Your machine player should avoid simply make arbitrary moves. As such, you must implement decision heuristics to enable your machine to play well. Do not let this task intimidate you. Any of several basic and easy to understand algorithms will be sufficient. For example, you might read up on minimax or alpha-beta search methods. A good introductory text on such search methods is Russell & Norvig, A.I.: A Modern Approach.
Your machine player must also demonstrate the advantages of supporting parallel thread execution on multi-core computers. Given a time limit that the staff will determine, your machine player on a multi-core machine must beat a reference player that we provide.
Our reference player will be a primitive A.I. player that conforms to the specifications of AiPlayerFactory. The reference player will support either only single-thread execution, or very basic multi-threaded capability, with simple search capabilities. As such, your final submission of your machine player should be able to defeat our reference player 100% of the time.
The reference player will be available for scrimmage freely towards the last week of the final release deadline. You may decide to test your machine player A.I. and multi-threaded implementation on the reference player before your submission. A significant portion of your final source code grade will be determined on your ability to defeat our reference player.
The graphical interface for a human-computer game should display at least the following information:
Once the game has started, the following functionality must be available:
This section describes the standard features that your program must support in order to work with our referee. Your program is required to conform to these specifications (even if you do not intend to enter the tournament), and the specifications may not be changed.
We define a standard string format for a chess move. The string should be 5 characters long. The first two characters represent the square where the piece began, the third character is a dash (-), and the next two characters represent the square where the piece moved to.
<move-desc> ::= <position>-<position> <position> ::= <col><row> <col> ::= a | b | c | d | e | f | g | h <row> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
Your machine player is allowed to use multiple threads and be thinking while the opponent is thinking and making his move. However, you are not allowed to use the resources of a computer other than the one running the machine player. That means you cannot attempt to access any external computer or resource file before or during play.
Your Antichess application should complete the partially specified text user interface for net.antichess.ai.TextUI. Your implementation of this class should provide a public main method. The TextUI should wait for user input without providing a prompt. Nothing should be printed when the application is first started. Valid user input is in the form of commands. Outputs as a result of a command should be zero or more lines, each terminated with a newline.
The main method must be executed with zero
command-line arguments. The behavior of the TextUI is unspecified
when main is run with one or more command-line arguments — you
may wish to provide command-line arguments in order to facilitate
ImplementationTests or other provide other functionality not covered
by this specification.
We have provided a sample input file, sample.input, and its expected output, sample.expected. You ought to be able to run your text UI and compare its results using the following commands:
% java net.antichess.ai.TextUI < sample.input > sample.actual % diff -u sample.expected sample.actual
Game files are stored in an text file format known as XML which stands for eXtensible Markup Language. XML has a well-defined, treelike structure; thus, it is straightforward to check if an XML document is well-formed (as compared to an arbitary tab- or space- delimited file format, which might be easier for people to read). Java 5 has built-in XML support, called JAXP (tutorial). Also see the w3schools tutorial on XML.
Not every XML file is a valid Antichess game file. An XML Schema is a file written in XML that defines the desired format for other XML files.
We provide you with an XML Schema antichess.xsd that defines the XML format for a game of Antichess. Any XML file that validates against antichess.xsd should be able to be loaded by your antichess application. Conversely, any XML file that does not validate against the schema should be rejected by your application, and an appropriate error message should be displayed to the user.
We have made the schema eXtensible, so if you decide to add special features to your own Antichess application, you can extend our file format to save this additional information. Because of this flexibility, game files written by your application should be able to be read by any other team's application, even if the other applications do not have, or do not know about, the special features that your application has.
Take a look at the sample game file, aptly named sample_game.xml. As you can see, the file records the historic, as well as the current, information for the game. This example records a saved game where white won by checkmating the black king.
We now describe each element of the game file, in turn.
<game ruleset="STRING"> ... </game>
A game element contains four subelements:
time, moveHistory, pieces,
and gameOver.
<time timed="BOOLEAN" initWhite="MILLISECONDS" initBlack="MILLISECONDS"
currentWhite="MILLISECONDS" currentBlack="MILLISECONDS" />
timed attribute is true if the game is timed.
The initWhite and initBlack attributes represent the
total time given to White and Black (respectively) at the start of
the game; this should be an integer, representing time in
milliseconds. The currentWhite and
currentBlack attributes represent the time left on the clock for
White and Black at the point in the game when this file was saved,
also in milliseconds.<moveHistory> ... </moveHistory>
move tags. It takes no
attributes.<move side="SIDE" value="MOVE" time="MILLISECONDS" />
side attribute must
be either white or black. The
value attribute is a move described in the standard string format given
above, e.g. "c5-c7". The time attribute
specifies the time remaining on the clock of the player who made
the move, in milliseconds. If the game is untimed, then this
attribute may be omitted.<pieces> ... </pieces>
pieces tag is just used as a container for
zero or more square tags. It takes no attributes.<square id="SQUARE" side="SIDE" piece="PIECE" />
id
attribute is a location on the chess board, such as
c5. The side attribute must be
either white or black. The
piece attribute is one of pawn,
rook, knight, bishop,
queen, or king.<gameOver winner="SIDE" description="GAME-END" />
winner attribute must be
either white or black. The
description attribute indicates how the game ended;
the choices are piecesLost, checkmate,
timeExpired, or stalemate. (Note that, in
our version of antichess, stalemate does not end the game and so
is not a valid value for this tag even though the schema permits it.)
There are two XML parsing frameworks in the Java 1.5 SDK, SAX and DOM.
Our advice is to either use: (a) the SAX parser, which does proper
validation via the setSchema method
without jumping through any hoops, or (b) a non-validating DOM
parser (ie, don't call setSchema) and validate by using the
SchemaFactory
to generate a
Schema
which can generate a
Validator
to check your
DOMSource
after parsing.
To make a responsive Antichess GUI you need to know about threads. Threads are hard — just look at the API for java.lang.Thread for crying out loud! Many of the methods are deprecated because even the guys at Sun couldn't get it right the first time. Thus, to help you with your final project, we're going to provide you with some snippets of sample code that use threads that you can use in your project, if you like.
The most common thread-related problem in the Antichess project is
figuring out how to ask the GUI for a move when it is a human
player's turn. Suppose your application has a Player
interface that has a method called getMove() that your
application invokes to get the move from a Player. The
problem is that when getMove() is invoked, there is no
limit on how long the player can take to return a move. More
importantly, while the player is trying to choose his move, the
rest of the application should not lock up because it is waiting
for the getMove() to finish. To make a responsive GUI,
you have to take advantage of the main thread (the one that you use
that calls getMove()) and the GUI thread (the one that
the Java Virtual Machine supplies for you that responds to mouse
clicks and keystrokes). Imagine the following snippet of code is
inside some GUI class that implements Player:
/**
* a field variable that represents the move the player
* made through some form of input into the GUI
*/
String move;
/**
* method of the Player interface that gets the player's move
*/
public synchronized String getMove() {
try {
while (move == null) {
try {
this.wait();
} catch (InterruptedException e) {}
}
return move;
} finally {
move = null;
}
}
/**
* method of the MouseListener interface that this GUI
* class also happens to implement
*/
public synchronized void mouseClicked(MouseEvent e) {
// do some computation on e
// to figure out what move the user made
// this will probably require keeping track of
// the previous click as well
if (clickResultsInValidMove) {
move = whateverTheValidMoveIsBasedOnTheMouseClick;
this.notify();
}
}
Basically, what happens is that when getMove() is
invoked, it enters the while loop which polls to see if
move has been set, periodically sleeping in-between to
free up the processor to other threads. While the main thread is
inside getMove(), the GUI thread may enter
mouseClicked() and set the move variable
so that the next time move is polled by the while loop
inside getMove(), it will break out of the loop and
return the move.
Note: This sample code may not be an exemplary use of threads in Java; however, it is a sufficient solution for the unresponsive-GUI problem.
You can use the observer pattern to decouple the Swing component
that displays the clock from the clock itself. Consider creating an
interface called StopwatchListener that listens for
changes on a stopwatch that sends updates at least once per second:
/**
* A StopwatchListener listens for time updates from a stopwatch.
*/
public interface StopwatchListener extends java.util.EventListener {
/** tells how much time is left on the stopwatch, in milliseconds */
public void timeChanged(long milliseconds);
}
Now consider creating a Swing component that listens for updates from a stopwatch. In this case, we create a label that displays the time for only one stopwatch.
public class TimeLabel extends JLabel implements StopwatchListener {
public void timeChanged(long milliseconds) {
long seconds = milliseconds / 1000;
long minutes = seconds / 60;
seconds = seconds % 60;
String time = String.valueOf(minutes) + ":" + String.valueOf(seconds);
setText(time);
}
}
So where does the threading come in? We use a
java.util.Timer to schedule periodic updates to our
StopwatchListener. By using Timer, we do
not use the Thread class directly; however,
Timer provides a valuable abstraction around threads
because it has a cancel method that allows us to
cancel the events that we schedule. Were we to use a
Thread, we would not be able to use its
stop() method as Thread.stop() is
deprecated. Note that there is also a timer class for scheduling
GUI events, javax.swing.Timer. See Using
Timers in Swing Applications for more details about when to use
which timer.
When using java.util.Timer, we can only "schedule"
events that are objects that extend
java.util.TimerTask. Thus, we create a
TimerTask that updates its listeners as follows:
import javax.swing.event.EventListenerList;
public class Stopwatch extends TimerTask {
private boolean running = false;
private long millisLeft;
private long startTime;
/** @requires millisLeft >= 0 */
public Stopwatch(long millisLeft) {
this.millisLeft = millisLeft;
}
public void start() {
if (running) return;
running = true;
startTime = System.currentTimeMillis();
}
public void stop() {
if (!running) return;
running = false;
long stopTime = System.currentTimeMillis();
millisLeft -= (stopTime - startTime);
}
public long getTime() {
if (running) {
return (millisLeft - (System.currentTimeMillis() - startTime));
} else {
return millisLeft;
}
}
/*
* To see where all of this crazy listener code comes from,
* check out javax.swing.event.EventListenerList
*/
private EventListenerList listenerList = new EventListenerList();
public void addStopwatchListener(StopwatchListener s) {
listenerList.add(StopwatchListener.class, s);
}
public void removeStopwatchListener(StopwatchListener s) {
listenerList.remove(StopwatchListener.class, s);
}
protected void fireTimeChanged() {
// Guaranteed to return a non-null array
StopWatchListener[] listeners =
listenerList.getListeners(StopWatchListener.class);
// Process the listeners last to first, notifying
// those that are interested in this event
long time = stopwatch.getTime();
for (int i = listeners.length - 1; i >= 0; i --) {
listeners[i].timeChanged(time);
}
}
public void run() {
fireTimeChanged();
}
}
As you can see, when the run() method is invoked, the
latest time is acquired from the Stopwatch and is sent
to every registered StopwatchListener. Thus, the
following would be a plausible way to use Stopwatch:
/**
* This is an incomplete Game class, but it demonstrates
* the use of the code above.
*/
public class Game {
private Player whitePlayer, blackPlayer;
private Stopwatch whiteWatch = new Stopwatch(5 * 60 * 1000);
private Stopwatch blackWatch = new Stopwatch(5 * 60 * 1000);
private Timer timer = new Timer();
/**
* Creates a simple clock panel that will get updated by the stopwatches.
*/
public JPanel createClockPanel() {
JLabel whiteLabel = new TimeLabel();
JLabel blackLabel = new TimeLabel();
whiteWatch.addStopwatchListener(whiteLabel);
blackWatch.addStopwatchListener(blackLabel);
JPanel panel = new JPanel();
panel.add(whiteLabel);
panel.add(blackLabel);
}
/**
* Stops one player's clock and starts the other's.
*/
private void switchClockTo(boolean white) {
// stop the clock for the previous player
Stopwatch lastWatch = (white) ? blackWatch : whiteWatch;
lastWatch.stop();
timer.cancel();
// start the clock for the next player
Stopwatch nextWatch = (white) ? whiteWatch : blackWatch;
timer = new Timer();
timer.scheduleAtFixedRate(nextWatch, 100, 500);
}
}
Q: How should castling and en passant be represented in the standard
string format for the game XML files?
A: When castling occurs, the move should be saved as a single king move.
The rook's movement should be inferred.
Likewise, an en passant move should be saved as a single pawn move.
One of our links to specifications pointed to an old set of specifications that had a MachinePlayer. This link has since been corrected. Please ignore MachinePlayer and note that you just implement AiPlayerFactory to play on the scrimmage and tournament server.