La méthode du Minimax
Nous avons vu qu'il fallait, pour exploiter correctement l'arbre de décision, devenu plus compliqué et plus dense qu'une forêt, de la méthode, et une bonne scie pour élaguer.
Commençons par la méthode, qui nous évitera de nous retrouver avec des milliards de chiffres dont nous ne saurons que faire.
La méthode universellement utilisée (programmes de dames, d'échecs, de go, d'othello, de bridge,... ) s'appelle le Minimax.
Le Minimax schématise le processus décisionnel que devrait suivre tout joueur : supposer que chaque joueur va, à chaque moment, prendre la décision qui est la meilleure pour lui (ceci est l'axiome de base de toute la théorie des jeux).
Ceci signifie donc que l'ordinateur, contrairement à ce que peut parfois laisser croire son jeu, ne va pas vous tenter de piège dans l'espoir que vous tombiez dedans. Par contre, il prendra et maintiendra des positions fortes pour lui, qui peuvent ressembler à des pièges pour vous.
Examinons un cas précis, pour comprendre comment "raisonne" l'ordinateur.
schéma n° 3
Dans cet organigramme qui s'arrête au niveau 1, nous supposons que la position initiale de l'ordinateur soit identifiée par la lettre A, et que l'ordinateur a 3 possibilités de jeu, qui l'amènent respectivement aux positions B1, B2, B3. Nous avons associé à ces positions la valeur que l'ordinateur trouve en effectuant leur évaluation statique. Vous voyez que l'ordinateur peut choisir entre les valeurs 5, 10, 3, trouvées en B1, B2 et B3. Il prendra naturellement la solution la plus avantageuse pour lui, c'est à dire celle correspondant à la valeur la plus élevée (ici 10 en B2).
Examinons maintenant un organigramme de niveau 2 :
schéma n° 4
Dans ce cas, les évaluations effectuées en B1, B2, B3 n'ont pas de signification, puisque aux coups suivants (amenant aux positions C1 à C 9) ce sont d'autres valeurs qui sont trouvées, les pions ayant forcément bougé. Votre vision dans l'avenir va donc plus loin, et c'est cet avenir, le plus lointain possible, qu'il faut examiner.
L'ordinateur choisira bien sûr au début entre les coups amenant à B1, B2 et B3. S'il joue le coup l'amenant à B1, ce sera son adversaire qui choisira la réponse, amenant aux positions C1, C2 ou C3. De même, si l'ordinateur joue le coup amenant en B2, l'adversaire choisira entre C4, C5 et C6, et si l'ordinateur choisit B3, l'adversaire choisira entre C7, C8 et C9. Comme l'adversaire n'est pas là pour vous faire de cadeaux, et s'il a les mêmes critères d'évaluation que l'ordinateur (ce qu'il faut bien supposer), il va choisir dans chaque cas la solution qui désavantage l'ordinateur, donc celle correspondant aux valeurs les plus faibles des évaluations statiques. L'ordinateur ne pourra donc jamais atteindre les positions tentantes telles que C1 ou C9.
Ainsi, si l'ordinateur joue le coup amenant à la position B1, l'adversaire répondra par le coup amenant en C3 qui donne une valeur de 3, si l'ordinateur choisit B2, l'adversaire répondra par la position C4 qui donne une valeur de 5, si l'ordinateur choisit B3, il répondra par C8, qui donne une valeur de 2. Nous sommes donc ramenés à un organigramme de type suivant :
schéma n° 5
Entre les 3 valeurs correspondant à B1, B2 et B3, l'ordinateur a intérêt à choisir celle qui lui donne le plus de points, donc la voie B2, qui lui rapportera 5, son adversaire étant amené à lui répondre par le coup amenant à la position C4.
De même, si nous poursuivions notre raisonnement au niveau 3, nous verrions que le choix du coup étant alors, en C1, C2...C9 du ressort de l'ordinateur, celui-ci choisirait alors dans chaque branche la position correspondant à la plus forte des valeurs possibles (voir le schéma n° 6).
schéma n° 6
Plaçons-nous à la position C1. L'ordinateur a le choix entre 3 possibilités, l'amenant à des positions (que j'aurais pu appeler D1, D2, D3), respectivement valorisées 2, 1, 5. Il en déduit que, s'il est amené à se retrouver dans la position C1, le meilleur coup qu'il pourra jouer l'amènera dans une position de valeur 5 points. Il peut donc d'ores et déjà affecter cette valeur de 5 à la position C1. De même, il peut affecter 11 à C2, et 8 à C3.
Cependant, depuis la position B1, ce sera l'adversaire qui choisira entre C1, C2 et C3. Logiquement, celui-ci devrait prendre la solution la moins avantageuse pour l'ordinateur, c'est à dire celle issue de C1. Ceci permet alors d'affecter la valeur 5 en B1. De même, nous allons remonter la valeur 2 en B2 (issue de C6), et 3 en B3 (issue de C7). Le meilleur choix pour l'ordinateur est donc la branche B1, qui lui donne un score de 5 en passant par C1 (choix probablement imposé par l'adversaire s'il joue bien).
Ainsi, le processus utilisé par le programme correspond à l'alternance des décisions (ordinateur/adversaire), et alterne les niveaux dits "maximisants", où le choix du coup à jouer appartient à l'ordinateur, et les niveaux dits "minimisants", où le choix du coup appartient à son adversaire. La solution remontant au sommet est, avec certitude, le meilleur choix initial, compte tenu des meilleures réponses possibles de l'adversaire dans chaque cas.
Vous voyez que seules les évaluations de fin de branche sont nécessaires, les résultats remontant ensuite au sommet par alternance de maximisations et de minimisations.
Le Minimax permet d'examiner avec méthode l'arbre complexe des décisions, il ne permet pas d'élaguer. Nous allons aborder les méthodes d'élagage plus loin.
Cependant, pour préparer efficacement la prochaine leçon, je vous convie à un petit exercice que nous corrigerons ensemble, et qui vous fera mieux comprendre la notion suivante : le magnifique, l'indispensable algorithme alpha-bêta.
A partir du schéma n° 6 :
1) Vérifiez tout d'abord que, en affectant n'importe quelles valeurs aux 3 branches issues de C5, on ne modifie en rien le choix de l'ordinateur.
2) Donnez le nombre de branches qui peuvent ainsi prendre n'importe quelle valeur sans changer le choix final de l'ordinateur (valeur 5, et chemin passant par B1 et C1).
Lorsque nous aurons déterminé qu'il existe des branches qui peuvent prendre des valeurs quelconques sans changer la solution, nous pourrons nous dire que nous aurions mieux fait de ne pas examiner ces branches, en effectuant un élagage adéquat.