Shéma de l'algorithme MinMax

Comme j'ai un peu de mal à bien saisir l'algorithme, je vous envoie juste le schéma (la seule chose que j'ai bien comprise).
J'ai aussi posté le shéma de l'algorithme alpha beta pour comparer...



Voilà, en espérant que c'est aussi clair pour vous que pour moi...

Finalement, je vous montre l'algorithme que j'avais trouvé et que je ne comprends pas en entier...

• MiniMax(p)=h(p) si p est une position terminale
  
• MiniMax(p)=max(MiniMax(o1), ..., MiniMax(on)) si p est une position joueur avec fils o1, ..., on
  
• MiniMax(p)=min(MiniMax(j1), ..., MiniMax(jm)) si p est une position opposant avec fils j1, ..., jm
  

On peut vérifier que MiniMax(p) est la meilleure valeur possible à partir de la position p, si l'opposant joue de façon optimale. Il est clair que pour appliquer l'algorithme MiniMax il suffit de disposer de

• un type de données position qui permet de représenter les états possibles du jeu (et une position initiale) ;
  
• une fonction h : position R union +-infini pour évaluer les positions terminales ;
  
• une fonction estjoueur : position ® {oui, non} qui sert à déterminer si une position est une position joueur ou opposant ;
  
• une fonction accessibles qui prenne une position p et retourne la liste des positions accessibles par les coups disponibles à partir de p.
  

Cela nous donne notre interface C :

/* les positions */
struct position {
. . . /* Ceci dépend du jeu
* et ne doit pas être utilisé par la visite de l'arbre */
};

typedef struct position *position;

/* une liste de positions */
typedef struct {
> int nombre;
> position *tableau;
> /* On utilise un tableau, dont le nombre d'éléments est ci-dessus */
>/* Les coups à jouer sont représentés par leur position dans le tableau */
} posliste;

/* enfin, les fonctions propres au jeu */
double h(position p);
int estjoueur(position p);
posliste accessibles(position p);

/* plus une fonction qui permet de libérer de la mémoire */
void libere(posliste pl);
hum, hum... voilà :S

Désolé si je viens encore tout critiquer, mais là, ce n'est pas vraiment l'algorithme. Plutôt une liste de définitions des objets nécessaires à l'algo. Non?

ah oui mdr j'avais oublié de copier collerl'algo aussi

je dis pas que ce site est bien fait, mais ca venait de la:
http://www.di.ens.fr/~granboul/enseignement/mmfai/algo2001-2002/tp5/

L'algorithme ALPHA-BETA peut être décrit par le pseudo-code suivant :

fonnction ALPHA-BETA(P, A, B) /* ici A est toujours inférieur à B */
si P est une feuille alors
retourner la valeur de P
sinon
initialiser Alpha de P à -¥ et Beta de P à +¥
si P est un noeud Min alors
pour tout fils Pi de P faire
Val = ALPHA-BETA(Pi, A, Min(B,Beta de P))
Beta de P = Min(Beta de P, Val)
Si A >= Beta de P /*ceci est la coupure alpha */
alors retourner Beta de P
finfaire
retourner Beta de P
sinon
pour tout fils Pi de P faire
Val = ALPHA-BETA(Pi, Max(A,Alpha de P), B)
Alpha de P = Max(Alpha de P, Val)
Si Alpha de P >= B /*ceci est la coupure beta */
alors retourner Alpha de P
finfaire
retourner Alpha de P

sinon ya celui la:
http://www.emn.fr/x-info/pdavid/Enseignement/IA/poly-ia/jeux/min-max.html

Principe

On suppose que chaque joueur choisira son meilleur coup, le meilleur coup de l'adversaire correspondant au moins bon coup du joueur courant.
On "remonte" de proche en proche les valeurs des feuilles (fins de parties) jusqu'à la racine (position courante) ; on peut ainsi choisir le coup qui mène à la position la plus favorable.

Algorithme

1. si n est terminal alors CV <- eval(n)
2. sinon pour i de 1 à j faire // j = nb de fils de n
(a) Générer fi , ie fils de n
(b) si k = 1
alors CV <- V(fi)
sinon // i >= 2
si n noeud min alors CV <- min(CV, V(fi))
si n noeud max alors CV <- max(CV, V(fi))
3. retourner CV

Exemple

Je vous laisse en trouver de mieux

Pour l'utilisation probable qu'on en fera, voir dans la partie compte-rendu et avancement / réunion du 15 novembre

Je pense que ça interviendra au niveau de la fonction cherchant quels sont les chemins possibles, mais peut-être bien que je n'ai plus les yeus en face des trous pour ce soir...