L'algorithme min-max¶

L’algorithme Minimax est une méthode utilisée dans les jeux à deux joueurs (où les joueurs jouent à tour de rôle et ont des intérêts opposés), et on va donc ici aussi l'utiliser. L’objectif de Minimax est de choisir le coup qui garantit le meilleur résultat possible en supposant que l’adversaire joue, lui aussi, de manière optimale.

Principe fondamental¶

Il y a deux joueurs :

MAX : cherche à maximiser le score (c'est l'IA dans notre cas).
MIN : cherche à minimiser le score (c'est l'adversaire, car il veut maximiser son score donc minimiser le notre).

À chaque tour : - Si c’est MAX qui joue, on choisit le mouvement qui donne le score le plus élevé. - Si c’est MIN qui joue, on choisit le mouvement qui donne le score le plus bas.

Arbre de décision¶

Minimax représente la partie comme un arbre :

La racine est la position actuelle du jeu.
Chaque branche représente un coup possible.
Les feuilles (au bas de l’arbre) représentent les positions finales ou approximées.

On évalue les feuilles (même approximativement), puis on remonte les scores vers le haut pour déterminer la meilleure action.

Position actuelle
├─ Coup 1
│    ├─ Réponse 1.1
│    └─ Réponse 1.2
└─ Coup 2
     ├─ Réponse 2.1
     └─ Réponse 2.2

Propagation du score (Min → Max)¶

Lorsque l’arbre est analysé :

Aux nœuds MIN, on garde la plus petite valeur (adversaire qui cherche à nous nuire).
Aux nœuds MAX, on garde la plus grande valeur (notre meilleure opportunité).

Cette alternance se poursuit jusqu’à remonter à la racine. Le coup choisi est celui qui mène au meilleur résultat pour MAX.

Limite pratique¶

Analyser tous les coups possibles dans un jeu réel est souvent impossible (la combinaison d'états devient trop grande).

On limite donc la profondeur d’analyse et on évalue les positions intermédiaires avec notre score d'évaluation heuristique !

Implémentez donc l'algorithme min-max décrit jusqu'ici, en fixant pour l'instant une profondeur l'exploration de 4.

Conseil important¶

Codez une fonction minimax(board, depth, maximizingPlayer, piece_ai="O", piece_human="X") qui

si depth > 0 ou qu'un des 2 joueurs gagne ou que le plateau est plein : renvoie (score de la position, None)
si depth == 0, renvoie (min ou max de minimax(...,depth-1,...), colonne correspondante)

C'est ce qu'on appelle une fonction récursive (càd qui s'appelle elle-même).