De nombreuses améliorations ont été proposées à l'algorithme AlphaBeta, afin de se rapprocher le plus possible de l'arbre minimal de recherche.
Celles qui ont le plus de succès sont dérivées ou proches du concept d'un algorithme baptisé SCOUT, décrit par Pearl en 1980.
Voyons d'abord le principe de SCOUT, que l'on pourrait appeler une 'tactique d'espionnage'.
Ce qui serait bien, pour un joueur qui a déjà évalué une branche de son arbre, c'est qu'il puisse, de façon rapide, estimer si une autre branche est meilleure sans pour autant l'évaluer.
Si le joueur constate que cette branche n'a pas d'intérêt, il peut directement passer à la suivante.
Par contre, si la branche s'avère être potentiellement meilleure que la précédente, il ne lui reste plus qu'à l'évaluer en détail afin de connaitre la valeur précise de cette branche et donc chiffrer l'intérêt de ce coup.
Le principe de Scout est donc d'espionner rapidement un coup pour savoir s'il vaut la peine d'être évalué réellement.
On peut le décrire, en pseudo-code, à l'aide de l'algorithme décrit dans le Listing 6.
Mais, me direz-vous à juste titre, comment 'espionner' une branche ? Comment savoir de façon 'rapide' si elle donne potentiellement un résultat meilleur qu'une valeur donnée ?
Une technique pour jeter ce coup d'oeil rapide est dérivée de l'AlphaBeta : c'est la version dite à fenêtre nulle (ZeroWindow).
Reprenons l'algorithme AlphaBeta et rappelons le rôle du paramètre beta. Pour le joueur (celui qui a le trait`) que l'on appelera 'Jean' par la suite, beta représente la meilleure suite que son adversaire 'André' a déjà trouvée, contre toute attente.
Supposons que le joueur Jean se trompe lui-même, volontairement, en s'inventant une suite factice de l'adversaire André qui fasse juste mieux que la meilleure note qu'il a déjà pour lui même.
Au lieu de renvoyer la vraie valeur de beta à la sous-branche, il lui renvoie une 'fausse' valeur de beta, juste à peine supérieure à sa propre valeur alpha (beta:=alpha+1).
En fait, ce faisant il se dit "Faisons comme si André a déjà par ailleurs une suite bien meilleure que celle qu'il a en réalité".
Plus profondément, dans la récursion, quand le même joueur Jean trouvera une note juste meilleure que celle qu'il a déjà, il ne prolongera plus la recherche, car elle sera devenue inutile, pouvant être contrecarrée par le coup "factice" de André au préalable.
Bref le joueur Jean se force lui-même à ne pas chercher plus loin dès qu'il a trouvé mieux que son alpha initial. Il provoque lui-même une coupure beta dès qu'il améliore. De ce fait, il rend la main à André dès qu'il a trouvé mieux: "Allez c'est pas bon cherche autre chose, là j'améliore".
Par contre, André évalue ses propres coups avec une valeur de beta correcte (la valeur -alpha de Jean au départ). Jean ne va jamais lui 'envoyer' une valeur plus basse, car dans ce cas, une coupure beta aurait empéché Jean de le faire.
Les coupures beta d'André auraient donc eu lieu de toutes façons, même si la largeur de la fenêtre n'avait pas été réduite.
Son "objectif" est meilleur que la réalité, car son alpha est plus élevé que le véritable, mais cela ne change rien : la valeur alpha ne provoque pas de coupures.
André optimise son score au mieux, quelque soit la valeur de alpha.
Si André trouve un score meilleur que son beta, il l'indiquera à Jean, en lui retournant une valeur supérieure ou égale à son beta.
Dans ce cas, Jean récupèrera donc une valeur, vue de son point de vue, inférieure ou égale à son alpha.
Bref, en appelant l'AlphaBeta avec une valeur de beta "factice" égale à alpha+1, un joueur récupère :
En pratique le test "if MeilleurQue(valeur) then ..." de notre listing Scout peut donc être écrit de la manière suivante :
if -AlphaBeta(-succ(valeur),valeur)>valeur then ...
Personnellement, j'ai préféré écrire une fonction "ZeroWindow" se substituant à l'AlphaBeta standard, car une seule valeur est nécessaire (plus besoin de beta puisque beta:=alpha+1).
Un pseudo-code de la routine "ZeroWindow" est indiqué sur le Listing 7.
L'algorithme Scout permet d'éviter l'évaluation de certaines feuilles que l'algorithme AlphaBeta aurait visité. Mais, par ailleurs, l'algorithme AlphaBeta évite certaines feuilles que Scout explore...
Il existe un algorithme, très similaire à celui de Scout mais dérivé de l'AlphaBeta, qui cherche en plus à exploiter la connaissance des valeurs de alpha et beta.
Cet algorithme est connu sous le nom de "Principal Variation Search" (PVS en abrégé).
Comme dans l'algorithme Scout, le joueur commence d'abord à évaluer son premier coup. Ensuite, pour chacun de ses coups suivants (s'il n'a pas de coupures beta), il commence par jeter un coup d'oeil rapide par un espionnage ZeroWindow pour savoir si ce coup est meilleur que son alpha.
Si ce n'est pas le cas (plus petit que alpha), il peut passer au coup suivant et il a gagné du temps en évitant d'approfondir cette branche.
Si par hasard, cette ligne s'avère meilleure que son alpha, il a au moins ressorti de son rapide coup d'oeil une valeur qui est un minorant de la valeur de la branche.
Si ce minorant est plus grand que son beta, c'est que cette branche ne vaut pas la peine d'être regardée en détail, car on est déjà sûr de provoquer une coupure beta...
Par contre, si le minorant est compris entre alpha et beta, il faut bien re-évaluer cette ligne qui est peut-être la meilleure. Dans ce cas, on le fait, en tenant compte du fait que ce minorant devient, au pire, une nouvelle valeur de alpha et donc provoquera plus de coupures de l'adversaire.
Un exemple, toujours en pseudo-code, de l'algorithme PVS est indiqué dans le Listing 8.
Vous constaterez un petit rafinement, attribué à Reinefeld (1985) qui permet d'éviter de re-évaluer précisément après espionnage les deux dernières sous-branches, car c'est inutile dans ce cas.
La question que l'on peut se poser est : "Mais quel gain ces routines d'espionnage apportent-elles ?"
En théorie, ces routines sont plus d'autant plus rapides (comparées à l'AlphaBeta).
Elles sont donc très utiles dans les jeux classiques tels que les dames ou les échecs, mais beaucoup moins pour CRESUS, car la divergence est faible et la routine "Cherche Et Classe" très primaire.
Lorsque l'ordre des coups est effectué par un tirage aléatoire (pas de "Cherche et Classe" mais juste un "Cherche"), les techniques d'espionnage sont considérées comme équivalentes à l'AlphaBeta simple.
Dans la version de CRESUS sous Windows, l'algorithme implanté est de type PVS pour les niveaux les moins profonds. Dès que la profondeur atteint la valeur de 6, l'algorithme appelle un AlphaBeta classique et évalue la position sans espionnage.
Une autre petite remarque toute personnelle : Vous vous êtes peut-être posé la question, tout comme moi, sur l'intérêt dans l'algorithme PVS d'évaluer systématiquement sans espionnage le premier coup.
En fait, on pourrait très bien aussi l'espionner.
On ne le fait pas car souvent, et en particulier pour les premières branches de l'arbre, la valeur de alpha est très basse et l'espionnage inutile (on est certain de faire mieux que le pire score).
Néanmoins, dans certaines sous-branches au coeur de l'arbre, il peut s'avérer intéressant d'espionner aussi le premier coup...
Je laisse ce sujet ouvert, dans le but de mettre votre sagacité à l'épreuve, mais, sur un plan informatique, remplacer le test du premier coup par un autre test n'est pas très compliqué ... (Mieux vaut le faire sur un autre jeu que CRESUS, en particulier un jeu pour lequel la divergence est plus importante et donc les techniques d'espionnage plus justifiées).