Comme nous l'avons déjà dit, l'efficacité des différents algorithmes dépend fortement de l'ordre dans lequel on analyse les coups de chaque joueur.
Si on commence par évaluer la meilleure séquence dès le départ, on va provoquer beaucoup de coupures par la suite. Les algorithmes dans ce cas ne font que vérifier, au plus vite, que la séquence trouvée est bien la meilleure.
Ceci est d'autant plus vrai pour les algorithmes "à espionnage" (Scout et PVS) que pour l'AlphaBeta.
D'où l'idée, en général très efficace, de commencer par évaluer le jeu à une profondeur plus faible et d'en profiter pour trier les séquences de coups en fonction du résultat.
Ainsi, lorsque par la suite on évalue le jeu à une profondeur élevée, on bénéficie au moins d'un arbre ordonné de façon plus optimale qu'un rapide "Cherche Et Classe", et on peut ainsi accélérer la recherche.
La question est souvent:" Comment exploiter au mieux possible la connaissance apportée par l'exploration à profondeur réduite ?".
Pour les premiers niveaux, la technique la plus efficace est évidemment de stocker l'arbre de jeu, sous une forme ordonnée.
Malheureusement, et surtout pour les jeux à divergence importante, le stockage de l'arbre à une profondeur importante est très vite limité, à cause de la mémoire disponible.
Les auteurs de programmes performants complètent ce stockage des premiers niveaux à des techniques telles que un tableau de coups meurtriers ("response killer") ou une table de hachage ("hash table", comme celle utilisée dans les algorithmes de recherche dans une base de données).
L'objectif de ces tableaux est de garder un maximum d'informations des résultats obtenus à une profondeur importante, pour laquelle l'arbre ne peut plus être stocké.
Grossièrement, le principe consiste à retenir qu'en général, un tel coup est une bonne réponse à un tel autre coup de l'adversaire.
Je n'aborderais pas dans cet article tout ces raffinements (Il faut en laisser pour plus tard), dont l'intérêt se justifie peu pour un jeu tel que CRESUS.
Le principe de récupérer les informations issues d'une recherche effectuée à une profondeur inférieure et ainsi accélérer la recherche à un niveau plus profond est poussé à l'extrême dans la version dite 'Iterative Deepening'.
Dans ce cas, on commence par évaluer à une profondeur très faible, puis on augmente progressivement la profondeur jusqu'à le profondeur souhaitée.
Cet algorithme est très souvent utilisé, non seulement parce qu'il est effectivement efficace, mais aussi parce qu'il permet une gestion 'plus saine' du jeu.
En effet, le problème de des algorithmes précédents était d'évaluer le jeu à une profondeur fixée. Pour la plupart des jeux (CRESUS y compris), cette recherche est plus ou moins longue (en temps) selon la divergence (nombre de choix possibles pour chacun).
Si l'on effectue une recherche à profondeur constante, fixée pour l'ensemble de la partie, cette recherche sera longue en début de partie et beaucoup plus rapide vers la fin.
Tout simplement parce que la taille de l'arbre se réduit fortement lorsque le jeu évolue.
Avec l' Iterative Deepening , il est très facile de gérer des profondeurs différentes selon l'évolution du jeu.
On met en place une horloge et lorsque l'on a terminé l'analyse à une profondeur donnée, on évalue le temps qu'il faudra pour une itération supplementaire (une profondeur de plus).
Si le temps dépasse celui que l'on s'est fixé, on arrète et on donne le meilleur résultat obtenu.
Si par contre, il reste du temps suffisant à l'ordinateur, on continue la recherche en augmentant la profondeur d'analyse.
C'est ainsi que fonctionnent la plupart des programmes qui sont paramétrés en temps, et sont beaucoup plus agréables pour l'utilisateur.
Sans aborder en détail tous ces perfectionnements, que je vous laisse à titre d'exercice, j'ai quand même voulu montrer l'intérêt du reclassement même pour un jeu comme CRESUS.
Dans la version DOS et les sources fournis avec cet article, vous verrez un exemple d'algorithme qui :
Pour la deuxième phase (recherche à profondeur importante), j'ai utilisé un algorithme de type PVS sur les premiers niveaux (ceux de l'arbre stocké) et de type AlphaBeta pour les niveaux plus profonds.
Le gain apporté par ce reclassement de l'arbre est loin d'être négligeable !
J'ai évalué, sur une dizaine de parties tests, l'écart entre le nombre de feuilles examinés par l'AlphaBeta et celui obtenu par les autres méthodes. Cet écart (en pour cent) a ensuite été moyenné pour les 10 parties.
Cette mesure a été faite à une profondeur de 14.
| Algorithme | Ecart moyen (en %) |
| AlphaBeta Scout PVS AlphaBeta reclassé PVS reclassé |
0 (référence) +0,3 % -5,6 % -37,6 % -45,9 % |
On constate que l'écart entre Scout et AlphaBeta est négligeable en moyenne (bien qu'il puisse être trés différent d'une partie sur l'autre).
L'algorithme PVS fait "à peine mieux", ce qui n'est pas très étonnant vu la faible divergence de CRESUS et la rusticité de la routine "Cherche et Classe".
Par contre, dès que l'on exploite un arbre reclassé (par un AlphaBeta à profondeur 6), on constate une nette diminution du nombre de feuilles. (PS le nombre de feuilles tient évidemment aussi compte de celles générées par l'AlphaBeta à profondeur 6).
Ceci met bien en évidence l'importance d'une routine "Cherche et Classe" efficace.
Quand l'algorithme de recherche dans l'arbre reclassé est à espionnage (PVS reclassé), son efficacité par rapport à l'AlphaBeta (AlphaBeta reclassé) est accrue (-13 % plutôt que -5,6 %).
Ceci montre bien qu'il est encore plus important, pour les algorithmes à espionnage, d'examiner les coups dans un ordre pas trop absurde.
Je rappelle (encore...) que pour les jeux classiques, tels que échecs, dames, reversi, la divergence est plus importante que CRESUS, ce qui rend les algorithmes à espionnage beaucoup plus pertinents.
Pour en finir avec cet article d'introduction, je signale qu'il existe d'autres types d'algorithmes, très efficaces, mais qui ne sont pas 'extrapolés' de l'AlphaBeta et de la descente récursive d'un arbre de jeu.
Citons par exemple, l'algorithme SSS* (Stockman, 1979) très efficace mais gourmand en ressources machine.
Et pour ceux qui veulent être à la pointe du progrès dans le dommaine, l'algorithme "Prof Number Search" semble être le nec le plus ultra à l'heure actuelle (Allis, 1994)
J'espère que cet article, loin d'être exhaustif comme signalé dans l'introduction, vous aura intéressé et surtout donné l'envie de venir rejoindre le "clan" des programmeurs de jeux de réflexion.