Minimax


Minimax

Algorithme MinMax

L'algorithme MinMax est un algorithme qui s'applique à la théorie des jeux pour les jeux à deux joueurs à somme nulle. Pour une vaste famille de jeux, le théorème du minimax de von Neumann assure l'existence d'un tel algorithme, 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 joueurs 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-beta. En pratique, l'arbre est souvent trop vaste pour pouvoir être intégralement exploré (comme par exemple pour le jeu d'échecs ou de go). Seul une fraction de l'arbre est alors explorée.

Sommaire

Principe

L'algorithme MinMax est très simple : on 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 :

  • MinMax(p) = f(p) si p est une feuille de l’arbre où f est une fonction d’évaluation de la position du jeu
  • MinMax(p) = MAX(MinMax(O1), ..., MinMax(On)) si p est un nœud Joueur avec fils O1, ..., On
  • MinMax(p) = MIN(MinMax(O1), ..., MinMax(On)) si p est un nœud Opposant avec fils O1, ..., On

Exemple

Min Max Sample 1.png

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.

Min Max Sample 2.png

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

Si l’ensemble des valeurs prises par f(p) est symétrique par rapport à 0 alors nous pouvons définir une fonction g(p) 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(pi)) sinon

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

Min Max Sample 3.png

Optimisation Alpha-Beta

Cet algorithme peut être optimisé grâce à l'implémentation de la technique dite de l'élagage alpha-beta.

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Algorithme MinMax ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Minimax de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • MINIMAX — bzw. Mini Max bezeichnet: Min Max Theorem, ein Spezialfall des Existenzsatzes für Nash Gleichgewichte für Zwei Personen Nullsummenspiele Minimax Algorithmus, ein Algorithmus zur Berechnung solcher Gleichgewichte für Spiele mit perfekter… …   Deutsch Wikipedia

  • Minimax — bzw. Mini Max bezeichnet: Minimax Regel, eine Entscheidungsregel Min Max Theorem, ein Spezialfall des Existenzsatzes für Nash Gleichgewichte für Zwei Personen Nullsummenspiele Minimax Algorithmus, ein Algorithmus zur Berechnung solcher… …   Deutsch Wikipedia

  • Minimax — Minimax, Handfeuerlöschapparat, der, ähnlich wie die in Bd. 3, S. 779 ff. beschriebenen, mittels Gasdrucks einen Wasserstrahl auf 8–10 m Entfernung schleudert. Das kegelförmig gestaltete, in verschiedenen Größen aus verbleitem Eisenblech… …   Lexikon der gesamten Technik

  • minimax — [minimaks] n. m. ÉTYM. Mil. XXe; angl. minimax, 1941, d abord min max, 1928, J. von Neumann, de mini(mum), et maxi(mum). ❖ ♦ Math. Dans la théorie des jeux, plus petit des maximums représentant la perte ou le risque encourus (→ Minimisation, cit …   Encyclopédie Universelle

  • minimax — abbr. minimassimo …   Dizionario italiano

  • minimax — / minimaks/ s.m. [dal lat. scient. mini (mum ) max(imum ) minimo massimo ]. (matem.) [il minimo tra i massimi: il m. di una funzione ] ▶◀ mini massimo …   Enciclopedia Italiana

  • minimax — [min′ē maks΄, min′imaks΄] adj. of or having to do with a strategy or technique for minimizing the maximum error or loss n. such a strategy or technique …   English World dictionary

  • Minimax — This article is about the decision theory concept. For other uses, see Minimax (disambiguation). Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a… …   Wikipedia

  • Minimax — Para otros usos de este término, véase Minimax (infantil). En teoría de juegos, Minimax es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta. Minimax es un algoritmo recursivo. El… …   Wikipedia Español

  • Minimax — En teoría de juegos Minimax es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta. Minimax es un algoritmo recursivo. El funcionamiento de Minimax puede resumirse como elegir mejor… …   Enciclopedia Universal