El algoritmo Minimax es un algoritmo de retroceso utilizado en la toma de decisiones y la teoría de juegos para determinar el mejor movimiento para un jugador, siempre y cuando su oponente también juegue de manera óptima. Se utiliza comúnmente en juegos de dos jugadores por turnos como el Tres en Raya, Backgammon, Mancala y Ajedrez.
Minimax es una regla de decisión utilizada en IA, teoría de decisiones, teoría de juegos, estadísticas y filosofía para minimizar la pérdida potencial en el peor escenario (pérdida máxima). Cuando se trata de ganancias, se denomina maximin - maximizar la ganancia más baja. Inicialmente desarrollado para la teoría de juegos de suma cero de varios jugadores, se ha ampliado a juegos más complicados y toma de decisiones generales bajo incertidumbre.
Teoría de juegos
Los dos participantes en Minimax se denominan maximizador y minimizador. El maximizador se esfuerza por alcanzar la puntuación máxima, mientras que el minimizador busca alcanzar la puntuación más baja. A cada estado del tablero se le asigna un valor. Si el maximizador tiene la ventaja en una situación particular, la puntuación del tablero suele ser positiva. En esa condición del tablero, si el minimizador tiene la ventaja, suele ser algún número negativo.
Pseudocódigo
A continuación se muestra el pseudocódigo del algoritmo Minimax:
function minimax( node, depth, maximizingPlayer )
if depth = 0 or node is a terminal node then return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max( value, minimax( child, depth − 1, FALSE ) )
return value
else (* minimizing player *)
value := +∞
for each child of node do
value := min( value, minimax( child, depth − 1, TRUE ) )
return value
Funcionamiento
Podemos explicar el funcionamiento del algoritmo Minimax con un ejemplo. A continuación se muestra un ejemplo de un árbol de juego que ilustra un juego de dos jugadores.
En este ejemplo, hay dos jugadores llamados Maximizador y Minimizador.
El Maximizador se esforzará por obtener la puntuación más alta, mientras que el Minimizador buscará obtener la puntuación más baja.
Este algoritmo utiliza DFS. Por lo tanto, para llegar a los nodos terminales en este árbol de juego, debemos recorrer todas las hojas.
En el nodo terminal, se proporcionan los valores terminales. Por lo tanto, compararemos estos valores y recorreremos el árbol al revés hasta llegar al estado original.
Propiedades
El algoritmo Minimax es completo. Casi con seguridad encontrará una solución (si existe) en el árbol de búsqueda finito.
Si ambos oponentes juegan de manera óptima, el algoritmo Minimax es óptimo.
Complejidad temporal: debido a que realiza DFS para el árbol de juego, la complejidad temporal del algoritmo Minimax es O(bm), donde b es el factor de ramificación del árbol de juego y m es la profundidad máxima del árbol.
Complejidad espacial: el algoritmo Minimax tiene la misma complejidad espacial que DFS, que es O(bm).
La toma de decisiones de Minimax es no probabilística: a diferencia de las decisiones basadas en el valor esperado o la utilidad, no hace suposiciones sobre la probabilidad de los resultados alternativos, en lugar de confiar en el análisis de escenarios de los posibles resultados. A diferencia de estos otros enfoques de elección, es resistente a los cambios en las suposiciones. Otras adaptaciones a este método no probabilístico incluyen el arrepentimiento minimax y la teoría de decisiones de brecha de información.
Además, la desventaja fundamental del algoritmo Minimax es que se vuelve prolongado al jugar juegos complejos como el ajedrez, go, etc. Este estilo de juego presenta un alto factor de ramificación, lo que le da al jugador numerosas opciones. La desventaja del algoritmo Minimax se puede superar mediante la poda alfa-beta.
Si quieres conocer otras notas parecidas a Algoritmo minimax en ia y teoría de juegos puedes visitar la categoría Inteligencia.