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 <
[email protected]>
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.
