Árbol de juego, búsqueda, variante principal y variante actual

Todos estos juegos de tablero, da un poco igual de qué juego se trate (ej. ajedrez, damas, Othello, etc.) o de los detalles de su implementación, se basan en los mismos principios:

• Partiendo de la posición actual (raíz), el programa genera todos los movimientos posibles.
• El proceso anterior se repite recursivamente hasta una profundidad N, dando lugar a un árbol de jugadas.
• El árbol de jugadas se evalúa. Se parte de las hojas (tableros a profundidad N) aplicándoles una función de evaluación que establece cómo de buenos o malos son esos tableros para un bando y para el otro.
• Las evaluaciones se llevan desde las hojas hasta la raíz aplicando un procedimiento llamado “minimax”, que consiste en suponer que ambos bandos elegirán su mejor jugada cuando sea su turno. Un bando elegirá las jugadas que maximizan la puntuación, y el otro las que la minimizan. De ahí el nombre “minimax”.
• En ocasiones, se podan las ramas del árbol que no interesa analizar. Esto es muy importante para que el rendimiento sea bueno.
• Finalmente, el ordenador elige su mejor jugada, lo que da lugar a una nueva posición actual.
• Si el ordenador juega contra sí mismo se repite el proceso anterior desde la nueva posición actual. Si juega contra un humano se le pide su jugada.

Desde un punto de vista gráfico sería algo así:

Al proceso anterior se le denomina “búsqueda”, puesto que en el fondo lo que hace el ordenador es buscar la mejor jugada para su bando, asumiendo que el bando contrario también optará por su mejor jugada. La búsqueda puede ser “minimax” pura o, si incluye poda, puede ser búsqueda alfa – beta. Los detalles los veremos más adelante.

El resultado de la búsqueda, en realidad, no es sólo la siguiente jugada (en el caso del árbol anterior la jugada hacia la derecha que da lugar a un tablero valorado en 3), sino la secuencia de jugadas de uno y otro bando desde la raíz hasta una hoja. Es lo que se llama la “variante principal”, y en el fondo no es más que la “ruta” que el ordenador piensa que va a seguir la partida con los datos conocidos hasta ese momento, que siempre son imperfectos, porque la profundidad de análisis no es infinita:

En un momento dado de la ejecución, el programa estará generando y/o evaluando un determinado tablero del árbol. La ruta desde la raíz hasta ese tablero que se está generando y/o evaluando es lo que se llama la “variante actual”.

Todo lo anterior (el árbol de juego, la búsqueda “minimax” o alfa-beta, la variante actual, la variante principal, etc.) son ideas teóricas, son conceptos. Luego hay diferentes formas de implementarlas o llevarlas a la práctica.

Por ejemplo, alguien podría plantearse desarrollar todo el árbol de juego completo, almacenarlo en memoria, evaluarlo y elegir la siguiente jugada. No es la mejor opción, en primer lugar, porque consume mucha memoria (se almacena el árbol completo) y, en segundo lugar, porque no admite poda. La poda se hace en función de las evaluaciones y, aunque fuera posible hacerla en algunas circunstancias, con el árbol completo en memoria ya no tendría sentido hacerlo, porque ya se habría incurrido en el coste de construirlo y almacenarlo.

Por todo ello, en la práctica el árbol de juego se construye y se evalúa sobre la marcha, según se va construyendo. La construcción del árbol se hace “en profundidad”, es decir, primero se desarrolla la primera rama completa hasta la primera hoja, luego la segunda rama completa hasta la segunda hoja, etc. Y se va podando lo que, en función de las evaluaciones, no tiene sentido construir o desarrollar.

Es más, con un único tablero de 64 bytes es suficiente para gestionar el árbol de juego completo. Con ese tablero almacenamos la posición actual de la partida y, cuando toca decidir la siguiente jugada, generamos los movimientos posibles y los vamos “probando” y deshaciendo. Probarlos consiste en ejecutarlos o aplicarlos hasta la profundidad de análisis, evaluar las hojas con la función de evaluación, aplicar “minimax” para propagar las evaluaciones hacia la raíz, podar las ramas que se puedan podar, determinar la variante principal, y elegir el siguiente movimiento.

Por tanto, aunque desde un punto de vista conceptual el programa desarrolla y evalúa un árbol de jugadas, en la práctica todo se maneja con un único tablero. Todo esto quedará más claro según vayamos avanzando con el proyecto.