IMPORTANTE: este escrito considerará sólo el escribir un programa de ajedrez del modo más tradicional, sin redes neuronales. Y no es muy profundo pero incluso si ya sabes del tema varias veces es un agrado volver a leer de algo que te gusta de todas formas así que espero no aburrirte. Ahora bien, si no sabes programar, te cuento que es un proceso en el que se "le instruye" al compu qué hacer, y se suele hacer de una manera muy objetiva y clara, a menos que se utilicen esas técnicas de IA que están en boga que tienen resultados aún más difíciles de preveer.


Okey empecemos, pero me gustaría que sea participativo, alguien?

pregunta: Un programa de ajedrez calcula las 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, qué tan linda o qué tan fea (si es que te decides), un programa de ajedrez tambien debe juzgar posiciones, y así descartar muchas continuaciones sin sentido también.


pregunta: guau! pero igual 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. A esta evaluación se le suele llamar estática, pues lo usual es que por sí sola nunca vea variantes, y sólo usándola dentro de una búsqueda es posible obtener una evaluación dinámica.

En la evaluación de una posición, se determinan la presencia o ausencia de determinados factores y en qué grado (je esa frase la leí en otro lado). Naturalmente el material ocupa un papel importante, y entre otros factores se encuentran la seguridad de los reyes, estructura de peones y movilidad. Sé 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, y 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 y 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,
* De 20 a 80 por peón pasado, dependiendo de cuán cerca esté de la casilla de coronación,
* 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.
Definamos la evaluación 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... y de hecho como actualmente los programas ven continuaciones bien largas pues al final terminan jugando extremadamente bien!
Considerar de una manera aceptable cualquier cosa en la evaluación naturalmente requiere más tiempo de cómputo, provocando que el programa se pasee por menos posiciones por segundo(siendo "más lento"), así que no necesariamente más "inteligente" por cuanto a evaluación significa automáticamente más fuerte.
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 significa que tiene una evaluación más "inteligente", ya que pueden ser de distinta calidad y también en una buena búsqueda hay inteligencia y puede consumir un tiempo apreciable. Además por lo menos respecto a los programas amateurs, un programa puede ser mucho más lento que otro simplemente porque el autor ha sido menos capaz o no se ha preocupado de optimizar el código.

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 buen jugador. De partida la evaluación la escribe el programador así que qué se puede esperar de esto? bueno la verdad algunos en esta parte han experimentado con técnicas de machine learning aunque no tanto para escoger los parámetros que considerar sino para escoger los valores de puntaje a utilizar dentro de una estructura ya definida por el programador (y ha servidor pero no tanto). Bueno, una cosa muy rescatable de la evaluación es la "confiabilidad" en que el programa al menos 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 sus inexactitudes, mientras el humano puede tener muchas dudas, ser inconsecuente, etc).
De todas formas, es lo que le da el estilo de juego al programa y lo que lo mueve.

Para que el valorar una posición tenga alguna utilidad, viene el otro gran aspecto, que es la búsqueda, cuya efectividad depende de los detalles del algoritmo en sí y el hardware sobre el cual está corriendo el programa... Para que tengas una referencia respecto de esto, mi juego, en mi excompu, un AMD K6 a 233 Mhz, alcanza mínimo 18.000 posiciones visitadas por segundo, y aún así se me hacía poco, y en mi actual compu, un CELERON a 1.3 Ghz, es más de 6 veces más, pero igual... Muchísimos softwares de ajedrez, ya sean comerciales o amateurs, son dos veces más "rápidos" que amyan o aún más, en cuanto a pos/sec. 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 si es que se puede decir de esa manera, 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 evalúe 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).
Nota : yo digo árbol pero no implica que haya que implementar la estructura de datos llamada árbol ok?
Naturalmente para implementar la búsqueda antes que nada hay que darse el trabajo de tener representada ya la posición con los datos sobre cómo está el tablero y las piezas y tener una función por ejemplo a la que le pases la posicion y te calcule las posibles movimientos legales, entre otras trivialidades. Trivialidades no porque sea implementable en un rato sino porque hay más brillo en la búsqueda y la evaluación claro está.
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 el último movimiento calculado en la variante X un bando juega alfil por caballo, o algo así, en caso que el caballo haya estado defendido posiblemente el alfil también se muere y ya, pero eso estaría mas allá del cálculo del programa, así 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 además permitir ver jugadas pero achicando el espectro... lo más común y simple es probar sólo las capturas, que son las jugadas que pueden cambiar radicalmente una posición, no es así? de esta manera se retorna lo que más le convenga al bando que tenga el turno(el puntaje de evaluar o el de efectuar alguna captura), recuerda que este necesita ya sea el mínimo o el máximo dependiendo si es el bando del compu o no...
Además de capturas se pueden ver otro tipo de jugadas en esta parte final o Quiescence Search como le dicen en inglés... ("búsqueda de quietud") ya sea jugadas que hacen jaque al enemigo o atacan una pieza, o bien si nos están amenazando por ejemplo una torre con un caballín procurar verificar si se pierde la pieza.

Una pregunta me hacen aquí de que si se escoge una profundidad definida entonces si el programa está 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 malas 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 que puede. 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 provoca más diferencia de fuerza entre los programas de ajedrez, bastante más incluso que la función de evaluación.
El chiste generalmente 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. La verdad esto suena a veces tan técnico pero es lo mismo que haces al jugar ajedrez.

Bueno los descartes se dividen en dos tipos:

1.- futiles (creemos que el nodo será <=alpha), o
2.- auspiciosos (creemos que el nodo será >=beta).

1.- Por dar un ejemplo, bien profundo en la búsqueda(cerca de los nodos terminales), si la evaluación es menor que alpha(menos un margen) podrían no verse todas las jugadas, sino sólo las capturas, las que atacan otra pieza, avanzan un peón pasado, etc. y en el caso que el nodo no sea de tan al fondo, lo que se hace es una reducción para la mayoría de las jugadas (por ejemplo, todo lo que no sea una captura o una killer(jugada que ha sido buena anteriormente) o una amenaza, se ve con 1, 2 o más movimientos menos, ahora bien si su puntaje resulta mayor que alpha hay que volver a calcular con la profundidad pendiente original.
2.- Aquí es parecido pero respecto a beta. Ahora bien... 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 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 corte auspicioso, y más encima cuando se usa null-move se suele achicar + la profundidad pendiente 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 hartos errores diseminados en el arbolito por aquí y por allá.

No hay casi ningún descarte perfecto, normalmente se acepta nomás que hayan errores en el árbol de búsqueda, pero la mayoría son errores entre comillas, pues en el fondo son como ir a la qsearch más luego, o sea no es lo mismo que un error de evaluación. Hay que ver lo que funciona mejor en la práctica.

El factor exponencial de la cantidad total de nodos gastados cumplida cada iteración, puede quedar en un poquito más de 2.

Además de la irregularidad del árbol producto del descarte, que implica reducir la profundidad en aquellas líneas, por lo menos 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 árbol 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.

Te recomiendo hacer una full evaluación en todos o casi todos los nodos, es la info más útil que hay. Bueno al menos ese es mi estilo tú hace lo que quieras :P

int Minimax (posicion p, int turno, int profundidad)
{
     int mejor, mejorjugada, puntaje;

     if (profundidad <= 0)   { return MinimaxQ (p, turno, profundidad); }

     if (turno==turnoDelPrograma) { mejor=-INFINITO; }
     else                         { mejor=+INFINITO; }

     int cuantos=generarMovimientos (p, turno);

     for (int i = 1; i <= cuantos; ++i)
     {
          p.efectuarMovimientoIésimo(...);
          puntaje=Minimax (p, 1-turno, profundidad-1);
          p.deshacerMovimientoIésimo(...);

          if (turno==turnoDelPrograma && puntaje > mejor)
          {
               mejor=puntaje;  mejorjugada=i;
          }
          else if (turno!=turnoDelPrograma && puntaje < mejor)
          {
               mejor=puntaje;  mejorjugada=i;
          }
     }

     return mejor;
}

int Alphabeta (posicion p, int turno, int profundidad, int alpha, int beta)
{
     int mejor, mejorjugada, puntaje;

     if (profundidad <= 0)   { return AlphabetaQ (p, turno, profundidad, alpha, beta); }

     if (turno==turnoDelPrograma) { mejor=alpha; }
     else                         { mejor=beta; }

     int cuantos=generarMovimientos(p,turno);

     for (int i = 1; i <= cuantos; ++i)
     {
          p.efectuarMovimientoIésimo(...);
          puntaje=Alphabeta(p, 1-turno, profundidad-1, alpha, beta);
          p.deshacerMovimientoIésimo(...);

          if (turno==turnoDelPrograma && puntaje > alpha)   // (alpha es = a mejor)
          {
               if (puntaje >= beta) { return beta; }        // corte inmediato!

               alpha = puntaje;                             // achica ventana por lo menos

               mejor = puntaje;   mejorjugada = i;
          }
          else if (turno!=turnoDelPrograma && puntaje < beta) // (beta es = a mejor)
          {
               if (puntaje <= alpha) { return alpha; }        // corte inmediato!

               beta = puntaje;                                // achica ventana por lo menos

               mejor = puntaje;   mejorjugada = i;
          }
     }

     return mejor;
}

int Alphabeta (posicion p, int turno, int profundidad, int alpha, int beta)
{
     int mejor,mejorjugada,puntaje;

     if (profundidad <= 0)   { return AlphabetaQ (p, turno, profundidad, alpha, beta); }

     mejor=alpha;   // !!

     int cuantos=generarMovimientos(p,turno);

     for (int i = 1; i <= cuantos; ++i)
     {
          p.efectuarMovimientoIésimo(...);
          puntaje=-Alphabeta(p, 1-turno, profundidad-1, -beta, -alpha);  // !!
          p.deshacerMovimientoIésimo(...);

          if (puntaje > alpha)                           // (alpha es = a mejor)
          {
               if (puntaje >= beta) { return beta; }     // corte inmediato!

               alpha = puntaje;                          // achica ventana por lo menos

               mejor = puntaje;   mejorjugada = i;
          }
     }

     return mejor;
}

int Alphabeta (posicion p, int turno, int profundidad, int beta, int alpha)   // aquí nomás ponerlos dados vuelta
{

alpha = -alpha;  // cambio de signo
beta  = -beta;   // cambio de signo
...
...
          puntaje=-Alphabeta(p, 1-turno, profundidad-1, alpha, beta);     // ahora se pueden poner igual que antes!!
...
...
}

Jugando con las ventanitas

Ordenamiento

Tablas de hashing para un programa de ajedrez

Cómo obtener un índice y una clave para una posición de ajedrez?, bueno una manera muy recomendada es con el algoritmo de Zobrist, utilizando instrucciones XOR(o exclusivo):