KAISSA by Bill Wall

Kaissa (the legendary goddess of chess) was a Soviet chess program that 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 (age 26).

Kaissa evolved from the Institute for Theoretical and Experimental Physics (ITEP) and the Institute for Systems Science in Moscow, headed by mathematician Georgi Adelson-Velskiy. The program had an Elo rating around 1600. Kaissa evolved from a chess program used in a USA-USSR computer chess match in 1967 in which the USSR program defeated the Stanford program. In 1971 Donskoy began work on the new program, written in Assembly.

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.

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.

In 1972 Kaissa played a chess match against the readers of a popular Russian newspaper (Komsomolskaya Pravda). It drew one game and lost one game against the readers.

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.

Kaissa won the first World Computer Chess Championship in Stockholm. 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 Stackholm 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 exhibion 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 supposedly used Kaissa to solve an adjourned endgame he had at a 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) 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.

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