# Algorithme minimax

Un article de Wikipédia, l'encyclopédie libre.
Pour les articles homonymes, voir Théorème min-max.

L'algorithme minimax (aussi appelé algorithme MinMax) est un algorithme qui s'applique à la théorie des jeux[1] pour les jeux à deux joueurs à somme nulle (et à information complète) consistant à minimiser la perte maximum (c'est-à-dire dans le pire des cas). Pour une vaste famille de jeux, le théorème du minimax de von Neumann assure l'existence d'un tel algorithme[2], même si dans la pratique il n'est souvent guère aisé de le trouver. Le jeu de hex est un exemple où l'existence d'un tel algorithme est établie et montre que le premier joueur peut toujours gagner, sans pour autant que cette stratégie soit connue.

Il amène l'ordinateur à passer en revue toutes les possibilités pour un nombre limité de coups et à leur assigner une valeur qui prend en compte les bénéfices pour le joueur et pour son adversaire. Le meilleur choix est alors celui qui minimise les pertes du joueur tout en supposant que l'adversaire cherche au contraire à les maximiser (le jeu est à somme nulle).

Il existe différents algorithmes basés sur MinMax permettant d'optimiser la recherche du meilleur coup en limitant le nombre de nœuds visités dans l'arbre de jeu, le plus connu est l'élagage alpha-bêta. En pratique, l'arbre est souvent trop vaste pour pouvoir être intégralement exploré (comme pour le jeu d'échecs ou de go). Seule une fraction de l'arbre est alors explorée.

Dans le cas d'arbres très vastes une IA (système expert, évaluation par apprentissage à partir d'exemple, etc.) peut servir à élaguer certaines branches sur la base d'une estimation de leur utilité. C'est ce qui est employé, par exemple, dans le cadre du go.

## Principe[modifier | modifier le code]

L'algorithme minimax visite l'arbre de jeu pour faire remonter à la racine une valeur (appelée « valeur du jeu ») qui est calculée récursivement de la façon suivante :

- minimax(p) = f(p) si p est une feuille de l’arbre où f est une fonction d’évaluation de la position du jeu ;
- minimax(p) = MAX(minimax( O 1 {\displaystyle O_{1}} ), …, minimax( O n {\displaystyle O_{n}} )) si p est un nœud Joueur avec fils O 1 {\displaystyle O_{1}} , …, O n {\displaystyle O_{n}} ;
- minimax(p) = MIN(minimax( O 1 {\displaystyle O_{1}} ), …, minimax( O n {\displaystyle O_{n}} )) si p est un nœud Opposant avec fils O 1 {\displaystyle O_{1}} , …, O n {\displaystyle O_{n}} .

## Exemple[modifier | modifier le code]

Dans le schéma ci-dessus, les nœuds gris représentent les nœuds joueurs et les bleus les nœuds opposants. Pour déterminer la valeur du nœud A, on choisit la valeur maximum de l’ensemble des nœuds B (A est un nœud joueur). Il faut donc déterminer les valeurs des nœuds B qui reçoivent chacun la valeur minimum stockée dans leurs fils (nœuds B sont opposants). Les nœuds C sont des feuilles, leur valeur peut donc être calculée par la fonction d’évaluation.

Le nœud A prend donc la valeur 5. Le joueur doit donc jouer le coup l’amenant en B2. En observant l’arbre, on comprend bien que l’algorithme considère que l’opposant va jouer de manière optimale : il prend le minimum. Sans ce prédicat, on choisirait le nœud C1 qui propose le plus grand gain et le prochain coup sélectionné amènerait en B1. Mais alors on prend le risque que l’opposant joue C3 qui propose seulement un gain de 3.

En pratique, la valeur théorique de la position P ne pourra généralement pas être calculée. En conséquence, la fonction d’évaluation sera appliquée sur des positions non terminales. On considérera que plus la fonction d’évaluation est appliquée loin de la racine, meilleur est le résultat du calcul. C'est-à-dire qu’en examinant plus de coups successifs, nous supposons obtenir une meilleure approximation de la valeur théorique donc un meilleur choix de mouvement.

## Simplification negamax[modifier | modifier le code]

Si l’ensemble des valeurs prises par f(p) est symétrique par rapport à 0[1] une fonction g(p) peut être définie telle que :

- g(p) = f(p) si nous sommes sur un nœud joueur
- g(p) = - f(p) si nous sommes sur un nœud opposant

Ainsi on définit negamax à partir de cette nouvelle fonction :

- Negamax(p) = g(p) si P est terminale
- Negamax(p) = max(-NegaMax( p i {\displaystyle p_{i}} )) sinon

À partir du même exemple que pour l’algorithme Minmax, voici l'arbre résultant :

## Élagage alpha-bêta[modifier | modifier le code]

Cet algorithme peut être optimisé grâce à l'implémentation de la technique dite de l'élagage alpha-bêta[1].

## Annexes[modifier | modifier le code]

## Notes[modifier | modifier le code]

1. ↑ a, b et c Jean-Marc Alliot et Thomas Schiex, « La programmation des jeux », dans Intelligence artificielle et Informatique théorique, Cepadues, 1994 (ISBN 2-85428-324-4)
2. ↑ Mais si les joueurs ne connaissent pas les coups joués par leur adversaire, comme dans le jeu pierre-feuille-ciseaux, cet algorithme ne conduit qu'à des stratégies demandant l'utilisation du hasard; voir l'article sur le théorème pour plus de détails

### Bibliographie[modifier | modifier le code]

- A. Aho, J. Hopcroft, J. Ullman, Structures de données et algorithmes, Paris, InterEditions, 1987, 450 p. (ISBN 2-7296-0194-5), « Conceptions et stratégies algorithmiques »

### Articles connexes[modifier | modifier le code]

- Fonction convexe-concave
- Point col
- Théorème du minimax de von Neumann
- Recherche arborescente Monte-Carlo
- Élagage alpha-bêta

### Lien externe[modifier | modifier le code]

- (en) explication de l'algorithme minimax pour le jeu de tron dans le cadre d'un google ai challenge [archive]

[masquer] v · m Théorie des jeux
Définitions | Jeu sous forme normale · Extensive-form game (en) · Escalation of commitment (en) · Graphical game (en) · Jeu coopératif · Succinct game (en) · Information set (en) · Hierarchy of beliefs (en) · Préférence
Équilibre économique (concepts) | Équilibre de Nash · Équilibre parfait en sous-jeux · Mertens-stable equilibrium (en) · Bayesian Nash equilibrium (en) · Jeu bayésien · Trembling hand (en) · Proper equilibrium (en) · Epsilon-equilibrium (en) · Équilibre corrélé · Équilibre séquentiel · Quasi-perfect equilibrium (en) · Stratégie évolutivement stable · Risk dominance (en) · Core (en) · Valeur de Shapley · Optimum de Pareto · Gibbs equilibrium (en) · Quantal response equilibrium (en) · Self-confirming equilibrium (en) · Strong Nash equilibrium (en) · Markov perfect equilibrium (en)
Stratégies (en) | Dominance stratégique · Pure strategy (en) · Coopération-réciprocité-pardon · Grim trigger (en) · Collusion · Raisonnement rétrograde · Forward induction (en) · Markov strategy (en)
Classes de jeux | Symmetric game (en) · Perfect information (en) · Simultaneous game (en) · Sequential game (en) · Repeated game (en) · Signaling game (en) · Screening game (en) · Conversation libre · Jeu à somme nulle · Théorie des mécanismes d'incitation · Bargaining problem (en) · Stochastic game (en) · n-player game (en) · Large Poisson game (en) · Nontransitive game (en) · Global game (en) · Strictly determined game (en) · Jeu de potentiel
Jeux | Dilemme du prisonnier · Optional prisoner's dilemma (en) · Traveler's dilemma (en) · Coordination game (en) · Chicken (en) · Jeu du mille-pattes · Volunteer's dilemma (en) · Dollar auction (en) · Jeu de la guerre des sexes · Stag hunt (en) · Matching pennies (en) · Jeu de l'ultimatum · Pierre-papier-ciseaux · Jeu du pirate · Jeu du dictateur · Public goods game (en) · Blotto game (en) · War of attrition (en) · Problème du bar d'El Farol · Partage équitable · Fair cake-cutting (en) · Cournot game · Deadlock (en) · Diner's dilemma (en) · Guess 2/3 of the average (en) · Kuhn poker (en) · Nash bargaining game (en) · Prisoners and hats puzzle (en) · Trust game (en) · Princess and Monster game (en) · Monty Hall problem (en) · Rendezvous problem (en)
Theorèmes | Algorithme minimax · Équilibre de Nash · Purification theorem (en) · Folk theorem (en) · Revelation principle (en) · Théorème d'impossibilité d'Arrow
Personnalités | Albert W. Tucker · Amos Tversky · Ariel Rubinstein · Daniel Kahneman · David K. Levine (en) · David M. Kreps · Donald B. Gillies (en) · Drew Fudenberg (en) · Eric Maskin · Harold W. Kuhn · Herbert Simon · Hervé Moulin · Jean Tirole · Jean-François Mertens (en) · John Harsanyi · John Maynard Smith · Antoine-Augustin Cournot · John Nash · John von Neumann · Kenneth Arrow · Kenneth Binmore · Leonid Hurwicz · Lloyd Shapley · Melvin Dresher (en) · Merrill M. Flood (en) · Oskar Morgenstern · Paul Milgrom · Peyton Young (en) · Reinhard Selten · Robert Axelrod · Robert Aumann · Robert B. Wilson (en) · Roger Myerson · Samuel Bowles (en) · Thomas Schelling · William Vickrey
Voir aussi | All-pay auction (en) · Élagage alpha-bêta · Bertrand paradox (en) · Rationalité limitée · Théorie des jeux combinatoires · Confrontation analysis (en) · Coopétition · List of game theorists (en) · List of games in game theory (en) · No-win situation (en) · Topological game (en) · Tragédie des biens communs · Tyrannie des petites décisions

- Portail de l'informatique théorique
- Portail de la programmation informatique

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Algorithme_minimax&oldid=146574510 ».
Catégories :

- Théorie des jeux
- Algorithme d'optimisation
- Intelligence artificielle

[+]
Catégories cachées :

- Article contenant un appel à traduction en anglais
- Portail:Informatique théorique/Articles liés
- Portail:Informatique/Articles liés
- Projet:Mathématiques/Articles
- Portail:Programmation informatique/Articles liés