Les notions de
base de
Stefan Meyer-Kahlen
è
Peter Schreiner
Graphique, mise en
page et illustrations repris du site du Schachclub
Leinzell avec l'aimable autorisation de Klaus Schumacher
Traduit de l'Allemand par
Patrick
Buchmann avec l'aimable autorisation de Stefan
Meyer-Kahlen
Le
Système du Suisse
Téléchargement
Les modules
Comment faire...
Les
liens
Plan
simplifié du site
Archives
Le Forum du Fou
|
|
 |
 |
Les Tablebases
de Stefan Meyer-Kahlen - Novembre 1999
|
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.
Les échecs totalement
analysés?
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.
Tablebases, l'arme ultime
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.
Shredder - Rebel
WCCC99 Paderborn (3), 15.06.1999
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.
Ferret - Shredder
WCCC99 Paderborn, 18.06.1999
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.
|
|
|