Este algoritmo es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta.
MINIMAX realiza una exploración del árbol de búsqueda, de manera que el jugador que debe mover en primer lugar (MAX) tiende a elegir en cada unos de sus movimientos aquel camino que le conduzca a un nodo frontera con el mayor valor posible de la función de evaluación heurística. La estrategia del otro jugador (MIN) es la contraria, ya que tendrá que contrarrestar las decisiones de MAX.
Procedimiento MINIMAX:
MINIMAX(m,profundidad,jugador)
- Si m no tiene sucesores o si se considera que m ha alcanzado el limite de profundidad en profundidad,devolver fev(m) si m es un nodo MAX. En las mismas condiciones anteriores, devolver -fev(m) si m es un nodo MIN.(Para nosotros fev(m) representa lo prometedor que es el nodo m para MAX, independientemente de si m es un nodo MAX o MIN).
- Generar los sucesores m:
- Asignar a la variable mejor el valor mínimo que fev pueda tener(puede ser un valor de referencia previamente establecido).
- mejor = min{fev(j) para todo j}
- Para cada sucesor n de m:
- (1) M(n) = MINIMAX(n,profundidad+1,C(jugador)) - C(jugador) es una función que cambia de jugador.
- (2) mejor = max(-M(n), mejor)
3. Una vez que se han analizado recursivamente todos los sucesores de un determinado nivel(indicado por la variable profundidad), se devuelve el valor mejor.
No hay comentarios:
Publicar un comentario