Como funcionan los programas de ajedrez

Nota: Antonio Dieguez zodiamoon@yahoo.com

Si quieres programar un juego de ajedrez, o si quieres desempeñarte mejor cuando juegas contra uno o si tienes curiosidad te sería interesante conocer cómo le hace más o menos aquel programita que bajaste o compraste el otro día para hacer como que sabe jugar ajedrez (!?)

Primero que nada quiero decir que esto es sólo para introducir a personas interesadas en este tema, cualquiera que ya haya hecho un juego de ajedrez o ya sepa de esto sabrá como se implementarán este tipo de juegos, pero este documento de todas fomas tiene valor de tipo curiosístico, sobre todo si te gusta el ajedrez y como que te llama mucho la atención esto del ajedrez jugado por computadoras, o si estás cansado de tanto inglés de otras páginas. Ahora bien, si no sabes programar, te cuento que es un proceso en el que se "le instruye" al compu qué hacer, de una manera muy objetiva y clara, ya sea usando c, c++, java o cualquier otra especie...

Okey empecemos, pero me gustaría que sea participativo

pregunta: Un programa de ajedrez calcula l as variantes?

respuesta: Sí, un programa de ajedrez claro que calcula variantes...

pregunta: Pero no son demasiadas variantes? por ejemplo al comienzo de la partida son 20 las jugadas posibles y en el medio juego son aún más, y por ejemplo calcular seis movimientos en el medio juego asumiendo 35 movimientos posibles cada vez serían 35x35x35x35x35x35 = 1.838.265.625 !!, o sea más de mil millones de combinaciones para sólo inspeccionar 3 jugadas !!!

respuesta: sencillamente así como tú no tienes necesidad de calcular tantas millones de jugadas, el programa tampoco...

pregunta: claro eso pensé pero y como le hace para ver algunas y otras no? y como le hace por ejemplo si todas sus jugadas no ganan material ni hacen mate, como elige "su mejor" jugada?

respuesta: sencillamente asi como al ver una posición en tu mentecilla, ella te parece linda o fea, que tan linda o que tan fea (si es que te decides), un programa de ajedrez tambien debe juzgar posiciones, y descartar muchas también.

pregunta: guau! pero i gual todo esto esta como en el aire, como puede ser eso posible?

respuesta: Mira te lo voy a explicar en más detalle...

Un programa de ajedrez suele tener dos partes importantísimas, su algoritmo de búsqueda y su algoritmo de evaluación de posiciones.

En la evaluación, se determinan la presencia o ausencia de determinados factores y en qué grado (je creo que esa frase la leí en algun lado). Naturalmente el material ocupa un papel importante, y entre otros factores se encuentran la seguridad de los reyes, estructura de peones y movilidad. Se que todavía esto está como en el aire, pero no tiene nada de mágico!, a decir verdad tiene mucho de brutágico, ya que aquí se le asigna un puntaje a cada cosa, a veces de la manera más espeluznante...

Te doy un ejemplo, una evaluación muy sencilla sería:

100 por cada peon,

315 por cada caballo,

330 por cada alfil,

500 por cada torre,

940 por cada dama,

1 punto por cada casilla a la que se puedan mover los alfiles,

1 punto por cada casilla a la que se puedan mover las torres,

12 puntos por tener un peón en el centro,

De -20 hasta 15 gradualmente por la posicion de cada caballo (desde un rincon del tablero hasta el centro),

De -4 a 4 gradualmente por la posicion de la dama (desde un rincon hasta el centro),

-10 por peon doblado,

-15 por peon aislado,

bonus gradual para la posicion del rey, en la apertura mientras más cerca del centro es más malo y en los finales de partida (poco material) al revés.

Una evaluacion seria los puntajes de un bando menos los del otro. Desde el punto de vista del compu, sería bonuses de sus piezas menos bonuses de las piezas del contrincante, + algún otro factor que no se pueda evaluar por separado. Cosa que mientras más positivo el resultado la posicion es supuestamente mejor para él, y asignando el cero a una posición supuestamente igualada.

Te fijas? naturalmente es una evaluación muy mala y ningún programa de ajedrez decente tiene una tan sencilla pero te impresionaría notar que sólo con eso y un buen algoritmo de búsqueda ya un juego de ajedrez te impresionaría porque pareciera que estuviera vivo...

Considerar de una manera aceptable cualquier cosa en la evaluación naturalmente requiere más tiempo de cómputo, y no necesariamente haciendo un programa más "inteligente" de esta manera se hace más fuerte por esta razón (el programa más rápido alcanzaría a ver antes ciertas tácticas, o cambios súbitos en la evaluación que no haya previsto el más lento, etc.)

Respecto a esto hay programadores que prefieren hacer sus programas más inteligentes que rápidos, otros al revés y la mayoría ni lo uno ni lo otro... Por supuesto que no necesariamente un programa más lento que otro tiene una evaluación más "compleja" ya que el código puede no estar muy bien optimizado para la velocidad que digamos.

Por supuesto que una evaluación programada con reglas de este estilo, aunque sean muchas, y relativamente bien hechas, difícilmente igualará el criterio de un jugador no necesariamente muy bueno. Incluso suele pasar que en este sentido el programa sea menos capaz que su autor, así que qué se puede esperar de esto?, bueno una cosa rescatable es la fiabilidad, o sea que el programa es muy confiable y nunca se equivocará en evaluar exactamente cómo le dicen que lo haga, y en todo caso esta es una parte que se supone que con el tiempo se va mejorando o al menos disminuyendo en inexactitudes. De todas formas, es muy interesante y le da el estilo de juego al programa.

Para que el valorar una posición tenga alguna utilidad, viene el otro gran aspecto, que es el poder de cálculo, que depende del algoritmo de búsqueda y el hardware sobre el cual está corriendo el programa... Para que tengas una referencia respecto de esto, mi juego, en mi compu, que es todavía un AMD K6 a 233 Mhz, alcanza mínimo 18.000 posiciones visitadas por segundo, y aún así se me hace poco. Muchísimos softwares de ajedrez, ya sean comerciales o amateurs, sobrepasan las 50.000 posiciones visitadas por segundo en un PC como el mio. Deep Blue en su segundo match ante Kasparov, evaluaba alrededor de 200.000.000 de posiciones por segundo (!), no sé si Kasparov pase más allá de las 5 así que ahí notamos por donde va la fuerza del ser humano y por donde va la fuerza de las máquinas en este aspecto, no es que haya demasiada inteligencia artificial o algo así, simplemente prima la rapidez de la máquina, que no hace más que eso y no sabe ni amarrarse los cordones(de tener :) )

Pero y cómo funciona la búsqueda? bueno debemos usar nuestra función de evaluación de alguna forma... el ejemplo más trivial es, que a partir de la posición actual en el tablero, siendo el turno del compu, éste calcule todos sus movimientos que puede efectuar y los "pruebe" él solito y evalue cada una de las posiciones resultantes con su función de evaluación, y naturalmente la mejor jugada sería la que le dio una mejor valoración resultante.

Ahora bien... eso es sólo para 1 media jugada de profundidad de cálculo, como te podrás dar cuenta, pero agregar más medias jugadas no es muy difícil... lo que se forma es un lindo arbolito. Si ya has programado recursiones te sería muy fácil porque esta es una muy simple, maximizar, minimizar, maximizar, minimizar,...

En el árbol de variantes, el programa va cogiendo, en el caso de la más pura fuerza bruta, las mejores jugadas para cada bando en cada nodo del arbolito, según evaluaciones efectuadas en las posiciones "de más al fondo". Al cambiar de nodo en nodo (nodo=cada posicion dentro del arbolito), la posición en la memoria la vas cambiando (haciendo cada movida, y deshaciéndola luego de analizar la variante).

Naturalmente para implementar esto hay que darse el trabajo de tener una estructura para la posicion con los datos sobre como esta el tablero y las piezas y tener una funcion por ejemplo a la que le pases la posicion y te calcule las posibles movimientos legales, entre otras trivialidades.

En los nodos de más al fondo (las posiciones más profundas), la posición es evaluada, obteniendo así un puntaje en aquellos nodos, que luego implicarán un puntaje en el nodo padre luego de tener un puntaje todos los nodos hijos. Dependiendo del turno en cada nodo padre se elige el máximo de los puntajes de los hijos para él (si le toca al bando del computador) o el mínimo (si le toca al bando del contrario), habiendo definido nuestra evaluación siempre como bonuses del bando del computador-bonuses del bando contrario. Si lo piensas bien, esto funciona, y el nodo raiz, al final queda con un puntaje estimativo de la posicion inicial..., y la jugada a jugar por el compu será el movimiento que llevó a ese puntaje...

Okey ahora mi buen observador, seguramente ya te preguntaste qué pasa si en la ultima jugada calculada un bando come un caballo con su alfil o algo así, en caso que el caballo haya estado defendido posiblemente será recapturado y ya pero estaría mas allá del calculo del programa, asi que la evaluación, que vería un caballo menos para un bando sería completamente errónea...

Bueno lo que se hace siempre, teniendo en cuenta esto, es a partir de una cierta profundidad, no terminar inmediatamente retornando la evaluación, sino achicar el espectro... lo más común y simple es analizar sólo las capturas, que son las jugadas que pueden cambiar radicalmente una posición, no es así? ahora bien, supongamos que estamos en un nodo de esos en que veremos sólo las capturas como posibles jugadas, que pasa si todas son horrendas? o si no hay? bueno en este caso lo prudente es... devolver la evaluación de la posición en que estamos como es normal, lo que más le convenga al nodo en que se está (recuerda que este necesita ya sea el mínimo o el máximo dependiendo del turno.)

Además de capturas se pueden ver otro tipo de jugadas en esta parte final o Quiescence Search como le dicen en inglés... ya sea jugadas que hacen jaque al enemigo o pudieren cambiar mucho la valoración de la posición, o si nos están amenazando por ejemplo una torre con un caballín salir de la qsearch por un momento y probar todas las jugadas normalmente a ver si se pierde pieza. Naturalmente, no siempre ver mucho aquí vale la pena y hay que ver qué funciona mejor en la práctica...

Una pregunta me hacen aquí de que si se escoge una profundidad definida entonces si el programa esta jugando con tiempo entonces como responde cuando debe? elegimos la profundidad que parezca adecuada de antemano? bueno la verdad es que no hay para qué, lo común es hacer una búsqueda de profundidad igual a 1, luego a 2, luego a 3 etc. (no se cuenta la qsearch aquí) Puedes imaginar que como cada búsqueda de éstas (o iteración) no demora tanto en relación a la siguiente, a fin de cuentas la mayor parte del tiempo se tomará en la última iteración asi que no sería mucha pérdida, además que así en todo momento se sabe cual es la mejor jugada no? y además, por lo que veremos luego, una iteración x ayuda a que la iteración x+1 sea más eficiente.

Bueno espero que haya quedado todo claro hasta ahora, pero todavía no se ve nada de descarte de jugadas posibles cierto? empecemos... Primero que nada, hay algo muy obvio que nos ayuda muchísimo en este aspecto y es que cada quien juega lo mejor posible. Ahora bien, por lo menos yo a veces cuando juego con un rival débil (más débil que yo incluso asi que imagínate) me puedo pasar rollos con que se le va a ir algo y me arriesgo y no juego la que creo es mi jugada más correcta, pero esto no lo consideraremos ok? olvidemos también a Lasker por un momento en este tema.

Qué implica eso? bueno, si sabes jugar ajedrez ya lo sabes, móntate en un nodo en el cual le toque al compu jugar y supón que ya le viste que su primera jugada que le pruebas (cualquiera sirve en realidad) le da finalmente 46 puntos, bastante bien para nuestro programita, y ahora sigues analizando su segunda opción(jugada) y en aquel nodo hijo, en el cual juega el bando contrario, la primera jugada de este sujeto arroja un puntaje 23 como resultado. A ver qué cosa útil me puedes deducir con eso...?

Seguramente sabes a que me refiero, no? eso espero... lo que pasa es que en ese caso no necesitamos analizar ahora la segunda jugada del sujeto (del contrario) puesto que concluimos que este nodo hijo tiene un valor 23 o menos (recuerda, este hijo va a querer el mínimo...) y su nodo padre jamás lo elegirá puesto que el compu ya tiene una mejor alternativa con 46 puntos (recuerda, este va a querer el máximo...). En este caso, estos 46 puntos pasaron a ser un limite inferior para el puntaje del nodo, y en cuanto se vea que en alguna rama inferior que nazca de una jugada paralela arrojará 46 o menos, esa rama se termina porque no tendrá incidencia.

Si lo piensas bien, esta observación vale para cualquier punto del árbol y ya sea el turno del compu o no, sólo que como que se revierten algunas cosas. Bueno, un poquito de terminología: cuando se implementa esta cosa en un lenguaje de programación le llaman "alpha-beta", vale para ajedrez, damas y juegos por el estilo, el alpha es el límite inferior y el beta es el superior, y son parámetros cambiantes de la función recursiva de la búsqueda. Especifícamente cuando pasa eso de que no hace falta seguir viendo las alternativas de un bando le llaman "cut-off", okey mucho inglés asi que sigamos.

Okey cual es la ganancia con la idea anterior? bueno, depende. Se puede optimizar tratando de calcular primero las mejores jugadas en cada nodo para ver si ocurre uno de estos cut-offs luego. Una buena idea es guardar en memoria jugadas que han logrado estos cut-off en algún nodo y probarlas primero en otros nodos, especialmente de la misma profundidad, aunque tambien se comete la bruteza de guardar en memoria las jugadas que mejor han servido para cada posicion vista, y a eso viene el uso de una tabla de hashing, a menudo denominada tabla de transposicion, donde se guardan la id de la posición(fácil de calcular, difícil de repetirse pero no necesariamente única, para ahorrar memoria y tiempo) y la jugada recomendada y otras cosas. Otra pequeña idea por ejemplo es cuando se revisen las jugadas de caballo que se vean primero las que mueven hacia el centro ya que un movimiento a un rincón de un caballo no es precisamente un buen candidato, y ver jugadas de piezas que avancen antes de las que retroceden y cosas como esas. Qué opinas?

Me preguntan de nuevo, cuánta es la ganancia? y yo respondo, muchísima. Hay que tener en cuenta que la tabla de hashing también sirve para disminuir el doble trabajo cuando ocurren transposiciones ( por algo el nombre :) ). La cantidad de posiciones que se deben ver, por ejemplo, pueden pasar de un factor 35 a un factor 6 o algo así. Y menos mal que se puede descartar tanto matemáticamente porque descartar de otra forma es un lío, te imaginas? Este es un punto de constante mejora en cada programa, y lo que hace más diferencia entre un fuerte programa comercial como el Fritz, Junior, Chess Tiger, etc. y un programita mediocre de ajedrez como amyan, más incluso que la función de evaluación al parecer.

El chiste está en que no necesariamente se debe de constatar que, en el ejemplo dado anteriormente, una rama paralela arrojará 46 o menos, sino que, sin necesariamente probarlo, se estime o anticipe eso en cierto punto.

Por dar un ejemplito, bien profundo en la búsqueda podrían no verse jugadas de piezas a lugares atacados por peones. También bastante profundo en la búsqueda, unas pocas medias jugadas antes de terminar, si la situación en el tablero se ha alejado bastante del "path" (un ejemplo: turno es del compu, evaluacion>=beta+harto y enemigo no tiene buenas capturas o clavadas o peones pasados o queseyo), cortar ahí(retornar beta). También un descarte muy conocido y muy usado con leves diferencias es la jugada nula ("null-move" en inglés), y te la explico: en los nodos en los que la desees hacer, antes de calcular los posibles movimientos y todo lo demas primero haces una null-move o sea, no mueves y pasas altiro al nodo hijo, el valor que le dé el nodo hijo al padre es usado como un límite para el futuro valor del padre y si tienes suerte, este valor es lo suficientemente grande (en el caso de turno del compu) o lo suficientemente pequeño (en el caso de turno del otro) como para no analizar ninguna alternativa en absoluto debido a un cut-off, y más encima cuando se usa null-move se suele achicar + la profundidad cuando le pasas el trabajo al nodo hijo (es decir no sólo un movimiento menos, tres funciona bien por ej.), teniendo muchísima confianza en el principio "alguna jugada debe de haber que sea preferible a pasarle el turno al contrario", qué opinas? Por supuesto que el principio es muuuuy muy cierto excepto en posiciones de zugzwang(que felizmente casi siempre son en posiciones con poquitas piezas), pero que se le achique la profundidad provoca en general varios pequeños errores diseminados en el arbolito por aquí y por allá, y verdaderas malas pasadas de vez en vez, aunque sin duda conviene usarla. Finalmente es usual rebajar el factor a 3 o algo así.

Todo el descarte que un programa pueda hacer de todas formas es mínimo, porque es muy difícil y muy errorístico decirle por ejemplo "en este tipo de posiciones no calcules la línea que sigue con Ca6 o cosas así porque demás que no se saca nada". Y tampoco es fácil por ejemplo usar resultados de iteraciones anteriores para descartar de alguna forma ya que la misma "ventana alpha-beta", que te permite necesitar menos nodos, funciona no retornando muchos valores reales, sólo límites(y usualmente poco útiles.)

Naturalmente, el grado de profundidad no es necesariamente fijo en todas las variantes, en continuaciones que parecen forzadas, como recapturas, o al escapar de un jaque, y una que otras pocas situaciones conviene extender la búsqueda un poquito, aunque es el humano quien sí sabe extender en muuuchas situaciones cuando huele algo, y sí lo hace bien... pero suele pasar que el arbol de combinaciones explote demasiado en tamaño si se extienden algunas cosas sin extremo cuidado asi que tampoco es cosa de que se te ocurra algo para extender y ya, porque si "no había nada allí" el extender habrá sido casi sólo una pérdida desagradable de tiempo.

Eso es todo aqui, si sabes programar, te atrae el tema, y tienes tiempo y AUN NO has hecho un juego de ajedrez, no te entiendo. En la página de links hay unas direcciones que puedes revisar, varias de las cuales muestran limpios pedazos de código, información acerca de cómo se implementan las tablas de hashing para un programa de ajedrez, etc.

Buena suerte...