Cap. 7 - No tasar otra vez la misma casa
cap. 7 Memoria · Motor 2012
No tasar otra vez la misma casa
En la entrada de podas nombré la tabla hash de pasada: si esa posición ya se buscó, a veces se puede devolver el valor y no bajar otra vez. Esta es la entrada de cómo se recuerda. Sin esa memoria, alfa-beta tasaba mil veces el mismo salón llegado por pasillos distintos. Eso se llama transposición: 1. e4 e5 2. Nf3 Nc6 y 1. Nf3 Nc6 2. e4 e5 son la misma casa. El número de la puerta es una llave Zobrist.
Lo escribí en 2012 en hash.c. No he reescrito el algoritmo. Este artículo empieza por qué hace falta recordar, no por el tamaño en megas.
Por qué recordar importa
El árbol no es un árbol puro: es un grafo. La misma posición aparece por caminos distintos. Si cada visita vuelve a generar jugadas, a ordenarlas y a bajar, el reloj se gasta en trabajo ya hecho. Analogía: no volver a tasar la misma casa porque llegó por otra calle. Guarde el precio, la profundidad a la que miró, y la mejor puerta que abrió.
Esa memoria también sirve para otra cosa: detectar un bucle. Si la llave de ahora ya estaba en la pila de la partida, es repetición y empate. El cajón y el carrete usan la misma etiqueta.
Zobrist: un número por cada cosa que cambia
Albert Zobrist, 1970: a cada pieza en cada casilla se le asigna un entero aleatorio de 64 bits. La llave de la posición es el XOR de todos ellos, más el turno, los enroques y el peón al paso. XOR es barato e invertible: al mover, se quita la pieza del origen y se pone en el destino con dos XOR. No se recorre el tablero.
En Mango AC vive en LLAVESHASH (tipoDatos.h). iniciarHash() no tira los dados en cada arranque: copia tablas fijas (randoms, enpassant_random, castle_random) para que la misma posición tenga siempre la misma llave.
typedef struct {
uint64 llaves[64][16]; /* pieza x casilla */
uint64 lado; /* turno negro */
uint64 ep[64];
uint64 OOB, OOOB, OON, OOON;
} LLAVESHASH;
Analogía: cada ladrillo de la casa tiene un sello único. El número de la puerta es la mezcla de todos los sellos. Mueva un ladrillo: quite su sello y ponga el del sitio nuevo. La casa cambió; la etiqueta también.
Al hacer una jugada, hacerMovimiento() actualiza juego.llaveHash al vuelo. Al deshacer, restaura la llave guardada en la pila. La repetición compara esa llave con las de historicoJuego[], de dos en dos, hasta el horizonte de la regla de cincuenta movimientos.
El cajón: REGISTRO_TABLA_HASH
La tabla no guarda el tablero. Guarda un cajón indexado con los bits bajos de la llave: tabla_hash + (juego.llaveHash & LARGO_TABLA_HASH). Dentro hay cinco campos:
typedef struct {
uint64 id; /* llave completa (colisión) */
uint8 profundidad;
int puntaje;
MOVIMIENTO mov;
uint8 banderas;
} REGISTRO_TABLA_HASH;
El id es la llave entera: dos posiciones distintas pueden caer en el mismo cajón (los bits bajos coinciden). Si el id no coincide, el cajón es de otra casa y se ignora. El mov es la mejor jugada que se encontró entonces: la primera que probará la ordenación la próxima vez.
Al guardar, no se pisa un cajón más profundo de la misma posición. Los mates se ajustan con la capa para que «mate en tres» no dependa de a qué altura del árbol se anotó.
Las etiquetas del cajón
Un número solo no basta. Alfa-beta no siempre conoce el valor exacto: a veces solo sabe que es peor que alfa o mejor que beta. Por eso cada cajón lleva una bandera (macros.h):
| Bandera | Quiere decir | Qué hace verificarTablaHash |
|---|---|---|
EXACTO (4) |
Precio cerrado | Devuelve el valor (fuera de nudos PV) |
ARRIBA (1) |
A lo sumo este precio (falla baja) | Si valor ≤ alfa, corta con alfa |
ABAJO (2) |
Al menos este precio (corte beta) | Si valor ≥ beta, corta con beta |
EVITAR_NULL (8) |
El nulo no va a cortar | No prueba movimiento nulo |
Analogía: el cajón no dice solo «120.000 euros». Dice «precio exacto», «a lo sumo» o «al menos». Si usted busca una casa de menos de 100.000 y el cajón dice «al menos 150.000», no entra. Si dice «a lo sumo 80.000» y usted no compra por debajo de 100.000, tampoco. Solo el precio exacto le ahorra subir todos los pisos.
Solo se usa un cajón más profundo que el nudo actual. Un recuerdo superficial no sustituye una búsqueda más honda. EVITAR_NULL es un caso aparte: si ya se sabe que un nulo fallaría, no se gasta el ply en probarlo.
Otra tabla: solo la tasación
evaluacionTablero() también es cara si se llama mil veces en la misma hoja. Hay una tabla aparte, HASH_EVAL: llave e entero. Tamaño fijo LARGO_HASH_EVAL = 1.048.575 (20 bits). No guarda profundidad ni jugada. Solo el precio de la acera.
Cuánto ocupa: mangoac.ini
TamanioTablaHash vale de 1 a 9: llaves de 18 a 26 bits. Por defecto, 5 → 22 bits, unos 4,2 millones de cajones, unos 96 MB si cada registro pesa 24 bytes (el comentario de hash.c). UsarTablaHash la puede apagar. Se reserva en ini.c al arrancar.
| Valor ini | Bits | Cajones (aprox.) |
|---|---|---|
| 1 | 18 | 262.143 |
| 5 (defecto) | 22 | 4.194.303 · ~96 MB |
| 9 | 26 | 67.108.863 · ~1536 MB |
Qué archivos leer
| Archivo | Qué hay |
|---|---|
hash.c |
iniciarHash, agregarMovTablaHash, verificarTablaHash |
tipoDatos.h |
LLAVESHASH, REGISTRO_TABLA_HASH, HASH_EVAL |
macros.h |
Banderas; tamaños 18–26 bits; ES_REPETICION_TABLERO |
bitmma3.c / ini.c |
TamanioTablaHash; reserva de memoria |
El repositorio del motor: GitHub.
Cierre
Recordar no es jugar mejor por magia. Es no pagar dos veces el mismo trabajo. Zobrist etiqueta la casa; el cajón guarda precio, profundidad, mejor puerta y si el número es exacto, un suelo o un techo. Alfa-beta consulta al entrar y escribe al salir. La repetición usa la misma etiqueta para no seguir un bucle.
Encaja con lo anterior: los bitboards hacen barato generar; Negamax compara; la poda corta con una cota ya conocida. Lo que falta para que esa cota llegue pronto es el orden de las puertas. Eso es la siguiente entrada.
Correo de contacto: comprasmangocomputer@gmail.com
Comentarios
Publicar un comentario