El generador de jugadas es el programa que desarrolla el árbol. Partiendo del tablero actual (raíz del árbol), va generando jugadas de las diferentes piezas, y va dando lugar a nuevos tableros hijo. Y así sucesivamente, alternando bandos, hasta una profundidad N (profundidad de análisis), que normalmente es configurable.
El árbol tiene que tener una profundidad limitada porque, obviamente, ni la memoria del ordenador es ilimitada, ni el juego puede tardar un tiempo excesivo en decidir la siguiente jugada.
Si el ordenador tuviera tanta memoria como para almacenar el árbol de juego completo, y tanta capacidad de cálculo como para generarlo y tomar una decisión en un tiempo razonable, entonces estos programas serían invencibles o llevarían siempre a tablas (si el juego tuviera algún tipo de limitación o característica intrínseca que lo abocara a acabar en tablas si ambos jugadores jugaran de manera perfecta). Desde luego no es el caso del C64, que tiene 64 KB de memoria y 1 MHz de frecuencia de reloj.
Los tableros
Para que el generador de jugadas pueda generar tableros, lo primero que necesitamos es una forma de representar los tableros y las piezas. Y la forma más sencilla es mediante una matriz de M x M posiciones donde cada posición almacena (cualquier otra codificación sería válida):
- 0 si la casilla está vacía.
- 1, 2, 3, …, para las diferentes piezas de un bando.
- -1, -2, -3, …, para las diferentes piezas del otro bando.
Por ejemplo, para el juego de las damas de 8 x 8 (1 = peón blanco; -1 = peón negro):
-1, 0,-1, 0,-1, 0,-1, 0 0,-1, 0,-1, 0,-1, 0,-1 -1, 0,-1, 0,-1, 0,-1, 0 0, 0, 0, 0, 0, 0, 0, 0 0, 0, 0, 0, 0, 0, 0, 0 0, 1, 0, 1, 0, 1, 0, 1 1, 0, 1, 0, 1, 0, 1, 0 0, 1, 0, 1, 0, 1, 0, 1
De este modo, conociendo el tablero de partida, el bando que juega, y las reglas del juego (los movimientos permitidos), es posible generar todos los tableros hijo a los que daría lugar y vincularlos con su padre. Y así sucesivamente alternando los bandos.
La matriz es la solución obvia y la más natural. Pero no es la única ni la más "compacta" (la que menos memoria consume). De hecho, si observáis la matriz anterior comprobaréis que el 62% de las casillas están vacías (0).
¿Seguro que no se puede "comprimir" esa información? Por supuesto que se puede, pero si lo haces se te complicará la generación de jugadas o, más probablemente, tendrás que andar convirtiendo entre tableros comprimidos (el formato a utilizar para almacenar en memoria) y tableros sin comprimir (el formato a utilizar para generar jugadas y evaluar). Es decir, que ahorrarás memoria, pero gastarás más computación. Así es la vida…
No hay comentarios:
Publicar un comentario