El procedimiento de poda

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:

Poda

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.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s