La representación del tablero en el ajedrez por computadora es una estructura de datos en un programa de ajedrez que representa la posición en el tablero y el estado del 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 de movimientos (es decir, la búsqueda), así como el mantenimiento del estado del juego durante el juego. Existen varias representaciones diferentes en la junta directiva. Los programas de ajedrez a menudo utilizan más de una representación en el tablero en diferentes momentos, para mayor eficiencia. La eficiencia de ejecución y el uso de memoria son los factores principales a la hora de elegir una representación en la junta directiva; 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 llamado bitboards , que asigna bits de una palabra de 64 bits o una palabra doble 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 en la junta normalmente no incluye el estado de la regla del sorteo de triple repetición . Para determinar esta regla, es necesario mantener un historial completo del juego desde la última acción irreversible (captura, movimiento de peón o enroque) y, por lo tanto, generalmente se rastrea 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 resulta en una cantidad excesiva de empates. [2]
El estado del tablero también puede contener información secundaria derivada, como qué piezas atacan una casilla; para casillas que contienen piezas, qué espacios son atacados o custodiados por esa pieza; qué piezas están fijadas; y otro estado conveniente o temporal.
El estado del tablero está asociado con cada nodo del árbol del juego, representando una posición a la que se llega mediante un movimiento, ya sea que ese movimiento se haya jugado 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 incrementalmente de un nodo a otro a medida que se recorre el árbol.
Algunos de los primeros programas de ajedrez que trabajaban con cantidades extremadamente limitadas de memoria mantenían listas en serie (matrices) de las piezas en un orden conveniente para la búsqueda, de mayor a menor; asociado con cada pieza estaba su ubicación en el tablero, así como otra información, como casillas que representan sus movimientos legales. Había varias listas, una para piezas blancas y otra para piezas negras. Las listas solían dividirse en piezas y peones. Se trataba de una representación compacta porque la mayoría de las casillas del tablero están desocupadas, pero ineficiente porque era tedioso adquirir información sobre la relación de las piezas con el tablero o entre sí. Muchos de los programas actuales todavía utilizan listas de piezas junto con una estructura de representación de tablero separada, para brindar acceso en serie a las piezas sin 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 el cuadrado dado o, alternativamente, si el cuadrado está vacío. 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, etc. Este esquema se llama direccionamiento de buzones .
Un problema con este enfoque surge durante la generación de movimientos. Es necesario comprobar cada movimiento para garantizar que no se enrolle en un borde del tablero, lo que ralentiza significativamente el proceso. Una solución es usar una matriz de 12x12, con los bordes exteriores llenos con, digamos, el valor 99. Durante la generación del movimiento, la operación para verificar si hay una pieza en el cuadrado de destino también indicará si el cuadrado 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 los extremos izquierdo y derecho (que están marcados como fuera del tablero). [1] [3] Algunos motores de ajedrez utilizan matrices de 16x16 para mejorar la velocidad de conversión de números de base y permitir algunos trucos de codificación especiales para ataques, etc.
El método 0x88 aprovecha el hecho de que las dimensiones de 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 son dos tableros uno al lado del otro, el tablero real a la izquierda, mientras que el tablero a la derecha contendría territorio ilegal. El diseño binario para el rango y archivo 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 el archivo). Por ejemplo, 0x71 (binario 01110001) representaría el cuadrado b8 (en notación algebraica ). Al generar movimientos desde el tablero principal, se puede verificar que haya un cuadrado de destino en el tablero principal antes de consultar la matriz simplemente aplicando un AND al número del cuadrado con hexadecimal 0x88 (binario 10001000). Un resultado distinto de cero indica que el cuadrado 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 en la misma fila, columna o diagonal (una consulta común utilizada para determinar la verificación). [1] [4]
Una representación de tablero más eficiente pero más elaborada que las estructuras basadas en matrices es el bitboard . Un bitboard es una secuencia de bits de 64 bits (0 o 1), que indica la ausencia o presencia (falso o verdadero) de algún estado de cada espacio en el tablero. Luego se puede representar una posición del tablero utilizando una serie de tableros de bits. Por ejemplo, una serie de tableros de bits 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 en entidades de 64 bits en lugar de iteraciones para manipular y derivar información sobre el estado de la placa. Esto aprovecha al máximo el hardware disponible, especialmente ahora que los procesadores de 64 bits se han vuelto comunes.
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 cotejen previamente y se almacenen en una tabla, de modo que los posibles movimientos de la pieza se puedan recuperar en una sola búsqueda de memoria. del mapa de ataque de la casilla en la que reside la pieza que, excluyendo los espacios ocupados por piezas amigas (una operación bit a bit), produce 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 un archivo o en 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 bitboard se gira 90° para indexar archivos y 45° o -45° para indexación diagonal. Rotar un tablero de ajedrez es un desafío conceptual, 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 larga secuencia 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.
Los rangos, archivos y diagonales enmascarados de las piezas deslizantes se pueden utilizar mediante 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. Uno de esos esquemas que utiliza una función hash perfecta junto con trucos para minimizar el tamaño potencial de la tabla que debe almacenarse en la memoria se llama "tableros de bits mágicos".
Una tabla de transposición es un caché de posiciones vistas anteriormente y evaluaciones asociadas en un árbol de juego generado por un programa de juego de computadora. Para una búsqueda rápida de 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 en tablero de ajedrez (CCR), [ cita necesaria ] pero ninguno ha ganado aceptación.
CCR utiliza 4 bits por cuadrado para representar la ocupación del cuadrado, [Notas 1] un rango completo se puede representar 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 se puede extraer de un registro y agregarse al contador del programa para indexar una tabla de salto , ramificándose directamente al código para generar movimientos para el tipo de pieza en esta casilla (si corresponde). Aunque el programa es más largo que los métodos convencionales de generación de movimientos, no se requieren comprobaciones del borde del tablero y no es posible realizar movimientos fuera del tablero, lo que aumenta la velocidad de generación de movimientos.
Los inconvenientes de CCR son: 1) dependencia del tamaño de palabra de 32 bits; 2) disponibilidad de al menos 9 registros gratuitos para la API; 3) necesidad de programación ensambladora sobre una arquitectura CISC para acceder a los registros; 4) no portabilidad de la aplicación de ensamblaje.
{{citation}}: CS1 maint: numeric names: authors list (link)