Le Fou numérique

 
Tous les programmes d'échecs actuels utilisent des Hashtables. Tous ceux qui s'occupent d'échecs électroniques en ont certainement déjà entendu parler. Mais je ne suis pas sûr si chacun sait ce dont il est question exactement.
 
En principe, les Hashtables sont déjà une vieille histoire dans les échecs électroniques. Déjà les légendaires programmes sur les gros ordinateurs des temps primitifs les utilisaient et elles sont aussi une évidence pour les programmes actuels. Je peux cependant encore me souvenir de l'introduction avec son et trompettes des Hashtables pour les micro-ordinateurs. Comme pour toute nouveauté qui se respecte, on annonçait, et naturellement surtout aux clients et utilisateurs, la grande percée dans les échecs électroniques. L'étaient-elles vraiment?
 

Les Hashtables ne sont pas seulement utilisées dans les échecs électroniques, mais aussi dans beaucoup d'autres utilisations de logiciels. Il s'agit d'une procédure standard en informatique sur laquelle il existe d'innombrables publications et des algorithmes connus, mais nous voulons nous concentrer sur leur usage dans les échecs électroniques.
 
Voyons d'abord comment on pourrait désigner les Hashtables en Français courant: on parlerait de "tableaux d'inversion de coups". Cette expression est sûrement plus à même de se représenter quelque chose de valable. Elle décrit le sens des Hashtables assez bien, mais pour comprendre effectivement de quoi il s'agit, je dois décrire brièvement la manière de fonctionner d'un programme d'échecs.
 
Tous les programmes d'échecs commerciaux actuels fonctionnent sur le même principe: toutes les possibilités de coups sont essayées dans l'ordre, le meilleur coup calculé est ensuite joué. Naturellement, ce n'est pas toute la vérité, le grand art dans les échecs électroniques est de reconnaître à temps quelles possibilités de coups sont judicieuses pour que la recherche sur celles-ci soit menée rapidement ainsi que d'approfondir particulièrement les variantes intéressantes.
 
Néanmoins, 99.99% du temps est encore consacré par les programmes de pointe actuels à examiner des suites de coups insensés qu'un humain sait reconnaître pour ne jamais être exécutés sur un échiquier. C'est pourquoi il n'est pas totalement faux d'admettre que toutes les variantes sont examinées. Quand on réfléchit un peu et qu'on se demande de quelle manière les programmes d'échecs pourraient bien jouer s'ils ne dilapideraient pas une grande part de leur temps ainsi, ce serait sûrement une conclusion justifiée.
 
D'un autre côté, la vitesse de calcul est, sans conteste, la force des ordinateurs et, au fil du temps, il est devenu évident qu'il est plus efficace de prendre une grande partie de son temps avec l'évaluation de positions et de suites de coups ineptes plutôt que d'essayer de prime abord de ne sélectionner que les coups sensés. Les ordinateurs jouent simplement différemment que les humains, ils ne savent que quelque chose est mauvais que s'ils l'ont eux-mêmes essayé.
 

 
Chaque joueurs d'échecs, et même un non-joueur, constatera immédiatement que la position obtenue avec les quatre suites de coups ci-dessus est totalement identique. Mais comme il a déjà été dit, les programmes d'échecs ne sont pas aussi malins, et de loin, que l'on pourrait le supposer, c'est pourquoi je ne surprendrais personne, j'espère, en affirmant que les suites de coups ci-dessus sont d'abord totalement différentes pour un programme et lors du traitement toutes les suites de coups sont évaluées indépendamment. Il effectue donc le quadruple du travail nécessaire!
 
Cette particularité extrêmement peu satisfaisante a été mise en évidence très tôt par les programmeurs de logiciels d'échecs et les a bien sûr dérangés. Ils se sont mis en quête de solutions et ont découvert une réponse à ce problème par l'emploi des Hashtables. Les Hashtables sont donc essentiellement utilisées dans les échecs électroniques pour reconnaître de telles inversions de coups en enregistrant les positions déjà évaluées pour économiser par leur entremise du temps de traitement. D'où aussi, l'appellation "tableaux d'inversion de coups".
 

La chose n'est quand même pas tout à fait aussi simple. Il reste à solutionner deux problèmes. La mémoire vive des ordinateurs actuels est déjà très grandes, mais de loin pas assez pour enregistrer toutes les positions apparaissant et de pouvoir les lire au besoin. De plus les Hashtables existent depuis longtemps, même lorsque la mémoire vive était rare et chère. Comment arrive-t-on à reconnaître malgré tout les inversions de coups comme ci-dessus?
 
Le problème suivant est alors comment les reconnaître rapidement et efficacement, car si cela dure trop longtemps, il serait plus judicieux d'essayer toutes les possibilités séparément. Heureusement, il existe en informatique des procédures standards, soit dans ce cas les Hashtables. Le truc est d'attribuer à chaque position un code, par l'intermédiaire duquel, il est rapide de reconnaître plus tard si la position se répète. Dans mon programme d'échecs Shredder 5 la position initiale est par ex. codée par le nombre 64-bits 0x7623EEBC5FD42FDA.
 
Un humain ne peut rien en faire, mais pour un ordinateur ceci n'est pas un problème, il peut en une fraction de seconde comparer des milliers de tels chiffres entre eux. Pour le deuxième problème de l'efficacité, il existe une solution qui serait néanmoins trop longue à exposer clairement ici. Il suffit de savoir qu'il est possible très rapidement de calculer un nombre pour une position comme celle ci-dessus.
 

Comment procède-t-on en tant que programmeur d'échecs? Pour chaque position évaluée, on enregistre la valeur de la position avec son code dans les Hashtables. Avant chaque examen d'une nouvelle position on vérifie simplement dans les Hashtables si la position a déjà reçu une évaluation et si oui, on prend simplement cette valeur et c'est fini. En principe c'est tout, mais il reste deux problèmes à prendre en compte.
 
Nous savons qu'il existe plus de positions que celles qui sont stockables dans la mémoire vive et aussi beaucoup plus de positions que celles que l'on peut représenter dans un nombre 64-bits. Que se passe-t-il si la mémoire vive est saturée ou sui deux positions sont représentées par le même nombre? La dernière éventualité est forcément plus fréquente car il y a beaucoup plus de positions que de codes disponibles.
 
Le premier problème est assez facile à résoudre. Si la mémoire est pleine, il faut supprimer une entrée pour faire de la place. On procède naturellement en effaçant une entrée qui sera probablement plus utilisée. Par contre si on se trompe et si l'entrée qui vient d'être effacée est à nouveau nécessaire plus tard, on doit le recalculer et on ne pas simplement lire sa valeur. On ne peut pas tout avoir.
 
Le deuxième problème est de premier abord plus délicat. Dans le cas où on a deux numéros de code, et qu'ils sont identiques, on ne peut pas être certain à cent pour cent que les deux positions correspondantes le sont aussi, c'est à dire que l'on n'est pas sûr que la position en cours a effectivement déjà été analysée quand on trouve le même code dans les Hashtables.
 
Quand deux positions différentes sont stockées avec le même code, on parle de collision de Hash. Collisions de Hash semblent violentes, mais ne le sont pas réellement. Si on choisit avec soin la fonction qui attribue un code à une position donnée on peut presque exclure les collisions de Hash. Néanmoins, seulement presque, car un risque à la marge subsiste. Si une collision de Hash survient effectivement, elle est la plupart du temps anodine car la probabilité  qu'elle apparaisse dans une variante secondaire est très, très grande. Comme nous l'avons vu 99.99% des variantes calculées par un programme d'échecs sont inintéressantes.
 
Si une collision intervient quand même dans une variante importante et sensée, des problèmes peuvent en découler. Supposons que vous savez qu'une position avec une Dame et une Tour de mieux est très, très bonne et brusquement vous reprenez cette valeur tout à coup pour une autre position où la partie adverse possède un Cavalier de plus.
 
Si, maintenant, vous pensez que le jeu avec un programme d'échecs est le produit du hasard et ne produit de résultats intéressants qu'avec beaucoup de chance et sans collisions, alors je peux vous rassurer, dans ma carrière e programmeur d'échecs aucune collision de Hash n'est intervenue à ma connaissance. Les collisions de Hash sont par contre une très bonne excuse pour le programmeur en cas de coups particulièrement stupides de leur programme que l'on ne peut jamais avoir programmé aussi mal. Citation: "Je n'y peux rien, il doit s'agir d'une collision de Hash."
 

Dans tous les programmes d'échecs on peut paramétrer la taille des Hashtables, c'est à dire que l'on fixe combien de mémoire vive sera réservée aux Hashtables. Bien sûr se pose la question quelle est la valeur optimale. En règle générale, on peut déjà affirmer qu'il ne faut, dans aucun cas, régler les Hashtables plus grand que la mémoire vive libre à disposition. Cela est faisable sans problème dans un système d'exploitation moderne comme Windows, car Windows stocke la mémoire non nécessaire sur le disque dur. On appelle cela "swapper".
 
Les Hashtables sont toujours indispensables dans la mémoire, ainsi Windows ne sait plus quoi faire pour finalement copier continuellement les Hashtables entre la mémoire et le disque dur. On le constate par le grattement sauvage et continu sur le disque dur et un programme au comportement de plus en plus lent. Ceci est à éviter à tout prix, car le programme d'échecs, comme le reste sur l'ordinateur, est ralenti à l'extrême.
 
Si la taille des Hashtables est trop petite, il n'y a pas assez de place pour les positions examinées et d'anciens éléments qui pourraient être éventuellement utilisés plus tard doivent être effacés. On se rend compte aussi que que la taille optimale des Hashtables dépend aussi du temps de réflexion, donc du niveau de jeu sélectionné, car plus un programme calcule, plus de données doivent être stockées.
 
Ceci semble très compliqué, mais le travail est en règle générale pris en compte, en ce que le programme utilise de façon optimale la mémoire mise à disposition. On peut ainsi, dans mon programme Shredder, régler la taille les Hashtables aussi grande que possible sans que le programme ne risque un désavantage.
 
La mémoire vive effectivement disponible ne doit bien sûr pas être dépassée. Si on ne veut jouer que des Blitz, cela ne servira pas à grand chose de faire l'achat de 128 Mo de RAM, et de fournir 200 Mo au lieu de 100 Mo à Shredder. Celui qui veut procéder ainsi qu'il le fasse, cela ne gêne en rien et pour l'analyse cela peut être utile plus tard.
 

Maintenant que vous savez ce que sont des Hashtables et quelle taille doit leur être attribuée, se pose la question de leur efficacité. Il devrait être établi que plus un programme regarde loin en avant, plus le nombre d'inversion de coups possibles augmente. Comme en finale, il y a moyen de possibilités de coups à jouer qu'en milieu de jeu ou dans l'ouverture, et que le programme peut ainsi voir plus loin, les Hashtables sont bien plus utiles en finale. L'exemple type pour l'utilité des Hashtables est la position suivante:
 
comme les pions sont bloqués, seuls les Rois peuvent jouer pour le moment, il en résulte un nombre considérable d'inversions de coups possibles. Le coup candidat 1.Rb1, sans l'aide des Hashtables, ne sera pas trouvé ou seulement au bout de quelques jours de calcul sur un ordinateur rapide. Avec les Hashtables, la chose se présente différemment. Au bout de quelques secondes, l'ordinateur indique que 1.Rb1 peut amener un avantage gagnant aux Blancs. Ceci est bien sûr un exemple extrême, un tel gain ne peut pas être atteint dans tous les positions, mais également en milieu de partie avec beaucoup de pièces sur l'échiquier, les Hashtables sont d'une grande aide dont on ne veut plus se passer, une fois qu'elle est implémenté dans son programme.

Stefan Meyer-Kahlen – www.shredderchess.de – www.shredderchess.com