Reportajes 27/03/2017 | 21:43por GM Pepe Cuenca

¿Cómo piensan y operan los módulos de análisis?

Escasos son los ajedrecistas que no portan sus computadoras con módulo de ajedrez instalado en las mismas durante los torneos o durante las sesiones de entrenamiento en casa. Atrás quedó la época en la que para analizar una posición compleja, varios Grandes Maestros necesitaban horas e incluso días para sacarle todo el jugo, y en numerosas ocasiones, sin acierto.  Este problema hoy en día es resuelto en cuestión de segundos por una “máquina” que nos dice la mejor jugada en cualquier posición a un nivel más elevado que el del campeón del Mundo Magnus Carlsen.

En 1997 Deep Blue venció a Kasparov por 3.5 a 2.5 en lo que supuso el fin del reinado humano.  foto: www.ajedrezalataque.com

Pero…. un momento… ¿tenemos idea de cómo funcionan? ¿Cómo es posible que analicen  de una manera instantánea infinidad de variantes con acierto? Yo mismo, tras 20 años en competición, seguía sin tener ni pajolera idea del mecanismo de estos monstruos. Me picó el gusanillo de la curiosidad y he investigado un poquito sobre el tema. En este artículo trataremos de entender el funcionamiento de los módulos de análisis y su manera de pensar. Para ello, hablaremos sobre conceptos matemáticos, principalmente de algoritmos.

¡Pero no os asustéis! Vamos a tratar el tema de un modo superficial y todo el mundo va a poder entenderlo, ¡así que allá vamos!

Cómo funcionan: Algoritmo Minimax

El ajedrez es lo que se denomina un “juego de suma zero”, que no es más que un juego en el que las ganancias de uno de los jugadores equilibran exactamente las pérdidas del otro jugador. En consecuencia, las ganancias totales menos las pérdidas totales son iguales a cero, de ahí la nomenclatura “de suma zero”.

Por ejemplo, en la posición del diagrama, el blanco acaba de capturar en f6, ganando un caballo.

Ganancias del blanco: 1 caballo

Pérdidas del negro: 1 caballo

Ganancias – pérdidas =0. 



Para determinar el score en un juego de suma cero tras cierto número de jugadas, se usa el algoritmo minimax, en el que se asume el mejor juego posible de acuerdo a una función de evaluación.

Minimax es una palabra muy bonita, pero ¿cómo funciona este algoritmo?

En lo que se denomina una búsqueda one-ply, es decir, donde sólo secuencias de jugadas con longitud 1 son examinadas, el bando que juega (denominado max player) simplemente puede “ver” la evaluación después de todas las posibles jugadas. De esta forma, la jugada con la mejor evaluación es elegida. Pero en una búsqueda two-ply, donde el rival (min player) también mueve, es más complejo. Éste elige también la jugada que le proporciona la mejor evaluación.

Resumiendo, se trata de elegir el mejor movimiento para uno mismo suponiendo que el rival escogerá el peor para ti.

Consideremos el ejemplo del siguiente dibujo: 


Imaginemos que es el turno de las blancas, donde hay que elegir entre Tc7, Cd6 o a4. Para cada posible elección el negro puede escoger entre tres respuestas. Los números de abajo indican la evaluación de la posición (positivo favorable a las blancas y negativo a las negras). Como sugiere minimax, tenemos que ponernos en el peor de los casos y asumir que el negro va a responder con la jugada más dañina. Es por eso que en una primera fase del algoritmo, se calcula la jugada más dañina como respuesta, que será el mínimo en cada uno de los casos (-8, 0, 3). Finalmente, se calcula el máximo (3). Por tanto, la jugada a realizar por la máquina será Cd6. 

Como podemos ver, desde el punto de vista computacional, harían falta dos subrutinas para el Min player y el max player. Se pueden unir usando una versión del algoritmo minimax llamada Negamax, que se basa en la siguiente relación matemática: 

max (a,b) = - min (-a, -b)

Quien se haya parado a pensar un poco sobre minimax, se habrá dado cuenta de que usado a fuerza bruta es bastante ineficiente, de hecho tiene un coste computacional del orden 

0(R^p) 

donde R es el denominado factor de ramificación (branching factor) y p es la profundidad.  R suele ser aproximadamente 35 en una posición de medio juego (35 jugadas legales de media en cada turno) y p podría ser 100 ya que de media podríamos suponer 50 jugadas en cada partida. Por tanto 35^100= 2.5E154 lo que significa que tardaríamos muchos universos en llegar al final del árbol de búsqueda en una sóla partida. 

En consecuencia necesitamos una solución para este problema. Una de las más empleadas es la limitación de la profundidad de búsqueda. A cierta profundidad, simplemente le pegamos un buen "tajo" al árbol de búsqueda y realizamos una evaluación estática de la posición tal y como observamos en el dibujo de abajo. 



Evaluación de posiciones: 

¿Cómo evalúan las máquinas cada posición existente en el tablero? Esta cuestión es la más importante ya que incluso si el módulo de análisis es capaz de profundizar muchas jugadas, si la evaluación es incorrecta no servirá de nada. 

Dichas evaluaciones se producen mediante lo que se denomina función de evaluación, que se puede expresar de la siguiente manera: 

f(x)= w1*f1(x) + w2*f2(x)+ w3*f3(x)+ ... 

Una función de evaluación es una combinación lineal de "características" f(x) con pesos w que determinan la importancia de cada una de dichas características. La función de evaluación más básica realiza solamente un conteo de piezas existentes en el tablero: 

f1(x)= nº de damas blancas - nº de damas negras 

f2(x)= nº de torres blancas - nº de torres negras

f3(x)= nº de alfiles blancos - nº de alfiles negros

f4(x)= nº de caballos blancos - nº de caballos negros

f4(x)= nº de peones blancos - nº de peones negros

donde además los pesos asignados son los numeritos que aprendimos en el cole :) 

w1=9

w2=5

w3=3

w4=3

w5=1

Claramente, esta función de evaluación tan sencilla lleva a errores y los módulos no la usan. Como ejemplito ponemos el diagrama siguiente: 


Blancas juegan

donde la la función de evaluación presentada daría como resultado:

f(x)= 9*(1-0) + 5*(0-2) + 3*(1-1) + 3*(0-2) + 1*(1-4) = -10 

 (ventaja decisiva negra). Nada más lejos de la realidad ya que las blancas juegan Dh6 y el negro puede abandonar. Por esto las máquinas usan una evaluación avanzada donde diferentes técnicas son empleadas:

1. Evaluación gradual: 

Es interesante variar los pesos de las funciones según la fase de juego en la que nos encontremos. Por ejemplo, queremos que nuestro rey esté alejado del centro en el medio juego. Sin embargo, como todos sabemos, es una pieza fundamental en los finales y mejor que esté en el centro. Para medir la fase de juego existente, los módulos pueden usar el nº de piezas sobre el tablero por ejemplo. 

2. Pareja de alfiles

Se puede añadir un pequeño bonus por la pareja de alfiles (con la misma se cubren todas las casillas del tablero).

3. Tablas de piezas y casillas

Son una manera simple de asignar valores a piezas específicas en casillas específicas. Por ejemplo durante la apertura, los peones tendrán un pequeño bonus por ocupar casillas centrales. 

4. Seguridad del rey

Esto es muy importante. Por ejemplo se puede medir calculando la cantidad de peones que rodean al rey, o si hay una torre cerca del mismo.

5. Movilidad 

Uno normalmente prefiere posiciones donde tienes más opciones, por ejemplo alfiles con diagonales abiertas, etc... Esto se puede medir por ejemplo usando el nº de jugadas legales posibles en una posición como score para la movilidad.

6. Estructura de peones

Los peones doblados pueden dar un bonus negativo, o por ejemplo los peones aislados en finales, ya que como todos sabemos son más fáciles de atacar. 

7. Torre en columna abierta

Esto como sabemos suele ser positivo al igual que tener una torreen séptima. Hay muchos más factores que se pueden tener en cuenta pero estos siete resumen bien la idea de la evaluación avanzada que uno puede añadir a las funciones de evaluación. 


El efecto horizonte

Vamos a hablar ahora del efecto horizonte, algo que ocurre al limitar la profundidad de la búsqueda. Imagina que el módulo está buscando a profundidad 3 y hay una torre encerrada. Para evitar su pérdida, el módulo sacrifica un caballo para llevar la pérdida de torre "fuera del horizonte". Como resultado, se acaba perdiendo el caballo y la torre, ya que la pérdida de esta última era inevitable. 


Ilustración del efecto horizonte

Supongamos que en el ejemplo ilustrado arriba es el turno de las blancas y que la profundidad del módulo es 1. La torre de a5 está perdida pero la máquina jugaría Axf7 para evitar la pérdida de la torre dentro del horizonte. El resultado es desastroso, y el blanco tras Txf7 perdería ambas piezas.

La solución es lo que se conoce como la búsqueda de quiescencia (quiescence search) y esta consiste en no limitar la profundidad de análisis con un simple número, sino que el módulo analiza las variantes hasta que la posición es "tranquila". ¿Qué entendemos por una posición "tranquila"? Aquella en la que las capturas no son posibles. 

Algoritmo Alpha-Beta (Alpha-Beta pruning)

El algoritmo Alpha-Beta es una mejora importante sobre el algoritmo de búsqueda minimax. Fue propuesto por John McCarthy en 1955 en la conferencia de Darmouth. Reduce sustancialmente las posibilidades a analizar en el árbol de búsqueda al utilizar una técnica de ramificación y y acotamiento. Esto significa que si uno está analizando las posibles respuestas a una jugada, es suficiente encontrar una refutación. Quizás haya refutaciones más fuertes, pero no es necesario analizarlas ya que con una sola nos basta para descartar dicha opción.  Esto parece sencillo, pero cuando el análisis es muy profundo, es bastante complejo, así que vamos a tratar de entenderlo como siempre con algún ejemplo sencillo. 

Imagina que es el turno de las blancas y que estamos buscando en profundidad 2, lo cual significa que consideramos todas las jugadas del blanco y todas las posibles respuestas del negro a cada una de esas jugadas. Primeramente, elegimos una de las jugadas posibles del blanco, que vamos a denominar "Jugada 1". Consideramos todas las respuestas por parte del negro y como resultado de este análisis, la posición queda igualada si el blanco decide optar por "jugada 1".

Tras este primer análisis, consideramos otra posible jugada de las blancas "jugada 2". Imaginad que analizando las posibles respuestas de las negras, ¡la primera de ellas da como resultado que el negro gana un alfil! Digamos que "jugada 2" queda refutada sin necesidad de profundizar más en el resto de posibles respuestas de las negras. Quizás es incluso peor y el negro gana la dama o da mate directamente, pero la pérdida del alfil ya nos hace descartar "jugada 2", ahorrando mucho tiempo computacional. Por tanto, "jugada 1" prevalece sobre "jugada 2". Resumiendo, el análisis completo de "jugada 1" proporciona un límite, es decir, sabemos que al menos hay una jugada que iguala la posición, descartando cualquier cosa que sea claramente inferior. 

Por supuesto, cuando la profundidad de análisis es 3 o mayor, la complejidad aumenta sustancialmente, porque ambos jugadores ahora pueden elegir opciones que afectan al árbol de jugadas. La estrategia entonces es mantener un límite inferior y superior llamados alfa y beta. La función del límite inferior es no considerar una jugada si es demasiado mala. También establecemos un límite superior porque si una jugada a la profundidad 3 o mayor lleva a una continuación que es demasiado buena, el otro jugador no la permitirá, porque hay muchas maneras en el árbol de posibilidades que podría haber usado para evitar esta situación. El límite inferior de un jugador es el superior del otro. 

Reducción de coste computacional: 

El ahorro al usar este algoritmo es importante. Supongamos que un árbol de búsqueda minimax tiene x nodos. Los nodos del árbol del algoritmo alpha beta en un código bien escrito pueden llegar a ser la raiz cuadrada de x. ¿Cuántos nodos nos podemos ahorrar? Pues depende de lo bien ordenado que el árbol de búsqueda esté. Si siempre buscas la mejor jugada posible primero, eliminas la mayor cantidad de nodos. Por supuesto, no siempre sabemos cuál es la mejor jugada, ya que si no ni haría falta buscar :)

Contrariamente, si siempre buscáramos peores jugadas antes de las mejores, ¡no podríamos ahorrarnos ningún nodo! Por esta razón, un buen orden de búsqueda de jugadas es muy importante y es la parte principal de un buen programa de ajedrez. Como dijo Levin en 1961, asumiendo constantemente c jugadas para cada nodo visitado y con profundidad p, el máximo número de hojas en alfa-beta es equivalente a minimax, c^p. Si consideramos siempre la mejor jugada primero, es

  c ^ ceil(p/2) + c ^ floor(p/2) -1

donde ceil y floor son funciones que mapean un número real al entero mayor precedente o sucesivo. En la siguiente tabla mostramos el mínimo número de hojas. 

Número de hojas con profundidad n y c=40

      Profundidad                 mejor caso                peor caso

       0                                 1                             1

       1                                40                           40

         2                              1.600                        79

            3                              64.000                      1.639

          4                           2.560.000                   3.199

      ...                              ...                             ...


Ahora vamos a pasar a ver otras técnicas empleadas para la reducción del coste computacional:

Pruning "Null Move"

Para explicar esta técnica, vamos a usar una analogía con el boxeo. Le damos al rival un "puñetazo" o turno gratis, y si aún así no te puede noquear, entonces teniendo uno el turno probablemente hubiera ganado. La implementación de esta técnica es de la siguiente manera: antes de hacer una búsqueda completa en una posición, se hace una búsqueda con menor profundidad en la que el turno pertenece al rival.

¡Homer Simpson cedía golpes y golpes a Trederik Tatum y aún así el tipo aguantaba! ¡No hagas lo mismo en ajedrez!

Si el resultado es que el "score" o evaluación es mayor que un determinado valor "alfa", entonces no hay que seguir buscando en ese subárbol. Se ahorra tiempo porque se reduce la profundidad. Por supuesto, si habéis prestado un poco de atención ¡esta técnica falla en posiciones de Zugzwang! Como sabéis, en estas posiciones, cualquier jugada que realizamos pierde y desearíamos que el rival moviese. Con lo cual esta técnica no es aplicable para estas posiciones. 

Reducciones de últimas jugadas

Normalmente, en nuestra búsqueda, las jugadas están ordenadas de mejor a peor. Por tanto, es interesante buscar con máxima profundidad las primeras jugadas de la lista en cada nodo y con menor profundidad las últimas. De esta manera, tiempo computacional es ahorrado y el factor de ramificación se puede reducir incluso a 2. 

Por último, para terminar este artículo, vamos a centrarnos en como se "representa" un tablero de ajedrez en todos estos algoritmos. 

Representación del tablero: Los Bitboards

El primer problema al que se enfrentaron los desarrolladores de módulos de ajedrez fue el cómo representar de una manera lo más sencilla y económica posible el tablero y las piezas. Inicialmente la capacidad de hardware era demasiado limitada por lo que la eficiencia en la representación del juego era un factor muy importante.

Los bitboards supusieron un gran avance en la representación del tablero, sus piezas, movimientos, etc. También son conocidos como bitsets o bitmaps. Como hemos dicho, son usados entre otras cosas para representar el tablero dentro de un programa de una manera "pieza céntrica". Esencialmente, son conjuntos finitos de hasta 64 elementos, un bit por casilla. 

Además de modelizar el tablero con la localización de las piezas, alguna información adicional es necesaria para especificar por completo una posición de ajedrez, por ejemplo a quien corresponde el turno, si es posible enrocarse o no, posibles capturas al paso y el número de jugadas no progresivas (capturas y movimientos de peón), para tener en cuenta la regla de las 50 jugadas. En este artículo solo vamos a mencionar las estructuras para representar las piezas y el tablero. 

Una representación de "pieza céntrica" es una lista, vector o conjunto de todas las piezas todavía vivas en el tablero, además de la información adicional que indique qué casilla ocupa en el tablero. Una manera común de conseguir esto es el llamado método del "set-wise bitboard" en donde cada pieza es asociada con una palabra de 64 bits, y un bit para su ubicación. Se pueden usar las llamadas "listas de piezas", "conjuntos de piezas" o "bitboards"

Representación de un bitboard. Fuente: chessprogramming wikispaces


Las listas de piezas son listas o vectores de hasta 32 piezas en el tablero. El color y el tipo de piezas se asocian a con un cierto índice. Cada elemento de la lista o vector para cada pieza en particular asocia la casilla ocupada por esta pieza. Por ejemplo, la representación de Peter Jennins en MicroChess se se basa por completo en una lista de 32 bytes para cada posible pieza. 

¡Bueno, este ha sido el viaje por el mundo de las máquinas de ajedrez! Os dejo algunos enlaces de interés para quien quiera ahondar más en el tema!

Para más información:


GM Pepe Cuenca

Pepe Cuenca es Gran Maestro de ajedrez. Además, es Ingeniero de Caminos Canales y Puertos por la Universidad de Granada, Máster Erasmus Mundus en modelización matemática y doctorado en matemática aplicada por la Universidad de Hamburgo en Alemania.




Ordenado por Fecha descendente Fecha descendente Fecha ascendente Más popular Recibir actualizaciones

Comentarios 46

Invitado
Guest 12225937141
 
Únete a chess24
  • Gratis, rápido y sencillo

  • No hay comentarios para este artículo

Registro
o

¡Crea gratuitamente tu cuenta para empezar!

Haciendo clic en 'Regístrate' aceptas nuestros términos y condiciones y confirmas haber leído nuestra política de uso de datos, incluyendo la sección de uso de cookies.

¿Perdiste tu contraseña? No hay problema, ¡te enviamos un enlace para restaurarla!

Después de que nos envíes este formulario, recibirás un email con un enlace para restaurar la contraseña. Si sigue sin funcionar, contáctanos Servicio al cliente

¿Qué características te gustaría permitir?

Respetamos tu privacidad y la protección de datos. Algunos componentes de nuestra web requiere cookies o almacenar tu información personal.

Mostrar opciones

Ocultar opciones