Alexander L'vovich Brudno (russian: Александр Львович Брудно) (10 January 1918 – 1 December 2009)
was a
Russian
Russian(s) refers to anything related to Russia, including:
*Russians (, ''russkiye''), an ethnic group of the East Slavic peoples, primarily living in Russia and neighboring countries
*Rossiyane (), Russian language term for all citizens and peo ...
computer scientist
A computer scientist is a person who is trained in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...
, best known for fully describing the
alpha-beta pruning Alphabeta is an Israeli musical group. Alphabeta or Alpha Beta may also refer to:
*The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters
*Alpha Beta, a former chain of Californian supermarkets
*Alpha and beta anomers ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
.
From 1991 until his death he lived in Israel.
Biography
Brudno developed the "mathematics/machine interface" for the
M-2 computer constructed in 1952 at the Krzhizhanovskii laboratory of the Institute of Energy of the
Russian Academy of Sciences
The Russian Academy of Sciences (RAS; russian: Росси́йская акаде́мия нау́к (РАН) ''Rossíyskaya akadémiya naúk'') consists of the national academy of Russia; a network of scientific research institutes from across t ...
in the
Soviet Union
The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a transcontinental country that spanned much of Eurasia from 1922 to 1991. A flagship communist state, it was nominally a federal union of fifteen national ...
.
He was a great friend of
Alexander Kronrod
Aleksandr Semyonovich Kronrod (russian: Алекса́ндр Семёнович Кронро́д; October 22, 1921 – October 6, 1986) was a Soviet mathematician and computer scientist, best known for the Gauss–Kronrod quadrature formula wh ...
.
Brudno's work on
alpha-beta pruning Alphabeta is an Israeli musical group. Alphabeta or Alpha Beta may also refer to:
*The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters
*Alpha Beta, a former chain of Californian supermarkets
*Alpha and beta anomers ...
was published in 1963 in Russian and English.
The algorithm was used in
computer chess
Computer chess includes both hardware (dedicated computers) and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysi ...
program written by Vladimir Arlazarov and others at the
Institute for Theoretical and Experimental Physics
The Institute for Theoretical and Experimental Physics (ITEP; Russian Институт теоретической и экспериментальной физики) is a multi-disciplinary research center located in Moscow, Russia. ITEP carries ou ...
(ITEF or ITEP). According to Monty Newborn and the
Computer History Museum
The Computer History Museum (CHM) is a museum of computer history, located in Mountain View, California. The museum presents stories and artifacts of Silicon Valley and the information age, and explores the computing revolution and its impact on ...
, the algorithm was used later in
Kaissa
Kaissa (russian: Каисса) was a chess program developed in the Soviet Union in the 1960s. It was named so after Caissa, the goddess of chess. Kaissa became the first world computer chess champion in 1974 in Stockholm.
History
By 1967, a ...
the world computer chess champion in 1974.
In 1980, Brudno became a founder and scientific director of the first Russian school for young programmers
УПЦ ВТ. He was the scientific director of the first Russian programming Olympiads for the students, and published a book of problems from these competitions.
Brudno – Kronrod seminar
In 1959 Brudno and
Alexander Kronrod
Aleksandr Semyonovich Kronrod (russian: Алекса́ндр Семёнович Кронро́д; October 22, 1921 – October 6, 1986) was a Soviet mathematician and computer scientist, best known for the Gauss–Kronrod quadrature formula wh ...
organized seminar devoted to the presentation of different works in areas of system programming, programming of games (including chess), and artificial intelligence. Many well known results were presented and discussed at this seminar, including:
Gauss–Kronrod quadrature formula
The Gauss–Kronrod quadrature formula is an adaptive method for numerical integration. It is a variant of Gaussian quadrature, in which the evaluation points are chosen so that an accurate approximation can be computed by re-using the information ...
,
AVL trees
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node d ...
,
computer chess
Computer chess includes both hardware (dedicated computers) and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysi ...
,
Pattern recognition
Pattern recognition is the automated recognition of patterns and regularities in data. It has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphi ...
(M. Bongard
:ru:Бонгард, Михаил Моисеевич, P. Kunin and others),
Method of Four Russians In computer science, the Method of Four Russians is a technique for speeding up algorithms involving Boolean matrices, or more generally algorithms involving matrices in which each cell may take on only a bounded number of possible values.
Idea
...
and others.
In 1963 Brudno published his work on
alpha-beta pruning Alphabeta is an Israeli musical group. Alphabeta or Alpha Beta may also refer to:
*The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters
*Alpha Beta, a former chain of Californian supermarkets
*Alpha and beta anomers ...
. The key intuition was that a player could avoid evaluating certain moves that were clearly inferior to one already considered.
In the following game tree vertices represent positions and edges represent moves. The position's valuations are in the brackets
.
A
/ \a
?
/ \
D(1) E(?)
Assume that "whites" should make a move in position A and then "blacks" could make their own move. ‘Whites" should find better strategy to maximize their win (
Minimax
Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When de ...
strategy).
After evaluating AB and CD, it is easy to see that the best move for "whites’ is AB and it is not necessary to check move CE as the overall value of vertex C will be no better than 1. This is unchanged if B, D, E are trees and not leaves. Such considerations, taken on all levels of the game tree, are known as alpha-better pruning. It has been used in different game programming applications even before Brudno's work; Brudno's contribution was the formalization of the algorithm and analysis of its speedup.
In 1959 Brudno's work on alpha-beta pruning was motivated by an analysis of the card game where two players are dealt n cards each, with values 1...2n, and one player is chosen to go first. Each player puts down one card, with the larger card taking the trick, and the taker going first in the next move. The goal is to determine an optimal strategy given the players initial hand and move order. The analysis of this card game was used in the seminar to refine the understanding of recursion and structured programming, and development of updatable dictionaries.
Early alpha-beta pruning
Allen Newell
Allen Newell (March 19, 1927 – July 19, 1992) was a researcher in computer science and cognitive psychology at the RAND Corporation and at Carnegie Mellon University’s School of Computer Science, Tepper School of Business, and Department ...
and
Herbert A. Simon
Herbert Alexander Simon (June 15, 1916 – February 9, 2001) was an American political scientist, with a Ph.D. in political science, whose work also influenced the fields of computer science, economics, and cognitive psychology. His primary ...
who used what
John McCarthy calls an "approximation"
in 1958 wrote that alpha-beta "appears to have been reinvented a number of times".
Arthur Samuel
Arthur Lee Samuel (December 5, 1901 – July 29, 1990) was an American pioneer in the field of computer gaming and artificial intelligence. He popularized the term "machine learning" in 1959. The Samuel Checkers-playing Program was among the wo ...
had an early version and Richards, Hart, Levine and/or Edwards found alpha-beta independently in the
United States
The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country primarily located in North America. It consists of 50 states, a federal district, five major unincorporated territorie ...
.
McCarthy proposed similar ideas during the
Dartmouth Conference
The Dartmouth Conference is the longest continuous bilateral dialogue between American and Soviet (now Russian) representatives. The first Dartmouth Conference took place at Dartmouth College in 1961. Subsequent conferences were held through 1990 ...
in 1956 and suggested it to a group of his students including
Alan Kotok
Alan Kotok (November 9, 1941 – May 26, 2006) was an American computer scientist known for his work at Digital Equipment Corporation (Digital, or DEC) and at the World Wide Web Consortium (W3C). Steven Levy, in his book '' Hackers: Heroes of th ...
at MIT in 1961.
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
and Ronald W. Moore refined the algorithm in 1975
and it continued to be advanced.
Notes
References
*
* (Also in ''Problems of Cybernetics'', 10:225–241)
* Брудно А. Л., Л.И. Каплан, Олимпиады по программированию для школьников, Наука, 1985
External links
* Handwritte
letter (12.04.1971)an
postcard (19.11.1971)from Brudno to
A. P. Ershov.
*
{{DEFAULTSORT:Brudno, Aleksandr
Computer chess people
Russian computer scientists
Soviet inventors
Soviet computer scientists
1918 births
2009 deaths