Robert Hyatt

Retired Professor of Computer Science

University of Alabama at Birmingham


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 www.cis.uab.edu/hyatt/crafty. 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 100M nodes per second on a dual xeon 2660 (20 cores @ 2.9ghz/core). 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. 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.


The current work on Crafty is concentrated in three areas:

If you are interested in Crafty and its source code, which you can use to play chess, and its opening books, then follow this link to visit the Crafty source directories. 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. All chip vendors produce chips which have multiple complete CPUs (cores) 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 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. R.M. Hyatt, Book Learning - a methodology to tune an opening book automatically, The Journal of the International Computer Chess Association, Vol. 22, No. 1 (3-12).

2. R. Hyatt, "The Dynamic Tree-Splitting Parallel Search Algorithm," The Journal of the International Computer Chess Association, Vol 20, No. 1 (1998), 3-19.

3. 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.

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

5. 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).

6. 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.

7. 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.

8. 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).

9. 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.)

10. 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.

11. 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).

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

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

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

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

16. 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)

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

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