Alexander L'vovich Brudno | |
|---|---|
 | |
| Born | (1918-01-10)10 January 1918 |
| Died | 1 December 2009(2009-12-01) (aged 91) |
| Nationality | Soviet |
| Alma mater | Moscow State University |
| Known for | Alpha-beta pruning |
| Scientific career | |
| Fields | Computer Science |
| Doctoral advisor | Dmitrii Menshov |
Alexander L'vovich Brudno (Russian:Александр Львович Брудно) (10 January 1918 – 1 December 2009)[1] was aRussiancomputer scientist, best known for fully describing thealpha-beta pruningalgorithm.[2] From 1991 until his death he lived in Israel.
Brudno developed the "mathematics/machine interface" for theM-2 computer constructed in 1952 at the Krzhizhanovskii laboratory of the Institute of Energy of theRussian Academy of Sciences in theSoviet Union.[3][4] He was a great friend ofAlexander Kronrod.
Brudno's work onalpha-beta pruning was published in 1963 in Russian and English.
The algorithm was used incomputer chess program written by Vladimir Arlazarov and others at theInstitute for Theoretical and Experimental Physics (ITEF or ITEP). According to Monty Newborn and theComputer History Museum, the algorithm was used later inKaissa 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.
In 1959 Brudno andAlexander Kronrod 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,AVL trees,computer chess,Pattern recognition (M. Bongardru:Бонгард, Михаил Моисеевич, P. Kunin and others),Method of Four Russians and others.
In 1963 Brudno published his work onalpha-beta pruning. 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 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.
Allen Newell andHerbert A. Simon who used whatJohn McCarthy calls an "approximation"[5] in 1958 wrote that alpha-beta "appears to have been reinvented a number of times".[6]Arthur Samuel had an early version and Richards, Hart, Levine and/or Edwards found alpha-beta independently in theUnited States.[7] McCarthy proposed similar ideas during theDartmouth Conference in 1956 and suggested it to a group of his students includingAlan Kotok at MIT in 1961.[8]Donald Knuth and Ronald W. Moore refined the algorithm in 1975[9][10] and it continued to be advanced.
Media related toAlexander Brudno at Wikimedia Commons| International | |
|---|---|
| National | |
| Academics | |
