En esta sección hablaremos por primera vez de muchos de los conceptos que más tarde irán apareciendo a medida que desarrollemos cada uno de los temas previstos. Intentaremos esbozar aquí, a grandes rasgos, la estructura interna que debe tener cualquier programa de ajedrez e introduciremos mucha de la terminología que después usaremos.

Representación interna del tablero

En primer lugar, y como elemento más importante quizá de un programa de ajedrez, tenemos que hablar sobre la forma en que representaremos internamente el tablero de juego y la posición de cada una de las piezas. Aunque a priori esto parezca una cuestión fácil de resolver, la decisión tomada influirá enormemente en el resultado final y marcará la forma de proceder en el resto de módulos del programa.

A la hora de buscar la forma apropiada de representar una posición tendremos que tener en cuenta que no sólo deberemos recoger información sobre la posición de las piezas en el tablero sino también muchos otros datos necesarios durante una partida de ajedrez. Así, por ejemplo, tendremos que almacenar de alguna forma el jugador que posee el turno de juego, los derechos de enroque para cada lado, los peones que se pueden capturar al paso, las repeticiones de jugadas para poder aplicar la regla de las tres repeticiones, etc.

Existen muchas formas de representar internamente todos estos datos y en la sección dedicada a este tema veremos algunas de ellas.

Validación de movimientos

Otro aspecto muy importante de cara al desarrollo de un juego de este tipo es la validación de movimientos, esto es, la comprobación de si el movimiento de una pieza de una casilla determinada a otra es legal o no, en nuestro caso para el juego de ajedrez. Esta tarea será indispensable para comprobar la validez de los movimientos realizados por el usuario del programa.

En el ajedrez por ordenador, estas validaciones no siempre son sencillas. Sí es cierto que comprobar que un peón se ha movido un solo paso hacia delante cuando no hay ninguna pieza en la casilla de destino es fácil de realizar. Sin embargo, otro tipo de movimientos como los enroques o las capturas al paso son mucho más delicados y en ellos intervienen otros factores además del movimiento característico asociado al tipo de pieza. Todo ello unido a las comprobaciones de que un movimiento no provoque un jaque al propio rey, validación involucrada en cualquier movimiento y que debe ser tratada con sumo cuidado.

En el capítulo dedicado a esta sección veremos alguna técnica muy interesante para optimizar todo lo posible todas estas validaciones.

Generación de movimientos

Una vez tenemos una representación interna consistente del tablero y somos capaces de validar los movimientos realizados por el usuario lo siguiente que debemos poder hacer es pensar los posibles movimientos que puede realizar la máquina para una posición dada.

Deberemos construir por tanto una serie de procedimientos que nos ayuden a obtener, para una posición específica, una lista con todos los movimientos válidos que se pueden realizar. Además, en ocasiones también nos será útil disponer de procedimientos que no obtengan todos los movimientos posibles, sino sólo algunos subconjuntos característicos de éstos. Así, por ejemplo, podremos tener funciones para obtener todas las capturas de piezas posibles para una posición dada, o todos los escapes a jaques. Es pronto para comprender la utilidad de estos procedimientos, pero más adelante, cuando estudiemos los métodos de búsqueda de soluciones, todo tomará un sentido mucho más claro.

Ejecución de movimientos

Ahora que para una posición determinada ya podemos obtener una lista con todos los movimientos que podemos realizar, el siguiente paso es ejecutar alguno de ellos. Esto, que debería resultar una tarea sencilla, veremos después que se convierte en un proceso bastante engorroso, pero del que dependerá en gran medida la estabilidad de nuestro programa de ajedrez. Cualquier error a la hora de ejecutar los movimientos nos dará muchos quebraderos de cabeza en las fases siguientes.

El problema principal es que, como dijimos antes, no sólo habrá que actualizar en cada movimiento la posición de las piezas, sino que habrá que ir actualizando igualmente todos los datos antes comentados: derechos de enroque, peones al paso, además de otras muchas estructuras de las que hablaremos en su sección correspondiente. Indicar también aquí que además de realizar movimientos también deberemos ser capaces de deshacerlos, no sólo como opción de juego, sino como acción indispensable para la búsqueda del mejor movimiento por parte de la máquina. Más adelante veremos por qué es necesario todo esto y cómo se utiliza.

Evaluación de posiciones

Una vez llegados aquí, ya parece fácil imaginar como va a funcionar nuestro programa de ajedrez: primero esperaremos a que el usuario mueva alguna pieza, validaremos su moviendo, ejecutaremos el movimiento validado, posteriormente generaremos la lista con todos los posibles movimientos que puede realizar la máquina, ejecutaremos uno de ellos, y vuelta a empezar hasta el término de la partida. Sencillo, ¿verdad? [Ver figura 1]. La cuestión ahora es ¿cuál de los movimientos de la lista generada es el mejor que puedo hacer dada una posición? Pues bien, para resolver este problema deberemos construir un procedimiento de evaluación que tome una posición concreta del tablero y sea capaz de asignarle una puntuación determinada que indique de alguna forma quién va ganando la partida y con cuánta ventaja . La idea será entonces ejecutar todos los movimientos de la lista que hemos generado, asignarle una puntuación a las posiciones resultantes y por último ejecutar el movimiento que dé como resultado la posición con mayor puntuación a nuestro favor. Los problemas aparecen cuando tratamos de imaginar una forma sistemática de dar una puntuación a una posición de ajedrez. Obviamente, la calidad de nuestro procedimiento de evaluación será la responsable directa de la fuerza de nuestro programa de ajedrez. Se podría decir que esta función de evaluación es el corazón del programa, si ésta falla, no conseguiremos grandes resultados por muy eficiente que sea el resto. A esto hay que añadir además que la función de evaluación de un programa de este tipo es la parte más artística del desarrollo. No existen métodos preestablecidos para construirlas, aunque ya llegaremos a ello. Sigamos ahora complicando el problema un poco más.

Búsqueda de soluciones

Hasta aquí, ya sabemos esperar a que el usuario haga su jugada y responder nosotros con el mejor movimiento directo que encontremos. Sin embargo, todos sabemos que para jugar bien al ajedrez no sólo debemos fijarnos en la jugada que nos toca hacer inmediatamente, sino que tendremos que prever varias jugadas por adelantado. La aparente mejor jugada justo en el momento en que la hacemos puede no ser la mejor tres movimientos más adelante. Pues bien, un ordenador tiene que ser capaz de hacer esto mismo de una forma sistemática. No podemos conformarnos con generar todas las jugadas directas y elegir la mejor, sino que tendremos que ser capaces de adelantarnos varias jugadas hacia adelante y ver los efectos futuros que tendrá la jugada elegida.

Es pronto para explicar cómo llevaremos esto a cabo, pero podemos adelantar que para hacerlo posible representaremos las sucesiones de movimientos de uno y otro jugador en forma de árbol de forma que podamos ir recorriéndolo asignando puntuaciones a cada rama. Es por esto que a este tipo de procedimientos de búsqueda se les denomina búsqueda en árboles ( tree search ). Veremos en su momento varios procedimientos distintos para realizar esta tarea y algunas técnicas que ayuden a optimizar dichas búsquedas para que consuman menos tiempo de cálculo.

Figura 1: Ciclo de ejecución general del programa