Algoritmo Minimax

ALGORITMO MINIMAX

• Algoritmo de decisión para minimizar la pérdida máxima aplicada en juegos de adversarios
• Información completa (cada jugador conoce el estado del otro)
• Elección del mejor movimiento para cada jugador, suponiendo que el contrincante escogerá el peor
• El espacio de estados se representa mediante árboles alternados, donde:
   Nodo: Representa una situación del juego.
   Sucesores de un nodo: Situaciones del juego a las que se accede por movimientos legales aplicando sus reglas.
   Nivel: Contiene todas las situaciones posibles para uno de los jugadores.

Pasos del algoritmo Minimax: 

Ejemplo algoritmo Minimax:

En el algoritmo Minimax el espacio de búsqueda queda definido por:

Estado inicial: Es una configuración inicial del juego, es decir, un estado en el que se encuentre el juego. Para nuestro ejemplo sería:

 

  Operadores: Corresponden a las jugadas legales que se pueden hacer en el juego, en el caso del tres en raya no puedes marcar una casilla ya antes marcada.

 

 Condición Terminal: Determina cuando el juego se acabó, en nuestro ejemplo el juego termina cuando un jugador marca tres casillas seguidas iguales, ya se horizontalmente, verticalmente o en diagonal, o se marcan todas las casillas (empate) .

 

Función de Utilidad: Da un valor numérico a una configuración final de un juego. En un juego en donde se puede ganar, perder o empatar, los valores pueden ser 1, 0, o -1.