6.3.3. Resolución de juegos.
Si el árbol del juego es muy grande o infinito (por ejemplo, en el ajedrez) entonces la función de utilidad debe poder aplicarse sobre situaciones no terminales.
En estos casos, se generará el árbol hasta un nivel determinado y se propagarán los valores de las hojas utilizando la estrategia minimax.
Estrategia minimax:
- En los niveles que son movimientos de A, se maximiza el valor de los hijos.
- En los niveles que son movimientos de B, se minimiza el valor de los hijos.
El objetivo del problema es elegir el siguiente movimiento a realizar por el jugador A.
Solución: escoger el movimiento indicado por el hijo de la raíz con mayor valor.
Estrategia minimax con backtracking
Usando backtracking, realizaremos un recorrido exhaustivo en profundidad del árbol del juego.
Puesto que hay propagación de valores de los nodos hijos a los padres, usaremos una versión recursiva.