Algoritmo MiniMax

MINIMAX

Este algoritmo de decisión se utiliza para minimizar la pérdida máxima aplicada en juegos entre adversarios. La Información es completa ya que cada jugador conoce el estado del otro, y puede elegir el mejor movimiento para cada jugador, suponiendo que el contrincante escogerá el peor. Devuelve la acción correspondiente al movimiento mejor posible, es decir, el movimiento que conduce al resultado con la mejor utilidad, conforme al axioma que el oponente juega para minimizar la utilidad. Las funciones Valor-Max y el Valor-Min pasan por el árbol de juegos enteró, por todos los caminos hacia las hojas, para determinar el valor que le llega a un estado.

El algoritmo MINIMAX es un procedimiento recursivo y el corte de la recursión está dado por alguna de las siguientes condiciones: Gana algún jugador Se han explorado N capas, siendo N el límite establecido Se ha agotado el tiempo de exploración Se ha llegado a una situación estática donde no hay grandes cambios de un nivel a otro.

ALGORITMO MINIMAX • Posición inicial.

• Conjunto de operadores o reglas del juego (definen movimientos legales)

• Estado terminal

 • Función de utilidad, ej. gana, pierde, empata

PASOS DEL ALGORITMO MINIMAX

1. Generar el árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal.

2. Calcular los valores de la función de utilidad para cada nodo terminal.

3. Calcular el valor de los nodos superiores a partir del valor de los inferiores. Alternativamente se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente, de ahí el nombre de MINIMAX.

4. Elegir la jugada valorando los valores que han llegado al nivel superior.

Ejemplo de minimax

PODA ALFA-BETA

La poda alfa beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go.

El problema de la búsqueda Minimax es que el número de estados a explorar es exponencial al número de movimientos. Partiendo de este hecho, la técnica de poda alfa-beta trata de eliminar partes grandes del árbol, aplicándolo a un árbol Minimax estándar, de forma que se devuelva el mismo movimiento que devolvería este, gracias a que la poda de dichas ramas no influye en la decisión final.

EJEMPLO

EJERCICIO 

Algoritmo MiniMax

posición inicial 

PASOS DEL ALGORITMO MINIMAX

1. Generar el árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal.

2. Calcular los valores de la función de utilidad para cada nodo terminal.

3. Calcular el valor de los nodos superiores a partir del valor de los inferiores. Alternativamente se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente, de ahí el nombre de MINIMAX.

4. Elegir la jugada valorando los valores que han llegado al nivel superior.

Posición final 

https://es.wikipedia.org/wiki/Poda_alfa-beta

https://es.slideshare.net/JeffoG92/algoritmo-minimax