La representación del tablero en el ajedrez por ordenador es una estructura de datos en un programa de ajedrez que representa la posición en el tablero y el estado de juego asociado. [1] La representación del tablero es fundamental para todos los aspectos de un programa de ajedrez, incluida la generación de movimientos, la función de evaluación y la realización y deshacer movimientos (es decir, la búsqueda), así como el mantenimiento del estado del juego durante el juego. Existen varias representaciones de tablero diferentes. Los programas de ajedrez a menudo utilizan más de una representación de tablero en diferentes momentos, por eficiencia. La eficiencia de ejecución y el consumo de memoria son los factores principales a la hora de elegir una representación de tablero; las consideraciones secundarias son el esfuerzo necesario para codificar, probar y depurar la aplicación.
Los primeros programas utilizaban listas de piezas y listas de cuadrados, ambas basadas en matrices. La mayoría de las implementaciones modernas utilizan un enfoque de matriz de bits más elaborado pero más eficiente, denominado bitboards, que asigna bits de una palabra o palabra doble de 64 bits a cuadrados del tablero.
Una descripción completa de una posición de ajedrez, es decir, el "estado" de la posición, debe contener los siguientes elementos:
La representación del tablero no suele incluir el estado de la regla de la triple repetición de tablas . Para determinar esta regla, es necesario mantener un historial completo de la partida desde la última acción irreversible (captura, movimiento de peón o enroque), por lo que generalmente se registra en estructuras de datos separadas. Sin esta información, los modelos pueden repetir la posición a pesar de tener una ventaja ganadora, lo que da como resultado una cantidad excesiva de tablas. [2]
El estado del tablero también puede contener información derivada secundaria, como qué piezas atacan una casilla; para las casillas que contienen piezas, qué espacios son atacados o protegidos por esa pieza; qué piezas están clavadas; y otros estados convenientes o temporales.
El estado del tablero está asociado con cada nodo del árbol de juego y representa una posición a la que se llegó mediante un movimiento, ya sea que ese movimiento se haya realizado sobre el tablero o se haya generado como parte de la búsqueda del programa. Es conceptualmente local para el nodo, pero puede definirse globalmente y actualizarse de manera incremental de un nodo a otro a medida que se recorre el árbol.
Algunos de los primeros programas de ajedrez que funcionaban con cantidades de memoria extremadamente limitadas mantenían listas seriales (matrices) de las piezas en un orden que facilitaba la búsqueda, como la más grande a la más pequeña; asociada a cada pieza estaba su ubicación en el tablero, así como otra información, como las casillas que representaban sus movimientos legales. Había varias listas, una para las piezas blancas y otra para las negras. Las listas solían estar divididas en piezas y peones. Esta era una representación compacta porque la mayoría de las casillas del tablero están desocupadas, pero ineficiente porque obtener información sobre la relación de las piezas con el tablero o entre sí era tedioso. Muchos de los programas actuales aún utilizan listas de piezas junto con una estructura de representación del tablero independiente, para dar acceso serial a las piezas sin tener que buscar en el tablero.
Una de las formas más sencillas de representar un tablero es crear una matriz bidimensional de 8x8 (o, equivalentemente, una matriz unidimensional de 64 elementos). Cada elemento de la matriz identificaría qué pieza ocupaba la casilla dada o, alternativamente, si la casilla estaba vacía. Una codificación común es considerar 0 como vacío, positivo como blanco y negativo como negro, por ejemplo, peón blanco +1, peón negro -1, caballo blanco +2, caballo negro -2, alfil blanco +3, y así sucesivamente. Este esquema se llama direccionamiento de buzón .
Un problema con este enfoque surge durante la generación de movimientos. Cada movimiento debe ser revisado para asegurarse de que no se envuelva alrededor de un borde del tablero, lo que ralentiza significativamente el proceso. Una solución es utilizar una matriz de 12x12 en su lugar, con los bordes exteriores llenos con, digamos, el valor 99. Durante la generación de movimientos, la operación para verificar si hay una pieza en la casilla de destino también indicará si la casilla de destino está fuera del tablero. [1] [3]
Se puede lograr un mejor uso de la memoria con una matriz de 10x12, que proporciona las mismas funcionalidades que una de 12x12 al superponer los archivos de borde más a la izquierda y más a la derecha (que están marcados como fuera del tablero). [1] [3] Algunos motores de ajedrez usan matrices de 16x16 para mejorar la velocidad de la conversión de filas y números de filas y permitir algunos trucos de codificación especiales para ataques, etc.
El método 0x88 aprovecha el hecho de que las dimensiones 8x8 de un tablero de ajedrez son una potencia par de dos (es decir, 8 al cuadrado). El tablero utiliza una matriz unidimensional de tamaño 16x8 = 128, numerada del 0 al 127 en lugar de una matriz de tamaño 64. Básicamente, se trata de dos tableros uno al lado del otro, el tablero real a la izquierda mientras que el tablero de la derecha contendría territorio ilegal. El diseño binario para el rango y la fila de coordenadas de un tablero legal dentro de la matriz es 0rrr0fff(Las r son los 3 bits utilizados para representar el rango. Las f para la fila). Por ejemplo, 0x71 (binario 01110001) representaría la casilla b8 (en notación algebraica ). Al generar movimientos desde el tablero principal, uno puede verificar que una casilla de destino esté en el tablero principal antes de consultar la matriz simplemente mediante AND del número de casilla con hexadecimal 0x88 (binario 10001000). Un resultado distinto de cero indica que la casilla está fuera del tablero principal. Además, la diferencia entre las coordenadas de dos cuadrados determina de forma única si esos dos cuadrados están a lo largo de la misma fila, columna o diagonal (una consulta común utilizada para determinar la verificación). [1] [4]
Una representación del tablero más eficiente pero más elaborada que las estructuras basadas en matrices es el bitboard . Un bitboard es una secuencia de 64 bits (0 o 1), que indica la ausencia o presencia (falso o verdadero) de algún estado de cada espacio del tablero. La posición del tablero se puede representar mediante una serie de bitboards. Por ejemplo, una serie de bitboards para cada tipo de pieza, para cada lado, puede representar la posición del tablero.
La ventaja de esta representación es la capacidad de utilizar operaciones paralelas de bits sobre las entidades de 64 bits en lugar de iteraciones para manipular y derivar información sobre el estado de la placa. Esto permite aprovechar al máximo el hardware disponible, especialmente ahora que los procesadores de 64 bits se han generalizado.
Una ventaja sustancial de los tableros de bits es que permiten que los mapas de los espacios atacados por cada tipo de pieza en cada espacio del tablero se recopilen previamente y se almacenen en una tabla, de modo que los posibles movimientos de la pieza se puedan recuperar en una única búsqueda de memoria del mapa de ataque para el cuadrado en el que reside la pieza, lo que, excluyendo los espacios ocupados por piezas amigas (una operación bit a bit), arroja los movimientos legales de la pieza. Pero los movimientos de las piezas deslizantes (torres, alfiles, reinas) son indeterminados porque los movimientos de estas piezas dependen de la configuración de otras piezas en el tablero. Por eso se han ideado estructuras de datos especiales y complejas para representar sus movimientos.
Los tableros de bits rotados son una técnica de generación de movimientos para las piezas deslizantes que utiliza copias rotadas de un tablero de bits para colocar espacios (bits) en una fila o diagonal en bits adyacentes análogos a los bits que representan un rango. Estos bits se pueden extraer y utilizar como índice en una tabla para obtener el mapa de espacios atacados por estas piezas. El tablero de bits se rota 90° para la indexación de la fila y 45° o -45° para la indexación diagonal. Rotar un tablero de ajedrez es conceptualmente desafiante y rotar un tablero de bits es computacionalmente poco elegante, pero la transformación evita enumerar en serie los movimientos de las piezas o una secuencia prolongada de desplazamiento y enmascaramiento de un tablero de bits del mapa de ataque de la pieza para tener en cuenta la configuración del tablero.
Las filas, filas y diagonales enmascaradas de las piezas deslizantes se pueden utilizar a través de una función hash para indexar directamente una tabla de vectores de ataque precalculados en función de los bits de ocupación en la parte enmascarada. Un esquema de este tipo que utiliza una función hash perfecta junto con trucos para minimizar el tamaño potencial de la tabla que se debe almacenar en la memoria se denomina "tableros de bits mágicos".
Una tabla de transposición es un caché de posiciones vistas previamente y evaluaciones asociadas en un árbol de juego generado por un programa de juego de computadora. Para una búsqueda rápida en la tabla, se puede utilizar una función hash, como el hash Zobrist , para acelerar la búsqueda de tableros coincidentes. [5]
Se han propuesto otros métodos, como la Representación Compacta de Tablero de Ajedrez (CCR), [ cita requerida ] pero ninguno ha obtenido aceptación.
El CCR utiliza 4 bits por casilla para representar la ocupación de la casilla, [Notas 1] una fila entera puede representarse en 32 bits, y el tablero en 8 registros (con uno adicional para la información de posición restante). El código de ocupación de una casilla puede marcarse desde un registro y agregarse al contador del programa para indexar una tabla de saltos , ramificándose directamente al código para generar movimientos para el tipo de pieza en esta casilla (si hay alguno). Aunque el programa es más largo que para los métodos de generación de movimientos convencionales, no se requieren verificaciones del borde del tablero y no es posible realizar movimientos fuera del tablero, lo que aumenta la velocidad de generación de movimientos.
Las desventajas de CCR son: 1) dependencia de un tamaño de palabra de 32 bits; 2) disponibilidad de al menos 9 registros libres para la API; 3) necesidad de programación en ensamblador en una arquitectura CISC para acceder a los registros; 4) no portabilidad de la aplicación en ensamblador.
{{citation}}: CS1 maint: numeric names: authors list (link)