Búsqueda minimax

Ya sabemos generar los movimientos posibles para ambos bandos, tenemos unas estructuras de datos (tablas hash) donde guardar el mejor movimiento para cada tablero (siendo la secuencia de esos mejores movimientos la variante principal), sabemos desarrollar el árbol de juego (probar movimientos con “makeMove” y deshacerlos con “takeBack”) y ya, por último, somos capaces de evaluar las hojas del árbol con la función de evaluación. Por tanto, tenemos todas las piezas para montar la búsqueda, es decir, el proceso por el cual el C64 decidirá su siguiente jugada.

Hasta ahora, hemos dicho que ese proceso de búsqueda sería minimax, es decir, un proceso consistente en:

• Desarrollar el árbol de juego hasta las hojas.
• Aplicar la función de evaluación sobre las hojas.
• Hacer subir la evaluación hacia la raíz, seleccionando el máximo o el mínimo en función del turno de juego (ratón = máximo, gatos = mínimo).

Esto se puede hacer, y funciona, pero tiene un problema: el factor de ramificación.

El factor de ramificación es el número de tableros hijo que tiene un tablero. De media, si mueve el ratón, el factor de ramificación será cuatro, porque hay cuatro movimientos posibles, y si mueven los gatos será ocho, porque hay dos movimientos posibles por cuatro gatos. Al final, si la profundidad de análisis es ocho, eso nos da:

4 x 8 x 4 x 8 x 4 x 8 x 4 x 8 ≈ 1 millón de tableros

Es decir, habría que generar y evaluar más de un millón de tableros. Y eso a profundidad máxima (ocho), sin tener en cuenta los tableros intermedios a profundidad siete, a profundidad seis, a profundidad cinco, etc.

Total, aunque estemos hablando de poco tiempo para generar y evaluar cada tablero, al multiplicar por un millón de tableros, nos vamos a bastantes minutos. Téngase en cuenta que el C64 es un ordenador de 1 MHz.

La conclusión es que no podemos generar y evaluar el árbol completo. No es viable. Hay que podarlo. Y aquí es donde entra la búsqueda alfa – beta que veremos en las entradas que siguen.