Les élagages préalables
L'élagage alpha-bêta permet des économies de calculs substantielles, mais on peut aller encore plus loin.
Nous examinerons plusieurs types d'élagages préalables, c'est à dire d'élagages utilisés avant toute évaluation dans la branche.
- les sacrifices visiblement inutiles
Quand vous jouez, il y a un certain nombre de solutions que vous éliminez rapidement (parfois inconsciemment) car elles sont visiblement trop coûteuses. Essayons d"'expliquer" à l'ordinateur ce raisonnement.
Il s'agit de lui faire éliminer une solution lorsqu'il s'aperçoit qu'elle conduit à donner ou à perdre des pions sans espoir de les récupérer à court terme. Il faut bien sûr différencier ce cas des dons de pions qui constituent des phases initiales de combinaisons. L'ordinateur peut faire cette distinction : tant que le joueur donne des pions et que son adversaire est en prise, ou n'a qu'un nombre limité de coups à jouer (1 ou 2), il y a une possibilité de combinaison ou de forcing. Dès que l'adversaire a un certain nombre de réponses possibles (plus de 2 qui ne soient pas des prises), on n'est probablement plus dans une phase de combinaison possible, et tous les pions qui ont été perdu jusque là l'ont été en vain.
Vous remarquerez que j'ai utilisé là quelques précautions, et que je me réfugie derrière des probabilités. En effet, nous ne sommes plus dans des certitudes logiques mais dans des raisonnements de type empiriques, c'est à dire fondés sur la seule expérience (l'heuristique vous dis-je). De plus, ce raisonnement présente, j'en suis conscient, un certain nombre de failles, dont deux importantes :
* l'éventualité de gambit laissant espérer un gain ultérieur,
* la possibilité de donner des pions sans gain immédiat mais pour permettre, dans un avenir supérieur à celui envisagé par l'ordinateur, un passage à dame.
Ces deux difficultés peuvent être amoindries (mais non totalement annulées) en fixant assez haut la barre du sacrifice inutile (3 pions par exemple, le gambit gagnant de plus de 3 pions étant tout de même exceptionnel, et un prix de quatre pions ou plus pour passer à dame étant le plus souvent cher payé, sauf peut-être en fin de partie). On peut aussi fixer une barre habituelle plus basse, qui ne monte que lorsque l'adversaire est près de la ligne de dames, à condition de savoir déterminer cette distance à dame de façon fiable.
Remarquons que ces algorithmes doivent être neutralisés en fin de partie, sinon, la dame valant environ 3 pions, l'ordinateur n'envisagera jamais de donner deux ou trois dames pour en prendre une après un temps de repos (blocage sur la grande diagonale et sur le tric-trac).
- les solutions trop ouvertes
Nous sommes là encore dans des domaines incertains, qui jouent davantage sur les probabilités et sur l'expérience que sur une imparable logique (encore l'heuristique).
Imaginez que, à un niveau N de l'examen des avenirs possibles, l'adversaire a le choix entre 2 solutions. La première autorise 4 réponses de l'ordinateur, suivies chacune de 4 réponses de l'adversaire, chacune suivie de 4 possibilités. La seconde autorise 20 réponses, suivies chacune de 20 réponses de l'adversaire, et chacune suivie de 20 possibilités.
Si les évaluations finales vues du temps présent sont équivalentes dans chacun des cas (ce qui ne signifie pas que, lorsque vous serez dans l'avenir N et que l'ordinateur les examinera à nouveau, elles soient encore équivalentes, puisque le programme verra alors plus loin), il y a une chance sur 4x4x4, soit une chance sur 64, que l'une des solutions soit choisie si l'adversaire prend la solution une.
Par contre, s'il prend la deuxième solution, il n'y a qu'une chance sur 1000 que chacune soit retenue. L'ordinateur aura donc passé un temps 15 fois plus élevé à examiner des solutions 15 fois moins probables.
On peut en déduire que, plus l'arbre des possibilités se rétrécie, plus la probabilité de détecter le chemin effectivement retenu augmente. A l'inverse, plus il s'ouvre, plus chacune des solutions est peu probable, mais aussi plus il est vraisemblable qu'on pourra trouver, quand on arrivera là, une solution convenable, puisque les possibilités sont plus nombreuses.
On peut donc examiner plus loin chaque solution d'un arbre étroit (puisqu'elle est plus probable), ou (c'est équivalent, mais plus choquant à dire) limiter la réflexion dans un arbre large. Le critère de coupure peut être par exemple la multiplication à chaque niveau du nombre de branches viables ; si on coupe à 10 millions, on pourra examiner 7 niveaux de largeur moyenne 10 ou 13 niveaux de largeur moyenne 6 (en fait on n'examinera de toute façon pas toutes les branches, compte tenu de l'application de l'alpha-bêta et des autres élagages préalables).
Cette méthode, théoriquement peu satisfaisante car elle peut laisser passer à des niveaux élevés des possibilités intéressantes, fait néanmoins gagner un temps appréciable en présentant un risque limité. Elle n'est évidemment pas contradictoire avec la valorisation des degrés de liberté, mais peut être complémentaire. Cette méthode, utilisée par Dames 2020, a été peu décrite dans la littérature jusqu'ici, peut-être parce qu'elle est moins adaptée aux autres jeux .
- La recherche focalisée
Cette méthode consiste à faire une recherche exhaustive jusqu'à un certain niveau, puis à ne garder que 80% ou 90% des solutions (les meilleures), puis, au niveau suivant à focaliser encore sur les 80% ou 90% les meilleures, etc...
Le défaut lié à cette méthode est que, si les meilleures solutions à un niveau N le restent souvent au niveau N+1, ce n'est pas systématiquement le cas, et dans les 10% ou 20% qui restent, peut se cacher la voie retenue par l'adversaire, celle qui, justement, fait mal, et qu'on ne saura pas éviter si l'arbre est étroit.
Cette méthode, vous l'aurez compris, ne me plaît guère, et je lui préfère l'élagage des solutions trop ouvertes, qui est de même nature, mais me paraît mieux ciblée.
- Les solutions déjà examinées
Ah ! Là, vous allez vous sentir mieux : c'est du sûr.
Vous avez sans doute compris de ce qui précède que la démarche dynamique étudie des mouvements, alors que l'évaluation statique s'intéresse à des positions. Or, des enchaînements différents de mouvements peuvent aboutir à des positions identiques. Par exemple, les coups suivants :
1) 33-28, 18-23 2) 31-26, 16-21
ou 1) 31-26, 18-23 2) 33-28, 16-21
ou 1) 31-26, 16-21 2) 33-28, 18-23
ou 1) 33-28, 16-21 2) 31-26, 18-23
amènent, au niveau 4, c'est à dire au bout de deux coups, exactement à la même position.
On pourra donc s'efforcer de détecter si la position à étudier a déjà été rencontrée, ce qui permet de lui attribuer des caractéristiques déjà calculées, et d'élaguer toute les branches qui en partent. Pour profiter de cette caractéristique, il suffira de conserver les positions étudiées, et de comparer chaque nouvelle position à celles-ci. Il existe bien sûr un optimum dans le nombre de positions à conserver, car, au-delà d'un certain nombre, il est plus rapide de réétudier la branche complète que de comparer chaque position aux 10 ou 20 mille autres déjà enregistrées. Pour aider dans cette approche, le jeu de dames possède une particularité importante (qu'on ne trouve pas aux échecs), son caractère unidirectionnel. Cela signifie qu'une position donnée ne peut se retrouver qu'à un niveau donné, et pas avant ni après puisque les pions doivent avancer et ne peuvent pas reculer (je simplifie, en ne considérant pas le mouvement des dames, qui, effectivement, détruit cette unidirectionnalité, mais je ne m'expose qu'à étudier plusieurs fois des positions où les dames ont fait des aller-retour). Ainsi, l'exemple considéré ci-dessus donne une position que l'on atteint en 4 niveaux (2 coups), mais impossible à obtenir en 3 ou 5 niveaux. On pourra profiter de cette caractéristique en stockant les positions étudiées par niveau, ce qui limite le volume des comparaisons.