Minimax (a veces Minmax, MM o punto de silla) es una regla de decisión utilizada en inteligencia artificial, teoría de la decisión, teoría de juegos combinatorios, estadística y filosofía. Su objetivo es minimizar la posible pérdida en un escenario de peor caso (pérdida máxima). Cuando se trata de ganancias, se denomina 'maximin' – para maximizar la ganancia mínima. Formulado originalmente para la teoría de juegos de suma cero con varios jugadores, cubriendo tanto los casos en que los jugadores realizan movimientos alternos como aquellos en que realizan movimientos simultáneos, también se ha extendido a juegos más complejos y a la toma de decisiones general en presencia de incertidumbre.
El concepto es central en entornos adversariales, donde la ganancia de un jugador es la pérdida de otro. En tales contextos, minimax proporciona una estrategia conservadora: asumir que el oponente siempre elegirá la acción que sea peor para ti, y seleccionar el movimiento que maximice tu pago garantizado. Este principio subyace en muchos algoritmos de aprendizaje automático y aprendizaje profundo, particularmente en el entrenamiento de modelos generativos y el diseño de sistemas robustos.
Fundamentos de la Teoría de Juegos
En teoría de juegos, el valor maximin es el valor más alto que un jugador puede asegurarse obtener sin conocer las acciones de los demás jugadores; equivalentemente, es el valor más bajo que los otros jugadores pueden forzar al jugador a recibir cuando conocen su acción. La definición formal es: v_i_underline = max_{a_i} min_{a_{-i}} v_i(a_i, a_{-i}), donde i es el índice del jugador, a_i es la acción tomada por el jugador i, a_{-i} denota las acciones de todos los demás jugadores, y v_i es la función de valor del jugador i.
Calcular el valor maximin utiliza un enfoque de peor caso: para cada acción posible del jugador, se examinan todas las acciones posibles de los demás y se determina la peor combinación – aquella que da el valor más pequeño. Luego, se elige la acción que haga que este valor más pequeño sea lo más alto posible. Por ejemplo, considérese un juego de dos jugadores donde el jugador de filas puede elegir T, M o B, y el jugador de columnas puede elegir L o R, con pagos mostrados en una tabla. El jugador de filas puede jugar T, garantizando un pago de al menos 2 (B es arriesgado con −100, M puede dar −10), por lo que v_row_underline = 2. El jugador de columnas puede jugar L, asegurando al menos 0 (R arriesga −20), por lo que v_col_underline = 0. Si ambos juegan sus estrategias maximin (T, L), el vector de pagos es (3, 1).
El valor minimax de un jugador es el valor más pequeño que los otros jugadores pueden forzar al jugador a recibir, sin conocer las acciones del jugador; equivalentemente, es el valor más grande que el jugador puede asegurarse obtener cuando conocen las acciones de los demás. Su definición formal es: v_i_overline = min_{a_{-i}} max_{a_i} v_i(a_i, a_{-i}). En juegos de suma cero, el valor minimax es igual al valor maximin para cada jugador, lo que conduce al teorema minimax.
Teorema Minimax y Juegos de Suma Cero
El teorema minimax, demostrado por John von Neumann en 1928, establece que en juegos finitos de dos jugadores y suma cero con estrategias mixtas, el valor maximin es igual al valor minimax. Este teorema proporciona una base para el análisis de equilibrio. En tales juegos, el valor del juego es el pago esperado cuando ambos jugadores juegan de manera óptima. El teorema asegura que un jugador puede garantizar al menos este valor, y el oponente puede limitarlo a como máximo este valor.
Para juegos de movimientos simultáneos, el concepto se extiende a estrategias mixtas, donde los jugadores aleatorizan sobre acciones puras. El teorema minimax garantiza la existencia de un punto de silla en estrategias mixtas, que es un par de estrategias donde ningún jugador puede mejorar su pago desviándose unilateralmente. Este resultado es fundamental en el entrenamiento de redes neuronales, donde los ejemplos adversariales se analizan utilizando principios similares de peor caso.
Aplicaciones en Inteligencia Artificial
En IA, minimax se utiliza ampliamente en la toma de decisiones para juegos y escenarios adversariales. El ejemplo clásico es el algoritmo minimax para juegos de dos jugadores por turnos como ajedrez, damas o tres en raya. El algoritmo evalúa recursivamente el árbol de juego, asumiendo que el oponente juega de manera óptima. En cada nodo, el jugador elige el movimiento que maximiza su ganancia mínima, mientras que el oponente elige el movimiento que minimiza la ganancia máxima del jugador. Esto se combina a menudo con la poda alfa-beta para reducir la complejidad computacional.
En modelos de lenguaje grandes y arquitecturas transformer, los principios minimax aparecen en el entrenamiento adversarial, donde los modelos se entrenan para ser robustos frente a perturbaciones de peor caso. Por ejemplo, las redes generativas adversariales (GANs) utilizan un objetivo minimax: el generador intenta minimizar la capacidad del discriminador para distinguir datos reales de falsos, mientras que el discriminador intenta maximizar su precisión. Este proceso adversarial es una aplicación directa de minimax en aprendizaje profundo.
Extensiones y Variaciones
Minimax se ha extendido a juegos más complejos, incluidos juegos con azar (como backgammon) mediante expectiminimax, y juegos con información imperfecta mediante técnicas como la minimización de arrepentimiento contrafactual. En aprendizaje por refuerzo, minimax se utiliza en control robusto y entornos multiagente, donde los agentes deben tener en cuenta el comportamiento de peor caso del oponente. El concepto también aparece en optimización y estadística, donde los estimadores minimax minimizan el riesgo máximo.
En ajedrez por computadora y otros juegos de IA, minimax con poda alfa-beta sigue siendo una técnica central, aunque los sistemas modernos como OpenAI y Google DeepMind a menudo utilizan enfoques de aprendizaje automático que incorporan objetivos similares a minimax. El principio también es relevante en teoría de la decisión para elegir acciones bajo incertidumbre, donde un decisor selecciona la opción que minimiza la pérdida de peor caso.
Contexto Histórico y Conceptos Relacionados
La regla minimax tiene raíces en la teoría de juegos y la teoría de la decisión, con contribuciones de matemáticos como John von Neumann y Oskar Morgenstern. Está estrechamente relacionada con el concepto de punto de silla en optimización y con el equilibrio de Nash en juegos de suma no cero. En filosofía, minimax se utiliza en discusiones sobre racionalidad y aversión al riesgo.
En la IA moderna, minimax se contrasta a menudo con la teoría de decisión bayesiana, que utiliza probabilidades a priori en lugar de supuestos de peor caso. Mientras que minimax es conservador, los métodos bayesianos pueden ser más flexibles. La elección entre ellos depende de la disponibilidad de información probabilística. En la investigación en IA, minimax sigue siendo un punto de referencia para evaluar algoritmos de toma de decisiones, especialmente en entornos adversariales.
Véase También
- Poda alfa-beta
- Teoría de juegos
- Juego de suma cero
- Aprendizaje automático adversarial