Alexander Brudno

Alexander L'vovich Brudno
Alexander L'vovich Brudno
Born	January 10, 1918; Soviet Union
Died	December 1, 2009 (aged 91); Israel
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: Александр Львович Брудно) (January 10, 1918 – December 1, 2009)[1] was a Russian computer scientist, best known for fully describing the alpha-beta pruning algorithm.[2] 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 in the Soviet Union.[3][4] He was a great friend of Alexander Kronrod.

Brudno's work on alpha-beta pruning was published in 1963 in Russian and English.

The algorithm was used in computer chess program written by Vladimir Arlazarov and others at the Institute for Theoretical and Experimental Physics (ITEF or ITEP). According to Monty Newborn and the Computer History Museum, the algorithm was used later in Kaissa 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 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. Bongard ru:Бонгард, Михаил Моисеевич, P. Kunin and others), Method of Four Russians and others.

In 1963 Brudno published his work on alpha-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.

Early alpha-beta pruning

Allen Newell and Herbert A. Simon who used what John 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 the United States.[7] McCarthy proposed similar ideas during the Dartmouth Conference in 1956 and suggested it to a group of his students including Alan 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.

Notes

Alexander Brudno at Public Library (in Russian)
Marsland, T.A. (May 1987). "Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)" (PDF). J. Wiley & Sons. pp. 159–171. Archived from the original (PDF) on 2009-02-05. Retrieved 2006-12-21.
E.M. Landis, I.M. Yaglom, Remembering A.S. Kronrod, English translation by Viola Brudno. W. Gautschi (ed.) [written for Uspekhi Matematicheskikh Nauk, English publication Math. Intelligencer (2002), 22-30], available at Stanford University School of Engineering SCCM-00-01 (PostScript). Retrieved on 19 December 2006 Archived June 13, 2007, at the Wayback Machine
Russian Virtual Computer Museum (1997–2006). "The Fast Universal Digital Computer M-2". Archived from the original on 2010-12-20. Retrieved 2006-12-20.
McCarthy, John (27 November 2006). "Human Level AI Is Harder Than It Seemed in 1955". Archived from the original on 2010-12-06. Retrieved 2006-12-20.
Newell, Allen; Herbert A. Simon (March 1976). "Computer Science as Empirical Inquiry: Symbols and Search" (PDF). Communications of the ACM. 19 (3): 113–126. doi:10.1145/360018.360022. Archived from the original (PDF) on 2007-10-01. Retrieved 2006-12-21.
Richards, D.J.; Hart, T.P. (4 December 1961 – 28 October 1963). "The Alpha-Beta Heuristic (AIM-030)". Massachusetts Institute of Technology. hdl:1721.1/6098. Cite journal requires |journal= (help)
Kotok, Alan (3 December 2004). "MIT Artificial Intelligence Memo 41". Archived from the original on 2011-07-21. Retrieved 2006-07-01.
- Knuth, D. E.; Moore, R. W. (1975). "An Analysis of Alpha-Beta Pruning". Artificial Intelligence. 6 (4): 293–326. doi:10.1016/0004-3702(75)90019-3. :* Reprinted as Chapter 9 in Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102. ISBN 978-1-57586-212-5.
Abramson, Bruce (June 1989). "Control Strategies for Two-Player Games" (PDF). ACM Computing Surveys. 21 (2): 137–161. doi:10.1145/66443.66444. Archived from the original (PDF) on September 3, 2006. Retrieved 2006-12-21.

gollark: Oh BEES, email selfhosting.

gollark: As if you needed MORE reasons to utilise git.osmarks.net!

gollark: !git pull

gollark: !pull

gollark: !help

References

Gift of Monroe Newborn (1980). "Brudno in Moscow". Computer History Museum accession number 102645383. Retrieved 2006-12-25.
Brudno, A.L. (1963). "Bounds and valuations for shortening the search of estimates". Problemy Kibernetiki. 10: 141–150. (Also in Problems of Cybernetics, 10:225–241)
Брудно А. Л., Л.И. Каплан, Олимпиады по программированию для школьников, Наука, 1985

External links

Handwritten letter (12.04.1971) and postcard (19.11.1971) from Brudno to A. P. Ershov. (in English and Russian)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Library-1] Alexander Brudno at Public Library (in Russian)

[Marsland-2] Marsland, T.A. (May 1987). "Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)" (PDF). J. Wiley & Sons. pp. 159–171. Archived from the original (PDF) on 2009-02-05. Retrieved 2006-12-21.

[LY-3] E.M. Landis, I.M. Yaglom, Remembering A.S. Kronrod, English translation by Viola Brudno. W. Gautschi (ed.) [written for Uspekhi Matematicheskikh Nauk, English publication Math. Intelligencer (2002), 22-30], available at Stanford University School of Engineering SCCM-00-01 (PostScript). Retrieved on 19 December 2006 Archived June 13, 2007, at the Wayback Machine

[M-2-4] Russian Virtual Computer Museum (1997–2006). "The Fast Universal Digital Computer M-2". Archived from the original on 2010-12-20. Retrieved 2006-12-20.

[JMC-5] McCarthy, John (27 November 2006). "Human Level AI Is Harder Than It Seemed in 1955". Archived from the original on 2010-12-06. Retrieved 2006-12-20.

[NS-6] Newell, Allen; Herbert A. Simon (March 1976). "Computer Science as Empirical Inquiry: Symbols and Search" (PDF). Communications of the ACM. 19 (3): 113–126. doi:10.1145/360018.360022. Archived from the original (PDF) on 2007-10-01. Retrieved 2006-12-21.

[Richard-Hart-7] Richards, D.J.; Hart, T.P. (4 December 1961 – 28 October 1963). "The Alpha-Beta Heuristic (AIM-030)". Massachusetts Institute of Technology. hdl:1721.1/6098. Cite journal requires |journal= (help)

[AIM41-8] Kotok, Alan (3 December 2004). "MIT Artificial Intelligence Memo 41". Archived from the original on 2011-07-21. Retrieved 2006-07-01.

[Knuth-Moore-9] Knuth, D. E.; Moore, R. W. (1975). "An Analysis of Alpha-Beta Pruning". Artificial Intelligence. 6 (4): 293–326. doi:10.1016/0004-3702(75)90019-3. :* Reprinted as Chapter 9 in Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102. ISBN 978-1-57586-212-5.

[10] Knuth, D. E.; Moore, R. W. (1975). "An Analysis of Alpha-Beta Pruning". Artificial Intelligence. 6 (4): 293–326. doi:10.1016/0004-3702(75)90019-3. :* Reprinted as Chapter 9 in Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102. ISBN 978-1-57586-212-5.

[Abramson-10] Abramson, Bruce (June 1989). "Control Strategies for Two-Player Games" (PDF). ACM Computing Surveys. 21 (2): 137–161. doi:10.1145/66443.66444. Archived from the original (PDF) on September 3, 2006. Retrieved 2006-12-21.