Alexander L'vovich Brudno ( Ruso : Александр Львович Брудно ) (10 de enero de 1918 - 1 de diciembre de 2009) [1] fue un científico informático ruso , mejor conocido por describir completamente el algoritmo de poda alfa-beta . [2] Desde 1991 hasta su muerte vivió en Israel.
Alexander L'vovich Brudno | |
---|---|
Nació | |
Fallecido | 1 de diciembre de 2009 | (91 años)
Nacionalidad | Soviético |
alma mater | Universidad estatal de Moscú |
Conocido por | Poda alfa-beta |
Carrera científica | |
Campos | Ciencias de la Computación |
Asesor de doctorado | Dmitrii Menshov |
Biografía
Brudno desarrolló la "interfaz matemática / máquina" para la computadora M-2 construida en 1952 en el laboratorio Krzhizhanovskii del Instituto de Energía de la Academia de Ciencias de Rusia en la Unión Soviética . [3] [4] Fue un gran amigo de Alexander Kronrod .
El trabajo de Brudno sobre poda alfa-beta se publicó en 1963 en ruso e inglés.
El algoritmo fue utilizado en un programa de ajedrez por computadora escrito por Vladimir Arlazarov y otros en el Instituto de Física Teórica y Experimental (ITEF o ITEP). Según Monty Newborn y el Computer History Museum , el algoritmo se utilizó más tarde en Kaissa, el campeón mundial de ajedrez informático en 1974.
En 1980, Brudno se convirtió en fundador y director científico de la primera escuela rusa para jóvenes programadores УПЦ ВТ . Fue el director científico de las primeras Olimpiadas de programación rusa para los estudiantes y publicó un libro de problemas de estas competencias.
Brudno - seminario Kronrod
En 1959 Brudno y Alexander Kronrod organizaron un seminario dedicado a la presentación de diferentes trabajos en áreas de programación de sistemas, programación de juegos (incluido el ajedrez) e inteligencia artificial. En este seminario se presentaron y discutieron muchos resultados bien conocidos, que incluyen: fórmula de cuadratura de Gauss-Kronrod , árboles AVL , ajedrez por computadora , reconocimiento de patrones (M. Bongard ru: Бонгард, Михаил Моисеевич , P. Kunin y otros), método de los cuatro rusos y otros.
En 1963, Brudno publicó su trabajo sobre poda alfa-beta . La intuición clave era que un jugador podía evitar evaluar ciertos movimientos que eran claramente inferiores a uno ya considerado.
En el siguiente árbol de juego, los vértices representan posiciones y los bordes representan movimientos. Las valoraciones de la posición están entre paréntesis.
A / \a
? / \ D (1) E (?)
Suponga que los "blancos" deberían hacer un movimiento en la posición A y luego los "negros" podrían hacer su propio movimiento. Los 'blancos' deberían encontrar una mejor estrategia para maximizar su victoria ( estrategia Minimax ).
Después de evaluar AB y CD, es fácil ver que el mejor movimiento para "blancos" es AB y no es necesario marcar el movimiento CE ya que el valor general del vértice C no será mejor que 1. Esto no cambia si B, D, E son árboles y no hojas. Estas consideraciones, tomadas en todos los niveles del árbol del juego, se conocen como poda alfa mejor. Se ha utilizado en diferentes aplicaciones de programación de juegos incluso antes del trabajo de Brudno; La contribución de Brudno fue la formalización del algoritmo y el análisis de su aceleración.
En 1959, el trabajo de Brudno sobre la poda alfa-beta fue motivado por un análisis del juego de cartas en el que dos jugadores reciben n cartas cada uno, con valores 1 ... 2n, y se elige a un jugador para que vaya primero. Cada jugador coloca una carta, la carta más grande se lleva la baza y el receptor va primero en el siguiente movimiento. El objetivo es determinar una estrategia óptima dada la mano inicial de los jugadores y el orden de los movimientos. El análisis de este juego de cartas se utilizó en el seminario para perfeccionar la comprensión de la recursividad y la programación estructurada, y el desarrollo de diccionarios actualizables.
Poda temprana alfa-beta
Allen Newell y Herbert A. Simon, que utilizaron lo que John McCarthy llama una "aproximación" [5] en 1958, escribieron que alfa-beta "parece haber sido reinventado varias veces". [6] Arthur Samuel tenía una versión temprana y Richards, Hart, Levine y / o Edwards encontraron alfa-beta de forma independiente en los Estados Unidos . [7] [ cita requerida ] McCarthy propuso ideas similares durante la Conferencia de Dartmouth en 1956 y se las sugirió a un grupo de sus estudiantes, incluido Alan Kotok en el MIT en 1961. [8] Donald Knuth y Ronald W. Moore refinaron el algoritmo en 1975 [ 9] [10] y continuó avanzando.
Notas
- ^ Alexander Brudno en la biblioteca pública (en ruso)
- ^ Marsland, TA (mayo de 1987). "Métodos de ajedrez informático (PDF) de la Enciclopedia de Inteligencia Artificial. S. Shapiro (editor)" (PDF) . J. Wiley & Sons. págs. 159-171. Archivado desde el original (PDF) el 2009-02-05 . Consultado el 21 de diciembre de 2006 .
- ^ EM Landis , IM Yaglom , Recordando AS Kronrod , traducción al inglés de Viola Brudno. W. Gautschi (ed.) [Escrito para Uspekhi Matematicheskikh Nauk , publicación en inglés Math. Intelligencer (2002), 22-30], disponible en la Escuela de Ingeniería de la Universidad de Stanford SCCM-00-01 (PostScript). Recuperado el 19 de diciembre de 2006.Archivado el 13 de junio de 2007 en Wayback Machine.
- ^ Museo Ruso de Computadoras Virtuales (1997-2006). "La Rápida Computadora Digital Universal M-2" . Archivado desde el original el 20 de diciembre de 2010 . Consultado el 20 de diciembre de 2006 .
- ^ McCarthy, John (27 de noviembre de 2006). "La IA de nivel humano es más difícil de lo que parecía en 1955" . Archivado desde el original el 6 de diciembre de 2010 . Consultado el 20 de diciembre de 2006 .
- ^ Newell, Allen; Herbert A. Simon (marzo de 1976). "La informática como investigación empírica: símbolos y búsqueda" (PDF) . Comunicaciones de la ACM . 19 (3): 113–126. doi : 10.1145 / 360018.360022 . S2CID 5581562 . Archivado desde el original (PDF) el 2007-10-01 . Consultado el 21 de diciembre de 2006 .
- ^ Richards, DJ; Hart, TP (4 de diciembre de 1961-28 de octubre de 1963). "La heurística alfa-beta (AIM-030)". Instituto de Tecnología de Massachusetts. hdl : 1721,1 / 6098 . Cite journal requiere
|journal=
( ayuda ) - ^ Kotok, Alan (3 de diciembre de 2004). "Memorando 41 de Inteligencia Artificial del MIT" . Archivado desde el original el 21 de julio de 2011 . Consultado el 1 de julio de 2006 .
- ^ * Knuth, DE; Moore, RW (1975). "Un análisis de la poda alfa-beta". Inteligencia artificial . 6 (4): 293–326. doi : 10.1016 / 0004-3702 (75) 90019-3 . : * Reimpreso como Capítulo 9 en Knuth, Donald E. (2000). Artículos seleccionados sobre análisis de algoritmos . Stanford, California: Centro para el estudio del lenguaje y la información - CSLI Lecture Notes, no. 102. ISBN 978-1-57586-212-5.
- ^ Abramson, Bruce (junio de 1989). "Estrategias de control para juegos de dos jugadores" (PDF) . Encuestas de computación ACM . 21 (2): 137-161. doi : 10.1145 / 66443.66444 . S2CID 11526154 . Archivado desde el original (PDF) el 3 de septiembre de 2006 . Consultado el 21 de diciembre de 2006 .
Referencias
- Obsequio de Monroe Newborn (1980). "Brudno en Moscú" . Número de acceso al Museo de Historia de la Computación 102645383 . Consultado el 25 de diciembre de 2006 .
- Brudno, AL (1963). "Límites y valoraciones para acortar la búsqueda de estimaciones". Problemy Kibernetiki . 10 : 141-150.(También en Problems of Cybernetics , 10 : 225–241)
- Брудно А. Л., Л.И. Каплан, Олимпиады по программированию для школьников, Наука, 1985
enlaces externos
- Carta manuscrita (12.04.1971) y postal (19.11.1971) de Brudno a AP Ershov . (en inglés y ruso)