Minimax (parfois Minmax, MM ou point de selle) est une règle de décision utilisée en intelligence artificielle, en théorie de la décision, en théorie des jeux combinatoires, en statistique et en philosophie. Elle vise à minimiser la perte possible dans un scénario de pire cas (perte maximale). Lorsqu'il s'agit de gains, on parle de « maximin » – pour maximiser le gain minimal. Initialement formulée pour la théorie des jeux à somme nulle avec plusieurs joueurs, couvrant à la fois les cas où les joueurs effectuent des mouvements alternés et ceux où ils effectuent des mouvements simultanés, elle a également été étendue à des jeux plus complexes et à la prise de décision générale en présence d'incertitude.
Le concept est central dans les contextes adversariaux, où le gain d'un joueur est la perte d'un autre. Dans de tels contextes, minimax fournit une stratégie conservatrice : supposer que l'adversaire choisira toujours l'action la plus défavorable pour vous, et sélectionner le mouvement qui maximise votre gain garanti. Ce principe sous-tend de nombreux algorithmes en apprentissage automatique et en apprentissage profond, en particulier dans l'entraînement de modèles génératifs et la conception de systèmes robustes.
Fondements de la théorie des jeux
En théorie des jeux, la valeur maximin est la valeur la plus élevée qu'un joueur peut être sûr d'obtenir sans connaître les actions des autres joueurs ; de manière équivalente, c'est la valeur la plus basse que les autres joueurs peuvent forcer le joueur à recevoir lorsqu'ils connaissent son action. La définition formelle est : v_i_underline = max_{a_i} min_{a_{-i}} v_i(a_i, a_{-i}), où i est l'indice du joueur, a_i est l'action prise par le joueur i, a_{-i} désigne les actions de tous les autres joueurs, et v_i est la fonction de valeur du joueur i.
Le calcul de la valeur maximin utilise une approche de pire cas : pour chaque action possible du joueur, examiner toutes les actions possibles des autres et déterminer la combinaison la plus défavorable – celle donnant la plus petite valeur. Ensuite, choisir l'action qui rend cette plus petite valeur aussi élevée que possible. Par exemple, considérons un jeu à deux joueurs où le joueur en ligne peut choisir T, M ou B, et le joueur en colonne peut choisir L ou R, avec des gains présentés dans un tableau. Le joueur en ligne peut jouer T, garantissant un gain d'au moins 2 (B est risqué avec −100, M peut donner −10), donc v_ligne_underline = 2. Le joueur en colonne peut jouer L, sécurisant au moins 0 (R risque −20), donc v_colonne_underline = 0. Si les deux jouent leurs stratégies maximin (T, L), le vecteur de gains est (3, 1).
La valeur minimax d'un joueur est la plus petite valeur que les autres joueurs peuvent forcer le joueur à recevoir, sans connaître ses actions ; de manière équivalente, c'est la plus grande valeur que le joueur peut être sûr d'obtenir lorsqu'il connaît les actions des autres. Sa définition formelle est : v_i_overline = min_{a_{-i}} max_{a_i} v_i(a_i, a_{-i}). Dans les jeux à somme nulle, la valeur minimax est égale à la valeur maximin pour chaque joueur, ce qui conduit au théorème du minimax.
Théorème du minimax et jeux à somme nulle
Le théorème du minimax, prouvé par John von Neumann en 1928, stipule que dans les jeux finis, à deux joueurs et à somme nulle avec des stratégies mixtes, la valeur maximin est égale à la valeur minimax. Ce théorème fournit une base pour l'analyse de l'équilibre. Dans de tels jeux, la valeur du jeu est le gain attendu lorsque les deux joueurs jouent de manière optimale. Le théorème garantit qu'un joueur peut s'assurer au moins cette valeur, et que l'adversaire peut le limiter à au plus cette valeur.
Pour les jeux à mouvements simultanés, le concept s'étend aux stratégies mixtes, où les joueurs randomisent sur des actions pures. Le théorème du minimax garantit l'existence d'un point de selle en stratégies mixtes, qui est une paire de stratégies où aucun joueur ne peut améliorer son gain en déviant unilatéralement. Ce résultat est fondamental dans l'entraînement des réseaux de neurones, où les exemples adversariaux sont analysés en utilisant des principes de pire cas similaires.
Applications en intelligence artificielle
En IA, minimax est largement utilisé dans la prise de décision pour les jeux et les scénarios adversariaux. L'exemple classique est l'algorithme minimax pour les jeux à deux joueurs au tour par tour comme les échecs, les dames ou le morpion. L'algorithme évalue récursivement l'arbre de jeu, en supposant que l'adversaire joue de manière optimale. À chaque nœud, le joueur choisit le mouvement qui maximise son gain minimal, tandis que l'adversaire choisit le mouvement qui minimise le gain maximal du joueur. Cela est souvent combiné avec l'élagage alpha-bêta pour réduire la complexité computationnelle.
Dans les grands modèles de langage et les architectures transformers, les principes minimax apparaissent dans l'entraînement adversarial, où les modèles sont entraînés pour être robustes contre les perturbations de pire cas. Par exemple, les réseaux adversariaux génératifs (GAN) utilisent un objectif minimax : le générateur essaie de minimiser la capacité du discriminateur à distinguer les données réelles des fausses, tandis que le discriminateur essaie de maximiser sa précision. Ce processus adversarial est une application directe de minimax en apprentissage profond.
Extensions et variations
Minimax a été étendu à des jeux plus complexes, y compris les jeux avec hasard (comme le backgammon) en utilisant l'expectiminimax, et les jeux à information imparfaite en utilisant des techniques comme la minimisation du regret contrefactuel. En apprentissage par renforcement, minimax est utilisé dans le contrôle robuste et les contextes multi-agents, où les agents doivent tenir compte du comportement adverse de pire cas. Le concept apparaît également en optimisation et en statistique, où les estimateurs minimax minimisent le risque maximal.
Dans les échecs informatiques et d'autres IA de jeu, minimax avec élagage alpha-bêta reste une technique centrale, bien que les systèmes modernes comme OpenAI et Google DeepMind utilisent souvent des approches d'apprentissage automatique qui intègrent des objectifs de type minimax. Le principe est également pertinent en théorie de la décision pour choisir des actions sous incertitude, où un décideur sélectionne l'option qui minimise la perte de pire cas.
Contexte historique et concepts connexes
La règle minimax a ses racines dans la théorie des jeux et la théorie de la décision, avec des contributions de mathématiciens comme John von Neumann et Oskar Morgenstern. Elle est étroitement liée au concept de point de selle en optimisation et à l'équilibre de Nash dans les jeux à somme non nulle. En philosophie, minimax est utilisé dans les discussions sur la rationalité et l'aversion au risque.
Dans l'IA moderne, minimax est souvent contrasté avec la théorie de la décision bayésienne, qui utilise des probabilités a priori plutôt que des hypothèses de pire cas. Alors que minimax est conservateur, les méthodes bayésiennes peuvent être plus flexibles. Le choix entre elles dépend de la disponibilité d'informations probabilistes. Dans la recherche en IA, minimax reste une référence pour évaluer les algorithmes de prise de décision, en particulier dans les environnements adversariaux.
Voir aussi
- Élagage alpha-bêta
- Théorie des jeux
- Jeu à somme nulle
- Apprentissage automatique adversarial