Robert Hyatt

Associate Professor


Schedule

Available via hyatt@uab.edu for questions 24 hours daily. I am often on ICC in the evenings (9pm-12am CDT)when you see "hyatt" logged on. I am a regular poster in rec.games.chess.computer in usenet news, as well as at the Computer Chess Club which can be found here.

Research Interests

Computer Chess (Crafty)

This research is developing the computer chess program "Crafty", which is a direct descendent of Cray Blitz, the World Computer Champion from 1983 to 1989. This program is a "freeware" package available from ftp.cis.uab.edu/pub/hyatt. Crafty is based on the classic BITMAP approach to representing the chess board, but uses a unique methodology called "rotated bitmaps" to significantly improve the performance of the chess engine. This program is currently searching around 2,400,000 nodes per second on a dual xeon 2.8ghz machine, and is playing on ICC regularly. Its current peak ICC ratings are 3286 (bullet), 3388 (blitz) and 2792 (standard). Crafty also plays under the "scrappy" account but only plays vs humans, where Crafty plays all opponents, human or computer. Scrappy has a bullet peak of 3321 (ICC record), blitz 3546 (ICC record) and standard (2741). Crafty is portable, and uses xboard/winboard as a GUI under the appropriate operating systems.

Crafty is the derivative of "Cray Blitz", a computer chess program that itself was derived from "Blitz" a program I started to work on as an undergraduate. "Blitz" played its first move in the fall of 1968, and was developed continuously from that time until roughly 1980 when Cray Research chose to sponser the program for the publicity computer chess was producing at the time. Cray Blitz participated in computer chess events from 1980 through 1994 when the last ACM computer chess tournament was held in Cape May, New Jersey. Cray Blitz won several ACM computer chess events, and more notably, it won two consecutive World Computer Chess Championships, the first in 1983 in New York City, and the second in 1986 in Cologne, Germany.

Initial work on Crafty started immediately after the 1994 ACM event when we felt that it was time to "start over" and try something different from what we had been doing for 25+ years. I had always wanted to try the bitboard/bitmap approach used in Chess 4.X (the Northwestern Chess program by Dave Slate) and with new 64 bit processors available, it seemed like a good time for the change. Crafty has grown from a simple PC-based program to a program that runs on all known general-purpose computer platforms today, including those with multiple processors (CPUs). It has competed in many computer chess events, mainly those held over the Internet, such as the CCT events held on the Internet Chess Club approximately every 6-12 months. Crafty won the first CCT event, and has finished well in most of the others. The tournament crosstables can be viewed by following these links: CCT-1, CCT-2, CCT-3, CCT-4, CCT-5. CCT-6 was held on the Internet Chess Club the weekend of January 31 and February 1, 2004. Crafty ran on an AMD64 (opteron) machine with four 848 (2.2ghz) processors. It searched an average of 8 million nodes per second, and finished in first place. The tournament had 54 participants and was a 9-round Swiss with the top three programs playing a double-round-robin blitz event to choose the final winner. Crafty finished the main event with 5 wins and 4 draws (no losses) and won two of the playoff games and drew the other two. All in all it was an excellent result. More information on CCT-6, including the participants, the rules, and so forth can be found here.

Crafty again participated in the (now) annual World Computer Chess Championship, held in Iceland (2005). 12 programs participated, and Crafty finished in 5th place. This was one of those events where "everything that could go wrong did go wrong." For starters, this was a randomly-paired round-robin event with 12 players playing a total of 11 rounds. Crafty managed to draw to a pairing that had it playing the black pieces against all of the programs that were expected to do well at the event. Hopefully this is a once-in-a-lifetime happening, and we will have better luck next year in Spain. Crafty used a quad-processor AMD opteron 875 system, which used the new dual-core AMD-64 processors. This machine produced search speeds of 16M+ nodes per second. Click here to visit the official ICGA tournament web site for the 2005 WCCC event.

The current work on Crafty is concentrated in three areas:

If you are interested in Crafty, its source code, an executable you can use to play chess, the endgame tables, opening books, and so forth, then follow this link to visit the Crafty ftp site. Look at the read.me file first, then browse and download whatever interests you.

Parallel Architectures and Software

This research studies various parallel machine architectures and how they can best be used to improve the speed of software applications. These architectures pose different problems that must be addressed when developing parallel algorithms for them. Various types of parallel systems are being studied, including shared memory systems, distributed systems, and a distributed group of shared memory multiprocessors. We have several dual and quad-processor machines that are used in this research. This research has produced "Tuple-Space", a distributed processing programming environment that greatly simplifies the programming effort required to distribute an application. This system is continually being revised as it is used in various research projects.

Another interesting aspect of parallel computers is that there are now many systems available that are priced to be affordable and practical. As a result, much work has been done on the Linux kernel (and windows by Microsoft) to support these machines. There are many interesting architectural issues that offer plenty of opportunity for research. NUMA has become a common approach to connecting processors to avoid the high cost of a crossbar type connectivity, but it brings with it new issues that programmers have to work around to avoid severe performance degradation. Hyper-threading (on newer Intel processors) is another approach to make parallel programming affordable, but it too brings its own collection of unique problems to the table. AMD has announced a future processor that will have multiple complete CPUs on a single chip, further driving down the cost of a parallel machine while continuing to make life interesting with NUMA, cache and memory issues. All of these promise to offer significant performance gains, if the hardware issues can be handled efficiently.

Online technical papers

Education

BS, University of Southern Mississippi, 1970.
MS, University of Southern Mississippi, 1983.
Ph.D., University of Alabama at Birmingham, 1988.

Selected Publications

1. Y. Wang and R.M. Hyatt, Probabilistic Algorithms for Asynchronous Information Scattering in a Cluster, submitted to Journal of Parallel and Distributed Computing in February 2003.

2. Y. Wang and R. M. Hyatt, A Scalable Algorithm of Two Choices in Randomized Dynamic Load-Balancing, Submitted to Parallel Computing in February 2003.

3. Robert Hyatt and Timothy Mann (Compaq Computer Corp) "A lock-less transposition table implementation for parallel search chess engines," Journal of the International Computer Games Association, Vol. 25, No. 2, June 2002 (63-72).

4. Yibing Wang and Robert Hyatt, "A Distributed Task Scheduler for Cluster Computing", The 2002 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'02), Las Vegas, USA, June 2002.

5. Yibing Wang and Robert Hyatt, "Nezha: Breaking The Physical Boundary for Cluster Computing"i (Fast abstract), 40th Annual ACM Southeast Conference, Raleigh, North Carolina, USA, April 2002.

6. Hyatt, R., "Rotated bitmaps, a new twist on an old idea", Journal of the International Computer Chess Association, Vol. 22, No 4, December 1999, (213-222).

7. Lewis I. Patterson, Robert M. Hyatt, Richard S. Turner, Kevin D. Reilly, "Development of a Crash-Tolerant Tuple-Space", presented at the FSU/SCRI Cluster Computing Workshop, available via anonymous FTP from SCRI (SCRI hosts this workshop annually and distributes the proceedings via anonymous FTP.)

8. Robert M. Hyatt, Lewis I. Patterson, Richard S. Turner, Kevin D. Reilly, "Tuple-Space - Future Research Plans", presented at the FSU/ SCRI Cluster Computing Workshop, available via anonymous FTP from SCRI.

9. Robert M. Hyatt, Richard S. Turner, Lewis I. Patterson, Kevin D. Reilly, "Distributed Discrete Event Simulation - Design, Implementation and Use," Proceedings of SimTec '92, (159-165).

10. Robert M. Hyatt and Harry L. Nelson, "Chess and Supercomputers, details on optimizing Cray Blitz", proceedings of Supercomputing '90 in New York (354-363).

11. Robert M. Hyatt, Harry L. Nelson, Albert E. Gower, "Cray Blitz", in Computers, Chess, and Cognition , Springer-Verlag, 1990, (111-130).

12. Robert M. Hyatt, Bruce W. Suter, and Harry Nelson, "A Parallel Alpha/Beta Tree Searching Al", Parallel Computing 10 (1989) (299-308).

13. Robert M. Hyatt, "A High-Performance Parallel Algorithm to Search Depth-First Game Trees," Ph.D. Dissertation, University of Alabama at Birmingham, 1988.

14. Harry Nelson and Robert M. Hyatt, "The Cray Blitz Draw Heuristic", Journal of the International Computer Chess Association (ICCA)". vol 11, number 1, March 1988 (3-9)

15. R. Hyatt, H. Nelson, A. Gower, "Cray Blitz - 1984 Chess Champion", Telematics and Informatics (2) (4), Pergammon Press Ltd. (1986) (299-305).

16. Hyatt, R.M., Gower, A.E., Nelson, H.L., "Cray Blitz", Advances in Computer Chess 4, Pergammon Press, 1985 (89-106).