Chessbase News, Germany
April 1 2004
Kimo – a new approach for chess engines
01.04.2004 Traditional chess programs blindly search millions of
postions to find good moves. A new chess program due for release this
month breaks with the tradition. It works with chess knowledge
derived from 20,000 master games. Tests with a late beta version show
that in spite of some glaring defects Kimo is able to hold its own
against the world’s strongest programs. Details…
Kimo – a new approach to chess programming
Most chess programs available on the market today are built on the
principle of super-fast full-width searches. They generate large
numbers of positions, and use tiny bits of chess knowledge to
evaluate them. This method has hoisted them to the very highest
levels of tournament play.
But is this “brute force” approach the only way to achieve chess
excellence? Instead of looking at literally billions of positions
between moves, is it not possible to insert enough chess knowledge
into a program to make it understand the difference between
meaningful continuations and the purely nonsensical moves that
traditional chess programs spend 99.999% of their time examining.
The new program Kimo, created by a team of Russian programmers
(hailing originally from Armenia and neighboring republics), sets out
to do exactly that. Kimo’s algorithms are based not on a brute force
search but rather on chess knowledge derived from around 20,000 high
quality games. These have been extensively analysed by the program,
which draws heuristic conclusions on the principles of chess: the
value of the pieces in different positions, their strenghs and
weaknesses, attacking and defensive motifs, etc.
In tournament games Kimo relies to a great extent on these
heuristics, which are applied to pattern the computer recognises on
the chess board. It also conducts a traditional look-ahead, but the
search is highly selective and only takes into consideration
“promising” lines of play. According to its authors Kimo generates “a
million times less moves” than traditional chess programs.
It is of interest to note that former world champion Mikhail
Botvinnik, who pioneered the concept of knowledge-based chess
programming, directly contributed important elements that are today
part of Kimo’s chess heuristics.
Testing Kimo
The program Kimo 1.0 is due to appear in the European computer stores
later this month. In the US there will be a two-month delay due to
import restrictions caused by the massively parallel hardware requred
to run the Russians program. The German magazine Computerschach &
Spiele (CSS) managed to get a late beta version and run initial tests
on it. A full report by Lars Bremer is included in the April edition
of CSS. Bremer is an experienced editor of Europe’s biggest computer
magazine C’T and is an expert on computer games (you may want to
download his Munstrum program).
Traditionally chess programs that are tested by CSS must first
absolve a rigorous test suite of chess positions in which the program
must find certain key moves. This “Weltmeister-Test” suite (which you
can download here) is derived exclusively from games played in world
championship matches. This led to a first problem for the CSS
testers. The 20,000 games used to prime Kimo’s chess knowledge
included all world championship games, and these were in fact given
high priority in the data mining process. The result is that Kimo
solves most of the positions in the “Weltmeister-Test” almost
instantaneously – simply because it recognises them. This naturally
allows us to draw few conclusions regarding playing strength of the
program.
In his next test Lars Bremer ran a series of informal blitz games
against other programs, with disasterous results for Kimo. Even older
versions of Fritz were able to beat the Russian program, despite the
fact that Kimo usually came out of the opening with an excellent
position. This was probably because the program has a tiny but very
high-class openings book.
Here is a typical position in a blitz game against its rivals:
White has a satisfactory position in spite of (or because of) its
advanced castle pawns. A good continuation would have been Rf3 with
slight advantage. But Kimo somewhat recklessly sacrifices the
exchange with 16.Qf3?, expecting to launch a decisive king-side
attack. After stubborn defence by Fritz White simply ended up with
material down and a lost position.
The results of the tests on the blitz level were indicative of a
principle shortcoming of the program: its tactical vulnerability.
Tima and again Kimo would get promising positions, and then, based on
its knowledge heuristics, play an over-optimistic move to ruin the
position and lose the game. Lars Bremer estimates that Kimo will not
be able to occupy a place amongst the top programs in the blitz
rating lists.
Tournament games
At slower speeds the situation is a different one. In ten games
against today’s top programs Kimo scored exactly 50%, much to the
astonishment of the CSS testers. The general impression was that the
program was positionally superior to its opponents, with occasional
tactical lapses costing it a possible victory. The individual scores
in the test matches were 3:3 against Deep Junior 8 and 2:2 against
Deep Fritz 8 – putting Kimo right on the top of the rating lists at
classical time controls.
The following game is a typical example of Kimo’s positional
abilities, which always appear when the position is devoid of
short-term tactical tricks.
Kimo vs Deep Fritz 8
In closed positions with locked-up pawn structures Kimo reigns
supreme. Here it has tied up one of the strongest programs in the
world and masterfully manoeuvred its pieces for the final assault.
42.Nxb7 Rxb7 43.Nxa6 won a pawn, maintained the pressure on Black’s
position and quickly won the game.
But we have to return to the tactical weaknesses, to which Kimo is
particularly prone in open positions. Here is an example from the
test match against the Israeli program Deep Junior:
Kimo vs Deep Junior 8
Kimo is a pawn down but has initiative. But instead of playing
32.Ng6+ and going for the sure draw Kimo 32.Rh5?? In its main line
the program displayed 32…Qxd4 33.Rxh7+ Kxh7 34.Qxf5+ and perpetual
check. If we look at the log files we discover that it did consider
the killer 32…Nxd4 briefly, but evaluated the position after
33.Ng6+ Kg8 34.Ne7+ Kf8 35.Nd5 Rxh7 as 0.84 pawns better for White.
What Kimo overlooked — and that is the main weakness of the
“knowledge” method — is that after 35…Nb3+! 36.Kc2 Na1+! White is
going to be mated. The game ended 32…Nxd4 33.Ng6+ Kg8 34.Ne7+ Kf8
35.Nd5 0-1.
The following test game looked like a loss for Kimo, but the program
simplified the position and, with the help of its unknowing opponent,
set up the following fortress position:
Deep Junior 8 – Kimo
The position is a dead draw, and Kimo displays this in its main line
(0.00). Junior, on the other hand, thinks it has a winning advantage
(+2.65). Other programs show a similar evaluation. And this is what
makes Kimo so exceptional: in a static analysis of the position,
assisted by a short, highly selective search, the program has
determined that Black has a safe draw since the white rooks are
permently tied to the defence of the b-pawn. Such analysis is out of
the reach of all its computer colleagues.
Conclusions
In summary the CSS testers come to the following conclusion:
On analysis levels Kimo often finds incredible moves, which other top
programs will not be able to see or understand. The openings book is
tiny by today’s standard (just 30,000 positions, compared to many
millions for the other programs), but of such high quality that we
have yet to see Kimo come out of book with an inferior position. In
middlegame positions it is very reliable in finding good, solid
moves, many of which actually seem to initiate long-term strategic
plans. The endgame is generally played at a very high level, but
unfortunately the manufacturers have failed to implement five and
six-piece tablebases, which put Kimo at a distinct disadvantage when
playing against other top programs.
In general Kimo is a very promising step in the attempt to discard
pure brute force and use the “knowledge” method. It’s the over-all
playing strength is quite astonishing and equal to that of the top
programs. As an analytical tool Kimo shows constistant flashes of
brilliance, but it can also miss important tactical points. You
should definitely double-check Kimo analysis with Fritz, Junior or
Shredder before you put full faith in it.
But the biggest problem with Kimo is the running expense. The program
will only work on a custom-built massively parallel hardware, and it
also requires extensive care and maintenance. All of this is
exorbitantly expensive compared to contemporary cash-and-carry PCs.
We estimate that each game played by Kimo can run a bill of thousands
of dollars.
For this reason the CSS editors conclude that Kimo is not yet ready
to compete commercially with the other engines. But it is aa very
interesting new direction and worthy of being watched.
http://www.chessbase.com/newsdetail.asp?newsid=1558