Kimo – an 'intelligent' approach to chess

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 strengths and weaknesses, attacking and defensive motifs, etc.

In tournament games Kimo relies to a great extent on these heuristics, which are applied to patterns 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 required 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 solve 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 disastrous 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:

Kimo vs Fritz

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. Time 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 permanently 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 over-all playing strength is quite astonishing and equal to that of the top programs. As an analytical tool Kimo shows consistent 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 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 individual games played by Kimo can run a bill of tens 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 a very interesting new direction and worthy of being watched.