Representación del tablero

El primer problema: el ordenador no tiene ojos

En el proceso de construcción de un programa de ajedrez la primera dificultad con que nos encontramos es la necesidad de hacer llegar al ordenador la información que se refiere al juego.

Cuando alguien aprende a jugar al ajedrez lo primero que tiene que saber es la forma de las piezas y cómo es el campo de batalla, el tablero. Es el primer paso en el aprendizaje del juego: hay que conocer las piezas, distinguirlas por su forma y tamaño. Además es necesario saber que hay dos bandos y que se reconocen las piezas de uno y otro ejército por su color.

Para un ser humano esta tarea es tan fácil que ni reparamos en ella, se hace de forma automática, sólo hay que mirar el tablero y la disposición de las piezas.
Pero el ordenador no tiene ojos, no tiene forma de percibir el mundo real. Es necesario traducir la realidad física de las piezas y el tablero a una forma que pueda entender el programa. Y si hay algo que los ordenadores hacen bien es tratar con números.

Si consiguiéramos representar toda la información de una partida de ajedrez usando sólo números tendríamos un formato adecuado para ser tratado por el ordenador. Así llegamos a la primera forma de representación del tablero: una tabla o matriz de números.

Construimos una matriz de 64 casillas, cada una de ellas tendrá un valor numérico. Si la casilla está vacía tendremos un 0. Utilizaremos un 1 para el peón, 2 para el caballo, 3 alfil, 4 torre, 5 para la dama y 6 para el rey. Esto para las piezas blancas, para las negras el mismo número pero negativo.

Una mejora habitual es tener una matriz de 12 filas y 12 columnas. Estas filas y columnas adicionales (dos por cada lado) permiten al programa ser más eficiente en la generación de movimientos, porque es más fácil comprobar cuando un movimiento de una pieza la llevaría fuera de los límites del tablero.

Las casillas de estas lineas extra que quedan fuera del tablero real se marcan con un número distinto que indica que ninguna pieza puede llegar hasta allí.

Tenemos una forma de representar el juego, pero aún nos faltan cosas. En esta matriz de números no podemos guardar toda la información necesaria para una partida de ajedrez. Nos falta guardar cosas como los derechos de enroque y la posibilidad de comer al paso.

Bitboards

Lo que hemos descrito es la forma más sencilla y directa de representar el juego del ajedrez de una forma adecuada para los ordenadores. Los primeros programas usaron esta fórmula con éxito, y aún hoy en día es una forma perfectamente válida y que sigue empleándose mucho.

Sin embargo hay otras formas de abordar el problema, una de las más ingeniosas es el modelo de los tableros de bits. Según este modelo no tenemos una sola matriz, sino muchas. Y además nuestras matrices no contienen números sino valores booleanos: cada casilla puede estar en dos estados: verdadero o falso, sí o no. Para completar la información necesaria para el desarrollo del juego hay que leer en varios de estos tableros de bits y combinar los datos.

Así podremos tener, por ejemplo el tablero de los peones blancos, donde cada casilla ocupada por un peón blanco tendrá el valor verdadero y todas las que no estén ocupadas por un peón blanco tendrán valor falso.

Del mismo modo tendremos muchos otros tableros, por ejemplo “el de las piezas enemigas” o el de las “casillas controladas por piezas amigas”. En este último únicamente las casillas amenazadas por nuestras fuerzas tendrán valor “sí” o “verdadero”.

¿Cuál es la ventaja de este lío de tableros? Pues que es una forma óptima de presentar la información a una máquina. Los ordenadores son extraordinariamente eficientes haciendo operaciones booleanas de este tipo. Este método permite realizar una operación booleana entre dos tableros que da como resultado la solución a un problema concreto.

Por ejemplo, supongamos que es el turno de mover del programa y hay que calcular los posibles movimientos de uno de nuestros caballos.

Lo que hacemos es generar el tablero de bits de “casillas amenazadas por el caballo” y combinarlo con el tablero de “casillas ocupadas por fuerzas amigas”. El resultado de esta operación booleana nos dará como resultado otro tablero que será el de “casillas a las que puede desplazarse el caballo”, ya sea porque la casilla esta libre o porque está ocupada por una pieza enemiga.

Esta forma de representación del tablero es muy eficiente, ya que se adapta muy bien a la forma de calcular de los ordenadores y permite generar los movimientos posibles más rápidamente.

La velocidad es un aspecto crucial en los programas de ajedrez, se trata del primer mandamiento que todo programador debe tener presente: Un programa no puede jugar bien al ajedrez si es lento.

Como contrapartida, el modelo de los tableros de bits es más difícil de implementar que la forma clásica de la matriz numérica. Y en la práctica la diferencia de velocidad existe, pero un programa que siga el modelo de la matriz numérica puede ser también muy rápido y un adversario muy respetable.