Un tablero de bits es una estructura de datos de matriz de bits especializada comúnmente utilizada 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 paralelas bit a bit 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 juntos. Otros tableros de bits 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 de, o la presencia de piezas en, espacios discretos de un tablero de juego, mediante la asignación 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 de buzón tradicional , donde cada pieza o espacio en el tablero es un elemento de matriz.
Los bitboards 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 bit a bit como AND y OR pueden usarse 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 , el othello 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.
Descripción
Un tablero de bits, un campo de bits especializado, es un formato que empaqueta múltiples variables booleanas relacionadas en la misma palabra de máquina, que típicamente 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 peones en el centro del tablero (cuatro casillas centrales), puede comparar un tablero de bits para los peones del jugador con uno para el centro del tablero usando un método AND bit a bit. operación. Si no hay peones centrales, el resultado será cero bits (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 las variables temporales) pueden representar propiedades locales o contener resultados intercalados intermedios.
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 voltear 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 clasificar 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? " se puede responder con una sola búsqueda de memoria.
Las implementaciones de campo de bits 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 miniordenadores de 8 y 16 bits anteriores.
Problemas de implementación
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 son tediosos para que los desarrolladores de software escriban o depuren. Los métodos generativos auxiliares que no forman parte de la aplicación suelen ser necesarios para construir las tablas.
Uso del procesador
Pros
Las representaciones de tablero de bits utilizan operaciones paralelas a nivel de bits 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 varias 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 bifurcaciones pueden hacer que la canalización se vacíe si se predice mal una bifurcació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 que 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 ancho más alto o más bajo. Muchas CPU de 32 bits pueden tener algunas instrucciones de 64 bits y estas pueden tomar más de un ciclo o tener alguna desventaja en comparación con sus instrucciones de 32 bits.
Si el tablero de bits es más grande que el ancho del conjunto de instrucciones, se requerirán varias instrucciones para realizar una operación de ancho completo en él. Por lo tanto, un programa que utiliza placas de bits de 64 bits se ejecutará más rápido en un procesador de 64 bits que en un procesador de 32 bits.
Contras
Las representaciones de bitboard tienen un código mucho más largo, tanto código fuente como código objeto. Las secuencias largas de reproducción de bits son técnicamente difíciles de escribir y depurar. Los tableros de bits en sí son escasos, a veces contienen solo un bit en 64, por lo que las implementaciones de tablero de bits consumen mucha memoria. Ambos problemas pueden aumentar las pérdidas de caché o provocar errores de caché.
Si el procesador no tiene instrucciones de hardware para 'primero' (o ' contar ceros a la izquierda ') y ' contar unos ' (o 'contar ceros'), la implementación se verá significativamente obstaculizada, ya que estas operaciones son extremadamente ineficientes para codificar como bucles de lenguaje ensamblador.
Uso de caché y memoria
Pros
Los tableros de bits requieren más memoria que las estructuras de datos de tablero de lista de piezas, pero son más eficientes en ejecución porque muchas operaciones de bucle y comparación se reducen a una única (o pequeña cantidad de) operaciones 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 aplica mediante AND con el mapa de bits para el espacio . Un resultado distinto de cero significa que la pieza ataca el espacio .
Contras
Para algunos juegos, escribir un motor de tablero de bits 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 pérdidas de caché entre el nivel uno y el nivel dos. Esto es solo un problema potencial, no un gran inconveniente, ya que la mayoría de las máquinas tendrán suficiente caché de instrucciones para que esto no sea un problema.
Actualización incremental
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 ser prohibitivamente caro, por lo que los mapas de bits derivados se actualizan gradualmente, 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 espacios modificados, no todos los mapas de bits en el tablero, necesitan cambiar. 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 de correo anterior, donde la actualización es intrínsecamente local e incremental.
Mapas de bits precalculados y búsqueda de tablas
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 recopilarlos 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. tablero de ajedrez que de otro modo requeriría una enumeración.
Tableros de ajedrez
La representación obvia y más simple de la configuración de piezas en un tablero de ajedrez es como una lista (matriz) de piezas en un orden de búsqueda conveniente (de menor a mayor valor) que asigna cada pieza a su ubicación en el tablero. De manera análoga, la recopilación de los espacios atacados por cada pieza requiere una enumeración en serie de dichos espacios para una pieza. Este esquema se denomina direccionamiento de buzones de correo . 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 un 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 tableros de bits .
Estándar
En las representaciones de tablero de bits, cada bit de una palabra de 64 bits (o palabra doble en arquitecturas de 32 bits) se asocia con un cuadrado del tablero de ajedrez. Se puede utilizar cualquier mapeo de bits a cuadrados, pero por convención amplia, los bits se asocian 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 63 es el cuadrado h8.
Muchas configuraciones diferentes del tablero suelen estar 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 bitboards también pueden ser constantes como uno que representa el primer rango, que tendría un bit en las posiciones 0 - 7. Otros bitboards locales o de transición como "todos los espacios adyacentes al rey atacados por piezas opuestas" pueden clasificarse 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
Uno de los inconvenientes de los tableros de bits estándar es agrupar los vectores de ataque de las piezas deslizantes (torre, alfil, reina), porque tienen un número indefinido de espacios de ataque en función de otros espacios ocupados. Esto requiere varias secuencias largas de máscaras, turnos y complementos por pieza.
Representaciones auxiliares de bitboard
En reconocimiento del tamaño del código y la complejidad informática de la generación de tableros de bits para los vectores de ataque de piezas deslizantes, se han ideado estructuras de datos de tablero de bits alternativos para recopilarlos. Las representaciones del tablero de bits de caballeros, reyes, peones y otras configuraciones de tablero no se ven afectadas por el uso de tableros de bits auxiliares para las piezas deslizantes.
Tableros de bits rotados
Los tableros de bits rotados son estructuras de datos de tablero de bits complementarias que permiten la tabularización de 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 diagonales y anti-diagonal de los alfiles (los ataques de rango de las torres se pueden indexar desde tableros de bits estándar) . Con estos tableros de bits, una búsqueda en una sola tabla reemplaza largas secuencias de operaciones bit a bit.
Estos tableros de bits rotan la configuración de ocupación del tablero en 90 grados, 45 grados y / o 315 grados. Un tablero de bits estándar tendrá un byte por rango del tablero de ajedrez. Con este bitboard es fácil determinar los ataques de torre en un rango, usando una tabla indexada por el cuadrado ocupado y las posiciones ocupadas en el rango (porque los ataques de torre se detienen en el primer cuadrado ocupado). Al girar el tablero de bits 90 grados, los ataques de torre hacia arriba y hacia abajo en una lima se pueden examinar de la misma manera. Agregar tableros de bits rotados 45 grados y 315 grados (-45 grados) produce tableros de bits en los que las diagonales son fáciles de examinar. La dama puede examinarse combinando ataques de torre y alfil. En realidad, rotar un tablero de bits es una transformación poco elegante que puede requerir decenas de instrucciones. [2] [3]
Hash directo
Los vectores de ataque de filas y filas de las torres y los vectores de ataque diagonales y anti-diagonal de los alfiles se pueden enmascarar por separado y usar como índices en una tabla hash de vectores de ataque precalculados según la ocupación, de 8 bits cada uno para torres y de 2 a 8 bits. cada uno para obispos. El vector de ataque completo de una pieza se obtiene como la unión de cada uno de los dos vectores unidireccionales indexados 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] ver el esquema de hash empleado. [5]
Tableros de bits mágicos
Los tableros de bits mágicos son una extrapolación de la compensación espacio-temporal de la búsqueda directa de hash de los 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 los cuadrados exteriores o los rangos primero y octavo 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 otros bloqueos piezas) independientemente de la ocupación, por lo que 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 proceso exhaustivo de enumeración, en parte algorítmico y en parte de prueba y error, para generar la función hash. Pero el problema insoluble sigue siendo: 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 provoca una inundación de caché. Por lo tanto, los tableros de bits mágicos en muchas aplicaciones no proporcionan una ganancia de rendimiento sobre esquemas de hash más modestos o tableros de bits rotados. [6] [7]
Historia
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 de forma independiente 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. 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 mapearon convenientemente los 64 cuadrados del tablero de ajedrez en partes 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 compartidos con el equipo de programación de Dark Thought. Más tarde se implementaron en Crafty and 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 en función de 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 las colisiones hash, se denominó "tableros de bits mágicos". No obstante, el gran tamaño y las altas tasas de acceso de tales tablas causaron problemas de ocupación de memoria y contención de caché, y no fueron necesariamente más eficaces que el enfoque de tablero de bits rotado. Hoy en día, los programas de juegos permanecen divididos, y el mejor esquema depende de la aplicación.
Otros juegos
Muchos otros juegos además del ajedrez se benefician de los bitboards.
- En Connect Four , permiten realizar pruebas muy eficientes para cuatro discos consecutivos, con solo dos operaciones shift + AND por dirección.
- En Game of Life de Conway , son una posible alternativa a las matrices.
- Othello / Reversi (ver el artículo de Reversi ).
Ver también
Notas
- ^ No se requiere el uso de una función hash perfecta para la implementación de este método, y proporciona solo un beneficio muy pequeño sobre los métodos hash estándar.
Referencias
- ^ Atkin, Larry R .; Slate, David J. (1983) [1977]. "Ajedrez 4.5: el programa de ajedrez de la Universidad Northwestern". En Frey, Peter W. (ed.). Habilidad de ajedrez en el hombre y la máquina (2 ed.). Springer Verlag . págs. 82-118. CiteSeerX 10.1.1.111.926 . ISBN 0-387-90790-4.
- ^ Heinz, Ernst A. (septiembre de 1997). "Cómo el pensamiento oscuro juega al ajedrez" . Revista ICCA . 20 (3): 166-176.
- ^ Hyatt, Robert (1999). "Bitboards rotados: nuevo giro en una vieja idea" . Archivado desde el original el 28 de abril de 2005.
- ^ Tannous, Sam (23 de julio de 2007) [2006]. "Evitar bitboards rotados con búsqueda directa". Revista ICGA (2 ed.). Durham, Carolina del Norte, Estados Unidos. 30 (2): 85–91. arXiv : 0704.3773v2 . CiteSeerX 10.1.1.561.3461 . doi : 10.3233 / ICG-2007-30204 .
- ^ Knuth, Donald (1973). "Sección 6.4. Algoritmo D (Direccionamiento abierto con doble hash)". El arte de la programación informática . 3 .
- ^ Sherwin, Michael; Isenberg, Gerd (4 de diciembre de 2006). "¡Explicación de Magic Bitboards!" . Foro de Winboard .
Llámalo Bitboards de jardín de infantes
- ^ Hansen, Lasse (14 de junio de 2006). "Generador de movimiento de tablero de bits más rápido" . Foro de Winboard ..
- ^ "Algunos estudios en aprendizaje automático utilizando el juego de damas". Revista de investigación y desarrollo de IBM . 1959.
- ^ "Programación de una computadora para jugar al ajedrez". Encuestas matemáticas rusas . 1970.
Otras lecturas
- http://people.csail.mit.edu/heinz/dt/node2.html
enlaces externos
Calculadoras
- Representación y manipulación de 64 bits
juego de damas
- Tutorial de tablero de damas de Jonathan Kreuzer
Ajedrez
Artículos
- Tableros de bits - Chessprogramming wiki
- Área de programación del proyecto Beowulf
- Laramee, Francois-Dominic. Programación de ajedrez Parte 2: Estructuras de datos.
- Verhelst, Paul. Representaciones del tablero de ajedrez
- Hyatt, Robert. Representaciones del tablero del programa de ajedrez
- Frayn, Colin. Cómo implementar bitboards en un motor de ajedrez (teoría de programación de ajedrez)
- Pepicelli, Glen. Bitfields, Bitboards, and Beyond - (Ejemplo de bitboards en Java Language y una discusión de por qué esta optimización funciona con Java Virtual Machine (www.OnJava.com editor: O'Reilly 2005))
- Magic Move-Bitboard Generation en ajedrez informático. Pradyumna Kannan
Ejemplos de código
- [1] El autor del motor Frenzee había publicado algunos ejemplos de fuentes.
- [2] Un programa java Connect-4 de 155 líneas que demuestra el uso de tableros de bits.
Implementaciones
Fuente abierta
- Beowulf Unix, Linux, Windows. Tableros de bit rotados.
- Crafty Consulte el artículo Crafty. Escrito en C recta. Tableros de bits rotados en las versiones anteriores, ahora usa tableros de bits mágicos.
- GNU Chess Consulte el artículo GNU Chess.
- El motor de ajedrez Stockfish UCI ocupa el segundo lugar en Elo a partir de 2010
- Gray Matter C ++, tableros de bits rotados.
- KnightCap GPL. ELO de 2300.
- Pepito C. Bitboard, de Carlos del Cacho. Binarios de Windows y Linux, así como fuentes disponibles.
- Tableros de bits rotados Simontacci .
Fuente cerrada
- Página de inicio de DarkThought
OTELO
- Una discusión completa de los motores Othello ( Reversi ) con algo de código fuente que incluye un tablero de bits Othello en C y ensamblado.
- Edax (informática) Consulte el artículo de Edax. Un motor Othello ( Reversi ) con código fuente basado en bitboard.
Juegos de palabras
- Descripción general del uso del tablero de bits en juegos de palabras.