Supposons d'abord que le rôle de la stratégie soit pris en charge par une fonction, dite "fonction d'évaluation" qui va donner une note à une position donnée. La note sera d'autant plus élevée et positive lorsque l'ordinateur sera en position favorable, et négative lorsque l'ordinateur sera en mauvaise posture. Une note nulle reflètera une position équilibrée.
Pour CRESUS, cette note sera simplement la différence entre l'argent accumulé par l'ordinateur et celle de son adversaire.
Sans chercher à creuser en profondeur, la meilleure solution pour l'ordinateur est bien de choisir, parmi tous les coups qui lui sont permis, celui qui lui donne une évaluation maximale.
L'ordinateur va donc jouer tous les coups possibles, les uns après les autres. Après avoir joué un coup, il va évaluer la position résultante (lui donner une note). Puis il "déjouera" le coup, pour revenir à la position de départ et pouvoir jouer le coup suivant. Parmi tous les coups, il suffit de choisir celui qui donne une note maximale.
On peut représenter ce raisonnement par le diagramme suivant, que l'on appelera l'arbre du jeu:
Position initiale
Noeud o
| 5
+-----+-----+--+--+-----+-----+
Branches | | | | | | Coups
| | | | | | jouables
Feuilles
-5 3 -1 0 5 -3
Positions finales
Dans ce diagramme, la position de départ, en haut, est appelée un noeud de l'arbre. Il s'agit en l'occurence du noeud initial qui représente la position à analyser. A partir du noeud initial descendent plusieurs branches dont chacune représente un coup jouable.
Après avoir joué un coup, on se retrouve sur un nouveau noeud de l'arbre (une nouvelle position), mais qui a un statut différent : on va l'évaluer. Par convention, on appelera un tel noeud à évaluer une feuille de l'arbre (aussi appelé noeud terminal).
Il faut noter que les branches de l'arbre sont parcourues deux fois : une fois dans le sens descendant (quand on joue un coup), et une fois dans le sens remontant (quand on déjoue ce coup pour revenir à la position initiale).
Une traduction informatique du parcours de cet arbre (en pseudo- code) est indiquée dans le Listing 1.
Tiens vous avez remarqué que j'utilise une fonction plutôt qu'une procédure ? Au retour, cette fonction ressort le résultat de l'évaluation du meilleur coup. Pourquoi donc ?
C'est pour anticiper, bien entendu, mais d'ores et déjà, vous constaterez que la note du meilleur coup est plus 'fine' que celle que l'on aurait eu par une simple évaluation de la position initiale.
En effet, on a déjà creusé d'un coup !
Bon maintenant, voyons un peu plus loin. Plutôt que d'évaluer le noeud dès que l'on a joué, supposons que notre adversaire joue lui aussi un coup. Chacune des feuilles de notre arbre va devenir un noeud qui sera une position initiale de l'adversaire.
Pour chaque réponse de l'adversaire, on va ainsi créer des nouvelles branches au bout desquelles on va évaluer la position (nouvelles feuilles).
o
| -1
+--------------------+-----------------+
MAX | | |
o o o
| -3 | -1 | -6
+-----+-----+ +-----+--+--+-----+ +--+--+
MIN | | | | | | | | |
| | | | | | | | |
5 -3 2 0 -1 1 1 -6 2
Mais quelle branche va donc choisir l'adversaire ?
Il va évidemment choisir celle qui lui sera la moins défavorable, à savoir celle qui donne le score le plus faible pour l'ordinateur.
Le joueur humain, opposé de l'ordinateur, va donc choisir la branche dont la feuille à une valeur minimale. Après que l'ordinateur aie maximisé son coup, l'adversaire va minimiser les conséquences de ce coup.
L'algorithme, en pseudo-code, qui examine cet arbre est indiqué dans le Listing 2.
Continuons de généraliser.. Après le coup joué par l'adversaire, l'ordinateur va de nouveau devoir choisir le meilleur coup parmi tous ceux qui lui sont possibles. Il va donc de nouveau choisir la branche qui maximise la note d'évaluation.
Il suffit donc d'appeler "Maximise" plutôt que "Evalue" dans la réponse du joueur.
Mais, en réponse, l'adversaire va encore chercher à minimiser les conséquences de ce coup... (re-appel de Minimise dans la réponse de la réponse de la réponse)
Puis, l'ordinateur va de nouveau maximiser..
Euh jusqu'où va-t'on là ? On s'arrète quand ?
On pourrait ne s'arrêter qu'à la fin du jeu. Mais pour la plupart des jeux de réflexion, y compris CRESUS, je doute que vous ayez trouvé le coup à jouer en moins d'un siècle, même avec un macro ordinateur à supra-conducteur refroidi à l'hélium liquide !
Il faut prévoir une porte de sortie à notre algorithme...
En général, on choisit de creuser jusqu'à une certaine profondeur, et plus celle-ci est importante, plus on prévoit loin dans le jeu. Mais le prix à payer c'est un temps de réflexion plus important (On n'a rien pour rien).
L'algorithme de base de cette recherche de coup optimal, en version doublement récursive (maximise appelle minimise et minimise appelle maximise) est connu sous le nom de MINIMAX.
Cet algorithme est assez ancien (fin des années 50), et je ne sais pas exactement à qui l'attribuer, mais il semble que le papier de Samuel (1959) a contribué à l'exprimer clairement, bien que le minimax lui soit antérieur.
Un exemple (toujours en pseudo code) est représenté dans le Listing 3. En appelant Maximise au départ, avec une profondeur "Prof" donnée de recherche, la fonction va ressortir le meilleur coup pour l'ordinateur, ainsi que le résultat de la fonction d'évaluation si chacun joue au mieux (de son point de vue) jusqu'à cette profondeur de recherche.
Le Minimax est donc un algorithme qui permet de creuser l'arbre de jeu jusqu'à une profondeur donnée, et de remonter le résultat de la fonction d'évaluation si chacun des joueurs joue au mieux (selon le critère de la fonction d'évaluation bien entendu).
Avant d'examiner les améliorations de cette algorithme, commençons par analyser une simple variante, très utilisée, du minimax que certains ont appelé la notation 'négamax'...