Problem Set 5: Antichess

6.170 Handout 24; Handed out on March 15, 1994; Due on various dates: see below

Note: This document has been amended.

Introduction

Your final project is to design, build and test a program that plays antichess. You will work in teams of three or four. 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.

Section 2 of this handout describes the deliverables that are expected.

Section 3 gives the requirements specification including a description of the antichess game and some interfaces.

Section 4 gives some use some useful suggestions.

What To Hand In

The due dates for the various deliverables are:

April 5th         Initial Design Document
April 14th        Progress Report
April 20th,21st   Oral Presentation
May 5th           Final Report -- due at 4:30 pm
May 9th           Demonstration
May 11th          Optional Tournament

Design Document, Due April 5th

Your first task is to write a design document, the foundation on which your project will build. It should have the following sections. (The numbers in parentheses are suggested lengths; don't exceed them without good reason.)

Revised requirements specification (2 pages)
To begin your design, you need to carefully examine the requirements specification given to you by your customer (the 6.170 staff). As is typical of customer requirements, the specification is incomplete and may contain inconsistencies or ambiguities. You need to debug the requirements specification, resolving any ambiguities or inconsistencies and filling in missing details. (In particular, you need to define a user interface for the program!) The resulting revised specification should make clear to your customer what you think the completed program should do.
Module dependency diagram (1 page)
Use a module dependency diagram to introduce the overall structure of your program. Include just the major modules for clarity.
Schedule (1/2 page)
Perhaps most crucial to the success of your project is the plan by which you will complete it on time. The project schedule should describe what each member of the team will do. It should have a list of milestones and an equitable division of labor. (A milestone says 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.) You can choose how to divide tasks between team members; you could appoint a tester, a documenter and a coder, for instance, or you could allocate modules to team members. include concrete goals that you will achieve by the final due date. How well you meet these goals will affect your grade on later stages of the project, so don't be overly ambitious. On the other hand, plan to make good progress so that you can finish the project on time.
Design overview and rationale (1 page)
Describe the major modules and explain why they were chosen (e.g. for ease of implementation, validation and/or maintenance). Describe any important design decisions that cannot be isolated to a single type or operation, including decisions to reject alternatives.
Think about any changes that the customer may later require. Argue about the extensibility of your design--how easily new features can be added. Your design should be simple and well-structured, so that it will be easy to make modifications and additions. Count On Our Demanding Several Such Changes.
Partial module specifications (10 pages)
Describe the modules of your program by giving specifications for them. Specifications of abstract types should include an overview and specifications for the important operations.

Progress Report, Due April 14th

Your next deliverable is a progress report which describes any changes to the initial design and shows some tested, working code. You should include the sections of your design document with any changes in your design, work schedule, or assignment of responsibilities clearly marked.

In addition, include the following sections:

Implementation Overview (5 pages)
For each cluster give the rep (and, if unusual, a reason for choosing it), an abstraction function and a rep invariant. Give algorithms for operations for which an implementation does not immediately spring to mind. Mention any particular problems you anticipate.
Validation Strategy (1 page)
Describe how you intend to find and remove bugs from your program. It's up to you to decide how to make your program as bug-free as possible; you'll need to use several techniques such as compile-time checks, run-time assertions, reasoning about your code, testing, etc. You might want to use different techniques at different stages in the development, or on different modules.
Code
About a quarter of the code should be written and tested by the end of the design phase. The purpose of early coding is to catch errors in the design, so try to code the modules that seem hardest or whose specs are unclear.
Evidence Of Validation
Show test runs, bug reports, etc. Tests should not be run in the debugger, but from a specially prepared file.

Oral Presentations, On April 20th And 21st

This is another progress report, but this time presented orally to your TA. It should have similar content to your first progress report, with emphasis on your design and implementation strategy. All team members need not speak, but all should attend. Your team will be graded on the quality of the presentation, and you'll get suggestions on how to proceed in finishing your project.

Final Report, Due May 5th

Submit a final report describing your design and implementation, in the same format as the progress report. Note the revisions you have made.

The final report is due by 4:30 pm. Because of end of term constraints, late assignments will not be accepted; hand in what you have.

Demonstrations, On May 9th

Demonstrate your working program for your TA. This is also your opportunity to respond to criticisms of your final report.

Tournament, On May 11th

Each team may submit a program to participate in a single elimination antichess tournament. The tournament is optional, and will not affect your grade in any way. All students are welcome to attend and participate in the festivities. A nominal prize will be given to the winner. Additional information will be provided in a later handout.

Requirements Specification

The Game: Antichess

Antichess is a variant of chess in which the goal is to get rid of one's pieces. Here we describe how antichess is different from chess; the rules for chess are listed in Appendix A.

Player A wins the game against player B if:

all pieces of A except for the king are taken, or
player B checkmates player A.

The moves in Antichess differ from those in chess in that a player is forced to take the opponent's piece whenever that is possible. That is, if it is A's turn to move, and a piece of A is attacking a piece of B, then A must take that piece. If A can take several pieces of B, then A is free to choose the piece to take.

The king is special in that the foremost obligation of each player is to move the king out of a check. This overrides the rule to take the opponent's piece. However, 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.

As an example, suppose player A's king is under check from B's queen. Further, suppose A has two choices to move away from the check: move the king away or take B's queen. In this case, A must take B's queen.

In short, each move of player A must observe the following:

If A's king is under check, move it out of check.
If A can take one of B's pieces, then it must (unless disallowed by the previous rule).

For simplicity, some special moves in chess have been changed as follows in our version of antichess:

A pawn cannot move by two squares at the beginning.
Castling is not allowed.
En passant capture is not allowed.
When a pawn moves to the last row on the opposing side, it turns into a queen. (In normal chess, such a pawn can be turned into any piece of the player's choice.)

We shall play antichess with time restrictions, as is often the case in chess games. Each player is allocated a fixed amount of time to make all the moves in, say, 5 minutes. To this effect, there is a clock for each player that is set to 5 minutes at the start of the game. If it is player A's turn to move, A's clock will count down until the move is made. While it is B's turn to move, A's clock is suspended. 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 10 minutes, because by then at least one of the clocks would have run down to zero.

The Player/Referee Interface

The program is divided into two distinct parts: the machine player and the referee. The referee is responsible for maintaining the human interface: drawing the screen and reading keyboard and mouse input. It is also responsible for setting up the board, informing the players when it is their turn, fetching moves from the players, and keeping time. Your referee will allow a human to play against a machine player. The human will play white, and the computer will play black. The machine player will play the game against the user. It will receive updates on the state of the game from the referee, and choose a move on its turn. We will provide you with CLU abstractions defining the interface between referees and machine players. This interface will allow different machine players to be mixed and matched easily. At the end of the term, we will have a tournament in which the machine players implemented by students will play each other using a referee provided by us.

User Interface

Your referee will be responsible for drawing an up-to-date board. We have provided you with the {\tt window} abstraction to create an X-based interface. The abstraction is listed in /mit/6.170/ps5/src/window.spc. It allows the user to draw items like rectangles, buttons, and bitmaps on a window, and reports events like button-press, type-ins, and mouse-clicks. Your referee should also keep up-to-date displays of the following information (the format and layout of this information is up to you):

Player names, and the colors they are playing (black or white)
Whose move it is next
Time remaining on each player's clock. The time should be updated at the end of each move (we do not expect you to update the time during the moves.)
Any other status information.

Moves

Your referee should accept typed input. This will allow the human player to specify the move. The human player may type in a move of the form: Column1Row1-Column2Row2 (e.g. a1-b2). The columns are numbered 'a' to 'h' from left to right. The rows are numbered 1 to 8 from bottom to top.

Feel free to provide the user with other methods of entering moves, such as using the mouse.

Commands

In addition to moves, the referee must accept a number of commands for controlling the configuration and play of the game. Your design team must choose and document the method by which the user can input commands. For example, the slash (/) could bring up a list of possible commands, and the user could then type the first letter of the desired command. Other possible interfaces might make use of the mouse.

The commands recognized by antichess are:

NAME
Set the name of the current players. (Each player's name is printed with their score and remaining time.): TIME-LEFT
Set the amount of time that a specified player has.: SAVE
Save the current game into a file whose filename is specified by the user. The game continues after being saved. The format of the file is given in the Game File Format section.: LOAD
Replace the current game with the game saved in a file specified by the user.: NEW
Terminate current game and start a new one.: QUIT
Terminate current game and exit program.

The machine player should play more skillfully at a higher level than at a lower one. Apart from this requirement, your program will not be graded on the absolute level of the skill exhibited by your machine player. You should employ heuristics in your program to make it intelligent, but do not get bogged down in this process.

Game File Format

The figure below describes how antichess saves games into files.

The fields in the file are:

<next-turn-color> indicates which color moves next after the board is loaded (B or W).
<timeleft> is two numbers indicating the number of seconds left on each player's clock (white player first).
<board> describes the contents of each of the squares on the board. The first <piece> in the first <row> corresponds to square A1 on the display, and the last <piece> in the last <row> corresponds to square G7. An empty square is denoted by a hyphen, black pieces by lower case characters, and white pieces by upper case characters. (P/p = pawn, K/k= king, Q/q= queen, R/r= rook, B/b = bishop N/n = knight)

    <game-file> ::= <next-turn-color> newline
                    <timeleft> newline
                    <board>

    <next-turn-color> ::= B | W

    <timeleft> ::= <real> <real>

    <board> ::= <row> <row>  <row>  <row>  <row>  <row>  <row> <row>

    <row> ::= <piece> <piece> <piece> <piece> <piece> <piece> <piece> <piece>  newline

    <piece> ::= - | P | p | K | k | N | n | R | r | Q | q | B | b


			Figure.  Game File Format

As an example, the following figure shows the load file for the initial board configuration. Time left for each player is 5 minutes. In conventional chess layout, the white pieces are in the bottom two rows and black pieces in the top two.

                                  W
                                  300.0 300.0
                                  rnbqkbnr
                                  pppppppp
                                  --------
                                  --------
                                  --------
                                  --------
                                  PPPPPPPP
                                  RNBQKBNR


		Figure.  Load File for Initial Configuration

The Player/Referee Interface Specification

We have provided the specifications for the interface between the referee and the machine player. All of the interaction between the referee and the machine player must use this interface. You may not amend these specifications. If you have a problem with them, speak to your TA. This interface makes use of the standard string format for the board and a move. The standard format for a board is the same as the load file format. The standard format for a move is the five-character string described in the "Moves" Section above, such as a1-g7.

Machine Player Interface

(Some text omitted because it wasn't given to us in .tex form. Grrr.)

 % A machine player is a mutable data type reflecting the state and
 % strategy of a player in a game of antichess.

 options = null

 machine_player = data type is create, get_name, set_options, reset,  make_move

   create = proc (opts: options) returns (machine_player)
         % Effects: Returns a new machine player with the given options set.

   get_name = proc (p: machine_player) returns (string)
         % Effects: Returns a string name for the machine player.

   reset = proc (p: machine_player, board: string, opts: options)
         % Requires: board is a string representing a valid board.
         % Modifies: p
         % Effects: p is modified to reflect the new board and options (opts)
         %          preparatory to beginning a new game.

   set_options = proc (p: machine_player, opts: options)
         % Modifies: p
         % Effects: Reconfigures p's options.

   make_move = proc (p: machine_player,  opponent_move: string, 
		     timeleft: real, opponent_timeleft: real)
                     returns (string) signals (error(string))
         % Requires: opponent_move is a string representing a valid move
         %           by the opponent.
         % Modifies: p
         % Effects: Returns the next move of p, given the opponent's move 
         %          (opponent_move), the time left for p (timeleft), and
	 %	    the time left for the opponent (opponent_timeleft).
         %          (Note that p might take longer than timeleft, but then
         %          it stands to lose the game.)

 end machine_player

Hints

Design Matters Most

A good design will save you a lot of time later; it's well known that a small mistake made early in a project can become a big problem if it's not caught until much later. Think of the design as the major part of the project, and do it very carefully, trying to anticipate problems that may arise. Then your actual implementation will be more straightforward, and more fun. Validation shouldn't be an afterthought; you may choose a design because its implementation will be easier to test.

Don't Overdocument

Carefully worded amendments will save you the trouble of rewriting portions of the design. The final report is not a museum piece, so don't get carried away. Don't include any redundant material. For example, there's no need to explain the difference between black-box and glass-box testing; just indicate which of your test cases fall in each category. Incomplete documentation is better than no documentation at all. So when you're writing your code, if a potential problem or subtlety occurs to you, but you don't have time (or are unable) to formulate it properly, then just add a draft of a comment and mark it as such. Later, if you have time, you can go back and fix it. Being rigorous is not the same as belaboring the obvious. You can assume that your TA knows what a set or a stack is. There's no need to explain something from scratch when you can use standard terms and notions.

Don't Reinvent The Wheel

Part of being a good software engineer is knowing what you don't have to do. You'll find game playing algorithms in Winston and Horn's Artificial Intelligence. Use our window cluster to generate an X-based interface. The object files and the library are in /mit/6.170/lib. The specs are in /mit/6.170/ps5/src/window.spc. Our implementation of this cluster is based on the wish shell and the associated Tcl/Tk toolkit. We will try to ensure the availability of this shell on different platforms. Do not incorporate any other code in your project unless you clear it with your TA. While borrowing code from others is usually good software engineering practice, in this context it will be considered cheating.

Have Fun Being On A Team

Enjoy being part of a team. Run new ideas past your partners, and discuss problems with them. A good way to find a bug is to ask someone else to look at your code. If you're worried about finishing, start early!

Appendix A: Chess Rules

This section describes chess rules as given by F.I.D.E. (F.I.D.E. is the international organization that conducts the official World Chess Championship). Some of the rules that are not relevant for this project have been removed/modified.

The Chessboard

The game of chess is played between two opponents by moving pieces on a square board called a chessboard. The chessboard is composed of 64 equal squares. The eight vertical line 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 Pieces

At the beginning of the game, one player has 16 white pieces, and the other has 16 black pieces. These pieces are as follows:

A white king:          K            A black king:        k
A white queen:         Q            A black queen:       q
Two white rooks:       R            Two black rooks:     r
Two white knights:     N            Two black knights:   n
Two white bishops:     B            Two black bishops:   b
Eight white pawns:     P            Eight black pawns:   p

The initial position of the pieces on the chessboard is given below:


         The layout of a chess board at the beginning of the game.

The Moves

A move is defined by the following rules:

The player with the white pieces commences the game. The players alternate in making one move at a time until the game is completed.
A move is the transfer by a player of one of his pieces from one square to another square, which is either vacant or occupied by an opponent's piece.
No piece except the knight may cross a square occupied by another piece. That is, only the knight may leapfrog over another piece.
A piece played to a square occupied by an opponent's piece captures it as part of the same move. The captured piece is removed immediately from the chessboard.

Various pieces move in different ways:

The King The king moves to any adjoining square that is not attacked by an opponent's piece.
The Queen The queen moves to any square on the column, row, or the two diagonals on which it stands (except as limited by Rule 3).
The Rook The rook moves to any square (except as limited by rule 3 of Section \ref{move-def}) on the column or row on which it stands.
The Bishop The bishop moves to any square (except as limited by Rule 3) on the two diagonals on which it stands.
The Knight The knight's move is composed of two different steps; first, it makes one step of one single square along its row or column, and then, still moving away from the square of departure, one step of one single square on a diagonal. It does not matter if the square of the first step is occupied.
The Pawn The pawn may move only forward. It advances one vacant square along the column. When capturing, it advances one square along either of the diagonals on which it stands. On reaching the last row, a pawn must immediately be exchanged, as part of the same move, for (either) a queen, a rook, a bishop, or a knight, of the same color as the pawn, at the player's choice and without taking into account the other pieces still remaining on the chessboard. This exchange of a pawn for another piece is called promotion, and the effect of the promoted piece is immediate and permanent.

Check

The king is in check when the square it occupies is attacked 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 attacked by any of his opponent's pieces. Check must be parried by the move immediately following. If any check cannot be parried, the king is said to be checkmated or {\em mated}.

The Completed Game

The game is won by the player who has checkmated his opponent's king. This immediately ends the game.
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.