Kaissa

Kaissa was a chess program developed in the USSR in the 1960s. In 1972, it was named Kaissa by the Soviet journalist A. Khenkin, after the muse of chess Caissa, invented by Sir William Jones in 1763. Kaissa dominated international computer chess from 1974 to 1977. Kaissa made use of a pruning technique called "the method of analogies," meaning postions that were so alike that the same score could be attributed to all. Kaissa was revolutionary in its use of analogous positions and tree searching methods for reductions of computational load.

The original program was written by Vladimir Arlazasov, Alexander Bitman (Russian national chess master), Anatoly Uskov, Alexander Zhivotovsky, and later improved by Mikhail Donskoy (1948-2009). The first Soviet chess program was written around 1963. The program was written for the Fast Universal Digital Computer M-2, which had been used for rocket design and nuclear physics.

Kaissa evolved from the Institute for Theoretical and Experimental Physics (ITEP) and the Institute for Systems Science in Moscow, headed by mathematician Georgy Adelson-Velsky (1922- ). During a visit to the Soviet Union in 1965, Professor John McCarthy (1927-2011) accepted a challenge to have the Kotok-McCarthy chess program play the Soviet chess program.

Kaissa evolved from a chess program used in a USA-USSR computer chess match in 1967-68 in which the USSR program defeated the Stanford program, written by John McCarthy and Alan Kotok (1941-2006), with 2 wins and 2 draws.

USSR Program (Kaissa) – USA Program (Stanford), March 10, 1967, game 3

1.e4 e5 2.Nf3 Nc6 3.Nc3 Bc5 4.Nxe5 Nxe5 5.d4 Bd6 6.dxe5 Bxe5 7.f4 Bxc3+ 8.bxc3 Nf6 9.e5 Ne4 10.Qd3 Nc5 11.Qd5 Ne6?! (11…d6) 12.f5 Ng5? 13.h4 f6 14.hxg5 fxg5 15.Rxh7 Rf8 16.Rxg7 c6 17.Qd6 Rxf5 18.Rg8+ Rf8 19.Qxf8 mate 1-0

In 1971 Donskoy began work on the new program, written in Assembly.

In 1971, Kaissa ran on a mainframe (British ICL System 4/70 computer) equipped with a 64-bit processor. 64 is also the number of squares on a chessboard, so it was possible to use a single memory word to represent a yes-or-no or true-or-false predicate for the whole board. This was called the bit board. The ICL 4/70 computer had 24,000 bytes of memory. It enabled the program to evaluate 200 positions per second. It could store 10,000 opening positions in its memory. The program was written in Assembly language. The Assembly code occupied 384K bytes (8-bit words). The Russians would have had a more powerful chess program if it had used an IBM machine, but they were not allowed to buy or use one. The speed of the ICL 4/70 was 900,000 instructions per second. Previously, the ICL computer was being used by the Institute of Geophysics to calculate the probabilities of earthquakes.

Kaissa was a Shannon type A program that search 7 ply full width, with extensions for captures, checks, and forcing moves. The program employed the alpha-beta technique with a "window." The program introduced a feature called "best move service," storing a table of the 10 best moves. This was used to improve move ordering for the alpha-beta method. Another feature was a "dummy move," in which one side does nothing at its turn and used to discover threats.

From January through November, 1972, Kaissa played a correspondence chess match against the readers of “Komsomolskaya Pravda,” which was the newspaper of the communist youth wing. It drew one game and lost one game against the readers. The most votes for a move by the readers in a week was chosen as the move against Kaissa.

From 1971 to 1974, Kaissa had played 50 chess games, but no previous tournament experience.

In August 1974 the International Federation for Information Processing (IFIP) held the first large-scale international chess tournament for chess computers. The event was held in Stockholm and lasted 4 rounds and 4 days. The tournament director was International Master David Levy (1945- ).

Kaissa won the first World Computer Chess Championship in Stockholm with a perfect 4-0 score. Thirteen computers from eight nations participated in the first world computer chess championship. Kaissa had the largest book of stored openings (10,000 positions) than any other competing program. Kaissa could not run on a Stockholm ICL machine because of the special Soviet operating system, so it ran on a machine in Moscow via a telephone link.

Kaissa played Ostrich in the last round. A win for Ostrich would have given Ostrich a tie for first place. Ostrich missed two winning moves (one was a force mate in 6 moves) and lost the game. The forced mate by Ostrich involved a piece sacrifice which the program was unable to make.

In round 1, Kaissa mated Frantz in 34 moves. In round 2, Kaissa defeated Tech II in 33 moves (missing a mate in 1). In round 3, Kaissa mated Chaos in 36 moves. In round 4, Kaissa mated Ostrich in 67 moves. Earlier, Kaissa missed a forced perpetual check. Kaissa defeated 3 American entries and 1 Canadian entry to become world champion.

After the tournament, Kaissa and Chess 4.0 played in an exhibition game to determine which program was stronger. The game was adjudicated a draw after 65 moves in a rook vs rook and knight pawnless endgame. Chess 4.0 had missed a winning move earlier.

In August 1975 David Bronstein (1924-2006) supposedly used Kaissa to solve an adjourned endgame he had at a zonal tournament in Vilnius.

In 1977 the 2nd World Computer Chess Championship was held in Toronto, Canada. The event was won by Chess 4.6. Kaissa and Duchess (from Duke University in North Carolina) tied for 2nd-3rd. Kaissa was played on a IBM 370/165 machine. Kaissa lost to Duchess in the first round. After the event, an exhibition match was held between Kaissa and CHESS 4.6. CHESS 4.6 won.

In December, 1977 David Levy played a game against Kaissa and easily won. Kaissa ran on a fast Amdahl computer, but the computer operators did not optimize its performance.

In 1980 the 3rd World Computer Chess Championship was held in Linz, Austria. Belle and Chaos tied for 1st-2nd. Kaissa tied for 6th-11th place. Kaissa had a performance rating of 1637 in this event.

In 1981 Kaissa was being used to analyze 5-piece endings.

Kaissa was never improved because the Soviet government decided that the programmer's time was better spent working on practical projects. The chess group transferred to a different institute where they worked on database programming and developed the Russian equivalent of Oracle (relational database).

A PC version of Kaissa was developed in 1990. It took 4th place in the 2^nd Computer Olympiad in London in 1990.

In 1992, a Turbo C version of Kaissa was released.