Assignment 6: Chess
Danny Sleator and Pravir Gupta

CMU   15-211   Fall 2004

DUE December 10th, 11:59pm

Final Results

This page shows the results of the tournament, the extra credit 211 pool, and all of your games against BachChoy and JackBach.


chess_java.jar   The supplied code to start working on your chess engine.
gui.jar The originally distributed EasyChess GUI.
new_gui.jar New version of the GUI that supports observing games and allows your engine to send commands to the chess server.


In this assignment you will write a program that plays the game of chess. As you develop your program, and once it is completed, you can compete with other student's programs on a "chess server" that we have supplied. The chess server will give your program a chess rating, updated continuously as more games are played. You'll be able to see where your program stands in the ranking of all the other programs at any time by typing "best" on the chess server. We hope that this will be a really fun way for you to get your competitive juices flowing. Extra credit will be given to the top 20 finishers.

In addition to a chess server, we have supplied java code that does move generation (a non-trivial problem in itself), and a graphical user interface that lets your program connect to the chess server.

How will you know when your program is "good enough"? The answer is that there will be a "chess bot" called BachChoy on the chess server that you can have your program play against. As a minimum requirement, your program should be able to beat BachChoy consistently. For a perfect score on the assignment your engine should also be able to beat JackBach consistently.

Of course you can use any techniques you want, but we recommend that you take a look at the two lectures (games1, games2) about game programming and the references sited there. Feel free to look on the internet for ideas, but please, as always, all the code you submit must be your own. Of course you should cite any sources that you make use of.

We've supplied a lot of things here: move generator, GUI, chess server. There's a bit of work required to understand these things. But the actual programming required is just that of writing a chess search engine.

If you don't know the rules of chess, or chess terminology, here's a good tutorial.

You can work in groups of size up to 2 (two) for this assignment.

Supplied Java Code

We have given you 2 jar files - chess_java.jar and gui.jar. One of them is the GUI and the other one has the java files, some of which you have to modify. We've written the following complete java programs. You don't need to modify these although you're welcome to. (The text version)
A Move is an object that has the starting and ending points of a chess move. For castling the king's starting and ending points are used. A standard notation for a square of the chessboard is to indicate the file (a letter from a to h) and the rank (a number from 1 to 8). The ranks and files shown in the following diagram of the initial position of a chess game. In this notation, for example, the white queen is located on the square d1. (The white always has 1 and 2 rows and black always has 7 and 8 rows initially)

A move is often indicated by concatenating the starting square and the ending square. A typical first move is d2d4. (This used to be called pawn to king 4.) Our Move represents a move as four integers. The rank and file numbers are stored as integers from 0 to 7. So, the white queen is located on (3, 0). (Actually, you should modify the methods in the Move class with care, because some of them are used by StandAlone. In particular, the move notation must be standard.)

ChessBoard is a class that defines the state of a chess game. It also contains constructor methods initiating a position, and copying a position. It contains methods for generating all the legal Moves in a position and code that, given a Move updates the board state. It also contains a method for determining if the king is in check. A position with no legal moves in which the king is in check is checkmate. Check the public methods in and the comments for more information. The code is fairly elegant, but not particularly efficient.

StandAlone is a class that allows you to test your chess program in text-only mode by Playing against it. To do this just do

       java StandAlone
It will then print an ASCII board and prompt like this:
     Computer player: Quimbee Fonebone
     Starting new game with time control 5 0.
     Position (White to move):
        a b c d e f g h
     8 |r n b q k b n r| 8
     7 |p p p p p p p p| 7
     6 |- - - - - - - -| 6
     5 |- - - - - - - -| 5
     4 |- - - - - - - -| 4
     3 |- - - - - - - -| 3
     2 |P P P P P P P P| 2
     1 |R N B Q K B N R| 1
        a b c d e f g h
        h2h4 h2h3 g2g4 g2g3 g1f3 g1h3 f2f4 f2f3 e2e4 e2e3 
        d2d4 d2d3 c2c4 c2c3 b2b4 b2b3 b1a3 b1c3 a2a4 a2a3 
     White move (or "go" or "quit")>
At which point you can type in a move for white, or you can type "go" to tell it to make a move in the current position. StandAlone will access your program through methods you will write into a class called Engine (described below). It is also designed to work with a GUI called EasyChess.class (described below). Read the documentation inside of for more features.

Java Code that You have to Write

The file contains some completed methods and some incomplete ones. You must complete the following methods:

The rest of the public methods and definitions in this file should be left alone, because they may be used by StandAlone. The rest of the private methods are ones that we found useful in writing our solution. Feel free to use them, or not.

The file describes a method for doing chess evaluations, and it contains some tables of numbers that maybe useful for doing this. None of the code we've supplied (StandAlone, etc) depends on this.

About Time Controls

Let me say a little bit about time control. Each player in a chess game has a clock. The clock of the person whose turn it is counts down, the other player's clock stops. The player whose clock reaches zero loses. The time control is a pair of numbers (min, increment) which means that the clock initially has min minutes on it, and after a move is made the mover's clock gets increment seconds added onto his/her/its clock. The time control we'll be using to play your programs is (3,2) -- 3 minutes of initial time, and 2 seconds of increment.

The method allocateTime(int timeleft, int optime) is called at the beginning of computeMove. The two parameters are the time left for you and the time left for the opponent in seconds. Based on this, and the time control of the game, it figures out how much time to allocate for thinking about the next move. The boolean method timeup() should be called frequently during the search for a move to make. When it returns true this means that the search should wrap up quickly and return a move.

The code for allocateTime() is included in for you to look at. The way it computes this is that it assumes the game is going to last 30 more moves, so it allocates 1/30th of the remaining time, plus the increment, to the current move. You're welcome to change this if you want. The current version does not take the opponent's clock into account, although it could.

What You'll Need to Implement

The first reqirement is that your program be able to beat BachChoy. On a standard run-of-the-mill PC (2.2 GHZ), this can be done by implementing the following features: That's it. None of the more advanced features listed below are necessary.

For full credit, you're also required to beat JackBach. To do this you'll need to do quite a bit more. I found the following features (in addition to those above) sufficient to beat JackBach 95% of the time. Perhaps you won't need to implement all of these, or in exactly the same way. But this should be sufficient. These advanced techniques are described in more detail in my second lecture on game programming.

These advanced techniques are described in more detail in my second lecture on game programming.

Using the Java GUI

This software from gui.jar runs on all platforms. Put this in the same directory with all of your java files. To run your program, type 'java EasyChess'. You should see a login window where you have two options of logging in:-

  1. Login with your user name and password. In this case, click on 'Connect!' button. This will use your program to play the chess games. This is what you will be graded on.
  2. Login as a guest. You do not need to supply a username or password. Just click on the 'Login as Guest' button. The chess games that you play through this login will NOT use your chess program. You will have to make the moves using your mouse by clicking and dragging a piece.

Normally, you will log in to the chess server using the first option. However, for debugging purposes i.e. you want to play against your program, you can log in to the chess server twice (one as a guest where you make the move and one through your username, where your program makes a move) and then create an unrated match between them by typing 'match name 3 2'

Once you have logged in, you shall see the chess board, time control, message box and menu. While on the chess server your program can play others and get a rating. You can also chat with other people logged onto the server. More information below.

Playing against your program/Debugging

We have provided you a text interface and a GUI interface.

The text interface (type java StandAlone) does not connect to the server, but can be used for debugging and also playing against your program. Moreover, it does not do move validation, i.e. you can make an illegal move.

You can also debug through the GUI to play against your program as described in the above section.

Using the New Java GUI

The original GUI (above) is sufficient. But because of some small bugs, and features we wanted, we made a new version fo the GUI. It's new_gui.jar.

It allows you to observe games. It allows you to examine games, as long as you only go forward. It also allows your chess engine to issue commands to the chess server, such as "rematch" or "kib mate in 3, dude". To do this, create the following declaration and constructors in your

    public Hub theHub;

    Engine(Hub h) {
    	theHub = h;

    Engine() {
    	theHub = null;
Somewhere else in the code, when you want to send a command to the chess server by calling sendCommand() as shown below:
     if (theHub != null) theHub.sendCommand("kib "+str);

Chess Server

Everybody in the class has one account on the 211 Chess Server. Your account name is your andrew ID, and your password should have already been emailed to you. All games played on this account MUST BE PLAYED BY YOUR CHESS ENGINE. You can use the guest account to play games manually. (If you're running windows, you may want to try the Internet Chess Club's BlitzIn interface.) The machine hosting our chess server is Use port 5000. You can connect to it and get the pure text interface with "telnet 5000".

The chess server has a very rich functionality, that takes hundreds of pages to describe. For now, here are some very basic commands that should get you started. These are typed into the bottom of the "main consol" window of the GUI.

For more information about the chess server, a good summary document to read is this introduction. There are individual help files for each command. This page lists all of them, and has links to the files. (Not all of these commands will work on our 211 server, for example, the "5-minute" command has been replaced by the "211" command.)

In our chess server, the game is immediately declared a draw when a position has occured 3 times (twice before), or when 100 moves have been made in a row (count moves of both sides) where none of the moves are pawn moves, castling moves, or captures. (In usual chess declaring a draw in these situations requires that one side ask for a draw. Here we do this automatically, to eliminate the problem of having to decide when to offer a draw.)

The Bach Family

The following bots should always be logged into the chess server waiting to play with you:

These are listed from strongest to weakest. To start a game with, for example, BachChoy, type "match bachchoy". These bots can play several games at once. As you improve your program you can move up the list and try to beat them all.


HandIn Instructions

You must handin all of the java classes that you use, including the ones we supplied, even if you didn't change them.

You are required to also submit README.txt, which should list your name and your partner's name (if applicable), and include a paragraph describing the algorithms used in your chess bot.


The assignment is out of 100 points.

The points against BachChoy will be assigned as follows. (To play BachChoy type "match bachchoy".) We'll look at your last 10 games against BachChoy. We'll compute your score as follows: 1 for each win, 1/2 for each draw, 0 for each loss. We'll then multiply this total by 7 to convert this to points. We'll do the same thing for JackBach, except the multiplier will be 2. (The server logs all games played, so we'll use that to see your games.) (All of these games should be played with the standard 3 2 time control.) Notice that it does not matter if you lose a million games in a row against BachChoy, as long as you win your last 10 games you get full credit for BachChoy.

Here's how the 20 extra credit points for the 211 pool will be computed. You have to play at least 20 games in the 211 category. Then your rating will be established, and you'll be listed in the best and rank lists in the 211 category. Right after the moment the assignment is due, we'll take a snapshot of the entire 211 rank list. Only the top 20 finishers (who are enrolled as students in this course) will get extra credit points. The top finisher will get 20 points, the next will get 19 points, ... the 20th will get 1 point.

Tips and Resources

Here are some links to Google searches and web sites that you might find useful:
Bruce Moreland's Tutorial on Chess Programming
a search for iterative deepening on Google
quiescence search
Google search for information on evaluation functions
Google search for move ordering article about opening playbook
Google search for endgame strategy

Daniel Sleator
Last modified: Wed Nov 10 21:16:17 EST 2004