Amir Ban on Deep Junior

Ladies and Gentelmen: Amir Ban (right, in the picture above) the guest blogger, was an Israeli Olympiad math champion in the early 70s, with Shay Bushinsky he wrote Deep Junior, and he is also one of the inventors of the “disc on key”. This post is about computer chess. 

Let me introduce myself: I’m Amir Ban, and I wrote the computer chess program Junior, also known as Deep Junior. When Gil invited me to guest-blog for him on the subject of computer chess, I was honored and pleased, but what can I write to introduce the subject to the uninitiated? Well, as luck has it, I participated last week in a unique event in Barcelona, Spain: a man with machine vs. machine match! The “man” was veteran grandmaster and Spanish champion Miguel Illescas. The “machine” he assisted himself by was my own Junior 10 (a commercially available product) on his Toshiba notebook. On the other side of the board was my latest Deep Junior 11, due to be released later this summer, running on an ordinary core-duo Dell desktop.

Susan Polgar, a former women’s world chess champion, and the eldest of the three Hungarian-Jewish Polgar sisters, describes the event on her popular blog. The comments to the blog entry show some difference of opinion:

Comment 1: “That’s not fair to the computer at all.”

Comment 2: “Big deal, Junior 10 vs. Junior 11 with a grandmaster moving the mouse….”

Visualization of Deep Junior Bxh2 sacrifice in the 5th game, New York, 2003.
Hmm… We need some perspective here. For that, let us take a few quick flashbacks, starting ca. 60 years ago with the pioneering efforts of Alan Turing, and especially Claude Shannon, who in 1950 wrote “Programming a Computer For Playing Chess“. In the article, Shannon lays out the foundations of computer chess, still practiced to this day: Given the current position where the computer must play a move, it will generate the tree of all hypothetical continuations: All moves playable at the position, then all possible replies to each of these moves, then all possible replies to the replies, and so on. Theoretically this process may continue indefinitely until a terminal position is reached, i.e. a checkmate, or a draw by the rules of chess. Unfortunately (or rather, fortunately) this possibility is merely theoretical, as the typical number of legal moves per position is around 40, and a chess game may last a hundred or so moves, the exponential explosion of possibilities forces a limit to the practical depth of the moves tree.

The Shannon trophy

Shannon proposed stopping the tree generation at some practical depth, and attaching an evaluation to the position at the leaf.

The evaluation would be a number on a scale whose two extremes would be “white wins” and “black wins”. It may be computed based on, say, the balance of chess pieces material, for a start, and on identifiable strengths or weaknesses in the position, according to some formula. Having attached an evaluation to each of the leaves, the minimax algorithm may be applied to derive an evaluation for all non-leaf positions, including the root position. The minimax algorithm is simple to describe: At each node with white to play, the value is that of the successor node with maximum evaluation. At each node with black to play, the value is that of the successor node with minimum evaluation. Finally, the move to be played is one that achieves the root position value.

Shannon proposed two strategies: Type A, which envisions searching to a fixed depth, is now commonly known as brute-force. Type B, which proposes searching variations to variable depths dependent on their supposed game-specific relevance, is now commonly known as selective search. Neither approach seemed promising for a long time: The exponential explosion (and the weakness of computing machinery of the 50’s & 60’s) made attainable depths very modest, with or without selectivity. The selectivity idea, lucrative on paper, turned out to be difficult to implement without harming playing strength. Besides, even in brute-force mode programs suffered from a hilarious effect that became known as the horizon effect, which sometimes made them commit suicide with no objective provocation.
Well into the 70’s, the common reaction of chess experts to the efforts of chess programs was a patronizing smile. Skepticism of Shannon’s framework was rampant, and many abandoned it for dead. Douglas Hofstaedter, of Godel, Escher, Bach fame, speculated that only a program equipped with human-like faculties of reasoning, perceptions and feelings would suffice to play chess at the expert level (and so, according to Hofstaedter, if invited to play a game, may refuse and say that it would rather read poetry …). Hans Berliner, an international chess master and professor of Computer Science at Carnegie-Mellon, opined that the horizon effect places a limit on the strength of Shannon-type programs.

Yet, progress was being made, slowly. In the 60’s & 70’s McCarthy, Newell, Simon & Knuth discovered and refined the alpha-beta algorithm, a risk-free improvement to the minimax algorithm, which, under best conditions could nearly double search depths. In 1967 Greenblatt entered his program MacHackSix into a tournament where it managed to earn a chess rank. Other advances at the time produced some irrational optimism: In 1968, John McCarthy of Stanford University and Donald Michie of Edinburgh University told British International Master David Levy that in ten years there would be a program strong enough to beat him. Levy was so scandalized by this statement that he placed a 1000 pounds bet to prove them wrong. Ten years later, in 1978, Levy played against Slate & Atkin’s Chess 4.7, the strongest program of the day, in a 6-game match to settle the bet.

Chess 4.7 was not a pushover. Slate and Atkin revisited the brute-force approach, in a sophisticated manner, and were able to make progress. Their program’s rating was around 2000 (candidate master level). It was not good enough against David Levy, however. At Toronto, he beat it 3.5-1.5 to win the “Levy bet”.

International master, and president of the International Computer Games Association, David Levy.

Optimism and progress returned in the 80’s. Following Slate and Atkin’s example, it was the age of brute-force, and dedicated chess hardware. Hans Berliner, whom we met above as a skeptic, admitted his error and jumped on the bandwagon. He built the dedicated chess machine Hitech, which became world champion in the mid 80’s. Unrelated to him, two undergraduates at his university, Carnegie-Mellon, Feng-Hsiung Hsu and Murray Campbell, were doing even better: They designed and built very ambitious dedicated chess integrated circuits, which they named Deep Thought. Deep Thought’s calculating ability surpassed by a mile anything seen until then, and scored sensational achievements against strong players (and in a nostalgic meeting, gave David Levy a thrashing). For a few years in the late 80’s and early 90’s, they thoroughly dominated the competition. IBM Corporation took interest, offering Hsu and Campbell contracts. Soon Deep Thought was renamed to Deep Blue, which became IBM’s flagship project. They set their aim at defeating world champion Garry Kasparov.

But meanwhile, things were changing again. In the 90’s PC’s were coming of age, and good programming tools became available. Computer chess was no longer the exclusive domain of academia. Many independent developers appeared, with their innovation. The null-move pruning heuristic, popularized by Donninger, and my own half-ply heuristic were very effective depth enhancers. Soon, chess programs gained reputations of tactical monsters, being able to out-calculate humans in forced variations. In long-term strategy and positional understanding, however, they were not as proficient, and sometimes fared very poorly. So in man vs. machine games a pattern emerged where the programs fared well in “blitz”, i.e. a fast game where all moves must be completed in several minutes, because the human opponent could not keep up with the tactical complications, while in slow games (of 2-3 hours per game) the human master, if he could control the game and exploit the computer’s strategic errors, had an edge.

At the 1995 world championship at Hong-Kong, the first in which I participated, it was becoming apparent that the age of big hardware was drawing to a close: IBM’s Deep Blue came to play, expecting to take a stroll. However, they were surprisingly defeated by the Dutch program Fritz, who went on to win the world title, while running on a measly Pentium III 90 MHz! Unfazed, IBM announced at the closing ceremony that their 1996 Philadelphia match against world champion Garry Kasparov.

Kasparov won 4-2 in Philadelphia, rather easily, so IBM asked and got a rematch the following year, 1997, in New York City. The Deep Blue team worked feverishly throughout the year to improve, and introduced a new machine design, dubbed Deeper Blue. It was reputed to be able to calculate an incredible 200 million positions per second. Kasparov won the first game, but lost the second game in a way that left him psychologically crushed for the rest of the match: Deep Blue played a fine game, in which at some point, rather than seizing on an easy advantage, it played a solid move that left Kasparov with little counter-play. This was so uncharacteristic of the way computers play chess (or so Kasparov thought) that Kasparov became suspicious that IBM had cheated with illegal human help during the game. Hinting at such a possibility soured the atmosphere of the match, and ultimately boomeranged against Kasparov himself. Even more amazingly, hours after Kasparov resigned the 2nd game as lost, chess fans discovered that he could force a draw in that position, and that therefore he resigned a game that was not lost, an unprecedented occurrence (I believe I was a party to the original discovery, where chess programmer Bruce Moreland, myself, and others on the Internet Chess Club discussed and analyzed the game minutes after Kasparov’s resignation. Goaded on by Moreland’s repeated observation “I don’t see why this is lost”, we found a save).

The 3rd, 4th and 5th games were drawn, and on the 6th game Kasparov played weakly and lost, to lose the match 2.5-3.5. This was a historic result, which however was marred by the controversy created by his accusations (almost certainly unfounded), and by the fact that Kasparov was clearly out-psyched. It did not help, too, that IBM immediately disbanded the Deep Blue project and never played again. I and others in the computer chess community felt particularly betrayed by that disappearance act. We noted that the greatest achievement in computer chess history was received by a machine with a mere 12-game public career which was on top of that hardly convincing.

At this time Junior’s own career was taking off. Later that year (1997) Junior won the computer chess world championship in Paris, and followed through with four more world titles (Maastricht 2001, Maastricht 2002, Ramat-Gan 2004 and Turin 2006). The winner of the world champion gets to keep the Shannon trophy, a beautifully carved horse’s head named in honor of Claude Shannon, and nicknamed Shanny. Shanny graced my living room for many years. Junior is my joint project with Shay Bushinsky, and Deep Junior is how we call the version of the program that runs on several processors.

Kasparov, bruised by the defeat to Deep Blue, stayed away from man vs. machine competitions for several years, but came back in answer to a $1 million challenge by FIDE President Kirsan Ilyumzhinov to play against … Deep Junior. This 6 game match took place in the winter of 2003 in New York City, and was drawn 3-3. It was a high-class match and a wonderful achievement for Deep Junior, but it became immortal due to Deep Junior’s 11th move in the 5th game. The out-of-the-blue bishop sacrifice created a sensation when it was played, justified itself over the board by holding Kasparov to a draw (with black), and its correctness or incorrectness will perhaps be forever debated. This was no mere technical feat of calculation, one whose result is worked out in advance, but a plunge into darkness played against conventional wisdom and on general merits: True creativity. You can read all about it here http://www.chessbase.com/newsdetail.asp?newsid=777.

At present the point of parity between the strongest computers and the strongest masters may have already been passed. In 2004 and again in 2005, an event in Bilbao, Spain pitted three former world champions against three programs (Junior, Fritz and Hydra). In both cases the programs won by a wide margin. In 2007, Fritz beat world champion Vladimir Kramnik 4-2 in a match at Bonn.

What does all this mean? I don’t know, but obviously appearances may mislead: No, computers do not have to have higher intelligence to play at the highest level, and yes, they can be highly creative. An approach to a problem that at a time seems hopeless can turn out to be so successful that no one bothers to consider others. And, no, the computers’ ascendancy did not kill the interest in the game.

Returning to the Barcelona event, the result was 1-1, two draws in two games… The games were unspectacular, but high-level, and according to GM Illescas, free of errors. An excellent crowd of around 100 people at the auditorium of the CosmoCaixa science museum was pleased and stayed on for a discussion panel lasting late into evening, in which, predictably, brute-force, creativity, the human spirit and Deep Junior’s sacrifice were mentioned. For the interested, the game scores are below:

[Date “2008.06.05”]
[White “Illescas, Miquel”]
[Black “Deep Junior 11”]

1. Nf3 d5 2. d4 Nc6 3. c4 Bg4 4. cxd5 Bxf3 5. gxf3 Qxd5 6. e3 e6 7. Nc3 Qh5 8.
f4 Qxd1+ 9. Kxd1 O-O-O 10. Bg2 f5 11. Ke2 Nf6 12. Bd2 Ne7 13. Rac1 Ned5 14.
Nxd5 Nxd5 15. h4 c6 16. Rhg1 Rg8 17. h5 Be7 18. Bf3 Kd7 19. a3 a6 20. Kd3 Ra8
21. Bd1 a5 22. f3 Bd6 23. Bb3 a4 24. Ba2 Raf8 25. Rg2 Rf7 26. Rcg1 Be7 27. Ba5
Ra8 28. Be1 Rg8 29. Bd2 Bd6 30. Rg3 Be7 31. R3g2 Bd6 32. Rg3 Be7 33. R3g2
1/2-1/2

[Date “2008.06.05”]
[White “Deep Junior 11”]
[Black “Illescas , Miquel”]

1. e4 e5 2. Nf3 Nc6 3. Bb5 Nf6 4. d3 Bc5 5. c3 O-O 6. O-O
d5 7. exd5 Qxd5 8. Bc4 Qd6 9. b4 Bb6 10. Qe2 Bg4 11. Nbd2 Rfe8 12. Ne4 Nxe4 13.
dxe4 Be6 14. a4 a6 15. Ra2 Bxc4 16. Qxc4 Qe6 17. Qxe6 Rxe6 18. Rd1 Ree8 19. a5
Ba7 20. Rd7 Rad8 21. Rad2 Rxd7 22. Rxd7 Rc8 23. Kf1 f6 24. Ke2 Nb8 25. Rd3 Kf7
26. Nd2 Ke6 27. Nc4 Nc6 28. Rh3 Rh8 29. g4 Ne7 30. f4 exf4 31. Bxf4 Ng6 32. Bg3
h6 33. Rh5 Rd8 34. e5 fxe5 35. Nxe5 Nxe5 36. Rxe5+ Kf7 37. h4 c6 38. h5 Re8 39.
Rxe8 Kxe8 40. Be5 Kf7 41. c4 Bg1 42. Bc3 Bh2 43. Ke3 Bd6 44. Ke4 g6 45. Ke3
1/2-1/2

Banner of Barcelona event

Updates: May 2010: Here is a related post devoted to computerized chess on Dick Lipton’s blog. March 2012: Here is a another post on Lipton and Reagan’s blog about Ken Reagan’s work on testing if a human player uses a computer chess program and a NYT article To Detect Cheating in Chess, a Professor Builds a Better Program on Reagan’s work. And here is a follow up post “When is a law natural“.