Chess Applet - Homeostatic Chess Player

Chess applet version 5.05, compiled September 16, 2004.

Play chess against your computer. Click the piece you want to move and click the
square you want to move it to. By default the human is white, the machine is black.

About the Chess Applet

I named this computer chess applet a "homeostatic chess player" in honor of Philip K. Dick, the science fiction writer, who, in his stories, called his artificial intelligence (AI) devices "homeostatic." This online chess player is homeostatic in the sense that a well played chess game is a balance on the lines of strong moves in the chess game tree. By playing chess with this applet you are participating in an AI research experiment in distributed computation. Moves computed on your machine are sent to the chess memory server for storage and possible reuse. This is a good chess applet to play with for the following reasons:

Completeness: The applet implements the complete set of chess rules, including en passant (EP) capture, pawn promotion, castling, draw by stalemate, draw by repetition, draw by lack of progress, and optional time control.
Functionality: The chess applet is easy to use with mouse clicks to designate moves, sound and color to prompt the user or give feedback as appropriate, automatic generation of an algebraic notation game listing, and it allows users to change sides.
Server Features: The chess data server allows the user to save and restore games. Applet-computed moves are stored at the server for future use resulting in faster response and optimal playing strength.
Development: The applet is written with strict object oriented (OO) discipline for easier development and maintenance.
Performance: On fast hardware, the applet will challenge the average chess player and will occasionally beat the expert player. Playing strength will be improved by running the chess applet on faster hardware: it adjusts its look-ahead depth to fit your machine's power.

For more information about the operation of this client-server chess system, see our paper "A Distributed Model for Game Computing", which provides additional technical details. I hope you enjoy playing against the object oriented chess applet. It will average about one and a half minutes of thinking time per move. You can start a new browser session and let it run in the background while you work on other things, such as reading the rest of this page. It will "ding" when it has made its move (assuming your system supports sound).

One of the most rewarding things about writing this chess-playing applet is the large number of problems that had to be solved. This chess applet is written in Java using the Sun Java development kit (J2SE) so it will run on a wide variety of computers, including Apple Macintosh, Intel with Windows, OS/2, Linux, and many Unix machines.

Writing the program in Java provides portability among computers and operating systems. Writing it as an applet makes it easily distributed: anyone with an Internet connection and a Web browser can run (play) it. Writing it using the OO paradigm makes it easier to develop and maintain. The complete, fully operational, and tested applet took only about 100 hours to create (including design, coding, and testing). However, the Java language brings some performance issues to the programming problem. In fact, the chess applet runs 10 to 20 times slower than some chess programs written or compiled for specific hardware or operating systems. This results in the applet taking longer to look a certain number of moves ahead, or in looking fewer moves ahead for a given time. However, most people are not chess experts and will not mind having a slightly weaker computer opponent for recreational play.

Performance

If performance were the driving concern I wouldn't have written it in Java. I regard the applet primarily as a study in OO design. Different Java runtime implementations in various browser versions have widely varying performance (more than a factor of two) on the same hardware. As a study in OO design, this applet demonstrates the potential of an OO approach to AI software in general.

The chess applet adapts its performance to your platform (hardware and runtime). If it moves in less than 30 seconds (averaged over the last two moves), on the next move it will look one half move further ahead. If it takes it longer than 200 seconds to move (a weighted average over the last four computer moves), on the next move it will look one half move less far ahead. If you find the playing strength of this applet to be too weak, it will be improved by running it on faster hardware.

There is a "computational wall" that AI programs tend to hit. Chess (and other games, such as go) belongs to this class of problems in computer science called "intractable," due to the "combinatorial explosion" of the branching of the chess game tree. The average branching factor of the chess game tree is about 34 for the whole game, and about 40 between 10 and 30 moves.

The fact of the computational difficulty of chess play underscores the remarkability of the achievement of IBM's Deep Blue chess computer which defeated the world's best human player, then world champion Garry Kasparov, in a fair match. That specialized machine could look ahead a full 12 moves (24 tempi). Shortly after Deep Blue's victory in 1997, I publicly predicted that it would never again lose a game to a human player under match conditions. To date, my prediction holds true. Deep Blue was subsequently disassembled and will likely never play again. Any future major effort at a chess computer is likely to be significantly more powerful than Deep Blue. Thus we may say that generally, humans are no longer better than computers at chess. The game of go, however, is even "more intractable" than chess, and it will be many years before computers will be able to beat the best human players at go.

Applet Design

Java is an object oriented language that encourages object oriented design. The chess applet was written using strict OO discipline. All object data are declared private with public accessor and mutator functions. For the interested programmer, general information on computer chess programming is available at the Computer Chess Programming page.

Chess Modeling

The design goal is to have a simple, flexible, maintainable applet that is complete and correct in its play, and that uses the classic minimax (AKA min-max) algorithm for finding the best move. Central to achieving this design goal is to have an optimal chess model. Defining a good chess model is not a trivial problem. Here is my solution:

I initially attempted to have a piece-centric (rather than board-centric) model, but was not able to get away from a chess board representation. With a piece-centric model, each piece will have knowledge of its location (or relationships to other pieces) and what its legal moves are. With a board-centric model, the board keeps the location of the pieces. My model has aspects of both in a way that I believe is optimal (for an OO approach).

The chess board is modeled as a 2D array of chess pieces. Empty squares have "null" for their pieces. Each piece has a "square" (rank and file) that it stands on and a list of squares it can move to in the next turn (a Vector of legal moves).

For the chess configuration space search algorithm, a tree node object is needed which has a configuration (chess board) and a chess board evaluation function. The game node keeps a Vector of child game nodes for recursive search (min-max with alpha-beta pruning). The game node object also has a "best" configuration to carry to the top of the tree when the search is complete. The applet itself also keeps a current board configuration. The applet also knows how to draw the chessboard and pieces and to interact with the user. To summarize, the following classes are defined:

Square, a location (rank and file) with some state data for en passant capture and pawn promotion.
ChessPiece, a representation of a piece with material value, location (Square), state data, a Vector of Squares (legal moves) and legal move generation functions.
ChessBoard, an array of ChessPieces with some state variables and piece movement functions.
GameNode, a node in the chess game tree that has a ChessBoard to represent a point in the chess configuration space, a ChessBoard to represent the best move, and a Vector of GameNodes to represent the next available moves.
Chess, the applet itself, which has a ChessBoard and a chess game tree represented by a root GameNode.

Search Heuristics

In theory, a powerful enough computer could play perfect chess without heuristics simply by searching the game tree and evaluating positions on win-lose-draw criteria. However, in practice, available computers have difficulty looking more than a few moves ahead. Hence, some simple heuristics can help enormously in making the computer behave more intelligently.

The first heuristic is material value. A queen is more valuable than a knight, for example. My piece valuation system is based on traditional chess theory, with valuation as follows:

Pawn: 1.
Knight: 3.
Bishop: 3.5.
Rook: 5.
Queen: 9.

The material value heuristic takes precedence over positional subtleties. However, play is noticibly improved by adding a "freedom" heuristic: A position that has more legal moves available for one side than the other is better than one that does not. This heuristic is easy to implement by merely summing the legal moves available to each side and taking the difference. This heuristic encourages "freeing" moves in the opening, for example.

The third heuristic I implemented encourages moving each piece only once in the opening. Each piece is initially given a small penalty that is removed after it has been moved. "Piece" for this purpose does not include pawns, of course. Castling relieves the penalty doubly, and is thus encouraged.

Game tree search is depth first to a set depth that varies with computer performance. I used depth first search (rather than breadth first) so that child nodes could be destroyed before the full search is complete, saving memory.

Another search heuristic I implemented, that seems to improve play, is a truncated quiescense search. For any given move at the prescribed maximal search depth, if the move is a capture move, the algorithm will search one or two more levels, depending on whether the search depth is odd or even. The idea is that we want the final capture move to be by the player's opponent. An untruncated quiescence search was found to take too long. The current search depth is indicated in the Java console (from the "View" or "Window" menu of your browser).

A final heuristic is a small reward for advancing a pawn to help in the end game.

The position metric shown at the bottom of the board after each computer move is the future (look-ahead depth) board evaluation of the displayed position. A positive position metric is good for white.

Applet Features

Thinking Message

While the applet is thinking, it displays a text message showing the move being evaluated. For example:

Considering c5 (21) of 30 moves, 39 replies, 1852544 positions: Bc5 (0.47753)

This means that its option of moving a pawn to c5 is being considered, that it's the 21st of 30 moves to consider, that for this particular move, white has 39 replies, that so far it has looked at over 1.8 million board positions, and that moving its bishop to c5 is the best move found so far, with a position metric of 0.47753, which favors white. This message is updated every time it begins to evaluate another move. In this example, the message will be updated a total of 30 times before the computer makes its move.

Game Listing

Version 1.60 (March 23, 2001) indroduces the game listing feature. Clicking the "Show Listing" button toggles the visibility of the game listing text area to show a text record of the moves of the current game. This record may be copied and pasted into any text application for a permanent record.

Sound

The chess applet plays various sounds upon certain events. The startup sound clips and the reset sound clips are from the movies War Games and 2001: A Space Oddyssey. All sound files were obtained from public domain Web sites and are assigned to the following events:

Startup sound ("Shall we play a game?" from War Games), a long sound.
Alternate startup sound ("Would you like to play a game of chess? I play very well." HAL 9000 computer from 2001 Space Odyssey), a long sound.
Reset sound. ("Wouldn't you rather play a game of chess?" from War Games), a long sound.
Laughter sound on computer win (long sound).
Scream sound on computer loss (long sound).
Ding sound after computer move.
Sound for check.
Sound on illegal user move.
Vomit sound if user tries to move into check.
Sigh sound if computer resigns.
Fanfare sound on pawn promotion.
Yawn sound on a drawn game.

Version 1.61 (March 28, 2001) indroduces a feature to disable the long sounds that play when checkmate occurs or when resetting the board. Clicking the "Disable Sound" button toggles the enabled state of the long sounds.

Saving and Opening Games

The save and open features, incorporated in version 2.24, require that a chess data server be operational at the applet Web service site (as is the case here). When a game is saved, the applet assigns the session number to it and displays that number in the message text at the bottom of the applet. The saved game number is also written to the java console. To open a game at a later time, double click the file with the number of the game in the list box that appears when the "Open Game" button is pushed. It may take a few seconds for the game to load, depending on network traffic. Games may only be saved or opened when the computer is not thinking about its next move.

Forcing the Computer to Make its Move

Version 2.29 lets the user force the computer to stop thinking and make it's move with the control-M key combination. This might be useful if you want to reset the board for a new game, for instance. Be aware that if this feature is used, the computer will not have finished considering all its moves, and its play for that move will be weakened.

Client-Server Memory

Version 3.00 introduces client-server memory. Each time the computer is to move, it will first query the server move database to see if that position is on record. If so, the recommended move is returned along with the search depth that move was computed with. If the current applet instance is using an equal or shallower search depth, the server move will be used. If the current applet is searching deeper, the applet will compute the move. Moves computed by the applet are sent to the server for storage for future use. Using client-server memory makes the applet respond faster for cases when the move is found on the server. The client-server memory can make the applet play stronger by using stored moves computed on faster hardware.

Control Key Summary

Some of the chess applet features are accessed via control key combinations. Click on the applet to be sure it has the focus before giving a control key command. Control key feedback is via the Java console. Microsoft's Internet Explorer (MSIE) requires that the Java console be enabled via the "advanced" Internet options before it can be selected from the View menu. The following control key combinations are implemented:

Control-A Toggles automove. When toggled on, the computer will compute white's next move. When toggled off, if it's white's move, the computer will complete white's move computation and then play black's move normally. The start-up default is off.
Control-B Toggles remembered position use. When toggled on, the applet will use its remembered positions (if appropriate) instead of computing the next move. When toggled off, the applet will compute the next move, even if the current position and recommended move for the current or deeper search depth are contained in memory. The start-up default is memory use on.
Control-C Switches sides. If the computer was playing black, the computer plays white, and vice versa. Can only be used when the computer is not thinking about its next move.
Control-D Decrements the search depth for the next move computation. Can only be used when the computer is not thinking about its next move. This can be useful if you are impatient or desire a weaker computer opponent.
Control-H Toggles human vs. human play. Can only be used when the computer is not thinking about its next move. Useful for setting up positions for the computer to analyze.
Control-I Increments the search depth for the next move computation. Can only be used when the computer is not thinking about its next move. This can be useful for increasing the first move search depth if your computer hardware is extraordinarily powerful.
Control-M Forces the computer to stop thinking and make the move immediately.
Control-N Toggles the newby mode in which the squares a human player's piece can move to are highlighted in yellow when the user moves his mouse over the square the piece is on. Default is on.
Control-P Prints the current board position as a coded string to the Java console.
Control-R Rotates the board orientation. Default is with white below, black above.
Control-T Toggles the timed game mode. When enabled, each player has 90 minutes of cumulative thinking time in which to play the first 40 moves of the game. After 40 moves, an additional 60 minutes are allowed. The first player to run out of time loses. Default is off.
Control-V Toggles the verbose mode for additional information in the Java console. Default is off.
Control-[ (left bracket) Decreases the chess piece color contrast. For German keyboards use STRG-ü (STRG = Steuerung = Control).
Control-] (right bracket) Increases the chess piece color contrast. For German keyboards use STRG-+ (STRG = Steuerung = Control). Thanks to Captain for advice on the German keyboard combinations.
1 Sets the default piece color scheme: coffee and cream.
2 Sets a chess piece color scheme (verdant).
3 Sets a chess piece color scheme (indigo).
4 Sets a chess piece color scheme (royal).
5 Sets a chess piece color scheme (plum).
6 Sets a chess piece color scheme (rust).

Oracle Test Cases

An "oracle" is a test case with a known solution. The first four saved games are oracle test cases which any computer chess player should handle correctly with some minimum search depth. Test case one (g0000000001.txt) works correctly with a search depth of three or more. Turn off memory when trying the test cases with Control-B so that the applet thinks for itself. Then hit Control-C to make it compute white's move. After check, hit Control-C again to make it compute black's move. It should interpose the rook (and not counter check).

Test case two (g0000000002.txt) should work correctly with a search depth of four or more. Move the white knight to g6 and hit Control-C. The computer as black should save the king, not the rook.

Test case three (g0000000003.txt) should work correctly with a search depth of three or more. Hit Control-C and white should mate immediately.

Test case four (g0000000004.txt) should work correctly with a search depth of five or more. Hit Control-A and the white king should capture the pawn.

Known Limitations

The following are the known limitations of the chess applet. At this time there are no plans to amend any of them.

The applet does not enforce "touch move." Official chess rules require that a player move the first piece he touches (except for piece adjustment, which does not apply here).
The applet does not allow the taking back of moves (and neither do the rules of chess).
Some browsers will re-initialize the applet when returning to the page. To prevent the loss of game data, save your game before leaving the page.
The applet does not think during the human's turn to move.
In the timed game mode, upon notification of game loss, the players are allowed to continue play.
The applet allows the saving of games only if it is white's move or if the game is over. If you are playing black and wish to save the game, after the computer (white) has made its move, switch to the human vs. human mode (control-H), make your move, and then save the game. Start the computer thinking (control-C) to resume play.
The saved game file format contains the game listing, board position, and player to move information, not the sequence of moves, so draw by repetition recognition state is not preserved. That is, if you save a game and reopen it later and enter a repeated position, a draw by repetition that includes a position prior to saving will not be recognized.
The control buttons are too wide on MS Windows machines with the non-default "large fonts" selected in the screen settings. They are still usable, but the left- and right-most buttons will be partly off the applet frame.
When a game is saved after checkmate, it is possible, with some configurations, upon opening the game, to continue play. The fact that the game is over is not one of the attributes that is saved with the game. However, the game listing will generally indicate the checkmate condition.
Source code is available to academic researchers only. Please send your source code request to Dr. Rick Wagner (Wagner at Pollux dot USC dot edu) with your educational institution, a description of your research project, and your affirmation of your intent to safeguard the software from unauthorized copying, to properly attribute the source and to keep notifications such as this one with all derived products. I will respond to email source code requests sent from educational institution mail servers.

Version History

Thanks go to Harald Schifferl for his patience in testing and reporting bugs. Please report any bugs to wagner at pollux dot usc dot edu

1.00 February 2, 2001: Development started, Chess.java file created, the board was drawn
with character piece representations. Only pawn moves were under development in this
first version.

1.38 February 26, 2001: all basic features operational for complete and correct chess
play. The chess applet was Web published for testing on this day.

1.50 March 15, 2001: Sound feature added to the applet.

1.60 March 23, 2001: This version adds the game list text box feature.

1.61 March 27, 2001: This version adds the feature to disable the long playing sounds.

1.62 March 30, 2001: Adds the rank and file digits and letters to the chessboard.

1.65 May 23, 2001: Changes the elapsed time limits to 30 < e.t. < 600 s. Sets a minimum
recursion depth to 3 half-moves, preventing a counter-check tactic. Also fixes
a bug in interposing a piece in detection of checkmate by a queen.

1.67 February 14, 2002: Adds the move being considered to the message label when it's
the computer's turn to move.

1.69 February 15, 2002: Allows the setting of the thinking time boundaries in the applet
parameters.

1.70 February 17, 2002: Adds the number of the move being considered to the message label.

1.72 February 20, 2002: Implements testing for a draw by stalemate.

1.75 February 25, 2002: Implements testing for a draw by repetition and testing for a draw
by lack of progress (no irreversible moves for 50 moves). Fixes a bug in checking for
off-board moves in the generation of king moves.

1.76 February 26, 2002: Fixes a bug in the detection of a draw by repetition.

1.78 February 27, 2002: Fixes a bug in en passant capture by white.

1.80 February 27, 2002: Fixes a bug in the detection of a draw by stalemate.

1.82 March 1, 2002: Fixes a bug in the detection of checkmate and also fixes a bug
that allowed a counter-checking tactic.

1.84 March 1, 2002: Simplifies the function checkmateP().

1.85 March 4, 2002: Improves user messages in draw situations.

1.87 March 5, 2002: Fixes a bug added in versin 1.84 in the simplification of the checkmate
detection function checkmateP().

1.90 March 6, 2001: Fixes a bug in the detection of checkmate that would erroneously allow
the capture by or interposition of a pinned piece.

1.93 March 7, 2002: Fixes a bug, found by Harald Schifferl, in the determination of the
legal moves of a king. Improves search efficiency slightly by not considering the
moves of knights pinned to kings.

2.00 March 8, 2002: Improves performance slightly by fixing a minor bug in the search depth
computation and by removing some error trapping code. Removes some unused functions
from the source code. Adjusts evaluation parameters slightly for stronger play in the
opening.

2.08 March 12, 2002: Fixes a minor bug in refreshing legal moves. Improves performance
slightly by not considering moves of bishops pinned to kings by rook mode nor moves of
rooks pinned to kings by bishop mode. Disambiguates notation in the game listing when
more than one of a piece type might make the move.

2.11 March 14, 2002: Fixes three minor bugs in generating the kings' moves: it would
occasionally allow a king to check the other king, it would allow the king to capture
a supported piece, and it inappropriately allowed kings' moves into check by pawns.
4874 lines of code, including comments and white space.

2.14 March 18, 2002: Reduces code size by loop rolling the generation of knight and king
moves, making the source easier to maintain. 4463 lines of code.

2.24 March 27, 2002: Adds the save and load game features. 4751 lines of code and adds the
two files ChessDataClient.java and ChessDataServer.java.

2.29 March 29, 2002: Allows the user to force the computer to make it's move with the
control-M key combination. 4803 lines of code.

2.42 April 10, 2002: Adds the game file list feature for opening games. 4803 lines of code.

2.50 May 22, 2002: Fixes a rare bug in which the black king while in check under a mating
attack might retreat to the square in line with the checking piece. 4877 lines of
code.

2.56 June 11, 2002: Simplifies the computeMove() function and makes quiescence search depth
a function of the general search depth for stronger play. 4962 lines of code.

2.61 June 14, 2002: Fixes a bug in setPiece() in which extra EP capture indications were
generated. Results in slightly increased efficiency.

2.63 June 17, 2002: Implements computer resignation: the computer will resign if it sees
a forced mate coming. 4900 lines of code.

2.69 June 29, 2002: Correctness first, then performance. Implements alpha-beta pruning
for deeper thinking. 5083 lines of code.

2.82 July 10, 2002: Implements the auto-play feature, toggled on and off by control-A. Now
the user can watch the computer play against itself. 5467 lines of code, including
comments.

3.02 July 25, 2002: Implements chess server memory. In this version, the applet requests
a position query and waits for the server callback. If the position is not found for
the current or higher search depth, or if the server doesn't reply in five seconds,
the applet computes the move and sends the result to the server for storage. 5964
lines of code, including comments.

3.12 August 8, 2002: Implements the control-R key combination for board rotation.
6196 lines of code, including comments.

3.18 August 6, 2002: Implements the control-I and control-D key combinations for board
search depth incrementing and decrementing. 6248 lines of code, including comments.

3.22 August 23, 2002: Implements search depth boost computation based on hardware
perforamance. The base six log of one over the test time duration is used to
increment the default recursion limit. 6283 lines of code, including comments.

3.56 October 7, 2002: Adds the best move found so far to the "thinking" message.

4.00 October 31, 2002: Adds the chess piece color and contrast feature. 6575 lines of code.

4.07 November 6, 2002: Compiled with JDK v. 1.3.1. Compiled using the -O (optimize)
switch for 10% more speed in move computation. Refines the alebraic notation
function to more fully accord with convention.

4.17 February 18, 2003: Fixes a bug in disabling server memory use in duplicate positions.

4.21 June 10, 2003: Fixes a bug in dealing with pinned pieces.

4.22 December 16, 2003: Fixes another bug in dealing with pinned pieces.

4.26 January 29, 2004: Changes the client default socket port to 443 and adds code for setting
the port with applet parameters.

4.27 March 22, 2004: Adds recursion limit incrementing in duplicate positions to try to avoid
draws by repetition when the opponent is losing. Changes the default port back to 1997.

5.04 June 11, 2004: Changes chess memory and data service to MySQL server for hosting at
chess.captain.at. Major upgrade by Hannes "Captain" Mayer, compiled for publication
by Rick Wagner with JDK on Windows NT, in order to back off from the "bleeding edge."

5.05 September 16, 2004: Fixes a bug in the detection of pinned pieces. Thanks to Vleriy
Diatchenko and Dr. Bob Hosken who both found the bug in the same week.

Unrelated Links

A General Order(n) Sort

FixtureNet III

Robotics Instruction Course

Bill Johnson Landscape Photography

Chess player Dr. Walter Wagner's World Botanical Gardens.

Autobiography of Rick Wagner

Strangelets: The Strange Matter of Planetary Destruction

Captain's Ancient Coins site.

Cosmic rays: a muon detector.

Poetry by Annie Moses.

Click the Extreme Tracker icon to see statistics for this page.

This page created February 15, 2001.
Last updated: September 17, 2004 19:00:10 GMT

Your comments are welcome: RickWagner at ACM dot org.