The history of Blitz / Cray-Blitz / Crafty

1. Introduction

I became interested in computer chess as a high school senior in 1966 when a new TV series “Star Trek” first aired. In it, on more than one occasion, Mr. Spock was playing chess against the computer. The idea seemed to me to be fascinating and I started looking for more information. The only source was a university some 60 miles from home, so off I went to see what I might discover at the University of Southern Mississippi.

That interest continued until I started taking computer science courses in the Summer of 1968, the start of my junior year at the university. Amazingly, it has continued to the present. This paper is short on technical details, rather it is more about the developmental milestones along the way from Blitz to Cray Blitz to Crafty.

2. 1968

In the Summer of 1968, I completed a FORTRAN course at the University of Southern Mississippi. Since I had been playing chess since the age of 10 or so, and having seen Mr. Spock play chess against the Enterprise computer in the TV series Star Trek, combing chess and computers seemed like something that would be both fun and educational to work on. So off I went.

At that point in time, recursion was not something the university’s computing system could handle, since the FORTRAN compiler could not produce re-entrant code for recursion. I would not have used recursion even if it had been available, since I had no experience with it. I read Claude Shannon’s classic paper “Programming a Computer for Playing Chess” (Shannon, 1950) and then several papers on alpha/beta pruning. With that, I was ready to try writing a chess program.

My first program was simplistic. I had six search functions, Search1 through Search6. Each was responsible for that respective ply (i.e., Search1 called Search2, which called Search3, etc.).1

The program played its first move in October, 1968. I remember the first full game distinctly. I was sitting in the lab by myself, working with a computer with no terminal interface, just two card readers and two line printers. I would punch my move onto a card (IBM 029 keypunch) and run it through the card reader. After a bit, the printer would print one line (the computer’s move) and the program would wait for my next move. I recall our department chairman walking into the lab asking, “Hyatt, what in the world are you doing? I watched you insert a card, wait while the computer’s lights blink like mad, then you space the printer up a few lines to see what was printed, and then you return to the keypunch room. What ARE you doing?” I replied, “I am playing chess.” He shook his head and said, “Of course you are.”

I attended the 1970 ACM annual conference, the host for a historic event – the first computer chess tournament. I was amazed to see an actual chess tournament with only computers playing. I remember some amazingly funny things, from a program moving a pawn to the 8th rank but not promoting it, to Coko losing while it had a mate-in-2 position on the board. Every move it found a mate-in-2 and took that choice, never making progress until its opponent managed to promote a pawn and defeat it.

The program was a “back burner” project until 1973 when the University of Southern Mississippi acquired a new Xerox Sigma 9 computer. This machine had several important advantages. First, it was much faster, around 1.3M instructions per second (roughly 20X faster than the IBM/360 computer). Second, it had a “time-sharing operating system” that allowed many simultaneous users. Finally, and most importantly, it had a serial communication interface that could work with hard-wired network connections or with modems (up to 64 devices). Now I had access to a machine that I could use for serious chess program development! By this time, I had graduated with a B.S. in computer science (1970) and had been hired by the University as a systems programmer (operating system support), as well as a Computer Science instructor. This gave me plenty of late-night machine access since our student labs closed at 10 pm.

I dusted off my four-year-old (large) deck of punched cards, spent a few days making the necessary changes to work with the Xerox FORTRAN compiler, and then I was ready to go. I could now interface directly with the computer via a terminal and with a modem from home. No need for a printer or punched cards.

At this time, program progress accelerated quite a bit, thanks to the new time-sharing programming environment. A SEE (Static Exchange Evaluator) was added as the first pseudo-quiescence search. The program was now playing real chess and could finagle a win against a 1500 player maybe 1 out of every 3 or 4 games.

4. 1974

At some point during this time-frame, I was at a university “student recruiting fair” day and was in an exhibit booth next to the University of Southern Mississippi music department. I had been asked to demo my chess program for our booth exhibit, and Albert (Bert) Gower was next to me with the music department exhibit. He was a 1600 United States Chess Federation (USCF) rated player and he wanted to play a game against the program. He won fairly easily and we started talking. Soon thereafter he became a collaborator with me and took over our opening book preparation, as well as playing games to help improve the basic program playing skill. Bert remained a member of the team until we stopped competing in 1994.2

We allowed students to play the program during “slow times” on the computer, and when we asked for help in naming the program (with the plan to enter an ACM event in the future) students settled on the name “blitz” because it played fast chess fairly strongly compared to longer time controls. Blitz stuck as the name for many years.

The only thing notable about this year was that we entered Blitz in the 1976 ACM Computer Chess Championship, the first of a long string of ACM tournaments we would enter. This marked the seventh year of “official” computer chess tournaments where the programs played each other rather than human opponents.

6. 1981

This year had both a high point and a low point.

The first thing of interest became one of the things that almost led me to give up on computer chess. In 1970, Hans Berliner’s program (J. Biit) ran on an IBM 360 model 91, the fastest computer around at the time. Executing 16M+ instructions per second, this was the first machine with out-of-order execution and register renaming. It represented the kind of computing resource that very few could hope to access. As the 1970’s unfolded, Control Data Corporation (CDC) took over the “top dog” position in the computer hardware world with their Cyber series of computers, and the well-known Chess 3.x and Chess 4.x series of programs by David Slate, Larry Atkin and Keith Gorlan dominated computer chess through that decade.3

Seymour Cray was CDC’s chief machine architect and designer. In 1972 he left CDC and formed a company to build an even faster computer. As a systems programmer/instructor, I saw little chance to getting access to such hardware, and without it, there was little hope of competing with Chess 4.x and Belle. So, my interest in computer chess waned until I started to see discussions about the Cray-1. It could execute at a speed of 80M instructions per second, a new high-water mark for computing. I contacted them to propose that they sponsor my chess program Blitz by providing me nothing more than access to their machine to develop an even stronger version, to be named Cray Blitz, and some dedicated system time once a year to compete in the annual ACM event. Coincidental with my request, two top-level people at Cray (Peter Appleton-Jones and John Rollwagen) were flying to a conference. One of them opened up a copy of Flight magazine and saw the story “CDC Wins Another Computer Chess Event.” They realized that CDC was getting free publicity for a few machine cycles. They wanted a piece of the action.

Meanwhile my request to Cray had made its way to Cray’s Minneapolis office through a different channel and ended up in the programming section where benchmarks and operating system development were done. When the president of Cray (Rollwagen) brought up the topic of developing/supporting a chess program, a couple of the Cray guys spoke up. “We have a possible idea here.” They went on to explain how I had contacted them. I was invited to Minneapolis for a visit, and the rest is history.

Once I started to use the Cray (in 1981) we suddenly became competitive in the ACM events. At this point, the next bit of good fortune came our way. Harry Nelson (at Lawrence Livermore National Laboratories) became interested and was playing Cray Blitz (which was in the Cray user’s group library) against Chess 4.x running on one of CDC’s Cyber 176 computers. He called me out of the blue and started talking about computer chess on a Cray. He could not understand why Chess 4.x was out-searching Cray Blitz while using a slower computer. I explained that Chess 4.x was written in Compass (the CDC assembly language) while Cray Blitz was written in FORTRAN. This interested him, and he suggested rewriting time-critical parts of Cray Blitz in CAL (Cray Assembly Language). Not knowing a thing about Harry, I contacted Cray Research to find out who he was. They told me that “Harry’s a legend around here. He knows more about writing fast software on these machines than Seymour does.” I promptly asked him to join the team and he accepted. We now had the “group of 3” that continued through 1994. With Harry’s help, Cray Blitz’s playing strength improved as we found new and unusual ways to use their vector hardware to improve performance. Eventually even that began to get a bit stale.

The low point happened in a human tournament. We were getting ready for the 1981 ACM Computer Chess Tournament (Los Angeles) and wanted a trial-run before the event. For several years, we had been invited to the Mississippi State Closed Chess Championship. We were never a threat to win it, as they always had one well-known chess Master who played. The tournament was over Labor Day weekend so Cray happily let us have the Cray-1 (serial number 12 for those interested in such details) since they were shut down for the long weekend. They agreed to leave it up for us with an operator on duty to handle any problems.

I contacted the Mississippi Chess Association and told them we would participate in the tournament. As it turned out, this was a decision I later regretted. The issue was a rather poor USCF rule they started using that year which said (paraphrased) “a computer can enter USCF events, but each player has the right to choose at the beginning of the tournament to not be paired against a computer.” There were other specific rules for computers, such as not taking any prizes awarded (cash, books, and so forth) but the first rule turned out to be a big problem. A couple of players chose to exercise this right; Joe Sentef, the master that had won the event multiple times, did not. In fact, if he won in 1981, he would “retire” the trophy. Joe felt it would look bad if he chose to not play the computer.

Remember that this was our first tournament using the Cray. We went through that event with a perfect score. In the final round, we were paired against Joe and won with little fanfare. As a result, Joe did not win the tournament. A 1900 player officially “won” the event, a consequence of Cray Blitz not being allowed to be declared the winner (USCF rules) and that the player had requested to not be paired against a computer. Joe was very unhappy about this, for obvious reasons. He lost to the computer, and the winner of the tournament did not (upon request) play the computer. The local newspaper, the Clarion-Ledger, wrote a full-page article describing what happened. I had always disagreed with the wording of the rule, and had suggested (through the USCF computer rating committee) that it should say “a player can request to not be paired against the computer unless it appears to possibly affect the final standings of the top players.” They scoffed at the idea a computer could have such an effect. To their embarrassment, they saw how badly the rule affected this tournament.

It turned out that there were others that objected as well. Several reasons were given, most pretty ridiculous. For example, “this tournament is for Mississippi chess players only, the Cray computer is located in Minneapolis and is obviously not a state resident.” Or “the computer uses an opening book which violates the rules of chess.” (I asked them to point out the book it was using, and received blank expressions.) There were others. To me, this looked like a complete failure for us as instead of positive publicity, we generated mostly complaints. Chess Life didn’t agree and published the game, as did several other publications. But it really felt like a defeat to us.

Joe and I remained good friends for a few years, but the tournament result was always a point of contention. The good news was that (a) Cray Blitz became the first computer chess program to defeat a chess master in a tournament game (not blitz time control); and (b) the program was strong enough to become competitive in the ACM events.

This rule showed the disdain that chess players had for the computer – computers were interesting players, but inconsequential to the upper levels. In 1976 Chess 4.5 opened eyes when it won the class B section of the Paul Masson chess tournament (class B is USCF ratings between 1600 and 1799). Notice had been served that “the computers are coming” even back in 1976. Cray Blitz (and Belle) put an exclamation point on that statement in the early 1980s. We began to notice a new phenomenon at that point. The USCF modified the rule as I (and others) had suggested (as above), but they added a new option. The tournament organizer was given the ability to flag a tournament with (NC = No Computers) in the tournament announcements to further help in avoiding this kind of issue. Over time, more and more chess tournaments were advertised as NC until it ultimately became impossible to find non-NC events except in large cities in large tournaments, which were hard for most of us to attend. The era of computers versus humans had come to an end, except for arranged matches between strong players and computers, outside the tournament process.

At the 1981 ACM tournament, we finished in 2nd place, tied with Nuchess (the successor to Chess 4.x). In 1982 we finished in a 3-way tie for first place with (again) Nuchess and Belle which had taken over the top-ranked position in the computer chess rankings in 1980. We were off and running.

In the middle of 1983, Cray announced a new machine, the Cray XMP-2, their first machine with two processors. Boy, did this get our attention. We quickly did our first parallel search implementation and barely got it working prior to the 1983 World Computer Chess Championship (New York City). When I say “barely” I mean that we had the program playing reasonable moves, but it had not played a single full game. With great fear and trepidation, we entered round 1 of the World Championship. We had the Cray XMP-2 dedicated to us so no other users could steal cycles, and amazingly it played all 5 rounds without a single hiccup. We ended up winning that event and became World Computer Chess Champion.

This turned into (for us) a remarkable result. Computer problems and remote access (usually through dial-up modems back then) were always a problem: machines going down, communications interruptions, software glitches, and so on. It was rare to see complete games without issues. An experimental program, on a brand new (and experimental) computer, and using experimental operating system software, all had us expecting problems which kept our nerves on edge and our attention tightly focused on Cray Blitz watching for problems. Amazingly, none bit us.

One quote from this era stands out to me. In 1977 Monty Newborn famously said, “Chess masters used to come to computer chess tournaments to laugh. Now they come to watch. Soon they will come to learn.” As always, “soon” stretched out to a little more than a few years but eventually we reached the point where we are today, with humans having virtually no chance of beating a top computer chess program. It was a prophetic statement given today’s hindsight. At the time, it was a debatable prediction.

8. 1984

In early 1984, Cray announced the four-processor XMP-4. This required a rewrite of our parallel search to make it more general. It obviously doubled our speed again and we won the 1984 ACM tournament, albeit not without incident. Figure 1 shows the critical position for the game Nuchess versus Cray Blitz.

Some explanation is needed to understand this game. I had gotten sick prior to the tournament (flu most likely, my wife said we were staying up so late at night working on Cray Blitz that it was no wonder I came down with something – something I heard many times over the years). So, by the time of round 4, I was pretty well out of it as far as actually watching/understanding the game.

OPEN IN VIEWER

Fig. 1.

Nuchess (White) versus Cray Blitz, 1984 ACM North American Championship.

We were losing to Nuchess (Dave Slate’s successor to Chess 4.x, co-authored with William Blanchard). We were down a pawn, and even worse, we were in a passive position with Nuchess dominating the board. At move 44, Cray Blitz played the inexplicable Nc8, which is not a particularly great square for a knight. The tournament director, International Master Mike Valvo, asked us from the analysis stage, “Bob, what is your evaluation?” I replied, “−3.x”. He said, “I agree. Any idea what that last move was about?” I had no idea and told him so. At this point, Nuchess had several good choices, but it lacked one critical piece of evaluation information. Rather than worry about that lonely Black a-pawn it chose to take the g-pawn instead by playing Rxg6. At this point, Mike asked me, “How bad is it now?” I was sick physically and sick emotionally from seeing all those −3.x evaluations. I told him, “No change. We are still losing.” But then I realized something was different, and when I looked again, our evaluation was a startling +4.x. My comment? “Wait|! We are winning!”

Cray Blitz recaptured the rook on g6 and was NOT expecting Nuchess to recapture, leaving it down major material. What happened was Rxg6, and if Kxg6 then Nxb6 and after the cxd6 recapture, both sides were out of pieces. That lonely a-pawn suddenly loomed large since it was outside “the square of the king” and couldn’t be caught. We managed to dodge a bullet by having code that understood the square of the king, something missing from Nuchess. I remember William Blanchard asking Mike, “Is there any hope?” Mike responded, “None.”

The remainder of the games were all won by Cray Blitz and we took clear 1st place after nearly being a game down. That knight on c8 enabled all of this by allowing Cray Blitz to remove the last white piece which then allowed the pawn to promote uncontested.

There are always “issues” that arise for these events. The big one for us came about a week before the tournament’s first round. I was running some test positions since we were using yet another parallel search algorithm because the old one did not perform well with the four processors our machine had. Immediately the program hung in a deadlock and would no longer respond. I debugged and eventually discovered that the problem was not in our code, it was in Cray’s parallel FORTRAN library. By this time, I was on a first name basis with the operating systems team at Cray and I called them. I told them the old library appeared to work, but the new one was causing a problem. I knew we could not play with the old one because the new version of the operating system needed the new library otherwise other race conditions would likely be a major problem.

The Cray team jumped right in and started trying to debug their library to see what might be wrong. Apparently it was a significant problem and all of them were running tests, using all four of the four-CPU machines Cray had at their computer center. Somewhere into the second day of this intense effort, I got a call from Cray’s Vice-President for Systems Development. She asked, “Bob, somehow you have all of our system guys working on an operating systems problem, using all of our computer systems. Could I possibly borrow one of each to solve a customer problem?” I thought, “Uh oh. This could be trouble.” Then she laughed and said, “I am kidding. But, not really, I do need someone to fix this issue, but it can wait for a day or two.” We basically had all of the technical folks (and computers) working on a problem that had only been seen in a computer chess program (although we all knew it would affect other software as well).

Luckily, the operating systems team isolated and then fixed the bug, and some quick tests confirmed that the deadlock was gone. Just in time – about two days before we left for the 1984 tournament in Los Angeles. As you can see, rarely did things go smoothly. However, we learned to cope with these issues and remain sane.

As a brief tangent, before we played in the 1984 ACM event, I was fortunate to obtain Cray time to play in a human tournament in Mobile, Alabama. Recall that we were moving to a 4-processor Cray and we needed to test the code rewrite. About halfway through our round 1 game, we played the move Bxc6 checkmate. The opponent quietly played PxB, and there was no mate. We were puzzled. As commonly happens, a perplexing problem usually has a simple cause. After Bxc6 there were 3 legal moves. Unfortunately, Cray Blitz had four processors for the search at that node. Three found valid scores, but the fourth said in effect, “I have no moves to search, thus I am checkmated.” This processor returned its partial result last and overwrote the results from the threads that did real searches. The consequence was devastating; the program played a losing move. If the opponent had just had one more legal move … In any case, this was fixed, as were many other such annoyances.

I could probably recount dozens of similar stories. One that was particularly amusing was playing in a human event in the late 1970s. The first version of Blitz (prior to Cray’s involvement) used a full-width search similar to that deployed by Slate and Atkin. In the first round, we played a 1700 rated human and out of the clear we played a move Nxg7. He looked at the move, turned pale, spent 30 minutes analyzing the position, and then resigned. He was a piece for a pawn ahead, and White had absolutely no compensation for the sacrifice. I told him, “I am sorry to tell you this, but you were winning. This was a program bug where I had inverted the sign and the first move out of book was the worst move possible.” We had a good laugh. Even then people seemed to assume that a computer could not make a mistake.

As an aside here, Cray Blitz had become well-known, particularly in the world of Cray Computers. It was distributed by Cray as part of their user’s library and who knows how many computing cycles were burned on very expensive computer systems? It became known as such a stress-test (due to the symmetric multiprocessing search load) that Livermore Labs added it to their machine acceptance protocol. The program was considered to be one of the “programs that must all run at the same time, and the computer system cannot have any crashes or hangs for 30 consecutive days with this load on it, before we will accept delivery and pay for the machine.” It could burn computer cycles like no other program.

The next computer chess event for us was the 1985 ACM tournament held in Denver, CO. My wife and I had decided to leave the University of Southern Mississippi so that I could work on my Ph.D. degree. We planned on returning after that (I had expected 3 years away, maybe another year or two to complete my dissertation). Bert and I did some rushed tuning during the early summer knowing I would not have much time once I started the Ph.D. program. We played lots of games with Cray Blitz running very slowly on our Vax 11/780 against the well-known Super Constellation4

Our next event was the 1986 World Computer Chess Championship in Cologne, West Germany. I could not get away for the period of time needed, so we worked out a solution where Harry would fly to Germany as part of a vacation with his wife. He would be at the tournament site and communicate with me via an over-seas telnet connection that I could use to relay moves.

We won the first round in our normal fashion. Then we played the program Bobby5

By 1986, Cray Blitz was searching well over 160K nodes per second on a newer Cray, the Cray YMP-8, with 8 processors, each being about 50% faster than the Cray XMP. When we ran on the Vax, we were running at about 10 nodes per second, a huge performance difference and a huge difference in search depths. And a huge difference in tuning requirements. All I can say here is, “Lesson learned, loud and clear.”

A new, potentially dangerous opponent emerged: ChipTest by Feng-Hsiung Hsu, Murray Campbell and friends. Basically, it was Belle on a single chip. It was impressively fast, but with some search inefficiencies that left them vulnerable, at least for a year.

We met them for the first time in 1987 at the ACM event. Figure 2 shows the critical position from the game:

Our “event” here was an unknown race condition that had not shown up on the older XMP machines, but which was just waiting on the right conditions when we got to the 8 processor YMP. The critical point came at White’s move 14. As we were searching, the move Ne6 failed high and looked to be almost crushing. Hsu was expecting this and said he was losing. But when Cray Blitz displayed its move, it announced Na4 instead. This move had not shown up in any of the output. And it threw away a +1.5 advantage. I later found the bug, one of the classic race conditions that tend to occur in parallel search programs.

OPEN IN VIEWER

Fig. 2.

Cray Blitz (White) versus ChipTest, 1987 ACM North American Championship.

This was our last real chance to beat this program as every year afterward Hsu and company added additional chess processor chips and/or fabricated a faster version of their chip, and their search speed grew astronomically.

As the 1980s ended, ChipTest and its successor Deep Thought (many ChipTest processors) had taken over as the king of computer chess. In 1994, as preparation for the Kasparov versus Deep Blue (Deep Blue started as ChipTest later to become Deep Thought) ACM held its last computer chess tournament. We did not know this at the time, but it led to my next computer chess project, Crafty.

For each of the events we played in, we had to do a lot of scheduling to get access to a $50 million computer system. At times the hardware would be broken and we would have to scramble for a backup. At times building renovations at Cray would be a problem. It was really a struggle to balance all of that with trying to develop a stronger chess program. Even more importantly we needed lots of test time in light of the previous fiasco with tuning on a slow machine. As well, we needed dedicated time to test the parallel search changes that depended on fast hardware to expose race conditions. For a while, we made do with 2 am–5 am testing as that was all Cray could give us for multiple days. You knew we had a problem when I realized I was spending more time trying to set up test times than I did making changes to improve the program.

After the 1994 event, I decided it was time to do a complete code rewrite. This included using C instead of FORTRAN, ignoring exotic hardware like the vector operations on the Cray, and moving to the IBM PC type hardware that was getting faster. Within a month I had a new program running, one based on 64 bit “bitboards” as used by Chess 4.x, and a few others. Thus, Crafty was born. Its main claim to fame at the time was a sophisticated evaluation function (recall the square of the king as just one example) and a sophisticated search, all borrowed conceptually from Cray Blitz. Crafty is alive and well today, although since I retired in 2016, I have spent much less time on it than I used to. It still gets some of my attention as I have always enjoyed this fantastic hobby.

I feel fortunate to have been around for all of the computer chess developments. From the early days where many computers could not even play legal chess, to today’s programs that are essentially unbeatable by humans, no matter how strong the humans are. In fact, we are now seeing handicap matches where GM players are given a pawn (up to a piece) advantage at the start of the game, in an effort to equalize them with the computer’s incredible tactical abilities.

After over 40 years of programming computers to play chess, one key point regarding Crafty is that it was one of the very early computer chess programs where source code was made publicly available. It gave computer chess enthusiasts a very strong program, written in C (a commonly available programming language) which allowed them to look at the internals to learn ideas (and create new ideas). Unfortunately, as with most things, there was both good and bad. The bad came along as a few people decided to just copy the Crafty source code, make a few changes (mainly to its output to hide its origin) and then use these programs in various competitions. Trying to ferret out these programs turned into a major hassle for quite a few people. And as other open-source programs were made available, this only got worse. As a brief note, at one point, using some usual Unix “black magic” the number of different IP addresses that downloaded the Crafty source/executable files reached beyond one million. I never imagined that kind of popularity. Of course, that does not necessarily imply over one million different people thanks to network address translation behind firewalls, but it still represents a significant number of people.

The “newest kid on the block” is AlphaZero, from the Google Deep Mind project. It is a program based on neural networks, something that has been far too slow to use for chess for many years. But just as Slate/Atkin showed with Chess 4.x plus a seriously fast supercomputer, a brute-force Shannon type B program could not only compete, but could dominate computer chess events, Google has shown that with the development of the high-powered GPU/graphics cards available today, that suddenly the neural net computers are not as slow as they once were. They are not quite to the level of the very top traditional alpha/beta chess programs, but they are getting better on a day by day basis. And the interesting thing is that it is not requiring a lot of programming effort to improve the program. Rather, adjusting the dimensions of the neural net plus improving the training data is leading to a program that is probably closer to “learning” than any previous chess program.

As always, even as this seems like the ultimate development in computer chess, it won’t be any great surprise to see something even better appear on the horizon. I look forward to seeing it, as it seems that the improvements will never end. We have almost reached the point where, if the computer could laugh, IT would now be the one laughing at the human grandmasters. What an amazing turn-around since 1970.

OPEN IN VIEWER

Cray Blitz (Black) versus Mephisto, 1988 ACM North American Championship. Harry Nelson (standing, wearing in striped dark blue shirt) and Robert Hyatt (seated, wearing a striped light blue shirt). Courtesy of Monroe Newborn.