Cap. 11 - No hace falta mirar todas las ramas

cap. 11 Búsqueda · Motor 2012

No hace falta mirar todas las ramas

Negamax, alfa-beta y PVS en Mango AC
José Andrés Morales Linares
Madrid, España

En la entrada sobre bitboards expliqué cómo el motor ve el tablero. Aquí explico cómo decide. Cuando Mango AC «piensa», no adivina. Recorre un árbol de jugadas y se queda con la que, asumiendo que el rival también juega lo mejor que puede, le deja en mejor posición.

El algoritmo tiene nombre: Negamax alfa-beta con PVS (Principal Variation Search). La función se llama alfabetaNegado() y vive en busquedad.c. Lo escribí en 2012 y no lo he reescrito. Este artículo empieza por el árbol, no por las siglas.

Qué es el árbol de juego

Desde una posición hay, típicamente, unas treinta jugadas legales. Cada una produce una posición nueva, con otras treinta, y así. Si se dibuja, parece un árbol invertido: la posición actual es el tronco; cada jugada, una rama; las posiciones donde uno deja de buscar son las hojas.

Un nudo (o nodo) es una posición en ese árbol. Un ply es un medio movimiento: una jugada de un solo bando. «Profundidad 6» son seis plies: tres jugadas blancas y tres negras, aproximadamente. El techo en Mango AC es 24 (MAX_CAPAS_BUSQUEDAD).

El problema no es imaginar el árbol. Es que crece demasiado. Treinta ramas a cada paso, a diez plies, son miles de millones de hojas. Nadie las visita todas. El arte está en no mirar las que ya no pueden cambiar la decisión.

Dos voluntades: maximizar y minimizar

El ajedrez es un juego de suma cero: lo que gana uno lo pierde el otro. Yo quiero el número más alto (una posición mejor para mí). El rival quiere el más bajo (mejor para él, peor para mí). Eso se llama minimax: en mi turno elijo el máximo; en el suyo, él elige el mínimo.

Analogía: dos personas negocian el precio de una casa. El vendedor quiere subirlo; el comprador, bajarlo. Cada uno asume que el otro no va a regalar nada. El precio que «sale» no es el sueño de nadie: es lo mejor que cada uno puede forzar si el otro se defiende bien.

En las hojas ya no hay ramas. Ahí no se busca: se evalúa. evaluacionTablero() pone un número a la posición (material, peones, rey). Ese número sube por el árbol, maximizado o minimizado en cada piso, hasta la raíz. La raíz elige la jugada que conduce al mejor de esos números.

Negamax: siempre «lo mejor para quien mueve»

Minimax escribe dos casos: si me toca, max; si le toca, min. Negamax es el mismo algoritmo con un truco de signo. Quien está sentado en el nudo siempre pregunta: «¿cuál es mi mejor jugada?». El hijo responde con su propio mejor, y yo lo niego: lo que es bueno para él es malo para mí.

Analogía: en lugar de dos reglas («vendedor sube, comprador baja»), cada uno, cuando le toca hablar, pregunta solo «¿qué me conviene a mí ahora?» y el otro, al oírlo, invierte el signo. Una sola rutina sirve para ambos bandos.

Por eso el hijo se llama con los límites al revés y el resultado se niega:

V = -alfabetaNegado(capa + 1, profundidad-1, -beta, -alfa, VERDADERO);

Si el hijo dice «+120 para mí», yo oigo «−120 para mí». Esa es toda la magia de Negamax. El comentario en el código lo nombra así: «BUSQUEDA ALFA-BETA: Variación de búsqueda principal».

Alfa y beta: dos vallas en el camino

Recorrer el árbol entero sigue siendo imposible. Alfa-beta añade dos números que viajan con la búsqueda:

Nombre	Qué significa	En la vida
Alfa	Lo mejor que quien mueve ya puede forzar	El suelo: no vendo por menos de esto
Beta	Lo peor que el rival ya puede imponerle	El techo: no pago más de esto

Si en una rama aparece un valor mayor o igual que beta, el rival nunca dejaría llegar ahí: ya tiene algo peor para mí en otra parte. No hace falta mirar el resto de esa calle. Eso es un corte beta. En el código: si V >= beta, guardo un movimiento killer, anoto cota en la tabla hash y return V.

Analogía: busco piso. Ya vi uno aceptable (alfa). Entras a un edificio y el portero te dice el precio del primero. Si ya supera lo que estoy dispuesto a pagar (beta), no subo al segundo ni al tercero. El edificio entero queda podado.

Alfa-beta no cambia el resultado respecto a minimax si se recorren las mismas mejores ramas. Solo deja de visitar las que ya no pueden ganar. Cuanto mejor se ordenen las jugadas, antes llega el corte y menos ramas se miran.

El orden importa

Si miro primero la jugada mediocre, alfa sube tarde y recorto poco. Si miro primero la buena, recorto pronto. ponderarMovimientos() ordena así: jugada de la tabla hash, jugada de la variante principal, promociones, capturas (MVV/LVA), historia (origen→destino, profundidad²) y dos killers por capa. SEE en eet.c evita perseguir capturas que pierden material.

Analogía: si al entrar al mercado preguntas primero el puesto que suele tener el mejor precio, pronto sabes el suelo y dejas de entrar a los caros. Si empiezas por el fondo del pasillo, recorres todo.

PVS: la avenida y los callejones

Principal Variation Search apuesta a que la primera jugada, bien ordenada, es la mejor. A esa la busco con ventana completa [-beta, -alfa]. A las demás les hago una pregunta barata: «¿eres peor que alfa?» Eso es una ventana nula, de un solo punto: [-alfa-1, -alfa].

/* primera jugada legal: ventana completa */
V = -alfabetaNegado(..., -beta, -alfa, ...);

/* resto: ventana nula; si falla, re-búsqueda */
V = -alfabetaNegado(..., -alfa-1, -alfa, ...);
if ((alfa < V) && (V < beta))
    V = -alfabetaNegado(..., -beta, -alfa, ...);

Si el callejón resulta interesante (el valor entra en la ventana), vuelvo y lo recorro en serio. Si no, lo descarté barato. Un nudo es PV cuando la ventana es ancha: nodoPV = ((beta - alfa) > 1).

Analogía: recorro una ciudad. La avenida principal la camino despacio (ventana completa). En cada callejón asomo la cabeza: si no se ve nada mejor que lo que ya tengo, sigo. Si se ve algo raro, entro y lo recorro entero.

Cómo arranca Mango AC

pensarRapido() no llama a alfa-beta a ciegas. Primero consulta el libro de aperturas. Si en la raíz hay una sola jugada legal, la devuelve sin buscar. Luego entra en profundidad iterativa: busca a 1 ply, luego 2, luego 3, hasta el techo o hasta que se acabe el reloj. Cada iteración deja una variante principal (PV triangular) que ordena la siguiente.

Analogía: antes de cruzar el bosque a oscuras, lo recorro una vez a la luz del día, luego con una linterna un poco más lejos, usando el sendero que ya reconocí.

Alrededor de la puntuación anterior abro una ventana de aspiración de ±33 centésimas de peón. Si el resultado se sale, reabro con margen 66 y, si hace falta, con ventana infinita. Es asumir que la posición no cambia de carácter de un ply al siguiente; cuando sí cambia, pago el reintento.

Las hojas no se evalúan en medio del recambio

Cuando profundidad < 1 (o se llega al tope de capas), no llamo a la evaluación estática al instante. Llamo a busquedadTranquilidad(): solo capturas y jaques, hasta que la posición se calma. Evaluar en medio de un recambio de damas sería fotografiar la sala mientras aún mueven los muebles.

Podas que ahorran aún más

Encima de PVS hay atajos. No son el núcleo; son el aceitado. El movimiento nulo pregunta: si paso el turno y aún así estoy por encima de beta, esta posición era tan buena que no hace falta buscar mis jugadas. LMR (reducción de movimiento tardío) busca más corto a partir del cuarto candidato silencioso; si mejora alfa, re-busca a profundidad completa. Hay futility, razoring, extensiones de un ply (jaque, recaptura, peón a 7.ª) y tabla hash Zobrist para no repetir trabajo.

Si el reloj vence, la función deja de profundizar y se queda con la mejor jugada de la última iteración terminada. Por eso la profundidad iterativa no es un lujo: es la forma de tener siempre una respuesta lista.

El puente con los bitboards

En cada nudo, antes del bucle PVS:

juego.Buffer_MOV_INDEXCAPAS[capa+1] =
    generarTodosMov(juego.Buffer_MOV_INDEXCAPAS[capa]);
ponderarMovimientos(capa, &h_mov, profundidad);

Alfa-beta decide qué ramas no mirar. Los bitboards deciden lo rápido que se construye la lista de cada nudo que sí se mira. Sin generador rápido, el árbol no llega lejos. Sin alfa-beta, el generador rápido se gastaría en ramas inútiles. Los dos se necesitan.

Qué archivos leer en el código

Archivo	Qué hay
busquedad.c	pensarRapido(), profundidad iterativa, aspiración, alfabetaNegado()
busquedadTranquilidad.c	Hojas: solo capturas y jaques
ordenar.c	Orden de jugadas, killers, historia
hash.c	Tabla de transposición (Zobrist)
fevaluacion.c	El número que sube desde las hojas
ajedrez.c	La lista de ramas: generarTodosMov()

El repositorio del motor: GitHub.

Cierre

Un árbol de juego es el mapa de lo que podría pasar. Minimax es dos voluntades opuestas. Negamax es esa idea con un solo signo. Alfa y beta son el suelo y el techo que permiten no entrar a cada edificio. PVS recorre la avenida en serio y los callejones de reojo. La profundidad iterativa garantiza una respuesta aunque suene el reloj.

Eso es lo que hace alfabetaNegado() desde 2012. El estilo de juego de Mango AC nace ahí: no de mirar todo, sino de saber qué ramas ya no hace falta mirar.

Correo de contacto: comprasmangocomputer@gmail.com