2.4 Búsqueda adversaria

2.4.1 Algoritmo minimax

Minimax es un procedimiento de Búsqueda primero en profundidad, siendo ésta la estrategia principal para árboles de juego.

Minimax busca para abajo hasta cierta profundidad y trata a los nodos de dicho nivel de profundad como si fueran nodos terminales.

pInvoca una función heurística denominada función de evaluación estática, heurística o función de utilidad, para determinar los valores de esos nodos terminales.

• ¿Completo? Sí, cuando el juego es finito (en el ajedrez hay reglas que impiden un juego infinito)

• ¿Óptimo? Sí, cuando el adversario juega perfectamente - en el otro caso Minimax es sub-óptimo

• ¿Complejidad temporal? O(b^m)

• ¿Complejidad espacial? O(m) - se trata de una exploración de tipo búsqueda primero en profundidad, ahorrativa de memoria.

  • Los problemas asociados con la técnica minimax son:

• Cuándo cortar la búsqueda para llamar a la función de evaluación estática.

• Qué función de evaluación elegir.

  • Interesa además

• Cuán prometedora es la ruta.

• Cuánto tiempo tiene la computadora para decidir.

Árbol de juego general usando minimax.

Juego del gato.

Estados: tablero más fichas.

Estado inicial: tablero más ficha inicial.

Estados finales: tableros llenos o con línea ganadora.

Movimientos: 9 movimientos máximo posibles por jugada, uno por casilla.

Aplicación de movimientos: aplicable si la casilla no está ocupada.

Función de utilidad o heurística:

• 1 si es “ganador” para MAX.

• 0 si es empate.

• -1 si es “ganador para MIN.

Juego del gato (cont.)

• Función heurística: H(n)=M(n)-O(n)

• M(n) es el número de mis posibles líneas ganadoras (contando las vacías)

• O(n) es el número de sus posibles líneas ganadoras (contando las vacías).

• Si al final +: MAX gana

• Si al final - : MIN gana.

Juego del gato (cont.)

MIN tira donde tiene mayores

posibilidades.

3ª tirada de MAX

• Con estas reglas para analizar tiradas, seguramente se llega a un empate entre jugadores.

• Se crean árboles completos (primero en anchura).

• Ya creado el árbol se evalúa la función heurística.

• Para un juego más complejo es ineficiente crear árboles completos.

2.4.2 Poda alfa-beta

• Optimización de minimax.

• Búsqueda primero en profundidad, evaluando la heurística.

• Para cada nodo MAX se calcula un valor alfa.

Para cada nodo MIN se calcula un valor beta.

Ejercicio