Un bitboard es una estructura de datos de matriz de bits especializada que se utiliza comúnmente en sistemas informáticos que ejecutan juegos de mesa , donde cada bit corresponde a un espacio o pieza del tablero de juego. Esto permite realizar operaciones paralelas bit a bit para establecer o consultar el estado del juego o determinar movimientos o jugadas en el juego.
Los bits de un mismo tablero se relacionan entre sí mediante las reglas del juego y, cuando se toman juntos, suelen formar una posición de juego. Otros tableros se utilizan habitualmente como máscaras para transformar o responder a consultas sobre posiciones. Los tableros se pueden aplicar a cualquier juego cuyo progreso esté representado por el estado o la presencia de piezas en espacios discretos de un tablero, mediante la asignación de los estados de los espacios a bits en la estructura de datos. Los tableros son una representación alternativa más eficiente del tablero que la representación tradicional de buzón , en la que cada pieza o espacio del 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 tableros de bits se encuentran el ajedrez , las damas , 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 de computadora.
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 tablero de juego 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 peones en el centro del tablero (cuatro casillas centrales), puede simplemente comparar un bitboard para los peones del jugador con uno para el centro del tablero utilizando una operación AND bit a bit. Si no hay peones centrales, entonces el resultado serán todos bits cero (es decir, igual a cero). Múltiples bitboards pueden representar diferentes propiedades de espacios sobre el tablero, y bitboards especiales o temporales (como variables temporales) pueden representar propiedades locales o contener resultados intermedios cotejados.
La eficacia de los tableros de bits 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, al invertir los bits en las posiciones de origen y destino de un tablero de bits para la ubicación de las piezas 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 recopilar previamente y almacenar en una tabla, de modo que la respuesta a una pregunta como "¿cuáles son los movimientos legales de un caballo en el espacio e4?" se puede responder con una única búsqueda de memoria.
Las implementaciones de campos de bits aprovechan la presencia de operaciones lógicas de palabra completa (32 bits o 64 bits) como AND, OR, NOT y otras en las arquitecturas de CPU modernas para ser eficientes. Los tableros de bits pueden no ser efectivos en arquitecturas de microprocesadores y minicomputadoras de 8 y 16 bits anteriores.
Como resultado de la compresión y codificación necesarias del contenido de tablas masivas y la probabilidad de errores de transcripción o codificación, los programas de bitboard resultan tediosos para los desarrolladores de software, ya sea para escribirlos o para depurarlos. Por lo general, se requieren métodos generativos auxiliares que no forman parte de la aplicación para crear las tablas.
Las representaciones de bitboard utilizan operaciones paralelas bit a bit 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 canalizaciones 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 la canalización. Las secuencias de instrucciones normales con ramificaciones pueden hacer que la canalización se vacíe si se predice incorrectamente una ramificación. Muchas operaciones de bitboard requieren menos condicionales y, por lo tanto, aumentan la canalización y hacen un uso efectivo 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 dentro de este ancho. Por lo tanto, 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 ancho mayor o menor. Muchas CPU de 32 bits pueden tener algunas instrucciones de 64 bits y estas pueden tomar más de un ciclo o estar limitadas en comparación con sus instrucciones de 32 bits.
Si el bitboard es más grande 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 el código fuente como el código objeto. Las secuencias largas de manipulación de bits son técnicamente difíciles de escribir y depurar. Los bitboards en sí mismos son dispersos, a veces contienen solo un bit en 64, por lo que las implementaciones de bitboard consumen mucha memoria. Ambos problemas pueden aumentar los errores de caché o causar una sobrecarga de caché.
Si el procesador no tiene instrucciones de hardware para 'primer uno' (o ' contar ceros iniciales ') y ' contar unos ' (o 'contar ceros'), la implementación se verá significativamente perjudicada, ya que estas operaciones son extremadamente ineficientes para codificar como bucles de lenguaje ensamblador.
Los tableros de bits requieren más memoria que las estructuras de datos de tableros de lista de piezas, pero son más eficientes en la ejecución porque muchas operaciones de bucle y comparación se reducen a una sola operación (o una pequeña cantidad de) bit a bit. Por ejemplo, en el buzón, determinar si la pieza ataca el espacio requiere generar y recorrer los movimientos legales de la 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 de 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 celulares) con una cantidad limitada 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 solo 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 ajedrez. Reformar todos estos mapas en cada cambio de estado del juego (como un movimiento) puede ser prohibitivamente costoso, por lo que los mapas de bits derivados se actualizan de forma incremental, un proceso que requiere un código intrincado y preciso. Esto es mucho más rápido de ejecutar, porque solo los mapas de bits asociados con los espacios modificados, no todos los mapas de bits del tablero, necesitan cambiar. Sin una actualización incremental, la representación en mapas de bits puede no ser más eficiente que la antigua representación de buzón, 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 calcular previamente y recuperar mediante una búsqueda en la tabla en lugar de cotejarlos 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ían 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 que se puede buscar fácilmente (como de menor a mayor valor) que asigna cada pieza a su ubicación en el tablero. Análogamente, cotejar los espacios atacados por cada pieza requiere una enumeración serial de dichos espacios para una pieza. Este esquema se llama direccionamiento de buzón . 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 ajedrez, 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 asignación de bits a cuadrados, pero por convención general, los bits se asocian con cuadrados de izquierda a derecha y de abajo a 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 63 es el cuadrado h8.
Muchas configuraciones diferentes del tablero suelen estar representadas por sus propios tableros de bits, incluyendo las ubicaciones de los reyes, todos los peones blancos, todos los peones negros, así como los 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 casilla para todas las piezas que atacan la casilla, y el tablero de bits inverso para todas las casillas atacadas por una pieza por cada casilla 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 captura : los tableros de bits para "todas las piezas amigas protegiendo el espacio " y "todas las piezas oponentes atacando el espacio " permitirían unir las piezas para determinar fácilmente si una pieza objetivo en el espacio está en captura .
Una de las desventajas de los tableros de bits estándar es la recopilación de los vectores de ataque de las piezas que se desplazan (torre, alfil, dama), ya que tienen un número indefinido de espacios de ataque en función de otros espacios ocupados. Esto requiere varias secuencias largas de máscaras, desplazamientos y complementos por pieza.
En reconocimiento del tamaño del código y la complejidad computacional que implica generar tableros de bits para los vectores de ataque de las piezas deslizantes, se han diseñado estructuras de datos de tableros de bits alternativos para cotejarlos. Las representaciones de tableros de bits de caballos, reyes, peones y otras configuraciones de tablero no se ven afectadas por el uso de tableros de bits auxiliares para las piezas deslizantes.
Los bitboards rotados son estructuras de datos complementarias que permiten tabularizar los vectores de ataque de las piezas deslizantes, uno para los vectores de ataque de las torres en fila y otro para los vectores de ataque diagonal y antidiagonal de los alfiles (los ataques de rango de las torres se pueden indexar desde los bitboards estándar). Con estos bitboards, una única búsqueda en la tabla reemplaza largas secuencias de operaciones bit a bit.
Estos tableros rotan la configuración de ocupación del tablero en 90, 45 y/o 315 grados. Un tablero estándar tendrá un byte por fila del tablero de ajedrez. Con este tablero es fácil determinar los ataques de torres a lo largo de una fila, utilizando una tabla indexada por la casilla ocupada y las posiciones ocupadas en la fila (porque los ataques de torres se detienen en la primera casilla ocupada). Al rotar el tablero 90 grados, los ataques de torres hacia arriba y hacia abajo en una columna se pueden examinar de la misma manera. Agregar tableros rotados 45 y 315 grados (-45 grados) produce tableros en los que las diagonales son fáciles de examinar. La reina se puede examinar combinando los ataques de torre y alfil. En realidad, rotar un tablero es una transformación poco elegante que puede requerir docenas de instrucciones. [2] [3]
Los vectores de ataque de fila y fila de las torres y los vectores de ataque diagonal y antidiagonal de los alfiles se pueden enmascarar por separado y utilizar como índices en una tabla hash de vectores de ataque precalculados según la ocupación, de 8 bits cada uno para las torres y de 2 a 8 bits cada uno para los alfiles. 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] vea el esquema hash empleado. [5]
Los bitboards mágicos son una extrapolación del equilibrio espacio-temporal de la búsqueda directa de vectores de ataque mediante hash. Estos utilizan una transmutación del vector de ataque completo como índice en la tabla hash. Mágico 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 de 8*2^64 o 144 exabytes . [nb 1] La primera observación es que los cuadrados exteriores o el primer y octavo rango junto con los archivos 'a' y 'h' son irrelevantes para la ocupación del vector de ataque: la pieza ataca esos cuadrados o no (dependiendo de otras piezas bloqueadoras) independientemente de la ocupación, por lo que estos pueden eliminarse 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 exhaustivo proceso de enumeración, en parte algorítmico y en parte de prueba y error, para generar la función hash. Pero el problema sigue siendo insoluble: se trata de 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 da lugar a una inundación de caché. Por lo tanto, en muchas aplicaciones, las placas de bits mágicas no proporcionan ninguna mejora de rendimiento en comparación con esquemas de hash más modestos o placas de bits rotadas. [6] [7]
El método del tablero de bits 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 más complicado de ajedrez, parece que el método fue redescubierto independientemente más tarde por el equipo de Kaissa en la Unión Soviética a fines de la década de 1960, [9] y nuevamente por los autores del programa " Chess " de la Universidad Northwestern de EE. UU. a principios de la década de 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 mapeaban 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 de mediados de la década de 1990 y compartidos con el equipo de programación de Dark Thought. Más tarde se implementaron en Crafty y Dark Thought, pero la primera descripción publicada no fue hasta 1997.
Una década después, se introdujeron métodos de búsqueda directa que utilizaban filas, archivos y diagonales enmascarados para indexar una tabla de vectores de ataque en función de los estados de ocupación de los bits bajo la máscara. Uno de esos esquemas, que utilizaba una función hash perfecta para eliminar las colisiones de hash, se denominó "tableros de bits mágicos". No obstante, el gran tamaño y las altas tasas de acceso de dichas tablas causaban 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 estando divididos, y el mejor esquema depende de la aplicación.
Muchos otros juegos además del ajedrez se benefician de los tableros de bits.
Llámalo Bitboards de jardín de infantes