Bitboard
Un bitboard (tabla de mapa de bits especial) es una estructura de datos que permite representar una situación de juego (posición) dentro de una partida jugada sobre un tablero, que se utiliza especialmente en los programas de ordenador que simulan juegos de tablero, en particular para poder seguir los árboles de juego en los programas de ajedrez, teniendo como límite el número de Shannon.[1]
Visión general
editarLa idea básica de la estructura del bitboard es que la cuestión de si una determinada figura está presente en una posición de juego determinada puede responderse consigo o no. Debido a esto, la asignación de un tablero de juego de tamaño finito puede representarse como una secuencia de números binarios individuales, cada uno de los cuales puede asumir el valor 0 o 1.
Las cifras binarias (" bits ") son la base de la mayoría de los sistemas informáticos actuales . Si la información puede representarse como una secuencia de bits que se adaptan a una palabra de la máquina utilizada, entonces se puede procesar de forma muy eficiente. En particular, los factores que tienen un impacto en la eficiencia de las estructuras de bitboard son:
- el tamaño del bitboard: lo mejor es tener ese tamaño fijo y más pequeño o igual al tamaño de la palabra del ordenador;
- el número de piezas distintas, ya que una palabra sólo puede describir la asignación de un solo tipo de pieza.
Básicamente, las estructuras de bitboard son adecuadas para varios juegos de mesa. Por ejemplo, hay implementaciones de bitboards para juegos como Damas,[2] Othello,[3] Cuatro en raya[4] o Tres en raya.[5] Los bitboards, sin embargo, han ganado una importancia especial dentro del entorno del ajedrez por ordenador. Un tablero de ajedrez consta de 8 × 8 = 64 cuadros, por lo que una palabra de un bitboard asociado tiene 64 bits de longitud. Este tamaño puede procesarse directamente como palabra de datos mediante sistemas informáticos modernos, lo que permite una gran ventaja de velocidad. Algunos ejemplos de programas de ajedrez por ordenador que utilizan bitboards son Crafty[6] y la versión actual 5.0 de GNU Chess.[7]
Ventajas e inconvenientes
editarLa principal ventaja de las estructuras de los bitboards radica en su eficiencia potencialmente muy alta, tanto en términos de espacio de memoria como, sobre todo, en términos de velocidad del programa. Una posición completa de ajedrez puede ser codificada en una palabra de 64 bits, o menos eficientemente, en dos de 32 bits. Muchas operaciones con los bitboards representados de esta forma se pueden llevar a cabo mediante unas pocas instrucciones del procesador.[8]
El principal inconveniente de los bitboards es que son "diferentes" comparados con los tipos de representación más antiguos y más extendidos. Robert Hyatt, el desarrollador del conocido software de ajedrez Crafty, escribe sobre sus primeras experiencias con bitboards:
This has likely been the primary reason that bitmaps have not been widely used; they are different and take some time to ‘sink in’ to the point where they become easy to use. I would speculate that it took me roughly a year before I was able to get past the mental gymnastics of designing an algorithm using offset representation ideas and then working out how to modify the idea to fit the bitmap approach.Robert Hyatt
«Probablemente ésta ha sido la razón principal porque los mapas de bits no se han utilizado ampliamente; son diferentes y se tarda un tiempo en poder "llegar al fondo" hasta el punto de que sean fáciles de utilizar. No especularía si digo que tardé aproximadamente un año antes de poder superar la gimnasia mental de diseñar un algoritmo con ideas de representación desplazada y después averiguar cómo modificar la idea para adaptarla al enfoque del mapa de bits. » —Robert Hyatt
Dado que ahora existen varias implementaciones de bitboards de código abierto, es probable que actualmente, este argumento en contra de los bitboards sólo tenga un débil peso y su importancia siga disminuyendo.
Ejemplo de aplicación: Ajedrez por ordenador
editarComo ya se ha mencionado, en el caso de ajedrez una palabra en un bitboard es exactamente de 64 bits debido al tamaño del tablero de ajedrez. Como característica especial, hay 12 tipos diferentes de piezas ( peones, caballos, rey, torres, alfiles, reina, seis pero cada uno de ellos de color blanco y de color negro). Por ese motivo, se necesitan al menos cuatro palabras de 16 bits para representar completamente una posición. Normalmente, se utilizan muchos más datos para poder procesar la información con mayor facilidad, es decir, la información redundante también se guarda explícitamente.
El software Crafty mencionado en un principio, por ejemplo, guarda las posiciones de los 12 tipos de piezas aparte de las posiciones de todas las piezas blancas y negras con conjunto, así como las versiones giradas del tablero de juego para una mejor optimización. Una estructura de datos completa que describa completamente el estado actual del juego también debe contener otros tipos de información por ejemplo: oportunidades de enroque, captura "en pasando", la regla de 50 movimientos y otras posibles reglas especiales.
| 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 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
La posición inicial por ejemplo, (véase el diagrama) genera para los peones blancos un bitboard de posiciones con el siguiente patrón de bits dentro de una palabra de 64 bits (hay que tener en cuenta que el orden creciente de los bits dentro de la palabra, va de derecha a izquierda):
00000000 00000000 00000000 00000000 00000000 00000000 11111111 00000000 2
La forma en la que se "numera", es decir, qué cuadro del tablero de ajedrez está asignado a qué índice (posición de bit dentro de la palabra), es en última instancia opcional. En este ejemplo y en el siguiente, se numera línea a línea comenzando pl cuadro A1, por lo que el bit 0 pertenece a A1, el bit 1 a A2, y así sucesivamente hasta el bit 63 que pertenece a H8. Como ya se ha mencionado, algunos programas de ajedrez gestionan las estructuras de bitboard con diferentes modos de numerar (por filas o columnas, o incluso en diagonal), ya que esto les permite realizar determinadas operaciones de forma más eficiente.
Cálculo de los movimientos posibles
editarUn problema central en la implementación de un programa de ajedrez es el cálculo de los posibles movimientos hacia posiciones de destino desde una posición determinada. Utilizando estructuras de bitboards, se realizan operaciones lógicas bit a bit entre los diferentes mapas de bits. Hay que distinguir entre dos tipos de piezas: en el caso de las "piezas de salto" como los peones, caballos y rey, basta con mirar si el cuadro de destino está ocupado y de qué color es. En el caso de piezas "deslizantes" como torres, alfiles y reina, las posibilidades de movimiento son más complejas, ya que existen piezas que pueden bloquear determinadas posiciones de destino sin ocuparlas físicamente.
Peones, caballos, rey (piezas de salto)
editar
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Con este tipo de piezas basta con mirar si hay una pieza del propio color en el espacio objetivo, si hay una del otro color, se puede capturar. De hecho, los peones vuelven a ser un caso especial, ya que se mueven de forma diferente según capturan o no una pieza contraria. Dicho esto, estas diferencias de movimiento no se discutirán en este apartado.
Como ejemplo, consideramos un caballo en el espacio D4. Los posibles cuadros objetivo pueden verse en el dibujo. básicamente la cuestión de si el caballo se puede mover a una determinada posición de destino vuelve a ser una pregunta que debe responderse consigo o no, esta respuesta se puede codificar como un bitboard o "tabla de ataque" que se puede calcular y guardarla para cada cuadro de A1 a H8.
En el ejemplo escogido, el cuadro D4 es el 28º cuadro contado línea por línea desde A1 hacia arriba, por lo que en una lista de números de 64 bits, en el bit 27 (si el primer bit es el bit 0 ) asignaría el número siguiente (hay que tener en cuenta que el orden creciente de los bits dentro de la palabra, va de derecha a izquierda):
00000000 00000000 00101000 01000100 00000000 01000100 00101000 00000000 2
La condición lógica que debe cumplirse para que un caballo se pueda trasladar a una posición determinada es que no debe contener ninguna pieza de su propio color. en el bitboard complementario recién creado, el bit que cumple esta condición se pone a "1" para cada cuadro. El resultado deseado se obtiene finalmente mediante una operación AND bit a bit con el "bitboard de ataque" del caballo precalculado. Con leves modificaciones, puede utilizarse el mismo algoritmo para calcular los movimientos de los peones y del rey.
Torres, peones, reina (piezas deslizantes)
editarEstas piezas se mueven fundamentalmente de forma diferente a los tres tipos de pieza mencionados anteriormente. En el caso de estas piezas “deslizantes”, aparte de ver si la posición de destino está ocupada, mirar si está bloqueada, ya sea por piezas propias o del color contrario. La reina puede interpretarse como una combinación de torre y alfil, lo que puede representar una simplificación en el momento de la elección exacta de las estructuras de datos.
Referencias
editar- ↑ Jones, M.T. (2008). Artificial Intelligence: A Systems Approach: A Systems Approach (en danés). Jones & Bartlett Learning. p. 110. ISBN 978-1-4496-3115-4. Consultado el 28 de febrero de 2022.
- ↑ Darstellung von Bitboard-Strukturen im Dame-Spiel (englisch)
- ↑ Diskussion verschiedener Implementierungsdetails von Othello, inklusive Bitboards (englisch).
- ↑ Bitboards and Connect Four beschreibt ausführlich eine Implementierung für Vier gewinnt (englisch).
- ↑ Das Lehrvideo Bitboards für Tic-Tac-Toe erklärt eine Umsetzung für Tic-Tac-Toe (deutsch)
- ↑ Robert Hyatt: Artikel über die in Crafty verwendeten „rotated bitboard“-Strukturen. Archivado el 20 de julio de 2015 en Wayback Machine.
- ↑ Dokumentation von GNU Chess 5.0
- ↑ R. Hyatt: Vergleichender Artikel über Datenstrukturen für Schachprogramme Archivado el 24 de junio de 2016 en Wayback Machine.
Bibliografía
editar- «How DarkThought Plays Chess (Preprint of an article by Ernst A. Heinz in: ICCA Journal, Vol. 20(3), pp. 166-176, Sept. 1997)». People, 02-03-1998. [Consulta: 1r març 2022].
- Beowulf Unix, Linux, Windows. Rotated bitboards.
- Crafty See the Crafty article. Written in straight C. Rotated bitboards in the old versions, now uses magic bitboards.
- GNU Chess See the GNU Chess Article.
- Stockfish UCI chess engine ranking second in Elo as of 2010
- Gray Matter C++, rotated bitboards.
- KnightCap GPL. ELO of 2300.
- Pepito C. Bitboard, by Carlos del Cacho. Windows and Linux binaries as well as source available.
- Simontacci Rotated bitboards.
Enlaces externos
editar- «Bitboards in Board Word Games». Helps your game in Wordfeud, Words with friends and Scrabble. [Consulta: 1r març 2022].
- DarkThought Home Page