Un tablero de bits es una estructura de datos de matriz de bits especializada que se usa comúnmente en sistemas informáticos que juegan juegos de mesa , donde cada bit corresponde a un espacio o pieza del tablero de juego. Esto permite operaciones bit a bit paralelas para establecer o consultar el estado del juego, o determinar movimientos o jugadas en el juego.
Los bits en el mismo tablero de bits se relacionan entre sí según las reglas del juego, y a menudo forman una posición de juego cuando se toman en conjunto. Otros bitboards se utilizan comúnmente como máscaras para transformar o responder consultas sobre posiciones. Los tableros de bits son aplicables a cualquier juego cuyo progreso esté representado por el estado o la presencia de piezas en espacios discretos de un tablero de juego, mediante el mapeo de los estados del espacio a bits en la estructura de datos. Los bitboards son una representación de tablero alternativa más eficiente a la representación tradicional de buzón , donde cada pieza o espacio en el tablero es un elemento de matriz.
Los tableros de bits son especialmente efectivos cuando los bits asociados de varios estados relacionados en el tablero encajan en una sola palabra o palabra doble de la arquitectura de la CPU, de modo que los operadores de un solo bit como AND y OR se pueden usar para construir o consultar estados del juego.
Entre las implementaciones de juegos de computadora que utilizan bitboards se encuentran el ajedrez , las damas , el otelo y los juegos de palabras . El esquema se empleó por primera vez en programas de damas en la década de 1950, y desde mediados de la década de 1970 ha sido el estándar de facto para la representación de tableros de juego en autómatas informáticos.
Un bitboard, un campo de bits especializado, es un formato que empaqueta múltiples variables booleanas relacionadas en la misma palabra de máquina, que generalmente representa una posición en un juego de mesa o el estado de un juego. Cada bit representa un espacio; cuando el bit es positivo, una propiedad de ese espacio es verdadera. Los Bitboards permiten que la computadora responda algunas preguntas sobre el estado del juego con una operación bit a bit. Por ejemplo, si un programa de ajedrez quiere saber si el jugador blanco tiene algún peón en el centro del tablero (cuatro casillas centrales), puede simplemente comparar un tablero de bits para los peones del jugador con uno para el centro del tablero usando un comando AND bit a bit. operación. Si no hay peones centrales, el resultado será todos bits cero (es decir, igual a cero). Varios tableros de bits pueden representar diferentes propiedades de los espacios sobre el tablero, y los tableros de bits especiales o temporales (como variables temporales) pueden representar propiedades locales o contener resultados intercalados intermedios.
La eficacia de los bitboards se ve aumentada por otras dos propiedades de la implementación. En primer lugar, los tableros de bits se actualizan rápidamente de forma incremental, como por ejemplo volteando los bits en las posiciones de origen y destino en un tablero de bits para la ubicación de la pieza cuando se mueve una pieza. En segundo lugar, los mapas de bits que representan propiedades estáticas, como todos los espacios atacados por cada tipo de pieza para cada posición en un tablero de ajedrez, se pueden cotejar previamente y almacenar en una tabla, de modo que responder a una pregunta como "¿cuáles son los movimientos legales de un caballo en el espacio e4? " puede responderse mediante una única búsqueda de memoria.
Las implementaciones de Bitfield aprovechan la presencia de operaciones lógicas bit a bit de palabra completa (32 bits o 64 bits) como AND, OR, NOT y otras en arquitecturas de CPU modernas para ser eficientes. Es posible que los Bitboards no sean efectivos en arquitecturas de microprocesadores y minicomputadoras anteriores de 8 y 16 bits.
Como resultado de la necesaria compresión y codificación del contenido de tablas masivas y la probabilidad de errores de transcripción o codificación, los programas bitboard son tediosos para los desarrolladores de software, ya sea escribirlos o depurarlos. Generalmente se requieren métodos generativos auxiliares que no forman parte de la aplicación para construir las tablas.
Las representaciones de Bitboard utilizan operaciones bit a bit paralelas disponibles en casi todas las CPU que se completan en un ciclo y están completamente canalizadas y almacenadas en caché, etc. Casi todas las CPU tienen AND , OR , NOR y XOR . Además, las CPU modernas tienen canales de instrucciones que ponen en cola las instrucciones para su ejecución. Un procesador con múltiples unidades de ejecución puede realizar más de una instrucción por ciclo si hay más de una instrucción disponible en proceso. Las secuencias de instrucciones normales con bifurcaciones pueden hacer que la canalización se vacíe si se predice erróneamente una bifurcación. Muchas operaciones de bitboard requieren menos condicionales y, por lo tanto, aumentan la canalización y hacen un uso eficaz de múltiples unidades de ejecución en muchas CPU.
Las CPU tienen un ancho de bits para el cual están diseñadas y pueden realizar operaciones bit a bit en un ciclo en este ancho. Entonces, en una CPU de 64 bits o más, las operaciones de 64 bits pueden ocurrir en una instrucción. Puede haber soporte para instrucciones de mayor o menor ancho. Muchas CPU de 32 bits pueden tener algunas instrucciones de 64 bits y éstas pueden tardar más de un ciclo o tener desventajas en comparación con sus instrucciones de 32 bits.
Si el bitboard es mayor que el ancho del conjunto de instrucciones, se necesitarán varias instrucciones para realizar una operación de ancho completo en él. Por lo tanto, un programa que utilice bitboards de 64 bits se ejecutará más rápido en un procesador de 64 bits que en uno de 32 bits.
Las representaciones de Bitboard tienen un código mucho más largo, tanto fuente como objeto. Las secuencias largas de bits son técnicamente difíciles de escribir y depurar. Los propios bitboards son escasos y a veces contienen solo un bit de cada 64, por lo que las implementaciones de bitboard consumen mucha memoria. Ambos problemas pueden aumentar los errores de caché o provocar una destrucción de caché.
Si el procesador no tiene instrucciones de hardware para 'el primero' (o ' contar ceros a la izquierda ') y ' contar unos ' (o 'contar ceros'), la implementación se verá significativamente perjudicada, ya que estas operaciones son extremadamente ineficientes para codificar como bucles en lenguaje ensamblador.
Los bitboards requieren más memoria que las estructuras de datos de los tableros de lista de piezas, pero son más eficientes en su ejecución porque muchas operaciones de bucle y comparación se reducen a una única (o una pequeña cantidad de) operaciones bit a bit. Por ejemplo, en el buzón, determinar si una pieza ataca el espacio requiere generar y recorrer movimientos legales de pieza y comparar el espacio final con el espacio . Con los tableros de bits, los movimientos legales de la pieza se almacenan en un mapa de bits, y ese mapa se combina con el mapa de bits para el espacio . Un resultado distinto de cero significa que la pieza ataca el espacio .
Para algunos juegos, escribir un motor bitboard requiere una buena cantidad de código fuente, incluidas tablas de datos que serán más largas que la implementación compacta de buzón/enumeración. Para dispositivos móviles (como teléfonos móviles) con un número limitado de registros o caché de instrucciones del procesador, esto puede causar un problema. Para computadoras de tamaño completo, puede causar errores de caché entre el nivel uno y el nivel dos. Esto es sólo un problema potencial, no un inconveniente importante, ya que la mayoría de las máquinas tendrán suficiente caché de instrucciones para que esto no sea un problema.
Algunos tipos de tableros de bits se derivan de otros mediante un elaborado proceso de correlación cruzada, como los mapas de ataque en el ajedrez. Reformar todos estos mapas en cada cambio de estado del juego (como un movimiento) puede resultar prohibitivamente caro, por lo que los mapas de bits derivados se actualizan de forma incremental, un proceso que requiere un código complejo y preciso. Esto es mucho más rápido de ejecutar, porque sólo es necesario cambiar los mapas de bits asociados con espacios modificados, no todos los mapas de bits del tablero. Sin una actualización incremental, la representación en mapa de bits puede no ser más eficiente que la representación de buzón anterior, donde la actualización es intrínsecamente local e incremental.
Algunos tipos de mapas de bits que no dependen de las configuraciones del tablero se pueden precalcular y recuperar mediante una búsqueda en la tabla en lugar de cotejar después de un movimiento o cambio de estado del tablero, como los espacios atacados por un caballo o un rey ubicados en cada uno de los 64 espacios de un tablero de ajedrez que de otro modo requeriría una enumeración.
La representación obvia y más simple de la configuración de las piezas en un tablero de ajedrez es como una lista (matriz) de piezas en un orden conveniente para la búsqueda (como de menor a mayor en valor) que asigna cada pieza a su ubicación en el tablero. De manera análoga, cotejar los espacios atacados por cada pieza requiere una enumeración en serie de dichos espacios para una pieza. Este esquema se llama direccionamiento de buzones . Se mantienen listas separadas para piezas blancas y negras y, a menudo, para peones blancos y negros. Los mapas se actualizan en cada movimiento, lo que requiere una búsqueda lineal (o dos si se capturó una pieza) a través de la lista de piezas. La ventaja del buzón es el código simple; la desventaja es que las búsquedas lineales son lentas. Las estructuras de datos más rápidas, pero más elaboradas, que asignan piezas a ubicaciones se denominan bitboards .
En las representaciones de tablero de bits, cada bit de una palabra de 64 bits (o palabra doble en arquitecturas de 32 bits) está asociado con un cuadrado del tablero de ajedrez. Se puede utilizar cualquier mapeo de bits a cuadrados, pero por convención amplia, los bits están asociados con cuadrados de izquierda a derecha y de abajo hacia arriba, de modo que el bit 0 representa el cuadrado a1, el bit 7 es el cuadrado h1, el bit 56 es el cuadrado a8 y el bit 56 es el cuadrado a8. 63 es el cuadrado h8.
Muchas configuraciones diferentes del tablero generalmente están representadas por sus propios tableros de bits, incluidas las ubicaciones de los reyes, todos los peones blancos, todos los peones negros, así como tableros de bits para cada uno de los otros tipos de piezas o combinaciones de piezas como todas las piezas blancas. Dos tableros de bits de ataque también son universales: un tablero de bits por cuadrado para todas las piezas que atacan el cuadrado, y el tablero de bits inverso para todos los cuadrados atacados por una pieza por cada cuadrado que contiene una pieza. Los tableros de bits también pueden ser constantes, como uno que representa la primera fila, que tendría un bit en las posiciones 0 - 7. Otros tableros de bits locales o de transición como "todos los espacios adyacentes al rey atacados por piezas opuestas" pueden cotejarse según sea necesario o conveniente. [1]
Un ejemplo del uso de los tableros de bits sería determinar si una pieza está en premio : los tableros de bits para "todas las piezas amigas que protegen el espacio " y "todas las piezas opuestas que atacan el espacio " permitirían hacer coincidir las piezas para determinar fácilmente si una pieza objetivo en el espacio está en premio .
Uno de los inconvenientes de los bitboards estándar es cotejar los vectores de ataque de las piezas deslizantes (torre, alfil, reina), porque tienen un número indefinido de espacios de ataque dependiendo de otros espacios ocupados. Esto requiere varias secuencias largas de máscaras, turnos y complementos por pieza.
Teniendo en cuenta el tamaño del código y la complejidad informática de generar tableros de bits para los vectores de ataque de piezas deslizantes, se han ideado estructuras de datos de tableros de bits alternativos para cotejarlos. Las representaciones en el tablero de bits de caballos, reyes, peones y otras configuraciones del tablero no se ven afectadas por el uso de tableros de bits auxiliares para las piezas deslizantes.
Los tableros de bits rotados son estructuras de datos de tableros de bits complementarias que permiten tabularizar los vectores de ataque de piezas deslizantes, uno para los vectores de ataque de archivos de las torres y uno para los vectores de ataque diagonal y antidiagonal de los alfiles (los ataques de rango de las torres se pueden indexar a partir de tableros de bits estándar). . Con estos bitboards, una única búsqueda en una tabla reemplaza largas secuencias de operaciones bit a bit.
Estos bitboards rotan la configuración de ocupación del tablero 90 grados, 45 grados y/o 315 grados. Un bitboard estándar tendrá un byte por rango del tablero de ajedrez. Con este bitboard es fácil determinar los ataques de las torres en una fila, usando una tabla indexada por la casilla ocupada y las posiciones ocupadas en la fila (porque los ataques de las torres se detienen en la primera casilla ocupada). Al girar el tablero de bits 90 grados, los ataques de las torres hacia arriba y hacia abajo en una columna se pueden examinar de la misma manera. Agregar tableros de bits girados 45 grados y 315 grados (-45 grados) produce tableros de bits en los que las diagonales son fáciles de examinar. La dama puede ser examinada combinando ataques de torre y alfil. En realidad, rotar un bitboard es una transformación poco elegante que puede requerir docenas de instrucciones. [2] [3]
Los vectores de ataque de las bases de las torres y los vectores de ataque diagonal y antidiagonal de los alfiles pueden enmascararse por separado y usarse como índices en una tabla hash de vectores de ataque precalculados dependiendo de la ocupación, de 8 bits cada uno para las torres y de 2 a 8 bits. cada uno para los obispos. El vector de ataque completo de una pieza se obtiene como la unión de cada uno de los dos vectores unidireccionales indexados a partir de la tabla hash. El número de entradas en la tabla hash es modesto, del orden de 8*2^8 o 2K bytes, pero se requieren dos cálculos de función hash y dos búsquedas por pieza. [4] consulte el esquema de hash empleado. [5]
Los tableros de bits mágicos son una extrapolación de la compensación tiempo-espacio de la búsqueda directa de vectores de ataque. Estos utilizan una transmutación del vector de ataque completo como índice en la tabla hash. Magia es un nombre inapropiado y simplemente se refiere a la generación y uso de una función hash perfecta junto con trucos para reducir el tamaño potencial de la tabla hash que tendría que almacenarse en la memoria, que es 8*2^64 o 144 exabytes . . [nb 1] La primera observación es que las casillas exteriores o las filas primera y octava junto con las filas 'a' y 'h' son irrelevantes para la ocupación del vector de ataque: la pieza ataca esas casillas o no (dependiendo de otras opciones de bloqueo). piezas) independientemente de la ocupación, por lo que se pueden eliminar de la consideración, dejando solo 6x6 o 36 cuadrados (~bits en la función hash correspondiente). Al igual que con otros esquemas que requieren una función hash perfecta, es necesario un proceso exhaustivo de enumeración, en parte algorítmico y en parte prueba y error, para generar la función hash. Pero el problema intratable persiste: estas son tablas muy activas y su tamaño (menos de un millón de entradas en la mayoría de los casos) es enorme en relación con los tamaños de caché de nivel inferior de las arquitecturas de chips modernas, lo que resulta en una inundación de caché. Por lo tanto, los tableros de bits mágicos en muchas aplicaciones no proporcionan ninguna ganancia de rendimiento en comparación con esquemas de hash más modestos o tableros de bits rotados. [6] [7]
El método bitboard para representar un juego de mesa parece haber sido inventado a mediados de la década de 1950 por Arthur Samuel y se utilizó en su programa de damas. [8] Para el juego de ajedrez más complicado, parece que el método fue redescubierto independientemente más tarde por el equipo Kaissa en la Unión Soviética a finales de los años 1960, [9] y nuevamente por los autores del programa " Chess " de la Universidad Northwestern de Estados Unidos en principios de los años 1970. La longitud de palabra de 64 bits de las supercomputadoras de la década de 1970, como las máquinas Amdahl y Cray, facilitó el desarrollo de representaciones de tablero de bits que asignaban convenientemente los 64 cuadrados del tablero de ajedrez a bits de una palabra.
Los tableros de bits rotados para cotejar los movimientos de las piezas deslizantes fueron inventados por el profesor Robert Hyatt, autor de los motores de ajedrez Cray Blitz y Crafty, en algún momento a mediados de la década de 1990 y los compartió con el equipo de programación de Dark Thought. Posteriormente se implementaron en Crafty y Dark Thought, pero la primera descripción publicada no fue hasta 1997.
Una década más tarde, se introdujeron métodos de búsqueda directa que utilizan rangos, archivos y diagonales enmascarados para indexar una tabla de vectores de ataque según los estados de ocupación de los bits bajo la máscara. Uno de esos esquemas que utiliza una función hash perfecta para eliminar colisiones hash se denominó "tableros de bits mágicos". No obstante, el gran tamaño y las altas tasas de acceso de dichas tablas causaron problemas de ocupación de memoria y contención de caché, y no eran necesariamente más eficaces que el enfoque del tablero de bits rotado. Hoy en día, los programas de juegos siguen divididos y el mejor esquema depende de la aplicación.
Muchos otros juegos además del ajedrez se benefician de los bitboards.
Llámelo Bitboards de jardín de infantes