| 6.170 | Laboratory in Software Engineering Spring 2004 Final Project: Antichess Due: See Schedule |
Quick links:
Contents:
Antichess is a variant of chess in which the goal is to either lose all of your pieces (except your king) or force your opponent to checkmate you.
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 exist 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 can be found here: http://www.princeton.edu/~jedwards/cif/intro.html. You can ignore the descriptions of castling and en passant as these moves are not allowed in this semester's version of antichess. Another simplification in our set of rules is that when a pawn moves to the last row on the opposing side, it turns into a queen. (In standard chess, such a pawn can be turned into any piece of the player's choice.)
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:
The game is drawn when the king of the player who has the move is not in check, and this player cannot make any legal move. The player's king is then said to be stalemated. This immediately ends the game in a draw, i.e., neither player wins or loses the game.
| Stage | Due date |
% of project grade | Graded on |
|---|---|---|---|
| Preliminary design | Tues, April 13 |
|
Have you identified the issues? |
| Weekly meetings with TA | Mon, April 5 through Fri, May 7 |
|
Did all of the team members participate constructively? |
| Preliminary Release | Tues, April 27 |
|
Is it a good design? Is the required functionality present? |
| Final report | Tues, May 11 |
|
Quality of entire documentation including amendment and design critique. Are the tradeoffs & alternatives analyzed? |
| Implementation & Test | Tues, May 11 |
|
Does it work? Have you demonstrated that it works? What is the quality of the code, the design, and the tests? |
| User Interface and Quality of Play | Tues, May 11 |
|
How is the user experience? Is it easy-to-use? How sophisticated is the computer player? |
You will work in teams of three or four. Each team member should be responsible for a significant part of the design, documentation, code and testing. All members of a team will get the same grade, except in unusual circumstances. If your group is experiencing internal problems, see your TA immediately.
As you can see, more than half of your grade depends on design and documentation. Please realize that the most important aspect of any large software endeavor is design. A good, well documented design will make the rest of a group's work faster, easier and more enjoyable.
Each stage of this assignment should be handed in electronically to your TA by 4:30 PM on its due date. All of the source and compiled code should be put online on May 11, in your team project directory.
The final report is due by 4:30 pm on May 11, 2004. Because of end of term constraints, late reports will not be accepted.
You should express your preliminary design in under 15 pages. Your document will be a subset of that described in the Documenting a Software System handout. It will include a revised specification, a design, and an implementation overview (including an object model or models and a module dependency diagram). You do not need to include information about your testing strategy or provide a reflection of your experience (after all, you haven't really finished the project yet).
The revised specification, design, and implementation overview must discuss, among other issues:
The preliminary design should also include a project plan, which lists milestones for the team and allocation of tasks to each team member. A milestone is what you expect to be done by some date, such as a tested module or a working feature – an achievement that is objective, easy to evaluate, and significant. There must be at least two milestones in the project between the preliminary design and the final deadline. The division of labor should be equitable. (It is most useful to combine the milestones and the task allocation into a single table with task, who, and when columns, rather than making the milestones and task allocation into to separate documents which cannot be easily related.)
The preliminary design will be graded for clarity of expression and for whether you have thought rigorously about the problem, identified the major issues and challenges, and proposed a design that makes sense.
Since the final design is due as part of the preliminary release milestone, you should have found all major mistakes in your design. Therefore the final design will be graded on whether it is a good design, in addition to clarity of expression.
In order to demo what you had done at the preliminary release deadline, even if the demo is slightly later and you have made modifications in the meanwhile, you must retain a copy of your code as it existed before the deadline. You can create a snapshot of your source and/or compiled code by using a jar file. Then, you can run the demo by placing the jarfile in your classpath, or by making the jar itself executable.
Your group must demonstrate the following features:
Follow these steps to create the tag:
Later, if you wish to go back to the tagged version, run cvs update -r preliminary-release. This will put that revision in your workspace. You will not be able to commit from that workspace. If you wish to go back to the main trunk, run cvs update -A.
You should email your TA with the following information:
Your ta will run "cvs -d <your cvs root> co -r preliminary-release <your module>" and then follow your instructions to test the demo.
Put your code online in your team project directory. You do not need to turn in a printout of your code. In general, your group must turn in code that you wrote yourself. Therefore, you are generally not allowed to use third-party Java libraries. If you have some code that you found and you are unsure of whether or not you can use it, please see your TA. The following jars are automatically allowed, so you do not have to ask your TA if you can use them:
| javadoc6170.jar | javadoclet for 6.170 style tags |
| junit.jar | JUnit test suite |
| images.jar | provided chess piece images and image loader class |
| TableLayout.jar | library to aid in doing complex layouts |
| antichess-ai.jar | AI specification to compile against |
| xercesImpl.jar, xml-apis.jar | libraries for XML parsing (consult your TA if you plan to use a different XML library) |
| swt.jar, jface.jar, runtime.jar | libraries for the SWT GUI toolkit (SWT is an alternative GUI toolkit to Swing. SWT will be allowed, but it is not recommended.) |
The final report includes a section on Design Changes. Detail what changes you have made to the design that was submitted on April 27th. Be precise. It is vitally important that your TA have versions of the descriptive parts of the Revised Specification, Implementation Overview, and Validation Strategy that accurately describe your submitted code and what you actually did for testing or validation.
For demonstrations (as described immediately below), you must also make a jar file of your implementation named /mit/6.170/groups/seMMN/final.jar. This file must be runnable and must include all of your code in both source and compiled form.
Your AI 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 May 13.
In addition we provide you with a specification for machine players and a jar that implements the interfaces and extra classes needed to implement the machine player specification.
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
java -Xrunhprof:cpu=samples,file=log.txt,depth=4 MyClass
This will generate a file called log.txt. (Warning: this will take an order of magnitude longer than just calling "java MyClass". If your program is already taking a long time, you may very well want to run it on a small input for profiling purposes.) Go to the end of log.txt, and look for a ranked table of method calls. The methods at the top of the table are eating up most of the cpu time. For more detail on how a particular method is being called, look at the "trace" column, and note the ID number given there. If the ID, for example, is 437, then search in log.txt for "TRACE 437", which will tell you from which methods your suspect method is being called. For more information about reading this file, see here
Once you know where all your time is being taken, you have generally two options:
To learn more about jar files, review the jar tool manual from Sun.
As a quick reference, here are a few sample uses of the jar command:
To create antichess.jar from classes in package antichess:
jar cvf antichess.jar antichessTo list the contents of the jar file, use:
jar tf antichess.jarTo create a runnable antichess.jar
jar cvfm antichess.jar JarMainManifest antichessIn the example above, the file JarMainManifest should contain two lines. One is a single line which names the entry point:
Main-Class: antichess.AntichessThe other specifies your AI player factory, as discussed in the AiPlayerFactory spec To run the application using the jar file, use:
java -jar antichess.jar
Using a Makefile, as described the section above, can simplify and automate the creation of jar files.
Assuming that all necessary jars are on the CLASSPATH, your program should be runnable by the following command:
java -jar antichess.jarThe 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.
In addition, we will provide a referee which will allow your machine player to play against machine players from other groups. In order to be able to do this, you must provide a MachinePlayer class which conforms to the specification.
The 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 the antichess 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 cannot 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, AI: A Modern Approach.
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.
You must implement a class that implements the AiPlayerFactory interface given in the specification. Note that this factory may return different concrete classes from the createPlayer method, depending on amount of time given, rule set, etc.
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.
But before Xerces can create these Java objects, it makes sure that the file it is reading in validates against an XML Schema. An XML Schema is a file written in XML that defines the desired format for other XML files. In ps6.reader, you can find several examples of schemas, each of which has a .xsd file extension. These schemas define the formats for the .xml files found in each Traffick database.
We provide you with an XML Schema antichess.xsd that defines the text format for a game of antichess that your application must be able to load and save to. 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. To reiterate, 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.
If you are new to XML, then you may first want to read the w3schools tutorial on XML. Before writing the code that validates and reads in an antichess game file, we recommend that you look at ps6.reader.TraffickReader for an example of how to validate an XML file against a schema in Java, and how to use it to create Java objects from the XML. Thus, we also recommend that you include xercesImpl.jar and xml-apis.jar in your project as we have in Problem Set 6. Finally, take note of the convenience methods in ps6.reader.TraffickReader named getXXXFromAttribute() as well as the class ps6.reader.NodeElementIterator. These will help you discard unnecessary information returned to you by Xerces.
The API for Xerces is located at http://xml.apache.org/xerces2-j/javadocs/api/index.html, but a good example of the parser in action is available at http://xml.apache.org/~edwingo/jaxp-ri-1.2.0-fcs/docs/samples.html. The implementation of TraffickReader was based off of this example.
<game ruleset="STRING"> ... </game>
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. initWhite and
initBlack 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. currentWhite
and currentBlack 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.
For a stalemate, the winner attribute will be ignored.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 inbetween 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.
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 {
/** 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:
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
Object[] listeners = listenerList.getListenerList();
// Process the listeners last to first, notifying
// those that are interested in this event
long time = stopwatch.getTime();
for (int i = listeners.length - 2; i >= 0; i -= 2) {
if (listeners[i] == StopwatchListener.class) {
((StopwatchListener)listeners[i+1]).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);
}
}
This section lists clarifications and answers to common questions about Antichess.