Representación del tablero (Ajedrez)

En el ajedrez por computadora los programadores deben de escoger una estructura de datos para representar las posiciones del ajedrez. Muchas estructuras de datos existen, llamadas colectivamente como representación del tablero. Los programas de ajedrez frecuentemente usan más de una representación del tablero por razones de eficiencia.

Requerimientos

Una completa descripción de una posición de ajedrez, debería de contener los siguientes elementos:

El lugar de cada pieza en el tablero
El jugador que tiene el turno de mover
El estado de la regla de los 50 movimientos
El estado del enroque de ambos jugadores
Si es posible que una pieza pueda capturar al paso, y de cual pieza se trata.

La representación del tablero típicamente no incluye la regla de empate de los 3 movimientos repetidos. Para determinar esta regla, se necesita mantener un historial completo del juego, y por lo tanto, esto se almacena en una estructura de datos diferente.

Tipos

Lista de piezas

Algunos de los primeros programas de computadoras de la historia debían trabajar con muy poca memoria, por lo tanto, alojar las 64 casillas del tablero en memoria representaba mucho. Entonces, estos programas almacenaban una lista de los lugares de cada una de las 16 piezas de ambos jugadores. En vez de buscar en cada una de las 64 casillas del tablero para encontrar las piezas, la lista de piezas daba acceso instantáneo a las piezas.

Basado en arreglos

Una de las formas más simples de representar un tablero es crear un arreglo de tamaño 8x8 (o de forma equivalente un arreglo unidimensional de 64 elementos). A cada elemento del arreglo correspondería la pieza que contiene la casilla, o en dado caso, si la casilla está vacía. Una posible codificación sería considerar 0 como vacío, positivo como pieza blanca, y negativo como pieza negra. Por ejemplo:

0	Vacío
1	Peón blanco
2	Caballo blanco
3	Alfil blanco
4	Torre blanca
5	Dama blanca
6	Rey blanco
-1	Peón negro
-2	Caballo negro
-3	Alfil negro
-4	Torre negra
-5	Dama negra
-6	Rey negro

Un problema al utilizar esta forma es la generación de la lista de movimientos. Cada movimiento se tiene que comprobar para asegurarse que está en el tablero, disminuyendo significativamente el proceso. Una solución sería usar un arreglo de 12x12, rellenando las casillas no propias del tablero con un valor fuera del rango, digamos, un 99. Durante la generación del movimiento, la operación para determinar la pieza que ocupa una determinada casilla siempre nos indicará que tal casilla está fuera del tablero.

Se puede obtener una mejoría en la memoria con un arreglo de 10x12, el cual provee las mismas funcionalidades que uno de 12x12, sobreponiendo las casillas de los costados de todas las filas, las cuales son marcadas como "fuera del tablero". Algunos programas usan arreglos de 16x16 para mejorar la velocidad en la conversión de las filas y columnas y también para permitir trucos especiales de codificación.

Los programadores de código máquina tienen otra alternativa. Usando 4 bits por casilla, una columna entera puede ser representada en 32 bits, y el tablero en 8 registros (con uno adicional para la información faltante). Con ayuda de una "tabla de saltos" (jump table) y agregando el valor de la pieza a un programa contador se puede ir directamente al código para generar movimientos del tipo de pieza de tal casilla. A pesar de que el programa es más grande que los métodos de generación de movimientos convencionales, no se necesita checar las casillas fuera del tablero, lo cual incrementa la velocidad de la generación de movimientos.

El método 0x88

El método 0x88 usa un arreglo de tamaño 16x8=128, numerado de 0 a 127. Básicamente son 2 tableros, uno a un lado del otro. El tablero real está a la izquierda y el tablero de la derecha representa los movimientos ilegales. Cuando se generan los movimientos del tablero real, se puede comprobar que la casilla destino está en el tablero real usando simplemente el operador AND del número de la casilla con 0x88. Un resultado diferente de cero indica que la casilla está fuera del tablero principal y que por lo tanto es una casilla ilegal. Esto favorece en la velocidad.

Tabla de bits (Bitboard)

Una representación comúnmente usada es por medio de una tabla de bits (bitboard). Una tabla de bits es una secuencia de 64 bits, los cuales indican ausencia o presencia de algún estado acerca de posiciones en el tablero. Una serie de tablas de bits por cada tipo de pieza de cada jugador podría representar completamente la posición del tablero.

La ventaja de este tipo de representación radica en la habilidad de usar operaciones a nivel de bits sobre las entidades de 64 bits en vez de realizar ciclos para manipular y derivar información acerca del estado del tablero. Esto aprovecha al máximo el uso del hardware disponible, especialmente en los exóticos procesadores de 64 bits.

Codificación Huffman

Las posiciones del tablero de ajedrez pueden ser representadas como patrones de bits, de tal forma que los elementos más comunes (casillas vacías y peones) son almacenados con menos bits que un elemento menos común.

Casilla vacía	=	0
Peón	=	10c
Alfil	=	1100c
Caballo	=	1101c
Torre	=	1110c
Dama	=	11110c
Rey	=	11111c

Donde c es el bit que representa el color de la pieza (1 = BLANCO, 0 = NEGRO).

Se necesitan algunos bits adicionales:

La regla de los 50 movimientos (6 bits)
La columna de posible captura al paso (4 bits)
El turno del jugador (1 bit)
Los derechos de enroque (4 bits)

La codificación Huffman es más intenso en el uso del CPU, en comparación con otras representaciones del tablero que minimizan los requerimientos del procesador y los ciclos de memoria. De cualquier forma, el tamaño final de la representación hace que ésta sea ideal para almacenar posiciones a largo plazo. Se usa, por ejemplo, para llevar un libro de aperturas porque en tal caso es más importante disminuir el tamaño que minimizar los ciclos del CPU.

Véase también

Referencias

Datos: Q3775931