Cap. 3 - Sesenta y cuatro interruptores
cap. 3 Bitboards · Motor 2012
Sesenta y cuatro interruptores
Cuando un motor de ajedrez «piensa», no contempla una sola partida. Recorre un árbol: cada jugada legal abre ramas, cada rama abre más, hasta llegar a posiciones hoja donde ya no busca y solo evalúa. Quien genera esas jugadas con lentitud se queda cerca de la raíz. Quien las genera con rapidez llega más lejos en el mismo segundo.
En 2012 elegí representar el tablero con bitboards: números de 64 bits y aritmética binaria. No fue un capricho de estilo. Fue la base para que generarTodosMov() alimentara el árbol de alfabetaNegado() lo bastante rápido como para profundizar. Este artículo explica qué es eso, empezando por el interruptor más pequeño que conoce una computadora: el bit.
Qué es un bit
Un bit es la unidad mínima de información. Solo admite dos estados: apagado o encendido, no o sí, 0 o 1. No hay un «un poco». Es el interruptor de una lámpara.
Toda la informática se construye apilando esos interruptores. Ocho bits forman un byte, suficiente para una letra. Con más bits caben números más grandes. Un entero de 64 bits es una fila de sesenta y cuatro interruptores. La computadora puede leerlos y combinarlos de una sola vez, como quien pulsa un panel entero y no cada tecla por separado.
El ajedrez tiene sesenta y cuatro escaques. Esa coincidencia no es magia, pero sí una invitación: un número de 64 bits puede ser un mapa del tablero, un interruptor por casilla.
El tablero como un edificio de ventanas
Imagine un edificio de ocho pisos y ocho ventanas por piso. Cada ventana tiene una luz. Si la luz está encendida, en esa casilla hay «algo»; si está apagada, está vacía. Un bitboard es exactamente ese plano de luces. No dibuja caballos ni torres: solo dice dónde hay presencia.
En Mango AC el bit 0 es a1, el 7 es h1, el 8 es a2, y así hasta h8. Es el orden de NUM2ALG en data.h. Encender la casilla e2 es poner a 1 el bit 12. Eso lo hace la tabla BITSET[64]: cada entrada es un 1 desplazado a su ventana.
Un solo mapa no basta. Hace falta uno de peones blancos, otro de caballos negros, otro de todas las piezas blancas juntas. La estructura BITTABLERO en tipoDatos.h guarda eso:
uint64 tablero[2][6]; /* color × tipo de pieza */ uint64 blancos; /* unión de las blancas */ uint64 negros; /* unión de las negras */ uint64 ocupados; /* blancas o negras */ uint64 desOcupados; /* el negativo: vacías */ uint64 destinos; /* adonde sí se puede ir */
tablero[BLANCO][PEON] es el plano de luces de los peones blancos. blancos es el OR de peón, caballo, alfil, torre, dama y rey de ese bando: todas las ventanas blancas encendidas a la vez. ocupados une ambos bandos. desOcupados es el complemento: ~ocupados, el negativo fotográfico.
Aritmética de bits, con analogías
La ventaja no está en guardar el tablero. Está en preguntarle cosas al mapa con operaciones que la CPU ya sabe hacer en un ciclo.
| Operación | En el tablero | En la vida |
|---|---|---|
AND & |
Casillas que cumplen las dos condiciones | Superponer dos acetatos: solo se ve donde ambos tienen tinta |
OR | |
Unión de dos conjuntos de casillas | Encender luces si cualquiera de dos interruptores está arriba |
NOT ~ |
Casillas vacías a partir de las ocupadas | El negativo de una fotografía |
XOR ^ |
Encender o apagar una casilla concreta | Un interruptor de pasillo: cada pulso invierte el estado |
shift << >> |
Deslizar todo el mapa un paso (un peón que avanza) | Correr una plantilla de papel un piso hacia arriba |
Un ejemplo concreto. Los destinos legales no son las 64 casillas: son las vacías o las del rival. En generarTodosMov() lo escribo así:
juego.desOcupados = ~juego.ocupados; juego.destinos = juego.desOcupados | juego.negros; /* si mueven blancas */
Una sola operación OR descarta las casillas propias. No hay un bucle «para cada escaque, ¿hay una pieza mía?». El panel entero responde a la vez.
Generar movimientos sin recorrer el tablero a ciegas
El método ingenuo sería: para i de 0 a 63, si hay una pieza, probar a dónde puede ir. Sesenta y cuatro visitas, la mayoría a casillas vacías. En un árbol se hace millones de veces. Es como abrir las 64 ventanas del edificio para ver cuáles tienen luz.
Con bitboards solo visito las luces encendidas. En operacionesBit.c, bitScanForwardBruijn() encuentra el bit a 1 de menor peso: la primera ventana iluminada. Luego bb &= bb-1 (o un XOR con BITSET[casilla]) apaga esa luz y paso a la siguiente. convertir2lista() hace exactamente eso: del mapa a una lista de índices 0–63.
El patrón de ajedrez.c es siempre el mismo. Tomo el mapa de una pieza, recorro orígenes, calculo destinos con una máscara, recorro destinos, empaqueto el movimiento:
tempOrigenes = juego.tablero[BLANCO][CABALLO];
while (tempOrigenes) {
escaqueOrigen = bitScanForwardBruijn(tempOrigenes);
tempDestinos = genCaballoAtaqueTablero(escaqueOrigen, juego);
/* … empaquetar cada destino en Buffer_MOV … */
tempOrigenes ^= BITSET[escaqueOrigen];
}
Si hay dos caballos, el bucle da dos vueltas. Las 62 casillas vacías no existen para el generador.
Piezas que saltan: caballo y rey
Un caballo no se detiene contra un obstáculo: salta. Puedo precalcular, para cada casilla, el mapa de destinos posibles en un tablero vacío (mascaraCaballo[64]). En tiempo de juego basta un AND con destinos:
#define genCaballoAtaqueTablero(escaque, t) (mascaraCaballo[escaque] & t.destinos) #define genReyAtaqueTablero(escaque, t) (mascaraRey[escaque] & t.destinos)
Es como tener, en cada habitación, un sello de goma con la silueta del salto. Lo estampo y recorto lo que cae sobre mis propias piezas. Una instrucción AND. En macros.h esas líneas se llaman «movimientos más rápidos».
El peón: deslizar la plantilla
El peón avanza hacia adelante y captura en diagonal. El avance es un desplazamiento del mapa sobre casillas vacías; la captura es otra máscara AND con las piezas enemigas. Si el peón negro está en la séptima fila, un segundo shift añade el avance doble. La promoción y el al paso se cuelgan de esas mismas máscaras. Otra vez: no pregunto casilla por casilla; deslizo y recorto.
Piezas que se deslizan: magic bitboards
Torre, alfil y dama se detienen en el primer obstáculo. El mapa de destinos depende de quién está sentado en el pasillo. Recorrer el pasillo paso a paso sería otra vez el método ingenuo.
La analogía útil es un pasillo de hotel. No me interesa el nombre de cada huésped: me interesa el patrón de puertas ocupadas. Ese patrón, multiplicado por una constante «mágica» y recortado a unos pocos bits, se convierte en el índice de una tabla que ya calculé al iniciar. La tabla responde: «con este amueblado, estas son las puertas alcanzables».
En el código, para una columna:
((ocupados & FILEMASK[casilla]) * FILEMAGIC[casilla]) >> 57
El AND extrae solo el pasillo. La multiplicación por FILEMAGIC compacta esa ocupación. El desplazamiento 57 deja un índice pequeño. Se consulta FILE_ATTACKS. Lo mismo en filas (RANK_ATTACKS) y en las dos diagonales (DIAGA8H1MAGIC, DIAGA1H8MAGIC). La dama es torre OR alfil. Eso vive en macros.h y se inicializa en ini.c / data.h.
No inventé los magic bitboards en 2012; los estudié en Chess Programming Wiki y en el motor Winglet, y los dejé como el mecanismo de las piezas deslizantes. El núcleo de búsqueda sigue usando esas macros hoy.
Del movimiento al árbol
Generar movimientos no es el juego. Es el combustible del juego. En cada nudo de alfabetaNegado() (busquedad.c) ocurre esto:
juego.Buffer_MOV_INDEXCAPAS[capa+1] =
generarTodosMov(juego.Buffer_MOV_INDEXCAPAS[capa]);
/* ordenar, hacer, comprobar jaque, buscar el hijo, deshacer */
El motor produce pseudo-legales (el rey podría quedar en jaque). La legalidad se filtra al hacer y deshacer, con esAtacadoPor() sobre el bitboard del rey. Perft (perft.c) cuenta ese árbol sin evaluar: sirve para validar el generador. Si Perft está bien, el árbol que recorre la búsqueda parte de una base sólida.
Aquí encaja la justificación. Alfa-beta, las podas y las tablas hash reducen ramas. Pero cada nudo que sí se visita pide una lista de jugadas. Si esa lista sale de aritmética de 64 bits, el coste por nudo baja. Con el mismo presupuesto de tiempo se visitan más nudos. Más nudos son más plies. Más plies son hojas más profundas: el motor deja de buscar más lejos de la posición que el oponente ve en el tablero. El techo de profundidad en Mango AC es 24 capas (MAX_CAPAS_BUSQUEDAD). Llegar cerca de ese techo en partida viva depende, entre otras cosas, de que el generador no sea el cuello de botella.
Contar bits también es barato: cuentaBit() usa el algoritmo HAKMEM, agrupando luces de dos en dos, de cuatro en cuatro, hasta el total. Sirve para material insuficiente, alfiles del mismo color, población de peones. Otra vez el panel entero, no un recuento casilla a casilla.
Qué archivos leer en el código
| Archivo | Qué hay |
|---|---|
tipoDatos.h |
uint64, estructura BITTABLERO |
operacionesBit.c |
Bitscan de Bruijn, cuentaBit, imprimir el mapa |
ajedrez.c |
generarTodosMov(): peón, torre, caballo, alfil, dama, rey |
macros.h |
Magic bitboards, destinos, empaquetado de 28 bits del movimiento |
data.h / ini.c |
BITSET, máscaras, magics, tablas de ataque |
busquedad.c / perft.c |
El árbol que consume esa lista de jugadas |
El repositorio del motor: GitHub.
Cierre
Un bit es un interruptor. Sesenta y cuatro interruptores son un tablero. AND, OR y un desplazamiento son preguntas al tablero entero. Magic bitboards son el índice de un pasillo ya memorizado. Junto, eso convierte la generación de jugadas en aritmética, no en un paseo por 64 casillas. Y esa aritmética es lo que permite, en el mismo reloj, bajar más peldaños del árbol hasta las hojas.
El estilo de juego de Mango AC sigue siendo el de 2012. El bitboard es parte de ese estilo: no lo reescribí. Sigue siendo la forma en que el motor ve el mundo.
Correo de contacto: comprasmangocomputer@gmail.com
Comentarios
Publicar un comentario