Jeux à deux joueurs, avec tours alternés, déterministe, à information complète, à somme nulle.
Les deux joureurs s'appelle MAX et MIN. C'est MAX qui commence.
Si le jeux est fini, on peut parcourir tous les états possibles, et utiliser seulement la fonction d'utilité sans heuristique.
La fonction d'utilité `"G"` appliqué à un état terminal `X` décompte le nombre les points gagnants pour MAX selon la règles du jeux, `"G"(X)`. Comme le jeu est à somme nulle, le nombre de points gagnants correspondant pour MIN est `-"G"(X)`.
L'algorithme MINIMAX se résume récursivement comme suit :
| `v:="Valeur_max"(X)` Retourner l'action `a` appartenant à `"A"(X)` telle que "Valeur_min"(R(X,a))` |
| Si `"Fin"(X)` alors retourner `"G"(X)` `v:=-oo` Pour chaque action `a` appartenant à `"A"(X)` faire :
|
| Si `"Fin"(X)` alors retourner `"G"(X)` `v:=+oo` Pour chaque action `a` appartenant à `"A"(X)` faire :
|
C'est un algorithme d'exploration en profondeur d'abord :
`b` : nombre d'actions possibles à chaque état.
`m` : profondeur maximal de l'arbre (nombre maximum de coups dans un jeux)
Complétude : oui si l'arbre est fini.
Optimalité : oui (si l'adversaire est aussi optimal) .
Complexité en temps : `O(b^m)`
Complxité en espace : `O(bm)`
L'algorithme évide de parcourir des parties de l'arbre qui n'ont pas d'influence sur le résultat final.
`alpha` : la valeur du meilleur choix pour MAX dans le pire des cas, trouvée jusqu'ici, où MAX joue en premier.
`beta` : la valeur du meilleur choix pour MIN dans le pire des cas, trouvée jusqu'ici, où MIN joue en premier.
`Decide_max(X)` :| `v:="Valeur_max"(X, -oo,+oo)` Retourner l'action `a` appartenant à `"A"(X)` telle que "Valeur_min"(R(X,a))` |
| Si `"Fin"(X,alpha beta)` alors retourner `"G"(X)` `v:=-oo` Pour chaque action `a` appartenant à `"A"(X)` faire :
|
| Si `"Fin"(X)` alors retourner `"G"(X)` `v:=+oo` Pour chaque action `a` appartenant à `"A"(X)` faire :
|
La complexité intitialement en `O(b^m)` se rapproche de `O(b^(m/2))`
---- 11 juin 2026 ----