A forgotten story of Soviet AI

The names of Turing, Minsky, and McCarthy, the founders of Computer Science and Artificial Intelligence in the west, are now familiar to everybody. However, little is known about the history of AI developments under the Iron Curtain of the USSR, although sometimes the competition between two systems was not less acute that in space. Below is a forgotten story of Soviet AI presented through the lens of the life of heroes of those events, Andrey Leman and his colleagues.

The year 1955 can be considered as the start of Soviet AI, when a group of mathematicians got access to computer M-2 and began software engineering to solve scientific inquiries and math puzzles.

Andrey Leman (1940–2012), who is now known for his co-authorship of Weisfeiler-Leman algorithm, and contributions to the first Soviet database INES and the first world champion Kaissa in chess, was one of the early members of Kronrod’s group who at the time was developing first programs of AI.

His life, from the wins in math olympiads at school to the work at AI lab to later emigration to the Silicon Valley, is a symbol of the generation of talented Soviet engineers and mathematicians.

Math Olympiads

Andrey Leman had an education typical for a smart young boy of those days: good grades in math, performance in math olympiads, and studying at the best university in the country. In the era of no-internet, math olympiads were the source of inspiration to pursue a professional career in mathematics and Andrey was naturally drawn into this.

One can say that this interest in puzzles was carried over the entire life of Andrey and he continued to solve hard problems at first as a mathematician and then as a programmer. He later collected such problems into a book that for many years was the main source of preparation among Soviet students.

At the age of 17, Andrey is a freshman at the top school in USSR, Moscow State University. He studied together with Boris Weisfeiler, whom he continued to work with until Boris’ emigration in 1975. He graduates from Moscow State University in 1962 and joins “the first AI lab” in USSR.

Artificial Intelligence Lab

If there was a single man who should be named as the founder of Soviet AI, it would be Alexander Kronrod, the head of the lab. Kronrod had a very interesting path as a scientist, starting as a promising young mathematician working on complex analysis and differential equations, he volunteered to serve in the army at the beginning of World War II, which awarded him several medals for bravery but also resulted in two injuries that didn’t allow him to continue his serving. In 1945 he joined Kurchatov’s Institute working on numerical mathematics until he realizes that computations can be more fruitful than “pure” mathematics.

Four years later he became the head of the mathematical department at the new Institute of Theoretical and Experimental Physics (ITEP) with the goal to lead the innovation in nuclear physics (calculation of nuclear reactors and accelerators of elementary particles, processing the results of observations in cloud chambers, etc.) — the direction that was of huge priority to the country. If not Kronrod’s strong belief in AI, the lab would only pursue the numerical simulations and AI would probably not appear at this institute. However, the high reputation of Kronrod allowed him and his group to also work on intelligent systems that could play cards games and chess.

A trendy topic in computer science back then was the computational complexity of discrete algorithms and Kronrod’s team also contributed to it. Two members of the team, G. Adelson-Velsky and E. Landis, proposed the first self-balancing binary search tree, now known as AVL tree.

The first notions of polynomially solvable problems and NP-completeness were introduced and the lab was interested in searching fast algorithms for various problems.

Most of the problems were quickly ruled out to either P or NP-complete sets, but two practically important problems, linear programming and graph isomorphism, fell out of this classification.

Afterwards, another Soviet mathematician, Leonid Khachiyan constructed a polynomial-time algorithm for linear programming, but graph isomorphism problem is still not known to be in class P.

Naturally, members of Kronrod lab including Andrey Leman and Boris Weisfeiler were interested in graph isomorphism problem. Their first significant result is known today as the Weisfeiler-Leman algorithm (1968).

Recently the interest in Weisfeiler-Leman algorithm increased due to the development of machine learning on graphs, where it laid the foundation for graph neural networks.

This work on graph isomorphism eventually led to the first dissertation of Leman in 1971 under Kronrod supervision; however, the personal enmity of the head of the Higher Attestation Commission (HAC) with the supervisor of Andrey led to refusal for the thesis with the formulation that “it’s not mathematics”.

“I’m not a mathematician, I’m a programmer.” — Andrey bitterly responded.

He then changed his interests from combinatorics to more programmer-like problems and defended his second thesis in 1973 under the supervision of V. Arlazarov on database management. His contribution to the first Soviet database INES which was used ubiquitously in the country brought him the USSR Council of Ministers Prize.

Andrey didn’t limit himself to database programming and worked on other problems of software engineering. One of these is the development of the AI chess players that became the first world champion.

AI playing chess

A few years after Alan Turing invented his “universal Turing machine”, there was an attempt to teach a computer to play chess by the father of information theory, Claude Shannon. This idea then gained popularity and there were parallel initiatives, one in the USA and another in the Soviet Union, to develop an algorithm that could learn to play chess.

In the USA it was the program developed by John McCarthy and his students at MIT. John McCarthy, among others, coined the term “artificial intelligence” in discussion with Turing in 1952 and was a pioneer of this emerging field.

In the USSR, it was the program developed by the group of Kronrod at ITEP. The development started in 1963 in Kronrod’s lab, which included many talented mathematicians such as G. Adelson-Velskyi, V. Arlazarov, and Andrey Leman. Readers of a Soviet newspaper, Komsomolka, who had a match against it, decided to call it Kaissa — the goddess of chess.

In 1965 J. McCarthy visited USSR and agreed with Kronrod to have the first international chess match between two programs, which happened in 1967. In the match of 4 games, Kaissa demonstrated strong opening knowledge and analytical skills, winning the series 3:1. But it was just the warm-up before the world cup.

In 1969 Kronrod and other mathematicians signed the letter in the defense of another Soviet mathematician Esenin-Volpin who was unfairly condemned. Such movements were strictly forbidden in the university and unfortunately, Kronrod was fired and his laboratory was dismissed.

The members of his lab joined the Institute for Control Problems (ICP); however, Kronrod didn’t join the new lab and V. Arlazarov became the head of the team leading the development of Kaissa for the first world cup of AI chess players.

In 1974, in Stockholm, 13 programs from 8 countries were competing for the title of the world champion. The matches were held five evenings in the concert hall of the biggest hotel in the city. Six games were played at the same time. Kaissa won all four games and earned the gold medal, overtaking American rivals Chess-4, Chaos, and Ribbit with 3 points each. It was a triumph for the whole nation to see their scientists bring the first gold medal in AI chess.

Subsequently, Kronrod said: “Chess is the drosophila of Artificial Intelligence”. It’s a superb experimental animal on which researchers can test their hypotheses.

Silicon Valley

Andrey continued to work with his AI friends from Kronrod’s lab: first at ICP in 1968–76 and then at Institute for System Analysis in 1976–90 until the Iron Curtain collapsed. In 1990 Andrey joined the “landing party” of the group in Silicon Valley.

In the startup formed there, the Cognitive Technology Inc, they developed optical recognition systems that became the leader in recognition of the scanned text in different languages. Their solution Cuneiform OCR was used by many IT giants such as Oracle, IBM, and Samsung.

From 1995 to 2012 Andrey worked as a programmer in various hi-tech startups. His final employer was Invitae, a genetics company, where he developed infrastructure systems that are still heavily used by the employees. He was new to bioinformatics but his curiosity about solving challenging problems helped him to succeed in this area too.

Andrey passed away in 2012 but is remembered as a reliable colleague and loyal friend, having a great sense of humor and always ready to help.

His contributions, as well as his colleagues’, helped to grow AI from a subfield of mathematics to one the most impactful areas of science and their works are now part of the history of Soviet AI.

— — — — — — —

Acknowledgments: Much of the history is collected from the colleagues of Andrey: Igor Faradzhev, Michael Furman, Ilia Ponomarenko, Olga Weisfeiler, Vladimir Arlazarov. Some of the information presented in this text can be found in the presentation “Symmetry vs Regularity: how it started and what it led to?” by Igor Faradzhev. Some photos used in the text granted by Igor Faradzhev. I’m grateful to Alexey Ivanov for useful suggestions on editing the text.

P.S. I will continue to write about graph machine learning, so if you are interested, follow me on medium or subscribe to my telegram channel (which I update every day) or my twitter (which I update once a week).