Asri-unix.458 net.chess utzoo!decvax!ucbvax!menlo70!sri-unix!mclure Thu Jan 7 17:07:17 1982 Queen vs. Rook This two-part article by Warren Stenberg and Edware J. Conway is reprinted from the January, 1979 issue of the Minnesota Chess Journal. It relates the details of a very significant event: a human grandmaster being taught something new about a "well known" ending by a chess playing computer. QUEEN vs. ROOK Part One: Beer in the Ear by Warren Stenberg Alfred Sheinwold, the celebrated Bridge columnist, records in one of his articles some valuable advice he received from his fa- ther as a young man. "Son", said the elder Sheinwold, "some day you are going to meet a stranger who will offer to bet you five dollars that he can make the Jack of Spades jump out of the pack and squirt beer in your ear. Now, son, don't you bet him, for, sure as you do, you are going to get an earful of beer." Unfortunately for him, GM Walter Browne did not have the bene- fit of such sage parental counsel and consequently wound up with some figurative beer in his figurative ear. What happened was that Browne was slickered into betting $100 that he could beat a computer with King and Queen vs. King and Rook. Though given two and a half hours and fifty moves, Browne was unable to carry out the task and had to pay up. We can hear our readers scoffing. "Ridiculous", they say, "every book on endings tells how to win with the queen against the rook." So they do. And they are all wrong! The queen can win, right enough, but the ending is much more difficult than anyone had ever suspected. A story goes with it. Early in December the annual computer chess championship of the U.S. was held at the computer society meeting in Washington D.C., and to the surprise of almost everyone the Slate-Atkin program (Chess 4.7) was dethroned as champion. The one person who wasn't surprised was Ken Thompson of Bell Labs, creator of the new cham- pion, appropriately named "Belle". The confrontation between Belle and Chess 4.7 resembles nothing more than another showdown between David and Goliath. Belle was playing on the modest PDP-11 computer (in the under $100 thousand price range) while Chess 4.7 enjoyed the facilities of the gargantuan CDC Cyber 176 computer (which weighs in at about $10 million counting all its peri- pherals.) But, like David with his slingshot, Belle also had its equalizer. The gimmicks which carried Belle to victory were three special "hardware" components for move generation, position evaluation and managing of the tree search. By having these processes hard-wired, much time is saved over carrying out the same tasks by programming (or "software".) This was enough to carry Belle to triumph in the tournament and in its individual encounter with Chess 4.7. But this may not mean that Chess 4.7 is washed up. Thompson estimates Belle's rating at about 1850, whereas Chess 4.7 currently boasts a 2040 rating. Either Thompson's evaluation of his creation is too modest, or its vic- tory was something of a fluke. After the tournament was over the CDC representative, the affa- ble Dave Cahlander, got together with the victorious Ken Thomp- son, and learned that Ken had some other tricks up his sleeve. In particular, Ken had done a complete computer analysis of the Queen vs. Rook ending and discovered that it was much more dif- ficult than popularly supposed. He had tried his program out against a number of strong players, including some masters, with remarkable results. The humans with the queen just couldn't win against the computer with the rook. Thompson had been negotiat- ing to get GM Robert Byrne to compete against his program at the Washington meeting; Byrne put in an appearance but cannily de- clined to play. Thompson's method of programming his ending is very easily described. Because there are only four pieces on the board, it is possible to store all possible positions in the computer's memory. Now each of these positions is given a number in the following way. Each position in which White (the player with the Queen) can force mate or win the Rook in one move is given the number one. Each position in which White can force a position numbered one in a single move is given the number two. Each po- sition in which White can force a position numbered two in a sin- gle move are assigned the number three. And so on. In this way every position got a number -- the number of moves to mate. The highest number was 31. This means that, starting from the worst possible position, the player with the queen can mate or win the rook in no more than 31 moves -- with best play. And so the computer's program for playing the ending is trivial. When the computer's turn to move comes, it merely looks at all positions it can reach in one move and selects the one with the highest number. (Remember that the computer, with the rook, is trying to maximize the number of moves to mate.) From this description it should be clear that the human player (with the queen) can never decrease his number by more than one, but that if he makes a really bad move, he can increase his number by a lot. Cahlander brought the news of these remarkable developments back to Minnesota and set up arrangements for experimenting with this ending against Minnesota players. Tom Unger, Ron Elmquist, state champion Roger Rudolph, MSCA President George Tiers, Jeff Pennig and Chuck Fenner were recruited to gather at Stenberg's to tilt by telephone against the computer at Bell Labs in New Jer- sey. Curt Brasket was also approached but his work required him to be out of town at the time. But Univac was represented by El- liot Adams (a member of the team which created the Black Knight computer chess program) who came to see the show. Ken Thompson was quite disappointed at the low calibre of the opposition; he felt that no one rated below 2400 would have a chance. So Cahlander tried to figure out how to lure a real star to participate. Byrne had side-stepped a confrontation in Wash- ington; a small honorarium was unlikely to be effective; but su- pose it were to be put in the form of a bet...? Which prominent chess player would be most attracted by a bet? Put in this way, the question answers itself, and Cahlander was soon on the phone to Walter Browne. Browne couldn't resist the chance to win $100 on a "sure thing." When the participants gathered at 6:30 PM some of the local players took on the computer without success. But when Browne checked in by phone at 8:00 PM all the other players stopped to watch the Master. Browne was started with the worst possible po- sition (31 moves to mate.) He assured the programmers that he would need nothing like the alloted 2.5 hours, half an hour should suffice. Famous last words! On move 17 Browne chased a will-o-the-wisp and tried to capture the rook; this caused him to drop six steps backward. On move 27 he was 14 moves to mate. On move 34 he was 17 moves to mate so that there was no way he could possibly win. He was still 17 moves to mate when he ran out of time before he had used up his alloted fifty moves. Browne remarked that he hadn't taken the whole thing all that seriously. We can certainly believe that! For Whom the "Belle" Tolls Walter Browne Belle W:KQR8 QQR5 B:KKB3 RK1ch K3r//5k/Q///// 1. k-n7 r-k2ch 24. q-q4 r-b7ch 2. k-b6 r-k3ch 25. k-k4 r-b3 3. k-q7 r-k2ch 26. q-q5ch k-k2 4. k-q8 r-k5 27. k-k5 r-kr6 5. q-qb5 r-k4 28. q-n7ch k-q1 6. q-q4 k-b4 29. q-kb7 r-qb3 7. k-q7 r-k5 30. k-q5 r-qn3 8. q-q3 k-b5 31. k-b5 r-qr6 9. k-q6 r-k6 32. q-b4? k-kb3 10 q-q4ch r-k5 33. q-kr4 k-k2 11 q-b2ch k-n5 34. k-q5 k-b2 12 k-q5 r-k1 35. k-k5 r-k3ch 13 q-kb6 r-k6 36. k-b5 r-q3 14 k-q4 r-kb6 37. q-qb4ch k-k2 15 q-kn6ch k-b5 38. k-k5 r-kr3 16 q-n2 r-qr6 39. q-b7ch k-b1 17 q-b6?? r-r8 40. k-b5 k-k1 18 q-b7ch k-b4 41. q-b1 r-q6 19 q-b2ch k-k3 42. q-b8ch k-k2 20 q-q2 r-r2 43. q-b7ch r-q2 21 q-n4 r-k2 44. q-b5ch k-q1 22 k-k4 k-b3ch 45. k-q6 r-qn2 23 k-b4 k-k3 46. draw agreed Notes: 1. lost 1 move; 17. lost 6 moves; 18 lost 2 moves (20 to mate); 21. lost 2 moves; 25. 17 moves to mate; 27 14 moves to mate; 30. 12 minutes 31. 14 moves to mate; 32. 17 moves to mate; 34. 17 moves to mate; 40. 14 moves to mate Browne wanted a chance to win his money back and proposed some five-minute games at ten dollars a game. Thompson and Cahlander agreed, and two games were played with Belle winning the first and Browne the second. By the time the seance was over we had been on the phone for five and a half hours -- on a three way conference call between California, New Jersey and Minnesota! Belle Labs (a division of Am. Tel. & Tel.) picked up the phone bill (or so they told Stenberg.) Browne was given a chance to try the ending again a couple of weeks later, as he still wanted to win the $100 back. Even those people who thought the computer would win the bet the first time around gave it little chance on the rematch. After all, Browne is one of the top players in the world, the only U.S. player (except for the reticent Bobby Fischer) who is conceded much of a chance of ever getting as far as the Candidate's Matches; and this time he would be well prepared and aware of the nature of the difficulties. Also, Browne, after his first try at the end- ing had been allowed to see the computer play itself, thus seeing the shortest way of winning. Belle vs. Belle (from position above) 1 Ka7 Re7+ 2 Kb8 Re8+ 3 Kc7 Re7+ 4 Kd8 Re4 5 Qa8 Re3 6 Kc7 Ke5 7 Qa5+ Ke4 8 Kd6 Kf4 9 Qh5 Rd3+ 10 Kc5 Ra3 11 Qh2+ Kg5 12 Qd2+ Kf5 13 Qc2+ Kg4 14 Kd4 Rf3 15 Qg2+ Rg3 16 Qe2+ Kg5 17 Qe5+ Kh4 18 Qe1 Kh3 19 Qh1+ Kg4 20 Ke4 Kg5 21 Qh2 Kg4 22 Qh6 Rg2 23 Qg6+ Kh3 24 Qh5+ Kg3 25 Ke3 Rg1 26 Qe5+ Kg2 27 Ke2 Rh1 28 Qe4+ Kg1 29 Qg4+ Kh2 30 Kf2 R any 31 Q mate Of course, Browne was to be given a different starting position (one which also required 31 moves) but even so the principles should remain the same. Browne allowed that he had studied the ending very carefully, but he was certainly not over-confident; in fact he demanded mre favorable conditions than on the first trial. He was to win the bet if he could checkmate or win the rook in fifty moves (as be- fore), but wanted the bet to be tied if he could accomplish the task between moves 51 and 55. Victory went to Browne this time, but it was no cinch. What happened was that he managed to win the rook on move 50! Browne was quite fascinated by this experience and says that he intends to take this show on the road. He intends to offer the following proposition at his exhibitions: the player with the queen gets ten minutes and the player with the rook gets five minutes and Browne will take either side for a ten dollar bet. The events described in this article mark a historic occasion in the computer's participation in the game of chess. For the first time the computer has shown that a long held view as to how a certain type of position should be handled, is in fact, entirely incorrect. Also, for the first time a computer has actually taught a Grandmaster how to treat a certain type of position. There there is an entirely new role for the computer in the game of chess. Anyone trying to predict how large a role this may eventually become is likely to wind up with egg on his face (or beer in his ear.) Part two: Browne's triumph by Edware J. Conway On Saturday, Dec 30, 1978, Grandmaster Walter Browne got his re- venge against the Belle computer in the Queen vs. Rook ending by beating it in a thrilling 50 move encounter. Browne played from his home in Berkeley CA, and Belle was in New Jersey. The third part of the phone hookup was here in Minnesota, with Dave Cah- lander and CHuck Fenner of CDC, while Dale Beihoffer and Ed Con- way reported for MCJ. Browne had shown great courage in accepting the bet and trying to beat this computer program the first time. Ken Thompson, who had programmed BELLE, had offered his bet to Botvinnik and Byrne, but they turned him down; Botvinnik no longer competes, and Byrne appeared not to be interested. But Browne had taken the bet and lost $100 ($50 each to Cahlander and Thompson); now he was trying to get his money back. How would he do? Stenberg thought that the computer analysis that Browne had seen was very suggestive and that he would deduce enough from it to win; so did Cahlander and Thompson. Certainly Browne has tremen- dous talent and drive - three U.S. Championships in a row - and had now had time to analyze. Was that enough? Browne was the least optimistic of anyone! He had played Belle and knew it was tough. It is the new U.S. Computer Chess Champion, having recent- ly dethroned Chess 4.7. It has won speed games against Masters at the Westfield Chess Club in New Jersey. But Browne is a fighter and wanted to win! So began the game. We list the computer's exact analysis of the minimum number of moves to win, as it shows how Browne was doing. And we did have fun predicting the moves and judging how well we would have done - and actually Dale Beihoffer did remarkably well, to the point of being a serious contender! The starting position was 2KQ////2r/2k/// with White to move and win in 31 moves. Of course at the beginning the Rook checks whenever it can. Browne had been worried about this and about spite checks at the end, so he hustled Cahlander and Thompson into a "bets-off" clause if it took him 51 to 55 moves to capture/mate. The time control was therefore agreed to be 55 moves in 2.5 hours. White: Walter Browne Black: Belle 1 Kb7 Rb4+ 6 Qe5 Kd3 11 Qg3+ Ke2 (21) 2 Kc6 Rc4+ 7 Kb5 Re4 (25) 12 Qc3 Rf4 (20) 3 Kb5 Rb4+ 8 Qf6 Ke3 (24) 13 Kd5 Rh4 (19) 4 Ka5 Re4 9 Kc5 Rf4 (23) 14 Qc2+ Ke3 (18) 5 Qd6 Rd4 10 Qg6 Ra4 (22) 15 Qd1! Kf2 (17) Browne stated that this move "deserves an exclamation point". All his moves have been very good, as the computer analysis shows he is making steady progress. 16 Qd2 Kf3 (17) 18 Qd1+ Kf4 (18) 20 Kd4 Rf5 (19) 17 Qe1 Rg4 (19) 19 Qe2 Rg5+ (20) 21 Qe3+ Kg4 (18) Apparently White's 16th, 17th and 19th moves are inferior, be- cause the computer analysis shows that no progress is being made. Ken Thompson had tried this program on lower rated players and finds that they go wrong when 14 to 16 moves away from the win. This "barrier" occurs when the White King is trying to cross the blockaded 3rd or 4th rank. The books don't help in dealing with this "barrier". Fine's analysis, for example, is correct after the Black King is cornered but is of no use at this point. For quite a while Browne battles this "barrier" and eventually crosses it. This was all very exciting - fear and hope intermin- gled - could he do it? 22 Ke4 Rf7 (17) 27 Qa3 Rf4 (15) 32 Ke5 Kg6 (14) 23 Qg1+ Kh5 (16) 28 Qh3+ Kg5 (16) 33 Qh8 Rg5+ (14) 24 Qg3 Rf8 (15) 29 Qg3+ Rg4 (15) 34 Ke6 Rg4 (14) 25 Ke5 Rf7 30 Qe5+ Kh4 26 Ke6 Rf8 (14) 31 Qh2+ Kg5 Ouch! 14 plus 34 equals 48 - with perfect play White could still win - but will he ever cross the "barrier"? Champion that he is, right now he does it! 35 Qg8+ Kh5 39 Qh6+ Kg4 (9) 43 Ke3 Rg1 36 Qh7+ Kg5 40 Ke4 Rg2 44 Qg5+ Kh2 37 Ke5 Rg3 41 Qg6+ Kh3 45 Qh4+ Kg2 38 Qg7+ Kh4 42 Qh5+ Kg3 46 Ke2 Ra1 (4) This part was played very fast by Browne and it was tense, for if Browne had lost three moves he could not win. In fact he lost two. He can win it now, just under the wire. There was a long pause, and Dale Beihoffer quickly found the "obvious" 47 Qg5+ 48 Qh6+ 49 Qg7+ 50 Q:a1 and wins. But why is Browne taking so long? He came up with a less obvious move: 47 Qe4+ Kh3 48 Qh7+ Kg3 49 Qg7+ Kh3 50 Q:a1 & wins So Browne did it - and got his money back. He could have come out ahead if he had accepted David Levy's wager on the rematch! You ask "What is the value to chess in all this?" Now we have much more insight into the problems posed by this hitherto un- derestimated ending. Part three: A Point for Our Side by John Larkins (from the April-May 1979 issue of Chess Voice) The preceeding presents a dramatic example of the growing strength of chess-playing computers. But one usually has mixed feelings when reading about such advances: a growing respect for the computers, but also a sinking feeling that they will soon be taking over our game. There is a sidelight to the previous sto- ry, however, that may help erase some of that forboding. The key to the computer's success was the beautifully simple and powerful mode of analysis programmed into it by Ken Thompson. Apparently for the first time ever, this assigned to each posi- tion the number of moves required to mate and thus allowed an ex- haustive analysis of all variations. But was it the first time ever? Chess Voice Games Editor Richard Shorman was strongly impressed by the computer's performance, but he pointed out to me that the same method of analysis had been applied to Queen and Rook endings and had produced the same con- clusion in a book published 89 years ago! This book, ANALYSIS OF THE CHESS ENDING KING AND QUEEN AGAINST KING AND ROOK (authored by "Euclid" and edited by E. Freebor- ough), was published in London in 1895 by Kegan Paul, Trench, Trubner & Co.. It has long been out of print and is now difficult to obtain, but a number of prized copies have been in circulation for years. Shorman has one of them and was kind enough to lend it to me. The book is hansomely printed with a gold leaf chessboard on its hard cover and it contans 144 pages of analysis accompanied by 191 diagrams -- 28 of them classified as key positions. The book is reputed to have been the work of an Englishman with the mar- velously chessic name of Crosskill. The book's introduction lays out the method of analysis and the conclusion reached by it: "...the number of moves necessary to win the game from any given point is definitely fixed." " The view commonly held and expressed that there could be no practical difficulty in winning with Queen against a Rook was... discarded as illusory." (pp. iv-v) It is true that not everything "taught" by the computer can be found in Euclid. All his diagrams start with the losing King only one or two squares from the edge of the board and the procedures for driving the King to that position are pretty much taken for granted. But, beyond that point, Euclid's analysis corresponds with the computer's. One ironic possibility (I have no information one way or the oth- er) is that Ken Thompson wrote his 1978 computer program with a copy of Euclid's 1895 book in his hand. The use of a chess-playing computer to teach chess to one of the world's leading grandmasters stands on its own as a truely signi- ficant event in the continuing competition of men and machines at the chessboard. But it is comforting to know that, in this case at least, man got there first. The computer turns out not to have broken new ground, but to have called to our attention what Euclid had published 89 years ago, but which somehow never got into the standard books on endings. ----------------------------------------------------------------- gopher://quux.org/ conversion by John Goerzen of http://communication.ucsd.edu/A-News/ This Usenet Oldnews Archive article may be copied and distributed freely, provided: 1. There is no money collected for the text(s) of the articles. 2. The following notice remains appended to each copy: The Usenet Oldnews Archive: Compilation Copyright (C) 1981, 1996 Bruce Jones, Henry Spencer, David Wiseman.