Bitboards, operadores bitwise y engines de ajedrez

Bitboards, operadores bitwise y engines de ajedrez

“Eso de que el número de casillas del tablero de ajedrez sea una potencia de 2 tiene que ser aprovechable desde el punto de vista de la programación”

Un engine de ajedrez se compone de tres partes principales:

1. Un generador de movimientos
2. Una función de búsqueda que nos permite movernos por el árbol de variantes usando el output del generador de movimientos
3. Una función de evaluación que nos dé un criterio para asignar una puntuación a una posición

De modo que el primer paso es el generador de movimientos. Como una primera aproximación, el generador de movimientos se puede separar en:

1. GenMove: la función/es que, dada una cierta posición, crea la lista de movimientos posibles, y por otro lado
2. MakeMove: la función/es que recoge esa lista de movimientos y los ejecuta de hecho sobre el tablero

Por ejemplo, es habitual codificar un movimiento en un entero de 16 bits (en los 6 primeros se guarda la casilla inicial, en los 6 siguientes la casilla de destino y en el resto otro tipo de información, como por ejemplo si se trata o no de una captura). De modo que que nuestra función GenMove devolvería un array de enteros de 16 bits y de longitud el número de movimientos legales (suponiendo que nuestro generador de movimientos devolviera sólo movimientos, lo que suele ser habitual, pero no necesario). Luego la función MakeMove iría ejecutando estos movimientos uno a uno para moverse por el árbol de variantes.

A la hora de desarrollar un engine de ajedrez uno de las principales decisiones que se han de tomar es la de cómo representar la posición que tenemos en el tablero. Y en concreto, cómo representar la información sobre cada pieza.

Los bitboards son básicamente la representación de la información de la posición del tablero por medio de enteros de 64 bits. Por ejemplo, podemos usar un entero de 64 bits para representar la posición de los caballos blancos en la posición inicial, usando un bit por cada casilla; el bit que representa una casilla vale 0, y vale y 1 si en la casilla hay un caballo blanco:

n n

→

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0

Es decir, la posición inicial de los caballos blancos viene representada por el entero 1000010. O puesto en forma de entero de 64 bits:

00000000 00000000 00000000 00000000 00000000 00000000 00000000 01000010

y si ahora lo ordenamos convenientemente para que se asemeje a un tablero de ajedrez:

00000000

00000000

00000000

00000000

00000000

00000000

00000000

01000010

Evidentemente, habría que hacer lo mismo para cada pieza. De este modo, nuestro programa podría tener una clase/estructura Tablero, con los miembros peonesBlancos, caballosBlancos, etc. O podemos preferir guardar esta información en un array de enteros de 64 bits de dimensiones [2][6]: 2 bandos con 6 piezas diferentes cada uno.

Bien, hasta ahora, aparte de que hemos almacenado la información de la posición del tablero de una manera bastante compacta y económica (lo que por otro lado en los ordenadores actuales tampoco es de gran utilidad), no parece que hayamos hecho gran cosa, de modo que vamos a ver qué nos ofrece el uso de nuestros amigos los bitboards, en concreto en lo relacionado con la generación de movimientos.

Pongamos que tenemos la posición inicial y queremos saber a qué casillas se puede mover el caballo blanco de b1. En nuestro entero de 64 bits caballosBlancos tenemos la información sobre la posición de nuestros caballos, y queremos calcular los posibles destinos de esta pieza, que en principio serían las casillas a3, c3 y d2. Aquí nos podemos dar cuenta de una cosa; cuando un caballo blanco (o para el caso de cualquier color) se encuentra en la casilla b1, las casillas a las que potencialmente puede saltar son siempre las mismas: a3, c3 y d2, de modo que ¿por qué no crear un array de 64 enteros de 64 bits (al que podríamos llamar algo así como uint64 saltosCaballos[64]) que en cada elemento tenga un bitboard que represente las casillas a las que puede saltar un caballo desde dicha casilla? Es decir, el elemento que se corresponde con la casilla b1 (saltosCaballos[b1]) puesto en binario y bien ordenadito sería:

00000000

00000000

00000000

00000000

00000000

10100000

00010000

00000000

Excelente; ahora se presenta un problema. En la posición inicial, el caballo de b1 no puede saltar a d2, ya que ahí se encuentra un peón blanco (si fuera un peón negro no habría problema: el hecho de que se tratara de una captura en vez de un movimiento “normal”, de momento lo dejaríamos de lado: añadiríamos esta información en el entero de 16 bits que codifica el movimiento y luego el MakeMove se encargaría de gestionar esa información a la hora de hacer el movimiento sobre el tablero). Muy bien, ahora es cuando entran en juego nuestros amigos los operadores bitwise. Si generamos un entero de 64 bits (al que podríamos llamar piezasBlancas) en el que cada bit valga 1 si en la casilla que representa hay una pieza blanca y un cero en caso contrario, es decir, para la posición inicial:

00000000

00000000

00000000

00000000

00000000

00000000

11111111

11111111

entonces ya casi lo tenemos: sólo tenemos que hacer una operación AND a nivel de bits entre el bitboard saltosCaballos[b1] y el complementario del entero de 64 bits que hemos llamado piezasBlancas, que en jerga de operadores bitwise se obtendría como “~piezasBlancas” y tendría la pinta

11111111

11111111

11111111

11111111

11111111

11111111

00000000

00000000

Ahora sí que lo tenemos: si hacemos la operación saltosCaballos[c1] & (~piezasBlancas) obtendríamos las casillas a las que podría saltar un caballo en la posición inicial desde b1. Puesto en forma de binarios ordenaditos:

saltosCaballos[c1]	&	~piezasBlancas	=	casillasDestino
00000000 00000000 00000000 00000000 00000000 10100000 00010000 00000000	AND	11111111 11111111 11111111 11111111 11111111 11111111 00000000 00000000	EQUAL	00000000 00000000 00000000 00000000 00000000 10100000 00000000 00000000

Por cierto, en este momento puede ser interesante comentar que, por lo que dicen los sabios del lugar, una de las ventajas de trabajar con operaciones bitwise es que estas son ultra-rápidas.

Ahora debemos recordar que nuestra finalidad es la de crear una lista de movimientos, de modo que ahora tendríamos que ingeniárnoslas para, con la información obtenida en los pasos anteriores, crear dos movimientos que irían a nuestra lista de movimientos posibles para la posición actual:

1. La pieza que está en b1 se mueve a a3
2. La pieza que está en b1 se mueve a c3

Una pista: para esta parte de la generación de movimientos es necesario tener una función que encuentre el “least significant bit” de un entero. Pero esta es otra historia y, quizás, será contada en otro momento.

¿Y qué ocurre con el resto de las piezas?

Para el caso del movimiento de los reyes la cosa es prácticamente idéntica: simplemente se pueden mover a cualquier posición de destino con tal de que no esté ocupada por una pieza del mismo bando.

Con las denominadas “slide pieces”, la cosa se complica algo, ya que las reglas no son tan sencillas como para el caso de los caballos y los reyes, pero con ayuda de los operadores bitwise se acaba obteniendo un generador de movimientos muy rápido.

Hasta aquí sobre los bitboards en lo relacionado a la generación de movimientos, pero hay otra parte del diseño de un engine de ajedrez en la que estos animalitos son la mar de útiles: la evaluación.

Los bitboards son una manera muy manejable de almacenar la información de lo que tenemos en el tablero, y además las operaciones lógicas con operadores bitwise son muy rápidas. Esto nos permite responder con una gran eficiencia a preguntas tales como “¿está esta torre en una columna abierta?”, “¿este es un peón pasado?”, “¿tiene el blanco peones en e4 y d4?”.

Hay que tener en cuenta que una vez que tenemos un engine de ajedrez funcionando, el 99% del tiempo de cpu se gasta en la función de evaluación, de modo que el uso de bitboards mata dos pájaros de un tiro: nos proporciona un generador de movimientos muy rápido (que evidentemente es el primer cuello de botella a la hora de desarrollar un engine: lo más rápido a lo que puede “ir” nuestro engine está limitado por la velocidad a la que puede hacer movimientos sin evaluación), y nos da una estructura de datos que nos permite llevar a cabo operaciones muy rápidas en la función de evaluación.