Retired Professor of Computer Science
University of Alabama at Birmingham
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
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:
- using parallel machines to search deeper into the game tree,
- improving the chess knowledge contained in the program so that it plays
better positional chess and also so that its strategy is goal-oriented
rather than random, and
- improving the search strategies so that the program analyzes deeper in
those positions that require it without wasting time on deep searches for those
positions that do not need it.
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.
BS, University of Southern Mississippi, 1970.
MS, University of Southern Mississippi, 1983.
Ph.D., University of Alabama at Birmingham, 1988.
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
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
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
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,
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
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).