Computer chess pioneer Mikhail Donskoy passes on

World-famous Russian programmer dies

14 January 2009: Mikhail Donskoy, an outstanding Russian IT specialist, one of the developers of the Kaissa chess program, died on 13 January at the age of 61. Kaissa was designed in the mid-60es by a group of Soviet mathematicians. In 1967, it defeated the a program developed at the Stanford University, and in 1974 became the first world champion in a chess programme competition.

Donskoy was also the chief system programmer for the INES data management system and created the INES archival system. The INES system was in the 80es installed at more than two thousand large production facilities across the USSR.

In 1988, Donskoy assembled a group of professionals to develop a new chess game for PCs, based on the Kaissa algorithm. The group of experts was made into the Paragraph company and later transformed into the independent firm DISCo, headed by Mikhail Donskoy. [Original report in English, Russian and Tatar – but we could not find the last link].

Mikhail Donskoy, 1948–2009

Mikhail Vladimirovich Donskoy, (1948 - January 13, 2009) was a Russian computer scientist and chess programmer. In 1971 he joined with Vladimir Arlazarov and Anatoly Uskov to program the successor of the ITEP Chess Program on an ICL System 4/70 at the Institute of Control Sciences, called Kaissa, which became the first World Computer Chess Champion in 1974 in Stockholm. The development of Kaissa was accompanied by Georgy Adelson-Velsky, Alexander Bitman, Alexander Brudno, Sasha Resnitsky, Boris Stilman and Mikhail Botvinnik.

From 1982 Mikhail Donskoy was the chief system programmer for the INES DBMS, the INES archive system original programmer. Since 1989 he was leader of the programmers group later growing into DISCo (Donskoy's Interactive Software Company). Mikhail Donskoy died of cancer at age 60. Misha Donskoy kept his illness a secret even from his best friends, who were shocked to learn about his death. We contacted two of them who sent us the following brief messages.

David Levy, London
Mikhail Donskoy was a kind and pleasant gentleman, and was an excellent ambassador for his country when he came to Stockholm in 1974 with his chess program KAISSA, there to win the first World Computer Chess Championship. Misha achieved much in the early days of computer chess but was always modest about his achievements. He was an excellent host to those from our community who had the good fortune to meet with him when visiting Moscow, and he remained interested in computer chess long after his own program ceased to participate. He and I were last in touch as recently as last month, arranging for his son Andrew to take delivery of a replica of the Shannon Trophy that the ICGA has made for all previous World Computer Chess Championship winners.

Monty Newborn, McGill University, Canada
In the good old days when Capitalism and Communism clashed, there was one bright light of cooperation between the West and the USSR that I was happy to be a part of. In the world of computer chess, the Soviet scientists were eager to cooperate with those of us in the West and us equally. Tony Marsland was the first to become involved, but Ken Thompson and I also enjoyed the comradeship and scientific involvement with Misha Donskoy and clan. Misha hosted us on a number of visits and showed us the best of times. We spoke about politics for hours with him. As a scientist and programmer he was first rate, with a strong understanding of how computers should be programmed to play, and actually doing the programming. He led the Soviet effort at a time when programming was far more difficult than it is today, and computers were far less capable. Of course, most notably, he will be remember as having developed the first world championship chess program, KAISSA.

To which we add our own memories...

Frederic Friedel, Hamburg, Germany
I met Misha Donskoy twice in Moscow and at a number of computer chess events. Once I was in Moscow with Ken Thompson, and we spent the afternoon with Mikhail Botvinnik and his team of programmers who had developed the "intelligent" program Pioneer. The same evening we visited Vladimir Alazarov, where Misha was also present. The afternoon had been spent with diffuse explanations of "force trajectories" and "attacking potential". In the evening I listened to Vladimir and Misha explain to Ken how they were able to save a few CPU cycles on each position in the (brute force) search with some clever algorithmic tricks. The two teams were worlds apart. Late at night the ladies left the room and Alazarov put four bottles of vodka on the dining table. When I tried to pour myself a glass from the one he had opened he stopped me and pointed to another. It was "my bottle," one each for of the four men present. Once Donskoy was in Canada and we took him to what at the time was the world's largest mall (I believe it was the West Edmonton Mall). It had indoor roller coasters, swimming, skiing, ice hockey – even an indoor beach. Misha looked around the gigantic, glittering mall and had two words of comment: "Like GUM". [Only people from the Soviet era will appreciate this comment. GUM was a "department store" complex, directly adjacent to the Red Square in Moscow. This is what it looked like at the time. We had great times with Misha and thoroughly enjoyed his wry humour. He will be missed.

Excerpt from the book How Computers Play Chess by David N. L. Levy and Monroe Newborn, W H Freeman & Co, August 1990. We reproduce it with kind permission of the autors. Note that a number of present-day algorithms – like null move and killer heuristics – were being used by the Kaissa team back in the 70s.

KAISSA

In 1971 a group of programmers at the Institute of Control Science began to rewrite the ITEP program that had been used in the 1967 match with Stanford, and by the following year it was ready, in its new form, to play a two game match against the readers of the newspaper Komsomolskaya Pravda. On most Sundays throughout 1972 the newspaper published KAISSA's moves in each of the two games and the readers sent in their suggested replies. In every case the move suggested by the majority of the readers was chosen and KAISSA's reply was published the following week. KAISSA drew one game and lost the other. The previous year Spassky had played two games against the readers of the same newspaper and scored one win and one draw. Obviously the combined force of the readership of Komsomolskaya Pravda produces rather strong chess and the program's result was quite creditable. KAISSA's basic look-ahead was set at seven ply, with further analysis along variations that involved captures and other forcing moves.

Thus KAISSA made its public debut. When the newspaper games ended the programming team continued to work on the program. Altogether about ten people were involved, including most of the group that created the ITEP program plus Mikhail Donskoy, who had just graduated from Moscow State University and who assumed the leading role in KAISSA's creation.

Soviet scientists (l-r): Vladimir Arlazarov, Alexander Ushkov and Mikhail Donskoy at Moscow’s Institute for Control Science, who in 1971 created the chess program Kaissa which included many original software features such as “bit boards.”

KAISSA used a complex evaluation function involving many features. In fact it was so complex that when I first asked Donskoy about it he replied "... I don't even remember what is in it." The program used the familiar method of searching all moves to a specified depth and then considering only captures, checks, other forcing moves and moves that were replies to checks. An upper bound of 30 plies was put on the depth of these forcing variations but this depth was reached very seldom during the tree search.

KAISSA used a slight modification to the alpha-beta algorithm so that before the search for a move began the values of alpha and beta were not set to minus infinity and plus infinity (as was usually the case in those days) but to rather narrower limits between which the value of the current position was expected to lie. In this way the search was reduced still further. This technique is known as windowing.

Monroe Newborn (far right, with daughter Amy) with the developers of the Soviet chess computer Kaissa (from left): Sasha Resnitsky, Boris Stilman, Misha Donskoy and former World Champion Mikhail Botvinnik

An improvement in the performance of the alpha-beta search was obtained by using what the programmers called the "best move service." They point out that in chess the number of possible moves (less than 10,000) is far smaller than the number of possible positions and that a classification of moves is therefore much easier than a classification of positions. The underlying principle of the best move service is that a move which was the best in many similar positions would most likely be plausible in the current position.

For each ply, ten moves were stored. These were the moves that were most frequently the best ones in other positions at the same depth. When ordering the moves from a particular position these "best moves" were put at the head of the list and hence they were considered earlier. The application of the best move service produced a ten-fold reduction in the time taken to search trees whose basic depth was five plies. This use of best moves soon became known as killer moves.

Vladimir Arlazarov, Ken Thompson and Mikhail Donskoy in 1992

Another innovation was the idea of introducing a dummy move at certain points in the game tree. If it is White's turn to move and Black makes a "blank" move then it is White's turn to move once again. If White can now gain a material advantage then the previous White move must have carried this threat. Under some circumstances a threat can be used to create a cut-off in the search process and this technique can therefore lead to a further reduction in the search time. Another use of the discovery of threats was that they can be included in the list of moves that need to be examined.

KAISSA was able to reduce its search still further by being able to recognize positions that were analogous to positions that had already been examined. If a move is absurd in a particular position then it is likely to be absurd in similar positions and it can therefore be excluded from the search until such time as circumstances appear that change the variation arising after the absurd move. A simple example of this strategy can be shown by considering the following position.

Under normal circumstances a chess program would always consider the moves Qd2-d4 and Qd2-g5 when making a move from this position, and KAISSA's use of the blank move would normally result in these two moves being considered because they are threats. But in the present position both moves are absurd because they put the white queen en prise. Let us assume that White plays 1.a2-a3 and that Black replies 1...a7-a5. Now most programs would once again consider 2.Qd2-d4 and 2.Qd2-g5, even though both moves are still absurd for the same reasons, but KAISSA has a list of all the squares attacked by each of Black's pieces and it would not consider Qd2-g5 until Black's h-pawn had advanced, nor would it examine Qd2-d4 until the black knight had moved. This is how a human plays chess and KAISSA's programmers pointed out that the standard of a human's play increases with the accuracy with which he determines when a move rejected earlier as absurd should be re-examined. (KAISSA defined absurd moves as those that lead to the immediate loss of material.)

The only problem in implementing this "method of analogies" was in deciding when the position had changed sufficiently to warrant re-examining a move that was rejected earlier. KAISSA's programmers made some progress in solving this problem but their research is beyond the scope of this book.

Misha Donskoy at the World Computer Chess Championship in Stockholm 1974

KAISS A's first appearance outside the Soviet Union came in August 1974 when it participated in the 1st World Computer Championships in Stockholm. It won two of its games very convincingly, it was temporarily in trouble in a third and totally lost for much of the game in the vital last round. But in the end KAISSA won all four games and the title of World Champion.

The second world computer chess championship in 1977 in Toronto, started with an unusual occurrence that led to a position that has gone down in computer chess history:

In the diagram Kaissa, which played black, gave away a rook with the move 34...Re8? and lost afterwards. A catastophic program bug, to give the rook for nothing? That was what most of the spectators believed. But later the programmers entered the obvious move 34...Kg7 into the program. Kaissa immediately explained why it didn't like it: 34...Kg7 35. Qf8+!! Kxf8 36. Bh6+ Bg7 37. Rc8 and white checkmates in two moves. This caused a sensation and was published in many chess magazines of that time. None of the human spectators present saw this nice queen sacrifice. As the result of this, Kaissa finished tournament 2nd-3rd (tied together with the "Duchess" program).

Links

• Mikhail Donskoy
• Kaissa
• Михаил Донской: История “Каиссы”
• Михаил Донской: Жизненный цикл программиста
• Жизненный цикл программиста