Généralités sur l'évaluation
Je vais d'abord vous présenter des généralités sur le raisonnement que font suivre les programmeurs à leurs logiciels, raisonnement constitué de ce que l'on appelle algorithmes, c'est à dire de suites d'opérations élémentaires. Vous entendrez, dans cette matière, parler également de méthodes "heuristiques".
Ce sont des méthodes, souvent fondées sur des calculs précis, mais aussi utilisant des techniques empiriques, qui permettent de trouver des voies viables se rapprochant par étapes de la solution finale.
On peut distinguer plusieurs types d'algorithmes, utilisés simultanément par les programmes, à travers deux phases imbriquées du "raisonnement" :
1) la démarche dynamique, qui correspond aux prévisions de mouvements de l'adversaire, aux réponses de l'ordinateur, aux contre-réponses de l'adversaire, etc..., et ce, le plus loin possible dans l'avenir. Cette vision de l'ordinateur est "tactique", car elle évalue les mouvements des pions, sans vue d'ensemble.
Si les processeurs avaient une capacité et une vitesse plusieurs milliards de fois supérieures à leurs performances actuelles, cette démarche suffirait à l'ordinateur qui, dès le premier coup, analyserait toutes les variantes possibles jusqu'au dernier coup, et jouerait à chaque tour le meilleur coup.
Hélas (ou heureusement), les ordinateurs n'en sont pas là ; il faut que la machine arrête son analyse au bout de quelques coups, et se livre alors au deuxième type d'analyse.
2) l'évaluation statique de la situation, qui correspond à la vision "coup d'oeil" que l'on peut avoir d'une position. Ainsi, indépendamment de coups que vous n'auriez pas vus, vous pouvez dire, en regardant une partie en cours, "les noirs sont mieux que les blancs". C'est cette évaluation statique que l'on doit apprendre au programme. Cette évaluation statique est la plus facile à expliquer. Sachez aussi que c'est la moins "scientifique", car elle est faite de méthodes très subjectives (tout comme votre appréciation d'une position peut être discutée par votre voisin). On l'assimile à une vision "stratégique" de la position.
L'évaluation statique
Il s'agit en fait de quantifier objectivement l'impression subjective que chacun de nous peut avoir en jetant un coup d'oeil à une position en cours de jeu, sans se livrer à une analyse des possibilités de développement.
Vous vous êtes sans doute souvent livré à cet exercice, en regardant par-dessus l'épaule des joueurs quelles étaient leurs positions respectives.
La subjectivité de la chose vous est sans doute apparue quand votre voisin (qui regardait par-dessus l'autre épaule) a émis un jugement différent du votre. Comment faire dire à l'ordinateur "les noirs sont mieux que les blancs" (ou l'inverse) avec un risque faible d'erreur ?
Examinons les critères que l'on va prendre en compte. Ils sont de deux sortes, souvent associées, le nombre de pions et la position.
Analysons chacun de ces critères :
1) - la différence du nombre de pions.
Cela paraît facile (il suffit de compter), mais se pose là une éternelle question souvent débattue au Café du Commerce (celui qui est juste en face du club) : combien la dame vaut-elle de pions ?
Je vous laisse bien sûr la réponse, mais sachez que les programmeurs prennent en général une valeur voisine de trois, avec des variantes quand leur programmation le leur permet (c'est à dire quand elle accepte des nombres non entiers), souvent un peu moins de trois en début de partie, un peu plus de trois en fin de partie.
2) - la position.
La position s'évalue en fonction d'un certain nombre de critères secondaires :
-la valeur des cases occupées.
Il s'agit là de valoriser l'occupation des cases du damier en fonction de l'importance stratégique que vous leur accordez.
Si vous voulez que votre ordinateur joue une partie classique, il sera bon de privilégier la case trois (supposons qu'il ait les noirs) ainsi que les cases centrales en début et milieu de partie (en fin de partie les choses sont bien sûr différentes), mais d'autres cases seront aussi valorisées, à des valeurs moindres.
Pour effectuer cette évaluation, il faut d'abord affecter une valeur à chaque case, en fonction de l'importance qu'on lui accorde. Ensuite, à un moment quelconque du jeu, on regardera quelle est la couleur du pion posé sur chaque case, et, si on est du côté des noirs, on ajoutera les valeurs des cases occupées par les noirs, et on retranchera celles occupées par les blancs.
La valeur associée à l'occupation par un pion blanc ou un noir n'est en général pas la même ; ainsi, la case 6 occupée par un pion noir aura une valeur positive de quelques points, tandis que, occupée par un pion blanc, elle aura une très forte valeur négative, le plus souvent opposée à celle de la case 45 quand elle est occupée par les noirs.
Vous pourrez ainsi privilégier une position classique, ou une Roozenburg, ou une partie de flanc (difficile pour un ordinateur), etc...
Un bon programme comprendra plusieurs valeurs, en fonction du type de partie (qu'il pourra reconnaître d'après l'occupation de certaines cases caractéristiques), mais aussi en fonction de la phase du jeu (début, milieu, fin)
Ceci n'est cependant aussi simple que cela ; en effet, les valeurs choisies doivent respecter deux critères :
* être représentatives de la valeur de la position,
* respecter des écarts logiques entre des cases correspondant à des mouvements possibles.
- les formations.
Il est souvent intéressant de donner quelques points supplémentaires aux positions qui permettent des marchands de bois, des flèches, des trèfles, ... et qui évitent, dans le doute, les lunettes. Le bon programme tiendra compte de tout cela.
On peut aussi privilégier l'enchaînement de l'adversaire, mais ceci est particulièrement ardu, car en l'absence de jugement humain, il est souvent malaisé de définir qui est l'enchaîneur et qui est l'enchaîné, et le risque de retrouver rapidement l'enchaîneur enchaîné est difficile à faire évaluer par l'ordinateur. Inutile de préciser que si les bonnes formations de l'ordinateur ajoutent des points, celles de l'adversaire vont en enlever.
- les degrés de liberté.
Le principe est que, si on ne regarde pas loin dans l'avenir, il vaut mieux avoir un grand nombre de possibilités parmi les pions à jouer (on appelle cela les degrés de liberté), que peu, car on aura alors plus de choix, et donc plus de chances de trouver une bonne solution.
Il faudra bien sûr chercher à diminuer le nombre de degrés de liberté de l'adversaire, mais il faut remarquer ici que l'analyse n'est pas symétrique. En effet, on ne peut parler de degrés de liberté que pour le joueur qui a le trait, le nombre de degrés de liberté de l'autre pouvant être modifié par le coup du premier. Dans la pratique, on ne fait pas toujours cette distinction, pour rendre possible la comparaison entre des positions qui n'ont pas le même trait.
- les temps .
Cette notion ressemble aux degrés de liberté, mais elle correspond à un déroulement dans le temps, et non dans l'espace. Un bon joueur préfère toujours être sûr qu'il peut encore jouer plusieurs coups avant d'être contraint à des échanges, qui peuvent casser sa position, ou lui faire perdre des pions. Il convient donc de vérifier que notre jeu nous laisse suffisamment de temps d'avance, et en laisse moins à l'adversaire. Ce critère n'est pas toujours pris en compte par les programmes de dames, pour deux raisons :
* il est propre au jeu de dames, et les principales recherches dans le domaine de la programmation se sont surtout intéressé aux échecs, le négligeant,
* il contient une notion importante de déroulement dans le temps, donc ne peut pas être correctement traité par une évaluation purement statique. Il convient d'ajouter à celle-ci une composante dynamique de l'évolution du jeu, ou de se contenter d'un ersatz discutable, par exemple le nombre de cases vides devant les pions, avant le contact avec l'adversaire.
Mais, le moyen le plus simple pour approcher cette notion reste le comptage des temps tel qu'expliqué par Cantaluppo dans les années 40, puis repris par d'autres :
On calcule le nombre de pions situé sur la ligne du fond + 2 fois le nombre sur la 2ème ligne + 3 fois le nombre sur la 3ème + ....etc. Même chose pour l'adversaire. On fait la différence (ordinateur-adversaire).
Dans un début de partie classique, il est bon d'obtenir le chiffre le plus bas possible (on dit qu'on a des temps de retard, mais le terme est mal choisi). Plus la partie avance, plus la valeur de cette différence doit diminuer, et elle est inverse à la fin.
- autres.
On peut encore ajouter d'autres critères pour valoriser la position.
Je citerai par exemple le regroupement des pions (il vaut mieux bien sûr qu'ils soient ensemble qu'étalés sur le damier), l'existence ou non de couloirs faibles pouvant mener à dame, le déséquilibre des forces sur un flanc, etc...
Je vous laisse proposer d'autres critères, qui seront d'autant meilleurs que l'ordinateur pourra les évaluer sans se livrer à des calculs trop compliqués.
Quand l'ordinateur a fait toutes ces évaluations que fait-il ?
Et bien il les mélange, il les malaxe, il les cuisine, et il en sort une valeur qui lui permet de comparer les différentes positions étudiées.
En fait il peut en tirer 2 valeurs séparées, celle du nombre de pions et celle de la position, et privilégier alors totalement le nombre de pions par rapport à la position ; cela oblige alors à traiter les gambits dans la démarche dynamique, nous y reviendrons. Dames 2020 (un très vieux programme) fonctionne ainsi, mais la plupart de ses concurrents (dont Quidam et Windames), s'inspirent des principes développés pour les programmes d'échecs où la perte d'une pièce est tolérable pour obtenir un gain positionnel, et ajoutent la valeur issue du comptage des pions à celle issue de l'analyse de la position, en leur affectant des coefficients appropriés, pour n'en tirer qu'un seul nombre (par exemple la valeur positionnelle, plus 100 fois la différence des pions). Cette méthode classique a aussi l'avantage de ne faire manipuler qu'une valeur au lieu de deux.
Vous avez bien compris que tout ceci est une alchimie qui laisse une large place aux appréciations du programmeur et de ses conseillers techniques. Mais il peut être intéressant, lorsqu'on joue contre un ordinateur, d'essayer de retrouver quels sont les aspects privilégiés et ceux négligés, et donc d'en déduire les points faibles du programme.