Dans la version présentée au paragraphe précédent de l'algorithme Minimax, on s'est placé successivement dans la peau de l'ordinateur puis dans celle de son adversaire. Ceci nous obligeait à alternativement maximiser puis minimiser la fonction d'évaluation.
Plaçons nous maintenant dans la peau d'un joueur quelconque, que ce soit indifféremment l'ordinateur ou son adversaire.
Chacun va essayer de maximiser son score, vu de son propre point de vue. Le joueur humain par exemple, opposé à l'ordinateur, va aussi chercher à optimiser son score, mais ce score est vu de ses propres yeux à lui : positif s'il est plus élevé que celui de l'ordinateur.
On va donc changer la définition de la fonction d'évaluation : c'est la note donnée à la position vue par le joueur qui a le trait !
Il ne faut plus raisonner 'ordinateur contre humain' mais 'joueur contre adversaire' (que le joueur soit un ordinateur ou un humain).
De même, il ne faut plus raisonner, dans la fonction d'évaluation, en notation 'blanc contre noir' par exemple. Si, au moment où l'on fait l'évaluation c'est à blanc de jouer, il faut évaluer la position pour blanc. Si c'est à noir de jouer, il faut l'évaluer pour noir, quelle que soit la couleur de l'ordinateur.
Dans CRESUS, la fonction d'évaluation devient la différence de score entre celui qui va jouer et l'adversaire.
Pourquoi cela ?
Bien parce que cela simplifie énormément notre algorithme, en évitant les doubles récursions typiques du minimax provoquées par des alternances de maximisation et de minimisation.
En effet, en jouant un coup (une branche de l'arbre), on 'passe le trait' à l'adversaire. Ce faisant, lorsque l'adversaire aura évalué la situation, il retournera au joueur une note, considérant la situation de son propre point de vue.
Comme le point de vue du joueur est, par essence, opposé à celui de l'adversaire, le joueur doit changer le signe de l'évaluation, et aborder le problème selon son propre critère.
Bref chaque joueur maximise sa situation, évaluée de son propre point de vue, qui est bien entendu opposé à celui de l'adversaire.
Cela conduit à un algorithme du minimax bien plus simple, tel que celui indiqué dans le Listing 4.
En passant, petit détail supplémentaire : vous constaterez que j'ai plaçé le calcul de l'évaluation dans la boucle de coups jouables, plutôt qu'au début de l'algorithme...
En fait c'est juste une astuce, très courante, pour éviter un réappel récursif de plus au minimax et éviter ainsi l'empilement des données que le compilateur rajoute.
En pratique, une autre 'astuce' est utilisée par les programmeurs qui consiste à évaluer le dernier coup sans pour autant le jouer réellement. Ce genre de petit détail influençant les nombreuses feuilles de l'arbre peut dans certains jeux (pas tellement pour CRESUS) apporter beaucoup car les routines 'joue' et 'déjoue' ne sont pas toujours aussi simples et rapides.
En résumé, le raisonnement dans la notation 'Négamax' est trés simple, si on se rappelle qu'il faut toujours réfléchir en se plaçant dans la peau du joueur qui a le trait, que ce soit l'ordinateur ou son adversaire, blanc ou noir, peu importe.
Sur un plan 'bêtement' mathématique, certains remarqueront que minimiser une fonction, c'est aussi maximiser son opposé !
La notation 'Négamax' est en général attribuée à Knuth et Moore dans un article traitant de la routine AlphaBeta, décrite ci-après.