Alexander Brudno - Alexander Brudno

Alexander L'vovich Brudno
Alexander Brudno Computer Chess.png
narozený(1918-01-10)10. ledna 1918
Sovětský svaz
Zemřel1. prosince 2009(2009-12-01) (ve věku 91)
Izrael
Národnostsovětský
Alma materMoskevská státní univerzita
Známý jakoProřezávání alfa-beta
Vědecká kariéra
PolePočítačová věda
Doktorský poradceDmitrii Menshov

Alexander L'vovich Brudno (ruština: Александр Львович Брудно) (10. ledna 1918 - 1. prosince 2009)[1] byl ruština počítačový vědec, nejlépe známý pro úplný popis prořezávání alfa-beta algoritmus.[2] Od roku 1991 až do své smrti žil v Izraeli.

Životopis

Brudno vyvinul "rozhraní matematiky / stroje" pro M-2 počítač zkonstruovaný v roce 1952 v laboratoři Krzhizhanovskii Energetického ústavu Ruská akademie věd v Sovětský svaz.[3][4] Byl velkým přítelem Alexander Kronrod.

Brudno pracuje na prořezávání alfa-beta vyšlo v roce 1963 v ruštině a angličtině.

Algoritmus byl použit v počítačové šachy program napsaný Vladimírem Arlazarovem a dalšími na Ústav pro teoretickou a experimentální fyziku (ITEF nebo ITEP). Podle Montyho novorozence a Muzeum počítačové historie, algoritmus byl použit později v Kaissa mistr světa v počítačových šachech v roce 1974.

V roce 1980 se Brudno stal zakladatelem a vědeckým ředitelem první ruské školy pro mladé programátory УПЦ ВТ. Byl vědeckým ředitelem prvních ruských programovacích olympiád pro studenty a vydal knihu problémů z těchto soutěží.

Seminář Brudno - Kronrod

V roce 1959 Brudno a Alexander Kronrod organizovaný seminář věnovaný prezentaci různých prací v oblastech systémového programování, programování her (včetně šachů) a umělé inteligence. Na tomto semináři bylo prezentováno a diskutováno mnoho známých výsledků, včetně: Gauss-Kronrodův kvadraturní vzorec, AVL stromy, počítačové šachy, Rozpoznávání vzorů (M. Bongard ru: Бонгард, Михаил Моисеевич, P. Kunin a další), Metoda čtyř Rusů a další.

V roce 1963 Brudno publikoval svou práci na prořezávání alfa-beta. Klíčovou intuicí bylo, že se hráč mohl vyhnout hodnocení určitých tahů, které byly jasně horší než ten, který již byl zvažován.

V následující hře představují vrcholy stromu pozice a hrany pohyby. Ocenění pozice jsou v závorkách.

         A /  a
   ? /  D (1) E (?)

Předpokládejme, že „bílí“ by se měli pohybovat v pozici A, a pak by „černí“ mohli udělat svůj vlastní tah. „Bílí“ by měli najít lepší strategii, jak maximalizovat své vítězství (Minimax strategie).

Po vyhodnocení AB a CD je snadné vidět, že nejlepší tah pro „bílé“ je AB a není nutné kontrolovat tah CE, protože celková hodnota vrcholu C nebude lepší než 1. To se nezmění, pokud B, D, E jsou stromy a ne listy. Takové úvahy, které se berou na všech úrovních herního stromu, se označují jako alfa-lepší prořezávání. Používal se v různých aplikacích programování her ještě před Brudnovou prací; Brudnovým příspěvkem byla formalizace algoritmu a analýza jeho zrychlení.

V roce 1959 byla Brudnova práce na prořezávání alfa-beta motivována analýzou karetní hry, kde jsou každému hráči rozdány n karty s hodnotami 1 ... 2n a jeden hráč je vybrán jako první. Každý hráč odloží jednu kartu, přičemž větší karta vezme trik a hráč v prvním tahu jde jako první. Cílem je určit optimální strategii vzhledem k počátečnímu pořadí hráčů a pohybů. Analýza této karetní hry byla na semináři použita k upřesnění porozumění rekurzi a strukturovanému programování a vývoji aktualizovatelných slovníků.

Včasné prořezávání alfa-beta

Allen Newell a Herbert A. Simon kdo co použil John McCarthy volá „přiblížení“[5] v roce 1958 napsal, že alfa-beta „se zdá být několikrát znovuobjevena“.[6] Arthur Samuel měl ranou verzi a Richards, Hart, Levine a / nebo Edwards našli v alfa verzi alfa-beta samostatně Spojené státy.[7][Citace je zapotřebí ] McCarthy navrhoval podobné myšlenky během Dartmouthská konference v roce 1956 a navrhl to skupině jeho studentů včetně Alan Kotok na MIT v roce 1961.[8] Donald Knuth a Ronald W. Moore algoritmus vylepšili v roce 1975[9][10] a pokračovalo to v postupu.

Poznámky

  1. ^ Alexander Brudno ve veřejné knihovně (v Rusku)
  2. ^ Marsland, T.A. (Květen 1987). „Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)“ (PDF). J. Wiley & Sons. str. 159–171. Archivovány od originál (PDF) dne 05.02.2009. Citováno 2006-12-21.
  3. ^ E.M. Landis, I.M. Yaglom, Vzpomínka na A.S. Kronrod, Anglický překlad Violy Brudno. W. Gautschi (ed.) [psáno pro Uspekhi Matematicheskikh Nauk, Anglická publikace Matematika. Vyzvědač (2002), 22-30], k dispozici na Stanford University School of Engineering SCCM-00-01 (PostScript). Citováno dne 19. prosince 2006 Archivováno 13. Června 2007 v Wayback Machine
  4. ^ Ruské muzeum virtuálních počítačů (1997–2006). „Rychlý univerzální digitální počítač M-2“. Archivováno od originálu 2010-12-20. Citováno 2006-12-20.
  5. ^ McCarthy, John (27. listopadu 2006). „AI na lidské úrovni je těžší, než se zdálo v roce 1955“. Archivováno od originálu dne 06.12.2010. Citováno 2006-12-20.
  6. ^ Newell, Allen; Herbert A. Simon (březen 1976). „Computer Science as Empirical Enquiry: Symbols and Search“ (PDF). Komunikace ACM. 19 (3): 113–126. doi:10.1145/360018.360022. S2CID  5581562. Archivovány od originál (PDF) dne 01.10.2007. Citováno 2006-12-21.
  7. ^ Richards, D.J .; Hart, T.P. (4. prosince 1961-28. Října 1963). "Alfa-Beta heuristika (AIM-030)". Massachusetts Institute of Technology. hdl:1721.1/6098. Citovat deník vyžaduje | deník = (Pomoc)
  8. ^ Kotok, Alan (3. prosince 2004). „Memo MIF o umělé inteligenci 41“. Archivováno od originálu dne 2011-07-21. Citováno 2006-07-01.
  9. ^ * Knuth, D. E.; Moore, R. W. (1975). "Analýza prořezávání alfa-beta". Umělá inteligence. 6 (4): 293–326. doi:10.1016/0004-3702(75)90019-3. : * Přetištěno jako Kapitola 9 v Knuth, Donald E. (2000). Vybrané statě o analýze algoritmů. Stanford, Kalifornie: Centrum pro studium jazyka a informací - CSLI Lecture Notes, no. 102. ISBN  978-1-57586-212-5.
  10. ^ Abramson, Bruce (červen 1989). „Strategie řízení pro hry pro dva hráče“ (PDF). ACM Computing Surveys. 21 (2): 137–161. doi:10.1145/66443.66444. S2CID  11526154. Archivovány od originál (PDF) 3. září 2006. Citováno 2006-12-21.

Reference

  • Dárek Monroe novorozenec (1980). "Brudno v Moskvě". Computer History Museum přístupové číslo 102645383. Citováno 2006-12-25.
  • Brudno, A.L. (1963). "Hranice a ocenění pro zkrácení hledání odhadů". Problém Kibernetiki. 10: 141–150. (Také v Problémy kybernetiky, 10:225–241)
  • Брудно А. ,., Л.И. Каплан, Олимпиады по программированию для школьников, Наука, 1985

externí odkazy