Sunday, September 20, 2015

Cambio de paradigma


La investigación seria en el ajedrez por computadora habría empezado formalmente con el famoso artículo de Claude Shannon, en 1950, el cual marca las pautas para desarrollar un programa completo que pudiese jugar al ajedrez. Sorprendentemente las ideas de Shannon están vigentes hoy en día, en donde los mejores motores de ajedrez utilizan muchas de las ideas descritas en el mencionado artículo.

Los programas actuales utilizan una función que evalúa cada posición (que es un polinomio lineal) y un algoritmo MiniMax, que permite analizar el árbol de variantes creado y calcular la función en los nodos terminales. Este procedimiento MiniMax tiene una versión más sofisticada, llamada Alfa-Beta, que casualmente, bosqueja Allan Turing en su artículo sobre ajedrez aunque aparentemente no se da cuenta de ello. En la medida que se hace un árbol de variantes (jugadas, respuestas, jugadas, más respuestas), los programas pueden evaluar mejor las posiciones. Por ejemplo, si ejecutamos una jugada que sacrifica la dama comiéndose un peón, podemos pensar que esto da al bando rival una posición ganadora, pero si se acepta el sacrificio y entonces ese bando recibe mate, la jugada de la entrega de la dama exige que se vea más jugadas adelante. He aquí lo que se llama pues, el problema del horizonte o para ponerlo de forma llana: hasta dónde podemos ver.

Hoy en día los programas como Houdini, Komodo y Stockfish dominan el mercado y pueden analizar 10 o más jugadas adelante, en donde cada jugada está hecha por dos movimientos, uno del blanco y otro del negro. A eso se le llaman plies, por lo que un ply es media jugada, el movimiento de un solo bando. Pero aparte de analizar ya con mucha precisión y mejor que los seres humanos, valoran cada posición terminal cada vez de forma más exacta. Los programas líderes del mercado son notables y prácticamente imbatibles por los seres humanos.

Pero aunque este paradigma ha funcionado muy bien, por muchos años, quizás tantos como lleva la investigación de ajedrez, se ha buscado que los programas jueguen como lo hacen los seres humanos. Vamos, que los ajedrecistas de elite no calculan todas las jugadas, sino un subconjunto muy limitado y sin embargo, juegan muy bien. Y éste es el problema no resuelto: ¿Qué hacen los seres humanos para hallar la mejor jugada sin tener que crear un amplio y voluminoso árbol de variantes? Eso parece ser un misterio aún, pero se sigue trabajando en ello.


El cambio de paradigma apenas quizás está comenzando. El año pasado un estudiante puso una red neuronal profunda y la entrenó con 100 millones de jugadas (sacadas del servidor gratuito FICS). El programa entonces, viendo todas esas jugadas aprendió a jugar al ajedrez. No se declararon algoritmos específicamente, sino el algoritmo que usa una rede neuronal para poder extrapolar datos y sacar conclusiones.

Hoy hablan de otro programa, llamado Giraffe, que no analiza muchos plies, sino que entiende los valores posicionales y no requiere de analizar árboles grandes. Juega pues más como los humanos. De nuevo, una red neuronal es la responsable de este trabajo y parece ser que el programa aprendió, así como los niños prodigio como Capablanca, a jugar "sólo viendo" cómo su padre movía las piezas. De acuerdo al último reporte, Giraffe, en 72 horas de entrenamiento, ya logra jugar con la fuerza de un Maestro Internacional. Pero éste es un trabajo no terminado. Vamos a ver si se mantienen las conclusiones y si esto se convierte en una nueva manera de programar motores de ajedrez.

______
(*) Claude Shannon (derecha) le otorga el premio a Feng-Hsiung Hsu por ganar con Deep Thought el Campeonato Mundial de Ajedrez por Computadora, en Edmonton, Alberta, 1989.

No comments: