Aunque el árbol de juego tenga una profundidad limitada, con unos pocos niveles (cuatro o cinco), podemos estar hablando de millones de tableros. Téngase en cuenta que el crecimiento en el número de tableros es exponencial con la profundidad. Cada tablero dará lugar a tantos hijos como el número de jugadas posibles, y así sucesivamente en cada nivel. Por tanto:
Número de tableros = (número de jugadas posibles) ^ profundidad
El número de jugadas posibles depende del juego y sus reglas. Por ejemplo, en el caso del ajedrez, si nos centramos en el tablero de inicio, hay veinte jugadas posibles (8 peones x 2 movimientos + 2 caballos x 2 movimientos = 20). No todos los tableros tendrán el mismo número de jugadas posibles, pero de forma estimativa, si asumimos ese valor y cinco niveles, tenemos:
Número de tableros = 20 x 20 x 20 x 20 x 20 = 20 ^ 5 = 3,2 millones
En este contexto, interesa podar todas las ramas del árbol que se pueda, aquellas que no tenga sentido analizar. No es obligatorio podar el árbol, pero sí una opción muy interesante.
Para poder podar el árbol hay que evaluarlo según se va construyendo. Si el programa se diseña de tal modo que primero se construye el árbol completo y luego se evalúa, no tiene tanto sentido podarlo, ya que ya se habrá incurrido en el coste de construirlo.
Supongamos que tenemos una situación como ésta:
Es decir, la rama 1 del árbol ya ha sido desarrollada y evaluada, y ha arrojado un valor de 200. Si al empezar a desarrollar la rama 2 surge un tablero con un valor de 300, dado que es el turno de las blancas, elegirán ese tablero u otro con valor superior. Por tanto, esa rama 2 ya nunca va a interesar a las negras, y puede dejar de construirse y evaluarse.
A mi entender, son situaciones un poco difíciles de detectar, y sólo compensa intentarlo cuando la profundidad de análisis es alta, porque es cuando más ahorro puede suponer.
No hay comentarios:
Publicar un comentario