A Distributed Model for Game Computing

Harald Schifferl and Rick Wagner
Accepted for presentation at the
Third International Conference on Application and Development of Computer Games
April, 2004, City University of Hong Kong, HKSAR.

Abstract

Computer games research has had positive results in many areas of application. We used a chess playing applet to investigate distributed computation with centralized storage of computation results. The average branching factor of the chess game tree is about 30, making computation of the full game tree (to a depth of 30 moves or more) infeasible. However, as a contest between two players, the number of acceptable (strong) moves at any time is limited, making the branching factor of the tree of "competent games" small enough to make storing a pre-computed database of moves feasible with regard to storage space. Distributing the computation of the move database makes the computation feasible with regard to time. We describe a system using a Web browser applet for distributed computation of chess moves and a chess data server for storing the computation results. The database of moves speeds up the chess play of the applet (when the move is found in the database) and the distributed applet computation of moves generates the database. Moves computed on faster hardware to a deeper search depth replace moves computed with a shallower depth so the database evolves (contains stronger moves) as hardware becomes faster over time. Results from public testing over a one-year period are reported.

1. Introduction

The game of chess is a good application for investigating our distributed model for game computing [8]. There is a large organized community of tournament rated chess players around the world and many of them are active participants in the World Wide Web. Getting a large number of good players to use our applet is important for testing our system. We developed a chess-playing Java applet that uses the classic min-max algorithm with alpha-beta pruning with a variable depth search for move computation. For normal play, the applet adjusts its search depth to give reasonably fast response for the hardware on which it finds itself running. Special parameters allowed us to fix the search depth for test purposes, and we let the applet play against itself to gather branching factor data for various search depths. The resulting data for 20 games at five different search depths are plotted below in Figure 1:


Figure 1: Branching factor vs. move number, average
of four games. Branching factor is further smoothed
by averaging over four moves within each game.

As can be seen from the data of Figure 1, the average branching factor of the chess game tree is about 30. These 30 moves are the set of possible (legal) moves from which the chessplayer selects. If we look at just the first 50 moves of the games of Figure 1, the average branching factor is about 34. In practice, however, chessplayers (human or otherwise) will choose from a small "strong" subset of the possible moves. In some cases, that strong subset will be as small as one (a forced move) and typically contains only a few moves. Chess analysts categorize the relative strength (or weakness) of a move as follows:

A weak move in an annotated game is labeled with one or more question marks. A single best but non-obvious move in an annotated game is labled with an exclamation mark. Figure 2, below, shows average branching factor as a function of search depth. There seems to be a definite decreasing trend downward with search depth. This is probably due to "smarter" play (which we assume is the case when the computer looks further ahead) tending to suppress the opponent's options more than being able to increase one's own.


Figure 2: Branching factor vs. search depth.

While the player is faced with an average of 30 or so legal moves on any given turn of play, he actually selects from a much smaller set of strong moves. If he fails to do so, he is faced with a weakened position. Small weaknesses are cumulative and rapidly result in defeat. Thus, expert players are walking a fine line in the game tree. Experience in tournament play, inspection of chess book openings, and over-the-board analysis leads us to the following conjecture:

Conjecture: The average branching factor of the strong chess game tree is less than two.

Chess games between competent players are generally won or lost in the middle game, so we are primarily interested in the first 30 moves of the game tree. If the conjecture is true, then storing the strong chess game tree to a depth of 30 moves (60 tempi) is feasible on a commonly available server. If the average strong move branching factor is 1.5, the number of positions to be stored is:

1.560 = 37 x 109

If each move requires a few (a hundred or so) bytes of storage, then that number of moves will fit within virtual memory in a good commercially available server. Inspection of references for "book" openings [1][2] shows the branching factor for recognized playable openings to be significantly below two. For example, in the venerable King's Gambit (1 e4 e5 2 f4 exf4 3 Nf3 g5) in Modern Chess Openings [1], the average branching factor for moves four through 10 (14 tempi) is 1.312. In the same book, the Queen's Gambit Declined, Orthodox Defense (1 d4 d5 2 c4 e6 3 Nc3 Nf6 4 Bg5 Be7 5 e3 0-0 6 Nf3 Nbd7 7 Rc1 c6 8 Bd3 dxc4 9 Bxc4 Nd5 10 Bxe7 Qxe7 11 0-0 Nxc3 12 Rxc3 e5) average branching factor for moves 13 through 19 (also 14 tempi) is 1.448.

Figure 1 shows that the legal move branching factor rises quite rapidly in the first five moves, and then levels off, so if the number of possible (legal) moves at any turn is an indication of the number of strong moves at any turn, then the analytical result for the opening stage of the game should also be applicable to the middle game. Corroborating evidence of the middle game strong move branching factor conjecture is available from analysis of some selected master chess games presented in the monthly pedagogical chess column Solitaire Chess by Bruce Pandolfini, appearing in Chess Life [6]. In the five top world player games analyzed in the April through August issues, covering white's moves ranging from move 10 through move 34, the average branching factor of strong moves is 1.08.

To investigate this conjecture and its implications, we created client-server extensions to a chess applet residing on a Web server (see http://rjwagner49.com/Robotics/Software/Applet/Chess/).

1.1 System Description

The client-server system consists of a Web-served chess-playing applet and a chess data server running on the same hardware as the Web service. Every time a user reaches the page with the applet, the applet sends some client system information to the server, which returns a sequential user ID number. The ID number is used for uniquely identifying chess game files saved on the server. When a move is made with the applet (either human or computer move), the game configuration (position and player to move) is sent to the server which then looks up the game configuration. If it exists in the database, the computed move (for that game configuration) is returned to the applet. If it is not there, "not found" is returned.

If the database move is returned to the applet, that move is used if it was computed at the same or greater search depth the applet is currently using. If not, the applet computes the move locally and sends the result to the server for storage. A functional flow diagram of the applet user and client/server interfaces is shown below in Figure 3.


Figure 3: Chess move functional flow diagram.

When the user performs an action such as moving a piece (the mousedown() function) or hitting a relevant keystroke (the keydown() function), an applet thread runs (the run() function) to perform the move. If server memory is not being used or if the move-getting timer times out (five seconds), the move is computed locally with the localMove() function.

2. Algorithm

2.1 Chess Data Server

The chess data server is a Java application that listens for socket connections from client applets. When a connection is made, the server spawns a new process thread to handle the communication. Service requests fall into the following categories:

2.1.1 Request for Session ID

The request for session ID is accompanied by the date, time, and operating system of the client platform. This information is stored sequentially in a file with the numerical session ID. In this way, connection statistics are maintained. The session ID is then sent to the applet.

2.1.2 Request to Open a Game

The server first reads the game file names from the disk and sends them to the client applet, which displays them in a list box from which the user picks. The desired game is then sent to the server. Games are identified by session ID. The appropriate game file is opened and its contents sent to the applet where it is displayed for continued play.

2.1.3 Request to Save a Game

The game information is saved to a disk file using the session ID to generate the file name.

2.1.4 Request to Store a Computed Move

The game configuration (board position and player to move), search depth for the computation, and move are inserted into a proprietary object oriented tree data structure. The insert operation is constant time (it will not increase as the database grows). The data structure is in server RAM (or virtual memory). These data are also stored as records in a data file, so that when the server starts up it can generate the tree data structure in RAM for fast realtime service to multiple applets. The insert operation will replace a move computed at a shallower search depth.

2.1.4 Request for a Computed Move

The game configuration is received and the data structure is searched. The find operation is constant time. If the game configuration is found, the move is sent to the applet, otherwise "not found" is sent.

2.2 Chess Applet

The chess applet computes moves using the classic min-max algorithm with alpha-beta pruning [4], truncated quiescent search, and dynamic search depth. The default contest is between human (white) and computer (black) but the applet also supports human vs. human, computer vs. human (as black), and computer vs. computer games. The board may be rotated so that the black side is down if the user wishes. The search depth is set dynamically during play based on the weighted average time of the last four move computations. If the time was longer than the maximum allowed (200 seconds), the search depth is decremented. If it was shorter than the minimum (30 seconds), the search depth is incremented. Changing the search depth on two successive computations is inhibited for stability. In this way, the applet adjusts its search depth to the power of the hardware on which it finds itself running, and adjusts to changing CPU load as the user might be multitasking with chess as a background task. The first move search depth can be set by applet parameter, by hardware speed testing at startup, or manually by the user.

2.2.1 Applet Network Functions

When the applet starts up it sends local system data to the server and requests a session ID. If there is no connection with the server, the game save and open buttons are not enabled, and further communication with the server is inhibited, except when the applet is restarted or the board is reset, and a new session ID is requested.

For a save game request, the session ID is sent to the server along with the game data. The server saves the game file and responds with the game number with which the user can later identify the game.

To open a game, the server sends a list of the saved games for the user to select from by double clicking on the file name. When the user makes his selection, the server opens the game file and sends the data to the applet where it is displayed as a chess game configuration for continued play.

With these save and open features, a user can play a game for a while, save it, shut down the applet, and come back later and continue playing the game. Repeated saves of the game (within the same session) write to the same game file. Resetting the board requests a new session ID so that the new game will be saved to a new file name and won't write over the old file.

When a player makes a move and it's time for the applet to compute a move, it sends the game configuration to the server in a request for a remembered move. If the server doesn't find the configuration, it replies "not found." If the move is found by the server and received by the applet, and if the move was computed at the same or deeper search depth as the applet's current search depth, the move is used. If not, the applet rejects the served move and begins computing the move. When the move computation is complete, the applet displays the move, notifies the user with a "ding" sound, and sends the computed game configuration and search depth to the server for storage.

2.2.2. Chess Modeling

The design goal was 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 [7]. 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 our solution:

We initially attempted to have a piece-centric (rather than board-centric) model, but were not able to get away from a chessboard 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. Our model has aspects of both in a way that we believe is acceptable for this object oriented (OO) approach. A diagram of the chess applet object model is shown below in Figure 4:


Figure 4: Chess applet object model. Java
language feature objects are not shown.

The chessboard 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 (chessboard) and a chessboard evaluation function. The game node keeps a Vector of child game nodes for recursive search (min-max with alpha-beta pruning) [7]. 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:

3. Experimental Results

The chess Java applet and chess move data server Java application were installed on a 750 Mhz Intel Pentium III with 256 MB RAM and a 10 GB hard drive running Mandrake Linux version 8.2. The Java server runtime is Kaffe version 1.0.6. The Internet service provider connection is a 256 kbit leased line via Ethernet 100 Base T LAN via a PCI interface. The server in Austria provides round trip response times from the west coast of the United States of America in well under the five second time-out period except in cases of unusual Internet conditions. Response time is typically one or two seconds. Due to the unique architecture of the database, server response time is invariant with database size.

3.1 Database Growth

We began testing the distributed computation features of our applet-server system in late July 2002. After some adjustments to the system, saved games were deleted and the database was emptied for public interaction. The growth of the chess move database from October 2002 is shown below in Figure 5.


Figure 5: Chess move database size as a function of time.

The stored move growth rate is proportional to Website chess player activity, which, after some initial stress testing, was nearly constant. The near constant database growth was expected because the Web page visitor traffic was nearly constant.

3.2 Statistics

Chess page statistics were kept by Extreme Tracker (http://extremetracking.com/), a free service. Chess server statistics were kept in an ASCII file on the server, stats.dat.

3.2.1 Chess Page Statistics

A typical 20-day period of unique visitors is shown below in Figure 6:


Figure 6: Chess page daily unique visitors.

In that 20-day period, unique visitors ranged from two to 11, with an average of 5.45 per day. Unique visitors for 20 months are shown below in Figure 7:


Figure 7: Chess page monthly unique visitors.

Page statistics service started in April 2002 so only 16 months are shown. The average is 183 unique visitors per month. Most visitors were referred from search engines, with Google (http://www.google.com) by far the most common with Yahoo and MSN second and third, respectively. Search keyword frequency is shown below in Figure 8:


Figure 8: Chess page search keyword frequency.

A typical search query is "chess applet source code."

3.2.2 Chess Server Statistics

Twenty lines from the most recent entries (as of this writing) to the statistics file (http://barbaric.hfs-design.at/chess/stats.dat) are shown in the listing below: 
0000003149, Mon Jul 21 15:11:52 GMT+01:00 2003, x86, Windows NT, 5.0, Recursion limit = 3
0000003150, Mon Jul 21 15:39:06 PDT 2003, x86, Windows NT, 5.0, Recursion limit = 4
0000003151, Tue Jul 22 02:35:32 EDT 2003, x86, Windows 98, 4.10, Recursion limit = 3
0000003152, Mon Jul 21 15:39:06 PDT 2003, x86, Windows NT, 5.0, Recursion limit = 4
0000003153, Mon Jul 21 15:39:06 PDT 2003, x86, Windows NT, 5.0, Recursion limit = 4
0000003154, Tue Jul 22 14:31:46 EDT 2003, x86, Windows XP, 5.1, Recursion limit = 3
0000003155, Tue Jul 22 19:35:26 GMT+01:00 2003, x86, Windows NT, 5.1, Recursion limit = 4
0000003156, Tue Jul 22 14:35:05 EDT 2003, x86, Windows XP, 5.1, Recursion limit = 3
0000003157, Tue Jul 22 14:36:51 EDT 2003, x86, Windows XP, 5.1, Recursion limit = 3
0000003158, Tue Jul 22 14:37:06 EDT 2003, x86, Windows XP, 5.1, Recursion limit = 3
0000003159, Tue Jul 22 12:56:04 PDT 2003, x86, Windows NT, 5.0, Recursion limit = 4
0000003160, Tue Jul 22 17:22:35 CDT 2003, x86, Windows 98, 4.10, Recursion limit = 3
0000003161, Tue Jul 22 17:25:02 CDT 2003, x86, Windows 98, 4.10, Recursion limit = 3
0000003162, Tue Jul 22 17:26:29 CDT 2003, x86, Windows 98, 4.10, Recursion limit = 3
0000003163, Tue Jul 22 15:55:44 PDT 2003, x86, Windows NT, 5.0, Recursion limit = 4
0000003164, Tue Jul 22 17:00:09 PDT 2003, x86, Windows NT, 5.0, Recursion limit = 4
0000003165, Tue Jul 22 17:09:37 PDT 2003, x86, Windows NT, 5.0, Recursion limit = 4
0000003166, Wed Jul 23 12:37:49 CST 2003, x86, Windows XP, 5.1, Recursion limit = 3
0000003167, Wed Jul 23 10:34:00 EDT 2003, x86, Windows NT, 5.0, Recursion limit = 3
0000003168, Wed Jul 23 13:12:12 EDT 2003, x86, Windows XP, 5.1, Recursion limit = 3
The ten-digit number is the session ID, which is followed by the date and time, time zone, year, processor type, operating system and version, and the initial recursion limit for the applet, which is set by testing the current processor power using a base six logarithmic formula. Six is the square root of the chess tree branching factor (approximately). The square root is appropriate due to the chess tree pruning performed by the alpha-beta search algorithm [4][7]. After the initial recursion limit is set, the applet adjusts the recursion limit dynamically so that the applet thinking time average remains under 200 seconds. Threes and fours are most prevalent for the initial recursion limit. Machines that are as powerful as the one used to develop the applet (1.7 Ghz Pentium 4) will have a recursion limit of four. Lesser machines will use a lower initial recursion limit. In the future we expect to see some fives begin to appear in the statistics.

4. Conclusion

Our conjecture, above, could not be fully verified with this one-year experiment. One way to verify the conjecture would to be to actually accumulate 37 billion stored moves and show that the resulting chess player is of world class strength, and at the rate of database growth, that would take two million years. To do that in a reasonable time would mean a million-fold increase in the usage rate of our chess playing system, and that's not likely to happen any time soon. However, we did verify that our approach is viable: the chess player is getting smarter and faster as time goes by. After a year of testing, we have demonstrated the feasibility of a distributed computation approach to chess computing. Moves computed on client computers, with unlimited parallel participation via the Internet, are stored on a chess data server for possible future use. Moves computed at a particular computation depth (move look-ahead) are replaced with moves computed with a deeper computation so that the database is improved with time both in the quality of the moves stored and in the likelihood that a given position with its recommended move is found in the database.

The design objectives of improving both chess applet response time and move quality for individual users were met.

4.1 Future Work

The intent of our distributed computing approach to computer chess is to store moves for reuse so that individual client users see a smarter faster chess playing opponent. We have noticed this trend toward a better system as the database has grown. Future efforts should survey users for corroboration of this observation. As time goes by, personal computers will become more powerful. The boost factor recorded in the server statistics file should show an upward trend, linear with time, which should parallel a logarithmic factor of Moore's law. As this trend continues, the database move quality should improve, and that should be reflected in user perceptions.

5. About the Authors

Harald Schifferl has extensive knowledge of computer network systems.

Rick Wagner is a chess player and computer scientist interested in the limits of artificial intelligence.

6. References

[1] de Firmian, Nick, Modern Chess Openings, 14th edition, Three Rivers Press, 1999.

[2] Horowitz, Israel. A., Chess Openings: Theory and Practice, Simon and Schuster, 1970.

[3] Khodarkovsky, Michael and Shankovich, Leonid, A New Era, How Garry Kasparov Changed the World of Chess, Ballantine Books, 1997.

[4] Moreland, Bruce, "Alpha-Beta Search," a Web page at http://www.seanet.com/~brucemo/topics/alphabeta.htm, July 10, 2002.

[5] Nunn, John, Burgess, Grahan, Emms, John, and Gallagher, Joe, Nunn's Chess Openings, Everyman Publishers, 1999.

[6] Pandolfini, Bruce, "Solitaire Chess," monthly column in Chess Life, April through August issues, 2003.

[7] Rich, Elaine and Knight, Kevin, Artificial Intelligence, Second Edition, McGraw Hill, Inc., 1991.

[8] Schaeffer, Jonathan and van den Herdk, H. Jaap, "Games, Computers, and Artificial Intelligence," Artificial Intelligence, 134(2002) 1-7.

Email Richard dot J dot Wagner at gmail dot com

index.html
Hand crafted HTML code copyright 2001-2019, by Dr. Rick Wagner, all rights reserved.

This page created August 12, 2002.
Last updated March 17, 2019.