Cap. 4 - Un entero y un rebobinado

cap. 4 Tablero · Motor 2012

Un entero y un rebobinado

hacerMovimiento y desHacerMovimiento
José Andrés Morales Linares
Madrid, España

El generador anota candidatas. Alfa-beta las prueba una a una. Probar no es copiar el tablero a un cajón nuevo: es hacer la jugada sobre el mismo bitboard y, al volver, deshacerla. Si cada ply fotocopiara la sala, el árbol no cabría en el reloj. Lo que cabe es un entero de 28 bits y una pila con lo que no se puede reconstruir a ciegas.

Lo escribí en 2012 en ajedrez.c. No he reescrito el algoritmo. Este artículo empieza por por qué no se copia el tablero, no por cada caso del switch.

Por qué no fotocopiar la sala

Un nudo genera treinta jugadas, baja, vuelve, prueba la siguiente. Copiar BITTABLERO (bitboards, ocupación, material, hash) en cada una es caro y sucio. Analogía: no se fotocopia la sala cada vez que mueve un mueble. Se mueve el mueble, se anota dónde estaba, y al rebobinar el carrete el mueble vuelve. El XOR de un bitboard es exactamente eso: el bit se apaga en origen y se enciende en destino con la misma operación.

Lo que el XOR no recuerda solo es el estado lateral: enroques, peón al paso, regla de cincuenta, la llave hash de antes. Eso va a la pila historicoJuego[], tipo DATAJUEGO.

La maleta de 28 bits

Una jugada no es una cadena e2e4 dentro del árbol. Es un uint32 con campos empaquetados. Los macros de macros.h leen y escriben cada etiqueta:

Campo	Bits	Qué guarda
Origen	0–5 (6)	Casilla 0…63 (a1 = 0)
Destino	6–11 (6)	Casilla destino
Pieza	12–15 (4)	Quién se mueve
Captura	16–19 (4)	Qué se come (0 = nada)
Promoción	20–23 (4)	A qué corona
Código	24–27 (4)	Silencio, doble peón, enroque, al paso, promociones

Analogía: una maleta con seis etiquetas. No hace falta una carta. El código distingue lo que el origen y el destino no dicen solos: un peón que avanza dos, un enroque, una captura al paso. Al deshacer, esas etiquetas dicen dónde devolver el peón capturado o la torre del enroque.

origen  = OBT_MOV_ORIGEN(mov);   /* bits 0..5  */
destino = OBT_MOV_DESTINO(mov);  /* bits 6..11 */
pieza   = OBT_MOV_PIEZA(mov);
captura = OBT_MOV_CAPTURA(mov);

Hacer: XOR, material, hash

hacerMovimiento() primero fotografía el estado lateral en historicoJuego[indiceHJuego]: enroques, ep, cincuenta, total de jugadas, el propio movimiento, la llave hash. Luego XOR del bitboard de la pieza (origen y destino a la vez: BITSET[origen] | BITSET[destino]), actualiza blancos/negros/ocupados, el array ESCAQUES[] y el material. La llave Zobrist se retoca al vuelo: se quita la pieza del origen, se pone en el destino; si hay captura, se quita la víctima; al final, XOR del lado (cambia el turno).

juego.historicoJuego[juego.indiceHJuego].llaveHash = juego.llaveHash;
juego.llaveHash ^= arrayHash.llaves[origen][pieza]
                ^  arrayHash.llaves[destino][pieza];
/* ... captura, ep, enroque ... */
juego.llaveHash ^= arrayHash.lado;
juego.indiceHJuego++;

El peón al paso, el enroque y la promoción son casos del switch (pieza): no se inventan después. Cada uno toca bits extra (el peón comido no está en el destino; la torre del enroque salta). Por eso van en el entero y no se infieren.

Deshacer: rebobinar el carrete

desHacerMovimiento() hace el XOR inverso sobre los bitboards (la misma máscara vuelve a apagar el destino y encender el origen) y restaura el estado lateral desde la pila. No recalcula la llave: la copia de vuelta.

juego.indiceHJuego--;
juego.OOB          = juego.historicoJuego[indice].OOB;
juego.posPeonPaso  = juego.historicoJuego[indice].posPeonPaso;
juego.llaveHash    = juego.historicoJuego[indice].llaveHash;
/* ... XOR inverso de tablero, blancos, ocupados, ESCAQUES ... */

Analogía: el carrete no inventa dónde estaba el mueble. Lo tenía escrito. Los bits se rebobinan porque XOR dos veces es la identidad. La llave, los enroques y el al paso no se arriesgan a un cálculo: se leen.

Después de hacer, el motor pregunta si el propio rey quedó atacado. Si sí, la jugada era pseudo-legal: se deshace y se ignora. El generador es barato; el filtro de jaque es el peaje de no generar solo lo legal.

Qué archivos leer

Archivo	Qué hay
ajedrez.c	hacerMovimiento (~804), desHacerMovimiento (~1256)
macros.h	EST_MOV_* / OBT_MOV_*: maleta de 28 bits
tipoDatos.h	DATAJUEGO, pila historicoJuego[]

El repositorio del motor: GitHub.

Cierre

El árbol camina sobre un solo tablero. Cada paso es un entero y un XOR; cada vuelta, el mismo XOR y una línea de la pila. No se fotocopia la sala. Se rebobina el carrete. Encaja con los bitboards (generar es barato) y con Perft (contar hojas es hacer, filtrar jaque, deshacer, sin tasar).

Hay capturas que ni siquiera merecen ese viaje: el intercambio en la casilla ya es ruinoso. Eso lo estima SEE. La siguiente entrada.

Correo de contacto: comprasmangocomputer@gmail.com