Cap. 12 - Hasta que se calme el tablero

cap. 12 Tranquilidad · Motor 2012

Hasta que se calme el tablero

Búsqueda de tranquilidad y el efecto horizonte
José Andrés Morales Linares
Madrid, España

Alfa-beta baja un número fijo de plies y, al llegar a la hoja, pide un número a evaluacionTablero(). Si esa hoja cae en medio de un recambio de damas, la tasación miente: cuenta una dama de más o de menos porque el recambio aún no ha terminado. Eso se llama efecto horizonte. La búsqueda de tranquilidad (quiescence search) es el tramo que añadí delante de la evaluación para no fotografiar la sala mientras mueven los muebles.

En Mango AC vive en busquedadTranquilidad.c. La llamo desde alfabetaNegado() cuando profundidad < 1, o cuando ya no caben más capas de búsqueda plena (MAX_CAPAS_BUSQUEDAD = 24). Lo escribí en 2012 y no lo he reescrito.

Qué es el horizonte

Imagine que deja de mirar el camino exactamente a diez pasos. Justo en el paso once hay un precipicio, o un tesoro. Usted no lo ve: su horizonte lo tapa. En ajedrez el precipicio suele ser una captura. El motor «gana» una dama en el último ply permitido y se frotan las manos; el ply que no miró era la recaptura. La evaluación dice +975 y la posición real está igualada.

Una posición tranquila es aquella en la que no hay recambios pendientes ni un rey en jaque que obligue a seguir. Ahí sí tiene sentido tasar. Mientras haya capturas jugosas o jaque, el polvo no se ha posado.

Analogía: no ponga precio a un combate mientras aún se intercambian golpes. Espere a que ambos bajen los puños. Eso es la tranquilidad.

Stand-pat: puedo no capturar

En tranquilidad no estoy obligado a seguir pegando. Puedo «plantarme»: aceptar la tasación estática de la posición actual. Eso se llama stand-pat. En el código:

Vparcial = evaluacionTablero(alfa, beta);
if (!estoyJaque) {
    if (Vparcial >= beta) return Vparcial;  /* ya basta */
    if (Vparcial > alfa)  alfa = Vparcial;  /* suelo nuevo */
}

Si la evaluación ya supera beta, el rival no dejaría llegar aquí: corte. Si supera alfa, ese valor pasa a ser el suelo. Luego solo miro capturas (o evasiones) que puedan mejorarlo. Analogía: ya tengo una oferta decente por la casa; solo visito al tasador de nuevo si alguien propone tirar un muro que claramente suba el precio.

Si estoy en jaque no puedo plantarme. El rey está bajo amenaza: hay que generar todas las jugadas legales (generarTodosMov), no solo capturas. Un jaque no es una posición tranquila.

Qué jugadas se miran

Fuera de jaque, generarMovCapPro() en ajedrez.c no recorre el tablero entero. Los destinos son las piezas enemigas: solo capturas. Los peones en séptima (o segunda, negras) añaden también el avance que corona. Al paso entra si aplica. agregarMovCapPro() ordena al estilo MVV/LVA: valor capturado × 128 menos valor que captura, más un extra si hay promoción.

Situación	Generador	Por qué
Sin jaque	generarMovCapPro	Solo capturas y coronaciones: el polvo del recambio
En jaque	generarTodosMov	Hay que salir: tapar, huir o capturar la pieza que da jaque

No busco jugadas tranquilas (un caballo a una casilla vacía) en este tramo. Si lo hiciera, el horizonte se alargaría otra vez hasta el infinito. La apuesta es: lo que distorsiona la tasación son las capturas, no un desarrollo lento.

Cómo se recorre: Negamax otra vez

Cada captura legal se hace, se comprueba que el propio rey no quede en jaque, y se llama de nuevo a la misma función, con el signo invertido:

V = -busquedadTranquilidad(capa + 1, -beta, -alfa);

Es el mismo Negamax de la búsqueda plena, pero el árbol solo tiene ramas de captura (o evasiones). Si V >= beta, corte; si mejora alfa, actualizo la variante triangular. Los nudos de este tramo se cuentan aparte: QcontadorNodos. En la salida UCI/xboard a veces verá nodos y qnodos: los segundos son este polvo.

Hay un techo para no ahogarse en un recambio eterno: MAX_CAPAS_QBUSQUEDAD = 30. Si se llega ahí, se evalúa y se termina. Analogía: si la pelea no acaba nunca, en algún momento hay que parar el cronómetro y puntuar.

Si estaba en jaque y no queda ninguna evasión legal, es mate: -VALOR_JAQUE_MATE + capa - 2. La regla de cincuenta movimientos, si se cumple, empata.

Delta: no persiga recambios que no alcanzan

Aunque solo mire capturas, hay demasiadas. Delta pruning: si ni capturando una dama (y, si hay peón a punto de coronar, un extra de 875) subo alfa, no sigo. En medio juego:

DELTA = VALOR_DAMA;           /* 975 */
if (peón blanco en 7.ª o negro en 2.ª)
    DELTA += 875;
if (Vparcial + DELTA < alfa)
    return alfa;

Analogía: si para llegar al precio que ya me han ofrecido tendría que encontrar un tesoro del tamaño de una dama, y ni así llega, no abro más cajones. En final no aplico este corte: allí un peón pasado sí puede valer una dama.

No recapture perdiendo: SEE

Antes de bajar por una captura, si no es promoción ni jaque ni final, miro EET() (SEE: static exchange evaluation en eet.c). Si entrego una pieza más cara que la que tomo y el intercambio estimado es peor que −15 centipéones, ni siquiera busco esa rama. Analogía: no cambio mi coche nuevo por una bicicleta y luego simulo el resto del día.

Dónde se engancha en el árbol

En alfabetaNegado() el horizonte de la búsqueda plena se acaba así:

if (capa >= MAX_CAPAS_BUSQUEDAD) return busquedadTranquilidad(capa, alfa, beta);
if (profundidad < 1)            return busquedadTranquilidad(capa, alfa, beta);

También la uso en un atajo de razoring a profundidad 1: si el material ya huele a corte, una pasada de tranquilidad basta para confirmar. La evaluación estática, la de la entrada anterior, se llama dentro de la tranquilidad (stand-pat y techo de 30 capas), no en crudo al terminar alfa-beta.

El puente con las otras piezas del motor es el de siempre: generarMovCapPro usa bitboards; el bucle es Negamax con alfa y beta; el número del stand-pat es evaluacionTablero.

Qué archivos leer en el código

Archivo	Qué hay
busquedadTranquilidad.c	Stand-pat, delta, bucle Negamax, mate en jaque
ajedrez.c	generarMovCapPro, agregarMovCapPro (MVV/LVA)
eet.c	SEE: no perseguir capturas perdedoras
busquedad.c	Quién llama a la tranquilidad al acabar el ply
macros.h	MAX_CAPAS_QBUSQUEDAD 30, INCREMENTO_PROMO_DELTA_CORTE

El repositorio del motor: GitHub.

Cierre

El horizonte es el borde de lo que uno se permite mirar. Evaluar justo en ese borde, en medio de un recambio, es mentirse. La búsqueda de tranquilidad alarga el borde solo por las capturas y los jaques, deja plantarse si la tasación ya basta (stand-pat), descarta tesoros imposibles (delta) y no cambia un coche por una bicicleta (SEE). Cuando el tablero se calma, entonces sí llama a evaluacionTablero.

Así encaja con las entradas anteriores: los bitboards generan esas capturas; Negamax las compara; la evaluación pone el precio cuando ya no hay polvo en el aire.

Correo de contacto: comprasmangocomputer@gmail.com