|
| auteur : Alp Mestan |
L'algorithme minimax est un algorithme de jeu qui s'applique lorsqu'il n'y a que 2 joueurs. C'est un algorithme qui consiste
à établir un arbre des situations de jeu : on part de l'état courant du jeu et l'on construis un arbre où chaque noeud enfant est engendré en rajoutant un coup joué au noeud parent. Il est dans cet
algorithme question d'une profondeur de recherche. Il s'agira en fait de donner un score (valeur d'utilité) à chaque noeud
en descendant jusqu'à une certaine profondeur et ensuite de choisir le meilleur score et de jouer selon le chemin qui mène à ce meilleur score.
fonction DECISION-MINIMAX(etat)
retourne une action
entrées : etat (etat courant dans le jeu)
v <- VALEUR-MAX(etat)
retourner l'action dans SUCCESSEURS(etat) ayant la valeur v
fonction VALEUR-MAX(etat)
retourne une valeur d'utilité
si TEST-TERMINAL(etat) alors retourner UTILITE(etat)
v <- -infini
pour a,s dans SUCCESSEURS(etat) faire
v <- MAX(v, VALEUR-MIN(s))
retourner v
fonction VALEUR-MIN(etat)
retourne une valeur d'utilité
si TEST-TERMINAL(etat) alors retourner UTILITE(etat)
v <- +infini
pour a,s dans SUCCESSEURS(etat) faire
v <- MIN(v, VALEUR-MAX(s))
retourner v
|
Ici, TEST-TERMINAL sert à déterminer le moment auquel on désire arrêter la rechercher et à partir duquel
on va choisir quel coup jouer.
Notez également que l'algorithme minimax est aussi régulièrement appelé "minmax".
|
Consultez les autres F.A.Q's
Les sources présentées sur cette page sont libres de droits
et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation
constitue une œuvre intellectuelle protégée par les droits d'auteur.
Copyright © 2008 Developpez Developpez LLC.
Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne
peut être faite de ce site ni de l'ensemble de son contenu : textes, documents
et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez
selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.
