Re: RUBIK Infinito

Posted by RUBIK Transfinito on Dic 31, 2012; 1:54pm
URL: http://foro-crashoil.109.s1.nabble.com/RUBIK-Infinito-tp14p79.html

@ KUZNACTI


El pionero de las hash tables de finales de ajedrez para ordenadores fue KEN THOMPSON, conocido también por ser el diseñador principal del sistema UNIX.

Puedes encontrar info sobre él y el tema en el artículo de Wikipedia sobre ajedrez computerizado:



COMPUTER CHESS
http://en.wikipedia.org/wiki/Computer_chess#Using_endgame_databases


(...) Endgame play had long been one of the great weaknesses of chess programs, because of the depth of search needed. Some otherwise master-level programs were unable to win in positions where even intermediate human players can force a win.

El juego de finales de partida había sido durante largo tiempo una de las mayores debilidades de los programas de ajedrez, debido a la profundidad de búsqueda requerida. Algunos programas que en todos los demás aspectos eran de nivel Maestro, eran incapaces de ganar en posiciones en las que incluso jugadores humanos de nivel intermedio pueden forzar una victoria.


To solve this problem, computers have been used to analyze some chess endgame positions completely, starting with king and pawn against king. Such endgame databases are generated in advance using a form of retrograde analysis, starting with positions where the final result is known (e.g., where one side has been mated) and seeing which other positions are one move away from them, then which are one move from those, etc. Ken Thompson, perhaps better known as the key designer of the UNIX operating system, was a pioneer in this area.

Para resolver este problema, se han usado computadores para analizar algunas posiciones de final de partida de manera exhaustiva, empezando con rey y peón contra rey. Esas bases de datos de finales de partida se generan por adelantado utilizando una forma de análisis retrógrado, empezando con posiciones para las que el resultado final es conocido (es decir, en las que un lado ha sufrido el jaque mate) y viendo qué otras posiciones están a un movimiento de distancia de ellas; a continuación, cuáles están a un movimiento de esas a su vez, etc. Ken Thompson, quizá más conocido por ser el diseñador clave del sistema operativo UNIX, fue pionero en este área.


The results of the computer analysis sometimes surprised people. In 1977 Thompson's Belle chess machine used the endgame tablebase for a king and rook against king and queen and was able to draw that theoretically lost ending against several masters (see Philidor position#Queen versus rook). This was despite not following the usual strategy to delay defeat by keeping the defending king and rook close together for as long as possible. Asked to explain the reasons behind some of the program's moves, Thompson was unable to do so beyond saying the program's database simply returned the best moves (...)

Los resultados del análisis por computador sorprendieron a la gente a veces. En 1977 la máquina de ajedrez Belle, perteneciente a Thompson, uso las bases de datos de finales de partida para Rey+Torre contra Rey+Dama y fue capaz de empatar ese final de partida, que se consideraba *teóricamente perdido*, contra varios maestros (ver la "Posición de Philidor#Dama contra Torre"). Esto fue incluso a pesar de no seguir la estrategia usual, consistente en demorar la derrota mediante el procedimiento de mantener rey y torre juntos durante tanto tiempo como sea posible. Al preguntársele las razones detrás de algunos de los movimientos del programa, Thompson fue incapaz de explicarlas más allá de decir que la base de datos del programa simplemente suministraba las mejores jugadas (...) [NOTA DE RUBIK: Halladas por fuerza bruta, claro -> la máquina calcula el juego óptimo, pero eso no permite que un humano comprenda QUÉ está sucediendo o que pueda ver una "pauta" que le sirva para diseñar estrategias]



Hace muchos años (mediados de los '90, estimo) salió en Investigación y Ciencia (Scientific American, versión en castellano) un artículo que comentaba el descubrimiento de K. Thompson con sus bases de datos para el final R+T+A vs. R+C+C, y comentaba que había probado que ese final que había siedo considerado siempre como "Tablas Teóricas" en la teoría del ajedrez, en realidad podía ser ganado siempre por el primer bando ... Eso sí, empleando típicamente 220 movimientos o más. Y repito que NO APARECE NINGUNA PAUTA que un humano pudiera usar como metodología. Tengo el artículo fotocopiado aparte por ahí. Cuando lo localice, lo escanearé y subiré a la red.

Creo que en un libro de Nigel Short (Finales de Piezas Menores) también se comenta este caso, y se especula sobre como el Caos invade también ciertas facetas del ajedrez. A fin de cuentas, hay métodos mecánicos para R+P vs. R, R+T vs. R y docenas de otros finales. Para otros muchos hay "reglas de la vieja" que suelen dar buenos resultados (pero no "determinísticamente"). Y luego está lo comentado, que parece ser intratable de otra forma que no sea fuerza bruta a nivel de un superordenador CRAY de los '90.


Todavía abundando sobre este tema, un tal Jonathan Schaeffer escribió un libro completo sobre cómo consiguió en su momento escribir el mejor programa de DAMAS del mundo. De hecho, creo que fue el que desbancó al campeón humano. De joven, él hizo su doctorado en programas de ajedrez, y notó ese efecto de que los mejores resultados los obtenían sobre todo los que disponían de ordenadores más rápidos, no los que creaban software más sutil.




El libro de Schaeffer es:


ONE JUMP AHEAD: COMPUTER PERFECTION AT CHECKERS

http://www.amazon.com/One-Jump-Ahead-Computer-Perfection/dp/0387765751/ref=sr_1_2?s=books&ie=UTF8&qid=1356961437&sr=1-2&keywords=one+jump+ahead


Es decir, "Un salto adelante: perfección de computador en las damas".

Hace años que quiero comprarlo y leerlo.


Por cierto que en 2009 Schaeffer concluyó un Cálculo de 20 años de duración en el que empleó docenas de ordenadores muy rápidos a la vez ... PARA EXPLORAR EXHAUSTIVAMENTE el grafo del juego de Damas. No miró todos los nodos uno por uno, sino que la búsqueda concluía cada vez que alcanzaba una posición de final conocido, a fin de eliminar así grandes sectores del árbol de variantes.

Su conclusión fue que LAS DAMAS SON TABLAS.

De todas formas, lo turbio del procedimiento hace dudar de que no se le colaran errores: el cálculo duró 20 años, y fue sustituyendo los creo que setenta-y-pico ordenadores iniciales por otros más rápidos a medida que progresaba la tecnología. De hecho, acabó con menos máquinas que al principio. Dudo que no se le pasara algo por alto o que no cometiera errores. Aun así, seguramente la conclusión es correcta y las damas son tablas.


En Investigación y Ciencia leí en mi época de estudiante de secundaria un artículo en el que supe de Schaeffer por primera vez, y se planteaba a los lectores el desafío de explorar las Damas en un Tablero de 6x6 para ver si eran Tablas. El artículo decía que eso estaba prácticamente en el límite de lo que sería capaz de hacer un supercomputador de la época (finales de los '80).



También en aquella época estaba en la revista (Investigacíon y Ciencia) la deliciosa sección de Temas Metamágicos, que llevaba el genial matemático recreativo Martin Gardner. En una serie que dedicó a la comparación entre algoritmos digitales y analógicos y a sus eficiencias relativas, comentó el problema (hablo de memoria) de hallar el camino *más largo* en un grafo. Parece que digitalmente era un problema duro, cuya función de trabajo crecía rapidísimo con el número de nodos. Sin embargo, alguien de los Países Bajos (¡creo que Dijkstra!) le envió una SOLUCIÓN ANALÓGICA que resolvía el problema para cualquier grafo en sólo dos pasos:

Tienes que tener el grafo "materializado", por ejemplo como nodos cogidos con hilos de lana. La idea es que coges un nodo cualquiera, y dejas pender el resto del grafo de ese nodo. Entonces coges el nodo que cuelgue más bajo de todos y repites la operación. Vuelves a coger el nodo más bajo de todos. ÉSTE y el anterior son los dos más alejados entre sí [esto es lo que recuerdo, quizá no sea preciso].