The Kibitzer 
by Tim Harding

CHESS COMPUTERS AREN'T REALLY SO CLEVER

It is time for The Kibitzer to take a look at the world of computer
chess. This article was written, to meet the deadline, after the first
two games in the Kasparov-Deep Blue 2 match. By the time most
of you read this column the match will be over, so I shall touch on
it tangentially but not attempt to report on it. 

Many others are doing that, and my own report will appear in the
7/1997 issue of my magazine "Chess Mail." 

I have been following chess and computing since the 1970s; prior
to that computer chess was largely the preserve of university
research on mainframe or minicomputers. The first Chess
Challenger "dedicated" chess computer appeared in European
shops for the Christmas market in 1977, followed in the next few
years by various competitors; many of these were very crude but
some of the top-of-the-range models could set ordinary club
players serious problems by the mid-1980s. It was at least another
decade before PCS became fast and powerful enough to run a
program that could rival the performance of the dedicated
computers that could do nothing except play chess. 

Some of you may have read my two books on the subject, both
long out of print now, "The Chess Computer Book" (Pergamon
1981) and "The New Chess Computer Book" (Pergamon 1985).
These dealt with the early days of commercial chess-playing
computers; as part of the research for the first book, in March 1981
I organised a two-day humans v computers tournament,
Computachess 81, at Dublin's ancient university, Trinity College
with 24 human and 16 computer opponents. Computer v computer
pairings were avoided whenever possible. This event was hardly a
scientific test but was amusing and some interesting results were
generated. 

Here is an example from the 1981 event in which the Sargon 2.5
program (White) defeated a young player rated 1609: 1 Nf3 d6 2
Nc3!? e5 3 d4 exd4 4 Nxd4 Nf6 5 e4 Be7 (Suddenly it's a Philidor
Defence.) 6 Bc4 Bd7 (Too passive; 6...0-0 followed by ...c6 is
better, striving for ...d5 and maybe even threatening ...Nxe4.) 7 Bf4
0-0 8 0-0 Nc6 9 Nxc6 Bxc6 10 Qd4 Re8 11 Rfd1 Bf8. Even early
computers tended to be good in such open classical positions. 12
e5! dxe5 13 Bxf7+! Kxf7. 

Black should have tried 13...Kh8! since although 14 Qc4 wins the
exchange the computer would still have had opportunities to slip
up afterwards. 14 Qc4+ Bd5 15 Nxd5 Re6 16 Nxc7 Qc8 17 Bxe5
Ne8 18 Rd8! 1-0. I didn't run a similar event for the second edition
of the book because by then the performance of computers against
humans under match conditions was becoming better known, with
many people entering "their" computers in weekend tournaments,
but I did run a match between computers and players from my
local club. 

In recent years the top computers have been good enough to give
strong human players a tough game as the series of AEGON man v
machine tournaments has shown, although it is encouraging that a
human master won the 1997 event with a score of 100%! 

By the mid-1980s chess computers were becoming big business
and it became nearly impossible to keep up with the rate of
development. I left the job of testing new models and programs to
others; nowadays Eric Hallsworth in England and a team of testers
in Sweden publish regular computer rating lists and write about
computer performance in Eric's bi-monthly magazine "Selective
Search." You can also follow computer chess debates in the Usenet
newsgroup rec.games.chess.computer although you may find much
of the topics very technical. 

Programming a computer to play chess is not easy and those who
do it well have usually made a career of it, improving their
knowledge incrementally and also benefitting from the rapid
advances in hardware (especially faster processors and cheaper
RAM) to do things that were just impossible or too expensive in
the 1970s and 1980s. Undoubtedly many of the latest programming
ideas are trade secrets but you can get a fair idea of what's going on
behind the scenes from "Selective Search." 

The theoretical basis for programming computers to play chess
goes back to the paper Claude E. Shannon of Bell Telephone Labs
wrote on the subject in the late 1940s. The first computer world
championship was held in 1974 and computer championships
became fairly regular events from the late 1970s, with separate
microcomputer events from which the programs running on big
hardware were excluded. The early days of 1970s computer chess
competition can still be read about in the collection "Chess Skill In
Man and Machine" edited Peter W. Frey (Springer-Verlag 1977)
and "The Machine Plays Chess?" by Alex G. Bell (Pergamon,
1978). 

"Artificial intelligence" was a buzzword in the 1980s and several
books were published dealing with the academic research into
chess programming, many of these being papers read at
conferences. Some of these topics may have been blind alleys;
others pointed the way towards Deep Blue 2. The first "Advances
In Computer Chess" conference book came out in 1977, followed
by others in 1980, 1982 and 1986. Most of these papers are very
technical. 

A selection of previously published material was collected and
edited by David Levy (chief organiser of the upcoming Mind
Sports Olympiad) in 1988, under the title "Computer Chess
Compendium." 

The trend through the 1980s and 1990s has been to eschew some
of the theoretical concepts seen in these papers, which aimed to try
to make a computer play chess more like a human master.
Botvinnik's much-hailed Pioneer project (which he described in the
late 1960s) never came to anything and that also seems to have
been the case, for whatever reason, with other university-based
projects. 

Pure "brute-force" programs, that just aimed to defeat opponents
by out-calculating them, have the shortcoming that if positions
cannot be reached in which there are favourable continuations, the
programs can only win by exploiting opponents' blunders.
Therefore some "intelligence" has to be built into brute-force
programs is required, but one short-cut to this now is to provide the
programs with ever-larger and more sophisticated openings books.
This means that the chances are that the opponent (human or
machine) will make a tactically exploitable error before the
program has to start thinking "strategically." The hardware
advances of recent years have made it ever-easier to concentrate on
developing brute-force methods, backed up by improving the
computers' endgame play, which has usually been their weakest
point - unless they can reach an endgame that has been completely
"solved". 

Even today's very advanced PC programs are still capable of
making surprising mistakes, however. The following case even
made me wonder if today's commercially-oriented programmers
were aware of all the academic literature I mentioned above. 

In the current (April-May) issue of "Selective Search" I read how
the programmers of Hiarcs, one of the stronger PC programs of
recent years, decided to rush out a new version 6 early this year,
because of a bug found in version 5. This bug was discovered by
Swedish testers, who play games out to a finish. 

The official statement on the release of HIARCS6 included these
sentences: "After extensive post-release testing at tournament time
controls it has been observed that HAIRCS5 occasionally takes a
draw by repetition in a totally won position. Most users have never
seen this, as they will have resigned long beforehand! However
occasionally HAIRCS5 will make a mate announcement and then
go round in circles, allowing the draw instead of completing the
mate!" 

This sounded familiar to me, although Eric Hallsworth gave no
examples in his magazine. Then I remembered the COKO incident! 

Turn the clock back a quarter of a century to the 1971 ACM
tournament. The program COKO III was White against GENIE in
the following position. 

White: Ke2, Qe4, Rh1, Bf1; pawns - a2, b2, c4, e3, f2, g2, h2.
Black: Kd6, Ra8, Re8; pawns - a7, b7, c6, f6, g5. 

Here White has an overwhelming material advantage (despite
having not moved two of its pieces) and continued its king-hunt
by: 28 c5+! Kxc5 29 Qd4+ Kb5 30 Kd1+ Ka5 31 b4+ Ka4 32 Qc3. 

This is the kind of position that probably arose in the HIARCS5
case; its programmers and testers had the programs set to stop and
record a win when one side had an advantage this big. No doubt if
you give this precise position to HIARCS5, it will win it, but
something of this kind must have happened. 

Now COKO threatens immediate mate by Qb3 so Black, being a
computer, did not resign but postponed the evil hour by a few
checks. 32...Red8+ 33 Kc2 Rd2+ 34 Kxd2 Rd8+ 35 Kc2 Rd2+ 36
Qxd2 It is hard to understand why COKO took with the queen this
time instead of Kxd2 leaving the Qb3 mate in place. Confronted
with every variation showing nearly an infinite plus score, it must
have become disorientated, and 25 years later a similar bug
affected HIARCS; probably it gave perpetual check instead of
mating. But this is only the beginning; see what happened next to
poor COKO: 

36 Ka3 37 Qc3+ Kxa2 

Now of course there is a mate in one but apparently nothing in
COKO's code told it mate in one is superior to mate in two or three
or four Black does not threaten to eliminate the mate so COKO
continued: 38 Kc1????! 

And the game went on: 38...f5 39 Kc2 f4 40 Kc1 g4 41 Kc2 f3 42
Kc1 fxg2 43 Kc2 gxh1=Q I think if HIARCS landed up in this
position it would definitely play Qb2 mate at last but COKO was
stuck in a loop, and after 44 Kc1?? Qxf1+ it even lost in the end! 

It is extremely improbable that anything like this could befall Deep
Blue 2 but you can never be sure. There could be bugs lurking
inside Deep Blue 2 that a handful of games are insufficient to
discover and exploit, even in a six-game match against the world
champion. 

The IBM programming team are reported as saying that they no
longer find that PC programs offer worthwhile opposition for Deep
Blue 2 so we are talking here about hardware many times more
sophisticated and powerful than that on which you or I may run a
program like HIARCS, Genius, Fritz or Rebel. It may be that the
best of those programs is in no way inferior to Deep Blue 2 if they
were running on identical hardware but I guess we'll never know. 

Even the old rule of thumb that computers are strong in tactical
situations, but prone to error in positional games, is going out of
the window now. With Deep Blue 2 playing the first game against
Kasparov like a maniac and the second like Karpov, it's clear that
both humans and computers have a lot to learn about chess! 

Israeli grandmaster Yona Kosashvili (rating 2560) was the winner
of the 1997 AEGON human v computer tournament in the
Netherlands recently. He won all his games and here is the one
from the last round. 

Kosashvili - CHESSICA The Hague, 1997 

1 c4 e5 2 Nc3 Nf6 3 e4 This is a relatively unusual move, 3 g3 or 3
Nf3 being normal. 3...c6 4 d4 According to the Encyclopaedia of
Chess Openings (ECO) this is an error because of the reply and
White is supposed to play 4 Nf3 here. 4...Bb4 ECO says Black has
some advantage now, citing the Bulgarian master Malich as its
authority. Perhaps, however, Kosashvili had investigated this line
for himself, or else he just recovered well in the next few moves? 5
dxe5 Many human players are afraid of tactical skirmishes against
computers but they can be won if the master calculates accurately
the kind of end-position which the computer will misjudge. 5
..Nxe4 6 Qd4 Qa5 7 Nge2 Nc5 Black threatens 8...Nb3 winning
the exchange so White covers the b3 square. 8 Qd1 d5 Black has a
lead in development and probably calculated principally the
variations resulting from captures on d5; now 9 cxd5 Bf5 would
give Black a strong initiative. However, castling would have been
safer. 9 a3 White will demonstrate that the computer's pieces are
not so well placed after all. If Black exchanges on c3 he will
clearly stand badly, so... 9...d4 DIAGRAM. White's next move is a
deep strategic sacrifice, which will confuse the computer's
evaluation function. 10 axb4!! Not 10 Qxd4 Nb3 nor 10 Nxd4
Bxc3+. For a slight material disadvantage, White now achieves a
fine position. 10...Qxa1 11 Nxd4 Ne6 12 Nb3 Qa6 13 c5 b5 14
Qd6 Computers have been taught to set a high value on castling so
CHESSICA makes it a priority to enable this. 14...Bd7 14...Qb7
seems better, trying to get the queen to a useful square (d7 or e7) as
soon as possible. 15 f4 Nd8 16 f5 Nb7 The situation of Black's
queen is comical. She has no moves at all. 17 Qd3 0-0 18 f6 Now
the castled king position is vulnerable. 18...Re8 19 Qg3 Bg4 The
computer gives up a piece to postpone its doom. If 19...g6 20 Qf4
and mate can only be postponed by 20...Nd8 21 Qh6 Rxe5+ 22
Be2 Ne6 23 Nd4 Qa1 24 Nxe6 Qxc1+ 25 Qxc1 with an easy win
for White. 

20 Qxg4 g6 21 Bf4 Nd8 22 Bd3 Ne6 23 0-0 Nd7 24 Bg3 Qb7 25
Ne4 Red8 26 Nd6 Qc7 27 Rc1 Rab8 28 Nd4 Nxd4 29 Qxd4 The
machine, in a completely lost position, now makes the kind of
move that shows that programming a chess computer is not an
exact science: 29...Rb6?? 1-0 CHESSICA's operator pulled the
plug since there is no reason not to play cxb6. 

The computers won the event overall, but since there were fifty of
them and fifty human players, I don't consider that as significant as
the fact that humans took the first three places. 

Maybe the evolution of computer chess will one day even prove
the old Weaver Adams conjecture that White has a forced win at
chess? Then we'll all have to decide whether we are too old to take
up the Japanese game of GO instead.