Le Fou numérique

 
Ces derniers, on parle beaucoup des Tablebases: Quel programme peut les utiliser et lequel ne le peut pas, ce qu'elles apportent, où on peut les acheter. Je ne me souviens par contre pas d'un article où est décrit ce que sont effectivement les Tablebases. Je voudrais rattraper ceci ici et expliquer aux intéressés cette très utile invention.
 
Les Tablebases sont en principe un très grandes bases de données où sont stockées toutes les positions possibles. Avec la position, on enregistre aussi une valeur qui indique si la position est gagnante, perdante ou nulle. Cela ne veut pas dire qu'il y est indiqué la position est "probablement nulle" ou "gagnante éventuellement", mais le nombre exact de coups jusqu'au mat est indiqué si la position n'est pas nulle. Si dans la base de données est écrit " Gagnant en 13coups", même le meilleur joueur d'échecs ne pourra plus arriver à tenir la nulle. De la même manière, personne ne pourra gagner une position si la valeur dans la base de données est équivalente à une nulle.
 
Ces déclarations ne sont bien sûr pas valables si un des joueurs ne dispose pas des informations de la base de données. Il est alors possible et cela arrive très fréquemment qu'une position théoriquement gagnante ne mène qu'à une nulle. Si un joueur ou un programmes d'échecs peut interroger les Tablebases lorsqu'il a le trait, il n'y aura plus d'échappatoire. La partie est poursuivie parfaitement jusqu'au mat.
 
Bien sûr, maintenant se posent les questions pourquoi tant de joueurs d'échecs investissent autant de temps et d'ardeur dans l'analyse d'une position et pourquoi il y a des gens comme moi qui essaient d'apprendre à jouer aux échecs à une machine, si tout est aussi simple. Un coup d'œil dans la base de données et on sait de suite quel côté va gagner ou s'il y a quand même nulle. Ceci est théoriquement possible, mais le hic de la chose est que ces bases de données sont très, très grandes et qu'il faut un temps considérable pour les générer.
 
Prenons par exemple toutes les positions avec respectivement les Rois, et une autre pièce. Il y a trois pièces sur l'échiquier, on dit un 3-pièces. Pour enregistrer cette base en totalité, il faut env. 62ko. Ceci n'est plus grand chose quand on sait que les ordinateurs à bas prix sont vendus avec un disque dur de 8Go (1Go = 1024Mo = 1021 x 1024ko).
 
Je me souviens encore très bien de mon premier ordinateur: il avait 64Ko de mémoire, mais dedans il y avait aussi le système d'exploitation au complet; les temps changent. Allons un pas plus loin et observons les 4-pièces, il ne reste que le Roi et une autre pièce de chaque côté. Pour enregistrer cette base de données au complet sur le disque dur il faut 30320ko ou env. 30Mo, toujours pas une grande masse mais déjà nettement plus que pour seulement trois pièces.
 

Pour ces positions, le résultat de la partie est aussi clair sans bases de données de finales, et chaque joueur, ayant dépassé le stade du débutant absolu, peut faire mat avec le Roi et la Dame, et la finale Dame contre Tour, même si déjà plus ardue, peut être gagnée sans l'aide de bases de données. Cela devient vraiment intéressant avec cinq pièces.
 
Ici existent quelques exemples pour lesquels il est déjà très difficile d'évaluer correctement la position. Comme exemple je citerai seulement RTp-RT ou RDp-RD, qui sont assez fréquentes dans la pratique des tournois. Le côté ayant l'avantage matériel peut ne pas forcément toujours gagner, et si la position est gagnante, alors elle est généralement très difficile et exige souvent des coups très précis pour transformer l'avantage en victoire.
 
De combien de place sur le disque dur a-t-on besoin pour toutes les Tablebases qui contiennent toutes les combinaisons possibles de cinq pièces? Il faut env. 6054466Ko = env. 6000Mo = env. 6Go, soit dix CD-Rom bien remplis! Il devient évident que la taille de mémoire physique nécessaire augmente de façon exponentielle quand on ne veut que lire les bases de données avec une seule pièce de plus.
 
Ceci est aussi la raison pour laquelle à ce jour on s'est arrêté aux 5-pièces, la taille de sauvegarde devient simplement trop importante pour enregistrer toutes les positions. Il existe déjà quelque 6-pièces comme bases de finales, mais d'ici que toutes les combinaisons avec six pièces soient disponibles comme Tablebases et que chacun puisse les avoir sur son ordinateur, il va sûrement encore se passer un peu de temps.
 

On peut bien sûr jouer avec l'idée de se demander quand nous aurons enfin générer toutes les 32-pièces au complet. Ceci voudrait dire que que les échecs sont résolus comme on l'appelle si joliment en informatique dans le domaine de la théorie des jeux. On pourrait ainsi, pour n'importe quelle position d'échecs, dire si elle est nulle ou si un côté va gagner et dans ce cas  combien de coups restent jusqu'au mat.
 
En particulier on saura aussi si les Blancs peuvent profiter pleinement de la priorité du trait à partir de la position initiale ou, si avec un jeu parfait des deux côtés on arrive toujours à une nulle, ou même si la priorité du trait est un désavantage et que les Noirs ont un avantage décisif dès la position initiale.
 
Ce point est vraiment idéal pour se chamailler et discuter, tout en glissant facilement vers des discussions philosophiques. Le problème est que le nombre des positions possibles aux échecs est plus grand que celui des atomes de l'univers connu. Avec les connaissances actuelles il est donc impossible de stocker toutes les positions. La question comment évaluer toutes les positions, on  n'est même pas obliger de l'aborder dans l'argumentation.
 
Un point de départ sensé dans une discussion serait naturellement de se poser les questions si on connaît effectivement le nombre d'atomes dans l'univers, comment coder peut-être plus efficacement toutes les positions d'échecs et s'il est possible de considérer l'univers comme un chose finie. On échoue rapidement dans les "univers parallèles" et parmi les "trous noirs". Comme vous pouvez voir ce point contient un potentiel de discussion important qui nous amènerait loin du cadre de cet article.
 
Il n'est d'ailleurs pas inhabituel qu'un jeu soit résolu, c'est à dire qu'il a été complètement calculé. Ceci a déjà été réalisé depuis un moment pour les jeux très simples en comparaison des échecs comme "Quatre gagne" ou la "marelle". Pour "quatre gagne" le jouer qui a le trait en premier peut toujours forcer le gain, la "marelle" est toujours nulle si les deux joueurs ne commettent pas d'erreurs.
 

Intéressons nous à présent à la manière d'obtenir les Tablebases utilisables aujourd'hui. Il existe deux possibilités. Ou on se les procure toutes faites ou on les génère soi-même sur son ordinateur. Les deux ont leur inconvénients. Sur Internet, il existent des sites qui proposent les Tablebases complètes au téléchargement, on se connecte sur le serveur correspondant et c'est parti!
 
Mai attention, faisons un petit calcul. Combien de temps cela va durer? 6Go pour toutes les 5-pièces avec un modem V90 usuel actuellement, ceci fait avec une bonne connexion dans le cas optimal 6Go à 3500ko/s = 1840700 secondes = env. 30678 minutes = env. 551 heures = env. 21 jours = 3 semaines , non-stop! Je ne veux même pas évoquer les l'état du réseau ou les déconnexions intempestives. Chacun peut calculer soi-même comment cette possibilité va peser sur sa prochaine, et probablement la suivante, facture téléphonique. Vous voyez que ce n'est guère recommandable.
 
J'ai procédé moi-même à ces calculs au printemps de cette année quand je me suis décidé  à faire participer Shredder, avec le soutien de Tablebases, aux Championnats du Monde à Paderborn . Que faire ? J'ai trouvé rapidement sur Internet un petit programme qui peut générer toutes les Tablebases sur son propre ordinateur. Il y avait une petite remarque dans la documentation jointe qui indiquait qu'il fallait pour le calcul des 5-pièces beaucoup de mémoire et également beaucoup de temps, mais je me disais que mon ordinateur, un  PII-450 avec 128Mo de RAM, serait assez rapide.
 
Pour démarrer, je commençais par la génération des 3-pièces. Ceci a été réglé très, très vite et pour continuer on pouvait passer aux 4-pièces. Là, il a fallu deux bonnes heures pour obtenir toutes les bases de données au complet, mais mes problèmes ne faisaient que vraiment commencer. Je commençais avec RFF-RC et toutes les autres finales avec des figures légères. Pour ces finales, il a déjà fallu 1 à 2 jours pour être générées complètement et je commençais à douter de mon entreprise.
 
Il fallait plus de mémoire donc j'investis dans une barrette supplémentaire de 128Mo, heureusement à l'époque pour un prix abordable. Mais même avec 256Mo de mémoire vive, j'atteignis rapidement les limites de mon ordinateur. Je pouvais encore calculer quelques finales, mais dès les finales contenant au moins un pion ce fut définitivement la fin. Je me décidais à chercher une autre méthode pour recevoir les Tablebases et me consolais que, avec la nouvelle mémoire achetée, je pourrai désormais utiliser de plus grosses Hashtables dans Shredder.
 
Il ne restait plus que la solution d'acheter quelque part les Tablebases prêtes à l'emploi. En Allemagne, je ne fus pas chanceux, officiellement elles n'existaient nulle part. Je mis néanmoins la main sur un fan des échecs électroniques américain qui avait effectivement télécharger toutes les 5-pièces depuis Internet avec son modem. D'après ses propres dires, il lui a fallu 1,5 mois en continu, ceci n'est sûrement vraiment possible qu'en Amérique. Nous avons réussi à nous mettre d'accord assez rapidement et il me promit de me graver les CD aussi rapidement que possible et de me les envoyer. Effectivement quelques jours plus tard, j'avais le paquet dans ma boîte à lettres.
 

Après toutes ces péripéties, j'étais donc très impatient de voir ce que la nouvelle arme ultime apporterait dans Shredder. J'ai essayé quelques positions de finales avec peu de pièces, et là, les bonnes solutions ont généralement été trouvées plus vite par Shredder avec les Tablebases. J'ai rapidement démarrer quelques parties d'essai et, ici aussi, une nette amélioration. Entre autres, les finales de Tour avec un pion de plus ont été le plus souvent gagnées et avec un pion de moins la nulle a été le plus souvent été sauvée.
 
J'étais enthousiaste. Mais rapidement, le désavantage des Tablebases m'est apparu aussi. en raison de leur taille, il est impossible de les charger complètement dans la mémoire vive de l'ordinateur. Elles devaient rester sur le relativement plus lent disque dur. Mais un facteur très important dans les échecs électroniques est la vitesse et l'efficacité d'un programme. En finales,  surtout avec très peu de pièces, il est très fréquent de rencontrer lans l'arbre de recherche, par exemple lors d'une longue suite de prises, une position avec cinq ou moins de pièces à évaluer.
 
S'il faut faire un accès sur le disque dur plus lent, le programme est freiné et perd nettement en vitesse de calcul, ce qui peut avoir des conséquences fatales. Dans le pire des cas, il n'y a plus que des accès au disque dur et il ne reste plus assez de temps pour vérifier les variantes importantes. Mais ce problème est solvable par l'emploi d'algorithmes intelligents pour qu'au final l'avantage des Tablebases est de loin prépondérant.
 
Actuellement, il est nettement plus facile d'accéder aux Tablebases. Toutes les 5-pièces sont livrées entre autre avec Shredder 5 et pour les 5-pièces, il y a des possibilités de livraison entre temps en Allemagne. Ceci est une des meilleures manières de recevoir les Tablebases.
 
Certains vont se demander pourquoi les Tablebases sont apparues aussi tardivement si elles sont aussi utiles. Une raison est sûrement que la taille des disques durs n'a augmentée que récemment à un niveau pour pouvoir les utiliser. D'un autre côté, il faut aussi dire que les bases de données de finales sont disponibles depuis longtemps.
 
Les formats précédents étaient néanmoins soit d'accès très rapide sur les base de données mais nécessitaient beaucoup de place sur le disque dur (bases de données d'Edwards), soit tellement comprimés donc l'accès était très long pour pouvoir les utiliser efficacement dans la recherche (bases de données de Thompson). Ce n'est qu'avec les bases de donnes de Nalimov qu'un grand pas en avant a été réalisé. Elles sont réduites à une taille raisonnable par un algorithme de compression très efficace et permettent quand même un accès rapide.
 
En conclusion je voudrais encore indiquer deux exemples issus de la pratique du Championnat du Monde à Paderborn, dans lesquels l'avantage et la force des bases de données de finale sont mis en évidence. Dans la première partie il est montré que des finales difficiles à jouer, qui contiennent des possibilités de nulle, peuvent être gagnées sans problème quand on peut bénéficier de l'aide de bases de données de finales.
 

1.d4 d5 2.c4 c6 3.Cf3 Cf6 4.Dc2 dxc4 5.Dxc4 Ff5 6.g3 e6 7.Fg2 Cbd7 8.Cc3 Fe7 9.0-0 0-0 10.Te1 Ce4 11.e3 Te8 12.Cd2 Cd6 13.De2 e5 14.d5 cxd5 15.Cxd5 Tc8 16.e4 Fe6 17.Cxe7+ Dxe7 18.b3 Tc2 19.Fa3 Tec8 20.Tec1 Txc1+ 21.Txc1 Txc1+ 22.Fxc1 Dd8 23.Fa3 Db6 24.Ff1 Cc5 25.Fb2 f6 26.De3 Ccxe4 27.Cxe4 Dxe3 28.Cxf6+ gxf6 29.fxe3 Ce4 30.Fe2 Rf7 31.Fd3 Fd5 32.g4 Rg6 33.h4 f5 34.Fe2 Rf6 35.g5+ Re6 36.Rh2 a5 37.Rg1 a4 38.bxa4 Fxa2 39.a5 Fd5 40.Fa3 Cc3 41.Fh5 Fc6 42.g6 hxg6 43.Fxg6 Cd5 44.h5 Rf6 45.Fc5 Cc3 46.Rf1 Ff3 47.Fb6 Fg4 48.Fd8+ Rg7 49.Fc7 Rf6 50.Rg2 Cd5 51.Fd8+ Rg7 52.Rg3 Cxe3 53.Rh4 Cd5 54.Rg5 Fh3 55.h6+ Rg8 56.Fe8 Cf4 57.Fd7 Fg4 58.Fc8 Rh7 59.Fc7 Ch3+ 60.Rf6 Cf2 61.Fxb7 Ce4+ 62.Rxe5 Fe2 63.a6 Fxa6
 
Au coup suivant Shredder annonce un mat en 31 coups! Sans l'aide des bases de données de finales, ce serait absolument impossible. On aboutit à une finale RFF-RC qui serait éventuellement difficile à gagner en 50 coups. Avec l'aide des bases de données, ce n'est plus un obstacle pour Shredder, le chemin vers le mat est déjà indiqué en totalité. 64.Fxa6 Rg6 65.h7 Rxh7 66.Rxf5 Cc5 67.Fc4 Cd7 68.Fb5 Cc5 69.Fb6 1-0
 
La deuxième partie est un très bel exemple que les programmes d'échecs avec l'aide des Tablebases peuvent être supérieures dans certaines positions de finale aux Grands-Maîtres même si la finale est encore le talon d'Achille des programmes d'échecs actuels.
 

1.e4 e5 2.Cf3 Cc6 3.Fc4 Fc5 4.b4 Fxb4 5.c3 Fa5 6.d4 exd4 7.0-0 Cge7 8.cxd4 d5 9.exd5 Cxd5 10.Fa3 Fe6 11.Fb5 Fb4 12.Fxc6+ bxc6 13.Fxb4 Cxb4 14.Da4 Dd6 15.Cc3 Cd3 16.d5 Cc5 17.Dxc6+ Dxc6 18.dxc6 Re7 19.Tfe1 Cd3 20.Te3 Cb4 21.Cd4 Thd8 22.Td1 Rf6 23.a3 Cd5 24.Ce4+ Re7 25.Tee1 Fg4 26.f3 Fc8 27.Cc5+ Rf6 28.Cb5 Fe6 29.Ca6 Tac8 30.Cbxc7 h5 31.h3 h4 32.a4 Cxc7 33.Txd8 Txd8 34.Cxc7 Tc8 35.Cxe6 fxe6 36.Tc1 e5 37.Rf2 Re6 38.g3 hxg3+ 39.Rxg3 Rd6 40.Td1+ Re6 41.Td7 Txc6 42.Txg7 Tc3 43.Tg4 Rf5 44.h4 Tc1 45.h5 Tc6 46.Tg7 Ta6 47.Tg4 Tc6 48.Tg7 Ta6 49.Tg8 Tb6 50.Rh4 Tb4+ 51.Rg3 Tb6 52.Rh4 Tb4+ 53.Tg4 Tb2 54.Rg3 Tb6 55.a5Td6 56.Tg7 Ta6 57.Tg8 Td6 58.Rh4 Td4+ 59.Rg3 Td6 60.Tb8 Rg5 61.Te8 Td5 62.a6 Ta5 63.Te7 e4 64.Txa7 Ta3 65.Rf2 Txf3+ 66.Re2 Rxh5
 

Dans cette position les deux GM présents, Boris Altermann et Thomas Luther, ne donnaient aucune chance aux Noirs. Pour les deux il est clair que les Blancs peuvent facilement gagner cette finale. Mais les deux programmes disposent des Tablebases et indiquent en toute quiétude à ce moment et plus tard une évaluation nulle, ce qui se vérifiera plus tard à l'analyse. 67.Ta8 Tf7 68.Re3 Te7 69.Tb8 Rg6 70.Tb6+ Rf5 et ½-½

Que peux-t-on conclure sur les Tablebases? Si on évite les quelques écueils lors de l'implantation, on dispose d'un très puissant moyen d'améliorer très nettement le comportement d'un programme d'échecs dans certaines positions. Ceci a été reconnu par la plupart des auteurs e programmes d'échecs. Beaucoup de nouveaux programmes, naturellement aussi Shredder 4, utilise le nouveau format de Tablebases.

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