Kasparov missed Beautiful win; Botvinnik's Program muffs analysis
Hans Berliner
In the ICCA Journal Vol. 16, No. 2; former World Champion M. Botvinnik
gives some positions that his new chess program, Sapiens, formerly known
as Pioneer, has solved. The first of these is from a game Kasparov-Ribli
1989, which is shown below.
-- -- -- -- -- BR BK --
-- -- -- -- -- BP BP BP
BP -- WQ -- BP -- -- --
-- WR -- -- -- -- -- --
BQ -- -- -- -- -- -- --
-- -- -- -- BB -- WP --
WP -- -- WR WP WP -- WP
-- -- -- -- -- -- WK --
Here Kasparov played 1. f:e3, and the game was agreed drawn. The Grandmaster
Raphael Vaganian pointed out that 1. Rd8! gives White some vinning chances.
Now enter Sapiens, which produced an analysis of a mere 18 nodes, and
determined that this position is a win for white with Rd8. The key line to
the Sapiens analysis is 1. Rd8!,Q:b5; 2. Qd6!,B:f2+; 3. K:f2, Re8, 4. Qe7 and
Sapiens pronounces this position as won.
The amazing thing about this analysis is that Sapiens did not even look at
any other first move than Rd8, not even 1. f:e3 which Kasparov actually
played. It also did not look at many (I think) important side variations
such at 4.-Qf5+ that could lead to perpetual check. It is an amazing
performance for a computer program. It would be even more amazing IF IT
WERE CORRECT. As it happens it is WRONG. In the final position above, 4.--
Qb6+ wins the black rook and the game, so White loses. One is naturally
inclined to ask how this program can find such brilliant moves as 1. Rd8 and
2. Qd6, and then fail so badly. Further, how could it be that Botvinnik puts
this forward as correct analysis? Did he have the same myopia?? Did the
program inherit his myopia via his programmers? More on this at the end. I
should still point out another important variation for understanding the
analysis. If Black plays 1.--R:d8; then 2. Rd5! wins the queen and the
game.
I thought the original combination would not be that difficult for a
computer, so I gave it to Hitech (brute-force). Hitech steadfastly refused
to play 1. Rd8, even at 12 ply, which should be enough to see what is going
on. So I walked it down the principal variation to the point where it
was supposed to play 4. Qe7??, and it balked at that too. When I played 4.
Qe7 for it, it immediately answered Qb6+ with a vinning score for Black.
That is how I found out that the analysis was flawed.
Well, I began to wonder how my selective search program (B* Hitech) would
do on this position. Lo and behold, after 147 nodes and 2.5 minutes, it
produced the move 1. Rd8!. Further, in order to substantiate this as the
best move, it went to a depth of 14 plus quiescence, which is just 4 short
of the whole analysis of Sapiens. Now the game continued with B* Hitech
making the White moves and I the Black: 1.--Q:b5; 2. Qd6! (62 more nodes to
extend the analysis),B:f2+; 3. K:f2 (44 more nodes), Re8; 4. a4!! ( the
vinning move ala Adams-Torre, the queen is decoyed to a square from which it
cannot give check; 129 more nodes of analysis). The game continued: Q:f5+
(after Q:a4; 5. Qe7! black can resign); 5. Kg2,Qe4+; 6. Kh3!,Qf5+; 7.
g4,Qf1+; 8. Kg3, Qe1+; 9. Kf3!,Qf1+; 10. Qe3, Qc1+; 11. Qf2 and now the only
check that Black still has is Qf4+ which loses queen for rook. To understand
the above analysis, it is important to know that the B* algorithm only
searches enough to convince itself that a particular move is best in the
current position. Thus, it would not need to see the whole analyis, but
only enough to be sure that nothing is better than the move it intends to
play.
There are similar variations if instead of 3.--Re8 black plays the immediate
3.-Qf5+ and the king hides in the same way. All this is found by B* Hitech,
but brute-force Hitech finds neither 1. Rd8 nor 4. a4. Very interesting!!
What are we to make of the various utterances of the characters in this
drama?
So the position is a win for White, and Garri missed it. I believe, 5. a4
is a true act of genius. Why did the people who commented on the game and
Botvinnik's program fail to find it? Don't ask me! It is commonplace for
even the best humans to have chess myopia; however, it is rare that their
programs inherit such myopia. I have always found that my programs are
quick to educate me when I am wrong. But then I am an experimentalist; not
a manicurist. Just in case I am not making myself very clear, it would be
possible to write a program that could produce (say) Mozart's 20th piano
concerto, if you gave it enough data to put the whole thing together.
Whether, it could compose any other music would be open to conjecture. In
any case, I feel honored to be associated with a program that outdid
Kasparov, Vaganian, Botvinnik, and the sphinx-like Sapiens.
Feng-Hsiung Hsu
>as Pioneer, has solved. The first of these is from a game Kasparov-Ribli
>1989, which is shown below.
>
> -- -- -- -- -- BR BK --
> -- -- -- -- -- BP BP BP
> BP -- WQ -- BP -- -- --
> -- WR -- -- -- -- -- --
> BQ -- -- -- -- -- -- --
> -- -- -- -- BB -- WP --
> WP -- -- WR WP WP -- WP
> -- -- -- -- -- -- WK --
>
It happened that DT-1 had analyzed this exact position with none other
than Kasparov himself back in 1990 when we were at Harvard University
for a visit.
>Well, I began to wonder how my selective search program (B* Hitech) would
>do on this position. Lo and behold, after 147 nodes and 2.5 minutes, it
^^^^^^^^^
>produced the move 1. Rd8!. Further, in order to substantiate this as the
>best move, it went to a depth of 14 plus quiescence, which is just 4 short
This must be refering to some artificial node measurements. After 2.5 min,
Hitech should have examined (100K*60*2.5) = 15 M raw nodes. Calling this
147 nodes means that each so called "node" IS about 100K nodes in typical
chess programs. This is about as meaningful as only counting the number of,
say, singularly extended nodes as the total number of nodes searched. Not
completely meaningless, but highly misleading to the average readers.
Judging from the selective depth reached, Hitech did not see the win, but
only saw that Rd8 is at least good for a draw. When we discussed the
position with Kasparov, he had already analyzed the position in great detail.
The hardest line requires WK to run all the way (30+ plies) to a7 to avoid
repetition draw. In order to see the win, the selective search depth
must reach at least 30 plies. On DT-1, this takes an 11-ply nominal
search. On DT-2, it takes 10 plies (under tournament time for a 6-processor
machine) to see the 30+ plies winning line, and 9 plies (under action time,
about 1/2 min) to play Rd8, seeing at least a draw. This is with a very
primitive quiescence search and without repetition detection for the last
4 plies. A comparable machine with a better quiescence search and with
hardware repetition detection should be able to play Rd8 in blitz time,
and possibly even seeing it winning.
>of the whole analysis of Sapiens. Now the game continued with B* Hitech
>making the White moves and I the Black: 1.--Q:b5; 2. Qd6! (62 more nodes to
>extend the analysis),B:f2+; 3. K:f2 (44 more nodes), Re8; 4. a4!! ( the
>vinning move ala Adams-Torre, the queen is decoyed to a square from which it
>cannot give check; 129 more nodes of analysis). The game continued: Q:f5+
>(after Q:a4; 5. Qe7! black can resign); 5. Kg2,Qe4+; 6. Kh3!,Qf5+; 7.
>g4,Qf1+; 8. Kg3, Qe1+; 9. Kf3!,Qf1+; 10. Ke3, Qc1+; 11. Kf2 and now the only
>check that Black still has is Qf4+ which loses queen for rook. To understand
This is not the longest line. Instead of 3. ... Re8, which left the rook
at a vulnerable position, 3. ... Qf5+ directly leads to a much longer line.
4. Kg1 (cannot play Kg2 in this line) Qb1 5. Kg2 Qe4 6. Kh3 Qf5 7. g4 Qf1
8. Kg3 Qe1 9. Kf3 Qf1 10. Ke3 Qh3 11. Kd4 (if Kd2, then Qh6, Kany g6 and the
Queen guards the rook, with an unclear ending) e5 12. Kd5 Qg2 13. Kc5 Qg1
14. Kc6 Qh1 15. Kb6 Qb1 16. Ka7 Qg1 17. Ka6 and the checks stop.
Ralf Stephan
> ... In any case, I feel honored to be associated with a program that outdid
> Kasparov, Vaganian, Botvinnik, and the sphinx-like Sapiens.
Very interesting article, thanks! Now, is there anyone at all in
the chess programming community who takes Botwinnik's program serious?
I mean, IMO the last decade has shown that a mixed approach between
brute force and selective algorithms is the way to go. Is there
more than rumours about the way Sapiens works? Please fill us in.
--
--| Ralf Stephan, Augsburg, Bavaria, Germany |-------| ra...@ark.abg.sub.org |-
--| GO d* -p+ c++ l++ m* s--/+ g++ w++ t r+ |-------| IT'S ... |-