klondike

En el contexto de los programas de ajedrez, cuando hablamos de representación del tablero nos referimos a la manera en que vamos a guardar la información sobre la situación concreta de la partida, básicamente la posición de las piezas en el tablero.

La forma en que almacenemos esta información será determinante para las funciones más básicas del programa (generación de posiciones). La elección del modelo de representación presumiblemente debe afectar mucho a aspectos como la rapidez de cálculo o el reconocimiento de patrones en una posición.

Conozco dos modelos de representación: guardar la información en una matriz de enteros o usar un modelo basado en tableros de bits (bitboards).
El primer método es el más simple, directo y evidente. Consiste en guardar la posición en una matriz de enteros, por ejemplo en una matriz de 8x8 y usar un código de valores para guardar la información, por ejemplo 0 para casillas no ocupadas por ninguna pieza, 1,2,3,4,5,6 para las piezas blancas y -1,-2,-3,-4,-5,-6 para las piezas negras.
Una variante de este método es usar una matriz mayor de 8x8, por ejemplo de 10x10, de esta forma es más fácil calcular movimientos (el control de los movimientos que caen fuera de los límites del tablero es más simple con estas dimensiones adicionales).
En este momento tengo dos versiones de mi programa, una que usa una matriz de 64 enteros y otra con una representación basada en una matriz de 144 elementos (12x12). Las diferencias en cuanto a rapidez de cálculo no son apreciables, pero el código de la segunda versión, la de la matriz con dimensiones adicionales, es más simple y claro.


Como alternativa a esta forma de guardar las posiciones tenemos el modelo de los tableros de bits. Aquí apenas voy a describir la idea general de esta forma de representación, puedes encontrar algo más en http://en.wikipedia.org/wiki/Bitboard
La información se guarda en matrices de bits de 8x8 y tenemos varios tableros de bits en lugar de uno solo. Cada uno guarda información de un aspecto concreto del tablero. Por ejemplo tenemos el tablero de los peones blancos en el que estarán activados los bits que correspondan a casillas ocupadas por un peón blanco, los demás bits estarán a 0.
La gran ventaja de este método es que permite hacer operaciones booleanas entre dos tableros que como resultado dan la solución a un problema concreto. Por ejemplo, para saber qué piezas captura un caballo blanco en e4 hacemos un AND del "tablero de saltos de caballo desde la casilla e4" con el "tablero de piezas negras". El resultado es otro tablero que tiene los bits de las capturas de caballo a 1.

Este modelo es muy atractivo, y además parece que se adapta muy bien al reconocimiento de patrones posicionales: algo ideal para un programa que pretende basar su fuerza en algo más que el cálculo de posiciones. Sin embargo no he escogido esta forma de representación para mi programa porque es más difícil de implementar que la matriz de enteros, y muchos fuertes programas actuales usan el método de la matriz única para guardar la información. Es decir, que el método simple tampoco parece malo de por sí.