Assignment 6: Chess 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. Files 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. Overview 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.
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. Java Code that You have to Write 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) This should compute and return a 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. 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 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. 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 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. 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: Alpha-Beta search The evaluation function as described in Evaluator.java Simple Iterative Deepening: search at depths 1, 2, 3, etc. When time runs out. just use the best move found by the last completed search. You want to make it so that if it finds a mate, then it doesn't continue with deeper searches. 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. A repetition table: This keeps an integer count for all the positions played in the game, and all the positions on the current search path down to (but not including) the current position being evaluated. (To maintain this you'll need methods to query, increment and decrement these counts.) Inside of alpha-beta, right at the beginning, check if this position has occured at least 2 times before. If so, the value of the position is immediately returned as 0. Move Ordering: The best move found by each call to alpha-beta search is stored in a hash table. When doing the search at a position, we try the best move first. (Typically this move was found in a shallower depth search.) This is followed by the capture moves, which is followed by the rest of the moves. Quiescent Search: Instead of calling Evaluate.eval(b) at the end of the alpha-beta search (when depth=0) you call a new quiescent alpha-beta search instead. The main difference between quiescent search and alpha-beta is that a different set of moves is considered. (So it uses the same alpha and beta parameters, etc.) If the player to move is in check, then all moves are considered. If not, we consider a "stand pat" move, that is we just use the evaluator on the current board position as one of our options. And then all the capture moves are considered. The other moves are not considered. If this turns out to be too slow, then you can artificially cut it off at some depth, like 4 or 5. 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:- 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. 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 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);
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 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 Shows all the players currently logged on. finger Johnny This command shows Johnny's ratings, other statistics, and "finger notes", which are a user settable set of messages. If Johnny is omitted it uses yourself. 211 This command puts your program into the 211 pool. After waiting a while, it will automatically pair your program with another one in the pool. It uses a number of criteria to choose the match. It tries not to pair the same ones too many times in a row, and it tries to pair players of close ratings, etc. The 211 pool uses a time control of (3, 2), 3 minutes initial time and 2 seconds of increment. Once a game ends, you are automatically taken out of the 211 pool. If you want your program to stay in the 211 pool, then go to the Menu->Game->stay in the 211 pool. This just issues the 211 command again automatically when your match finishes, putting you back in the pool. This way you can leave your program running all the time, unattended. observe Johnny This allows you to watch Johnny's current game. Turn it off with 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 Automatically observe all of Johnny's games. Turn it off with follow. (This does not work in the EasyChess interface. If you want to use this feature, login to the chess server with BlitzIn.) best This command shows the best players in various rating categories. The "211" category is the one resulting from the 211 pool. Note that you cannot get into this list until you have played 20 games in the relevant category. rank Johnny An extension of best that tells me the rank of Johnny in all categories. match Johnny This issues a match request against a player named Johnny. Johnny can then 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 This issues a personal tell to Johnny of the message "hi". To talk to Johnny again, it's sufficient to use ". hi again". shout hello! This shouts a message to everybody logged on to the chess server. history Johnny This shows an index of the last 20 games played by Johnny (or you, if the name is omitted). Each game has a number to its left. You can use the 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 This displays the help file about the resign command. Of course there are help files for all other commands. 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:
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. Rules On your regular account ALL GAMES MUST BE PLAYED by your chess engine. You may not use any code other than that supplied by us. If you get ideas from the literature or the web, reference the source. You can work in teams of two. If both accounts of a team are in the rank list, we will use the higher one for purposes of grading. 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. Grading The assignment is out of 100 points. 70 points for your performance against BachChoy 20 points for your performance against JackBach 10 points assigned by TA based on looking at your code and documentation Up to 20 points of extra credit assigned for your performance in the 211 pool. 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 Keep different versions of your code. You may want to consider using CVS. If you ever accidentally make your bot worse, and can't figure out why, you can restore a previous version of your code. Test frequently. Test the performance of your program after every major change. 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 about.com article about opening playbook Google search for endgame strategy Daniel Sleator Last modified: Wed Nov 10 21:16:17 EST 2004
