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.

¿Cuál es la mejor jugada, 1.e4 o 1.d4?

¿1. e4 o 1. d4?

Las dos jugadas más usadas en las partidas de ajedrez son las que se refieren al dominio del centro, a sacar las piezas rápidamente. De todas las jugadas de peones, 1.e4 o 1.d4 son las que más libertades otorgan a las otras piezas y de hecho, son las dos más usadas estadísticamente en la historia del ajedrez. pero... ¿cuál es mejor?

Para dar una posible respuesta -no definitiva- apelaré al artículo de Claude Shannon, el cual entre sus múltiples trabajo, en algún momento decidió incursionar sobre cómo debería programarse una computadora para poder jugar un ajedrez sensato, digamos que pudiese competir con los seres humanos, porque el escribir un programa que juegue simplemente al ajedrez, aunque juegue mal, no tiene ningún chiste.

Shannon escribió un artículo por los años cincuenta del siglo pasado, titulado "Programming a Computer for Playing Chess", en donde analiza a detalle lo que hay que hacer. Cabe decir que Shannon sí entendía bastante de ajedrez y tenía claras las ideas que quería plasmar en su eventual programa. Es importante decir que en ese entonces no se tenía acceso fácilmente a una computadora y además, ni siquiera existía el tema de la computadora personal. Pero debe quedar sin embargo algo claro: el artículo de Shannon es tan importante que prácticamente todos los programas actuales tienen muchas de las ideas que planteó el científico en su momento.

Sin ir a detalle sobre la idea de Shannon, propone éste una estrategia que le llamó tipo A, en donde a partir de una posición dada, se exploran todas las líneas de juego hasta una profundidad fija y se les asigna una puntuación al final de cada continuación. La puntuación  asignada a la posición se denomina hoy en día "función de evaluación" y es una medida de qué tan buena es una posición para el lado de quien le toca jugar. Para decidir esa puntuación, Shannon sugirió un número de factores que deben tomarse en cuenta:

1.  Material: asignando a las piezas los valores tradicionales, Dama (D)=9, Torre (T)=5, Alfil (A)=3.5, Caballo (C)=3, Peón (P)=1 y Rey (R)=200 (no importa el valor del rey, porque si éste es eliminado se acabó la partida, lo que importa es que sea un valor mucho más grande que el de las demás piezas).
2.  Formación de peones: castigo de 0.5 puntos por cada peón doblado (PD), aislado (PI) o atrasado (PB).
3.  Movilidad: es deseable tener muchas jugadas disponibles para el jugador que le toca mover y pocas para el oponente. Shannon sugiere 0.1 puntos por cada jugada disponible (JD).

Basado en esto, la función de evaluación bien puede escribirse como:

f(posición) = 200 (R-R') + 9(D-D') + 5(T-T') + 3.5(A-A') + 3(C-C') + (P-P') - 0.5(PD-PD'+PI-PI'+PB-PB') + 0.1(JD-JD')

donde las piezas primales son las del enemigo. Así, un valor positivo significa que las blancas tienen ventaja, una valoración negativa implica que el negro tiene mejor posición.

Cabe decir que esta función elemental es bastante acertada en la mayoría de las posiciones que se dan en ajedrez, pero desde luego, hay tantas excepciones que hay que refinar mucho más dicha función. De hecho, esto es el secreto de los programas más fuertes y no se conoce en la mayoría de los programas comerciales.

Pero si tomamos el criterio establecido por Shannon, podemos decidir si 1.e4 es mejor que 1.d4. Después de 1.e4, las blancas tienen 30 movimientos posibles (contando incluso los del rey). Después de 1.d4 las blancas tienen una valoraciín menor en la función descrita por Shannon.