| DUE December 10th, 11:59pm |
chess_java.jarThe supplied code to start working on your chess engine. gui.jarThe originally distributed EasyChess GUI. new_gui.jarNew 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.
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.
Move.java
ChessBoard.java
StandAlone.java (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 ChessBoard.java
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
Moves:
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 StandAlone.java for more features.
The file Engine.java contains some completed methods and some
incomplete ones. You must complete the following methods:
public Move computeMove(int timeleft, int optime) Move object. The two parameters
that it has are the time left on my clock and the time left on the opponent's
clock in seconds. (More on time controls below.) It's recommended that you
make use of an alpha-beta search, and an evaluation function for this part.
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 Evaluator.java 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.
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
Engine.java 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.
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.
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:-
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.
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.
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 Engine.java:
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);
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 hyper.link.cs.cmu.edu. Use port 5000. You can
connect to it and get the pure text interface with "telnet hyper.link.cs.cmu.edu
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.
who finger Johnny 211 observe Johnny observe. (This does not work in the EasyChess
interface. If you want to use this feature, login to the chess
server with BlitzIn.)
follow Johnny follow. (This does not work in the EasyChess
interface. If you want to use this feature, login to the chess
server with BlitzIn.)
best rank Johnny match Johnny accept the match, and the game starts. The default time control
for this game is also (3, 2), but the rating is in the blitz rating category,
not the 211 category. This is useful for comparing your program against other
specific opponents, and for playing the BachChoy bot to gauge the strength
of your program.
tell Johnny hi shout hello! history Johnny examine
Johnny 34 to see the moves of Johnny's game 34. Hit the enter key to
move through the game while in examine mode.
(This does not work in the EasyChess
interface. If you want to use this feature, login to the chess
server with BlitzIn.)
help resign 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 following bots should always be logged into the chess server waiting to play with you:
JSBach
StrongBach
JackBach
PDQBach
ReBach
BachChoy
BabyBach
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.
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.
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
about.com article about opening playbook
Google search for endgame strategy