Minimax sur un arbre

Les niveaux alternent : racine max, niveau $1$ min, niveau $2$ max, puis les feuilles.

Niveau $2$ (max) : $\max (3,5)=5$, $\max (6,9)=9$, $\max (1,2)=2$, $\max (0,-1)=0$. Niveau $1$ (min) : $\min (5,9)=5$ et $\min (2,0)=2$. Racine (max) : $\max (5,2)=5$, atteint par le coup de gauche.

Deux lectures, et la seconde compte. La feuille $9$ est la plus grande de l'arbre, et elle n'a aucune influence sur le résultat : elle est sous un nœud min qui lui préférera $5$. Un joueur qui choisit son coup en regardant « la meilleure position atteignable » se trompe systématiquement — c'est le point de minimax : la valeur d'une position n'est pas ce qu'on peut espérer, c'est ce que l'adversaire consentira à laisser.

La faute à ne pas commettre est de remonter la mauvaise opération. Le sous-arbre de droite porte les valeurs max $2$ et $0$ ; le nœud au-dessus est un min, il vaut donc $0$ et non $2$. C'est en écrivant les niveaux avant de calculer — pointe en haut, pointe en bas — qu'on s'évite l'erreur ; le calcul mené par programme confirme les valeurs min $5$ et $0$, et la racine à $5$.