stringtranslate.com

Alejandro Brudno

Alexander L'vovich Brudno ( ruso : Александр Львович Брудно ) (10 de enero de 1918 - 1 de diciembre de 2009) [1] fue un informático ruso , mejor conocido por describir completamente el algoritmo de poda alfa-beta . [2] Desde 1991 hasta su muerte vivió en Israel.

Biografía

Brudno desarrolló la "interfaz matemáticas/máquina" para la computadora M-2 construida en 1952 en el laboratorio Krzhizhanovskii del Instituto de Energía de la Academia Rusa de Ciencias en la Unión Soviética . [3] [4] Era 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 se utilizó en un programa de ajedrez informático 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 Museo de Historia de la Computación , el algoritmo se utilizó más tarde en Kaissa , campeona mundial de ajedrez por computadora 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 rusas de programación para estudiantes y publicó un libro con los problemas de estas competiciones.

Brudno – Seminario de Kronrod

En 1959, Brudno y Alexander Kronrod organizaron un seminario dedicado a la presentación de diferentes trabajos en las á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, entre ellos: 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 la poda alfa-beta . La intuición clave fue que un jugador podía evitar evaluar ciertos movimientos que eran claramente inferiores a uno ya considerado.

En el siguiente árbol de juegos, los vértices representan posiciones y los bordes representan movimientos. Las valoraciones de la posición están entre paréntesis.

 A / \a
  ? /\ re(1) mi(?)

Supongamos 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 los "blancos" es AB y no es necesario verificar 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 de que la contribución de Brudno fuera la formalización. algoritmo y análisis de su aceleración.

En 1959, el trabajo de Brudno sobre la poda alfa-beta estuvo 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 juegue primero. Cada jugador coloca una carta, la carta más grande hace la baza y la que la toma es la primera en el siguiente movimiento. El objetivo es determinar una estrategia óptima dada la mano inicial y el orden de movimientos de los jugadores. 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 alfa-beta temprana

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] 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 siguió avanzando.

Notas

  1. ^ Alexander Brudno en la biblioteca pública (en ruso)
  2. ^ Marsland, TA (mayo de 1987). "Métodos de ajedrez por computadora (PDF) de la Enciclopedia de Inteligencia Artificial. S. Shapiro (editor)" (PDF) . J. Wiley e hijos. págs. 159-171. Archivado desde el original (PDF) el 5 de febrero de 2009 . Consultado el 21 de diciembre de 2006 .
  3. ^ EM Landis , IM Yaglom , Recordando a 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.
  4. ^ "La rápida computadora digital universal M-2". Museo Ruso de Computación Virtual . 1997–2006. Archivado desde el original el 20 de diciembre de 2010 . Consultado el 20 de diciembre de 2006 .
  5. ^ McCarthy, John (27 de noviembre de 2006). "La IA a 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 .
  6. ^ Newell, Allen; Simon, Herbert A. (marzo de 1976). "La informática como investigación empírica: símbolos y búsqueda". Comunicaciones de la ACM . 19 (3): 113–126. doi :10.1145/360018.360022. S2CID  5581562.
  7. ^ Richards, DJ; Hart, TP (4 de diciembre de 1961 - 28 de octubre de 1963). "La heurística Alfa-Beta". Memos de IA . Instituto de Tecnología de Massachusetts. hdl :1721.1/6098. OBJETIVO-030.
  8. ^ Kotok, Alan (3 de diciembre de 2004). "Memorando 41 sobre inteligencia artificial del MIT". Archivado desde el original el 21 de julio de 2011 . Consultado el 1 de julio de 2006 .
  9. ^ * 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.
  10. ^ 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

Enlaces externos