Pioneer o el algoritmo perdido

por Juan Manuel Marches Ríos
28/01/2015 – Botvinnik fue el primer campeón mundial de ajedrez tras la II Guerra Mundial al ganar un match-Torneo en 1948 y se mantuvo en la cumbre hasta 1963. Era también ingeniero eléctrico y se sintió atraído por todo lo relacionado con la incipiente ciencia de la computación tras una intervención con Max Euwe en 1958 en la televisión alemana. Reportaje...

ChessBase 14 Download ChessBase 14  Download

Programa de gestión de bases de datos de ajedrez que es referencia mundial. Todos usan ChessBase, desde el campeón del mundo al aficionado. Inicie su historia de éxito personal con ChessBase.

Más información...

La computadora M-20 impulsó la computación en la URSS

En la URSS se estaban ya realizando estudios sobre el tema y se estaba promoviendo la construcción de una gran computadora: la M-20 (véase Campeonato Mundial de Programas de Ajedrez. 1. Génesis). Botvinnik desarrolla sus ideas, basadas en la estrategia B de Shannon en diversos trabajos. El primero de ellos en un artículo titulado “Men and machines at the chess board” (Chess in the USSR, 1961, № 3, Moscú) donde sienta las bases de sus ideas de desarrollar un algoritmo que emule el pensamiento de un maestro humano.

Desempeñó un puesto como consultor para el desarrollo de los programas de ajedrez Sovieticos, empezando por el  ITEP (Chess Program at Moscow’s Institute of Theoretical and Experimental Physics) el cual ganó un match al programa americano Kotok-McCarthy en 1967. Más tarde también actuó como consejero para los programadores de  Kaissa al Moscow’s Institute of Control Sciences. (Ver Primer Campeonato del Mundo de programas de ajedrez (II))

Botvinnik estaba convencido que un ordenador puede pensar como un humano

Sin embargo, Botvinnik tenía sus propias ideas sobre el pensamiento de un gran maestro. Después de publicar y discutir sus ideas sobre las “trayectorias mapsand de ataque” al Moscow Central Chess Club en 1966, ante el escepticismo de Georgy Adelson-Velsky (uno de los desarrolladores de ITEP) y otros oyentes, encontró a Vladimir Butenko como seguidor y colaborador. Primeramente Butenko implementó el vector de ataque en un tablero de 15×15 representándolo en la computadora M-20, determinando las trayectorias de las piezas. Después Botvinnik introdujo el concepto de “Zonas” en 1970, pero Butenko rehusó seguir cooperando y empezó a escribir su propio programa.

Pioneer

En los 70s y 80s, liderando un equipo formado por Boris Stilman, Alexander Yudin, Alexander Reznitskiy, Michael Tsfasman y Mikhail Chudakov, Botvinnik trabajó en su propio proyecto Pioneer y más tarde el CC Sapiens.

En 1972 publica “A flow Chart of the algorithm for Playing Chess”. En 1976 estuvo en el  2º Campeonato Mundial de Programas en Toronto, Canada. Tras esta experiencia, bautizó su programa con el nombre de Pioneer y llegaron otros trabajos: “Artificial chess master” (Botvinnik, Stillman, Yudin . Bulletin of the Academy of Sciences of the USSSR, Moscú, 1978, № 4, p.82-91.), “Research-based management model of a chess game” (Stillman . Technical report, VNIIE, Moscú, 1978), “The chess players and computer” (Botvinnik, Stillman, Yudin, Reznitskii, Tsfasman . para el the 2nd International Symposium on Artificial Intelligence, 9 páginas, y reimpreso en Leningrado, URSS, en Octubre 1980).

Botvinnik en la McGill University, 1977

La busqueda y trabajo en Pioneer se llevó a cabo en el State Committee for Science and Technology, el National Research Institute for Electrical Engineering, y el USSR Academy of Sciences, en Moscú. Pronto visitó junto con  Stilman y Yudin en  1978 la University of Mannheim, y la University of Dortmund en Alemania, así como el Control Data Corp., en USA. Basado en esta investigación, Boris Stilman acuño el término Linguistic Geometry , un nuevo tipo de la Teoría de Juegos.

Botvinnik mostró las habilidades de Pioneer con unas posiciones seleccionadas, como en esta publicación de 1979, pero nunca jugó una partida completa en público.

Botvinnik no fue capaz de resolver todos los problemas y su algoritmo nunca llegó a ir más allá de las soluciones teóricas. Además se estaba quedando atrás en la evolución de este campo y respecto otros programas . En 1988 se retiran del proyecto ante la falta de perspectivas (también hay que tener en cuenta la situación política y de  ya creciente desintegración de la Unión Soviética) Vadim Mirniy y Boris Stillman y dos años más tarde también renuncian Alexander Reznitskiy y Mikhail Chudakov. Se dio por finalizado el desarrollo de Pioneer en 1990, un poco antes de la disolución de la URSS.

El fiasco de CC Sapiens

Pero Botvinnik no se rindió. Rebautizó el proyecto como Chess Computer Sapìens ya como ciudadano ruso. Encontró ayuda del matemático Vasily Vladimiros y los economistas Evgeni Dmitievich Cherevik y Vitaly Vygodsky.

Intentó probar a la comunidad científica la validez del programa con el trabajo “Three Positions”, donde hacía que su algoritmo resolviera tres posiciones complejas, pero el experimento no cuajó

La primera de estas tres posiciones y el análisis más criticado es la de la partida Garry Kasparov vs. Zoltán Ribli, (Skelleftea World Cup 1989) tras 26. ¦xb5 ¥xe3:

[Event "Skellefteå World Cup"] [Site "?"] [Date "1989.??.??"] [Round "?"] [White "Kasparov"] [Black "Ribli"] [Result "1/2-1/2"] [SetUp "1"] [FEN "5rk1/5ppp/p1Q1p3/1R6/q7/4b1P1/P2RPP1P/6K1 w - - 0 1"] [PlyCount "10"] [EventDate "1989.??.??"] 1. Rd8 Qxb5 2. Qd6 Bxf2+ 3. Kxf2 Qf5+ $1 (3... Re8 $6 4. Qe7) 4. Kg1 (4. Kg2 Qe4+ $11) 4... Qb1+ 5. Kg2 (5. Kf2 Qf5+) 5... Qe4+ {tablas} 1/2-1/2

CC Sapiens analizó esta posición a 18 nodos de profundidad, y determinó que el blanco ganaba con 27. ¦d8.¦d8 £xb5 28.£d6 ¥xf2+ 29.¢xf2 ¦e8 30.£e7, y lo dio como valido pero “olvidó” considerar otras alternativas para el negro (como 27… ¥xf2!?) y en el crucial tercer movimiento. Escribe Hans Berliner: “Es de suponer que las continuación 29. … £f5+ se desestimó ya que no puede, posiblemente, conducir a una victoria del negro. Botvinnik sabía eso, como yo, ¿pero puede un programa informático resolver esta posición sin buscar más líneas?“. El grueso error 30. £e7?? (es claramente ganador para el negro 30… £b6+ y cae la ¦d8) aparentemente fue descubierto por Botvinnik o su equipo justo antes del momento del cierre de la edición, y que figura en una nota al pie, pero debido a un error de los editores, con tres páginas de separación.

Feng-Hsiung Hsu (más tarde el programador principal de Deep Blue), que también analizó esta posición con Deep Thought y el propio Gary Kasparov en 1990, posteó la línea ganadora: 29. … ¦e8 30.a4 o la más difícil que lleva a tablas 29 … £f5+! 30. ¢g1! en diversos forums como respuesta a otro análisis erróneo del programa B* HiTech del propio Berliner, con la línea 29 … £f5+! 30. ¢g2. Como admitió Berliner en su trabajo Playing Computer Chess in the Human Style, esto le permitió identificar un bug en el algorritmo de busqueda de su B* HiTech dando las gracias a Hsu por su información. 

Todo esto llevó a que Botvinnik fuera duramente criticado por Berliner y su antiguo rival,  David Bronstein y la comunidad no quedó muy convencida.

Todo terminó cuando el 5 de mayo de 1995 Botvinnik falleció. El proyecto fue archivado definitivamente a la espera de que algún día la actual Rusia desclasifique y divulgue estos trabajos. Solo entonces podremos calibrar la real valía del trabajo de toda una vida del patriarca del ajedrez en la URSS.

Don Beal, Ken Thompson, Monty Newborn, y Mikhail Botvinnik, WCCC 1983

Enlaces



Juan Manuel Marches Ríos
Discussion and Feedback Join the public discussion or submit your feedback to the editors


Comentar

Normas sobre los comentarios

 
 

¿Aún no eres usuario? Registro