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:
- 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, 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.
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).