Table de finale

Une table de finale (en anglais : endgame tablebase) est une base de données informatisée qui contient une analyse exhaustive et précalculée des positions de fins de partie du jeu d'échecs. Elle est généralement utilisé par un moteur d'échecs informatique pendant le jeu, ou par un humain ou un ordinateur qui analyse rétrospectivement une partie qui a déjà été jouée.

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Les Blancs jouent et font mat en 102 coups

La table de finale contient des positions de finales et leur évaluation (partie nulle, ou distance jusqu'au mat). Ainsi, on peut chercher à atteindre une position donnée ou à l'éviter. Les moteurs d'échecs (programmes d'échecs, comme Stockfish) peuvent s'en servir pour assurer leurs fins de parties avec le meilleur résultat possible.

De telles bases de données de finales sont générées en utilisant une forme d'analyse rétrograde : les positions de trois pièces sont utilisées pour l'analyse des positions de quatre pièces, ces dernières participent à la génération de celles de cinq pièces, etc.

Tables de finales disponibles

Une interface typique pour interroger une table de finale.

Ken Thompson, peut-être plus connu comme concepteur clé du système d'exploitation UNIX, est un pionnier en ce domaine^[1] ; au fil du temps, d'autres formats ont vu le jour, comme les tablebases de Steven J. Edwards, la De Koning Endgame Database (2002) et les Tablebases d'Eugene Nalimov (en). On a ainsi les tables suivantes :

Thompson : renvoient la distance à la promotion sans évaluation (gain, nulle ou défaite). Elles sont difficilement utilisables compressées.
Edwards : renvoient la distance au mat. Elles sont volumineuses.
Nalimov : renvoient la distance au mat. Elles sont utilisables car compressées.

Les tables de Nalimov sont les plus répandues. Étant libres, la plupart des programmes les utilisent : Crafty, Shredder, Fritz, etc. La prise en passant est considérée mais par contre, le roque et la règle des cinquante coups^[2] sont ignorés.

En 2012, les finales de sept pièces et moins ont été calculées par le département de science informatique de l'université de Moscou, sur un ordinateur appelé Lomonosov (en russe ломоносов). C'est pourquoi elles sont appelées « Tables de Lomonosov »^[3]^{[réf. souhaitée]}.

Toutefois, le jeu d'échecs peut difficilement être « résolu » par ce biais, le nombre total des positions légales du jeu d'échecs étant estimé à $1{,}8\cdot 10^{46}$ ^[4]^,^[5].

Mémoires de stockage

Jusqu'à 5 pièces : 938,39 Mo (Syzygy Endgame Tablebases)^{[réf. souhaitée]}.
Jusqu'à 6 pièces : 1 153 Go^[6].
Jusqu'à 7 pièces : 140 To (Lomonosov Tablebases), 1 To (Syzygy Endgame Tablebases)^{[réf. souhaitée]}.

Exemple d'utilisation en 1999

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

G. Kasparov - Reste du monde,
Internet, 1999
Les Noirs jouent et perdent la partie.

Article détaillé : Kasparov contre le monde.

Les bases de données de finales se firent connaître en 1999, lorsque le grand maître et champion du monde d'échecs Garry Kasparov joua une partie contre le « reste du monde » en consultation sur Internet^{[réf. souhaitée]}.

L'analyse de Kasparov conclut à un gain inévitable des Blancs (donc lui), comme le démontrèrent les tables de Nalimov après le 58^e coup des Blancs (58. g6) : avec un jeu parfait, les Noirs perdent en 79 coups, tout en respectant la règle des 50 coups^{[réf. souhaitée]}.

Logiciels d'étude de finale

Freezer (Eiko Bleicher)
Shredder classic : Oracle et Jocker analyse
FinalGen (générateur de bases de finale)
Hoffman

Notes et références

↑ Tristan Cazenave, Intelligence artificielle : une approche ludique, Ellipses, 2011 (ISBN 978-2-7298-6408-8), chap. 7 (« Bases de données de finales »).
↑ Ce site référence les plus longs mats calculés à partir des tablebases, par exemple un mat en 517 coups qui contrevient à règle des cinquante coups puisqu'il n'y a que cinq pièces et aucun pion sur l'échiquier.
↑ « Lomonosov tablebases », sur chessok.com (consulté le 30 juin 2023).

↑

code source C++ à améliorer

/* Rois oubliés */

include <QCoreApplication>
include <stdio.h>
include <math.h>
define MAX 8694

/*

1. RESULTATS

Le résultat obtenu avec le programme ci-dessous donne :

 Il y a 4,152.10^46 positions (légales ou non).\n"
 Il y a 3,961.10^42 positions (légales ou non) avec au maximum, pour chaque camp, 9 dames, 2 tours, 2 fous, 2 cavaliers.\n"
 Il y a 4,941.10^39 positions (légales ou non) avec au maximum, pour chaque camp, 2 dames, 2 tours, 2 fous, 2 cavaliers.\n"
 Il y a 1,198.10^38 positions (légales ou non) avec au maximum, pour chaque camp, 1 dame , 2 tours, 2 fous, 2 cavaliers.\n"

Ce nombre est partiellement sous-estimé en raison d'autres positions légales :

 1. d'une multiplication de certaines positions par 16 maximum si on tient compte des roques éventuels
 2. d'une multiplication de certaines positions par 6  maximum si on tient compte de la prise en passant
 3. de la différence entre 2 positions qui n'auraient pas le même passé si on tient compte de la règle des 3 positions identiques
 4. de la différence entre 2 positions qui n'auraient pas le même passé si on tient compte de la règle des 50 coups

Ce nombre est partiellement sur-estimé en raison des positions illégales :

 1. le camp ayant le trait ne peut pas capturer un roi
 2. le camp ayant le trait ne doit pas avoir son roi attaqué 3 fois, ni parfois 2 fois
 3. il est impossible que les pions se soient déplacées d'une certaine façon indépendamment des pièces adverses
 4. il est impossible que les pions se soient déplacées d'une certaine façon compte tenu du nombre de pièces adverses restantes sur l'échiquier
 5. certaines pièces ne peuvent être placée là (Fa1 avec Pb2)
 6. les cavaliers ne sont pas sur la bonne couleur (exemple : la position de départ avec trait aux Noirs est illégale)

La sous-estimation est très faible si on tient compte du roque et de la prise en passant seulement. La sur-estimation est moyenne.

2. SOURCES

Les sources internet sont :

- Résultat : https://fr.wikipedia.org/wiki/Nombre_de_Shannon
- Calcul   : http://m3www.gonze.org/wikiPG/index.php/Nombre_de_positions_l%C3%A9gales_au_jeu_d%27%C3%A9checs

Le nombre de positions légales possibles est estimé à environ :

- 7,7.10^45 (John Tromp)
- 1,8.10^46 (Shirish Chinchalkar)
- 4,8.10^44 (Wikipedia : https://tromp.github.io/chess/chess.html)

Toutefois, mes chiffres correspondent avec ceux de Shirish Chinchalkar.

3. RESUME

Le nombre de positions légales possibles est estimé à environ :

- 200.10^44 (moi)                 ( 100 %)
- 180.10^44 (Shirish Chinchalkar) (  43 %)
-  77.10^44 (John Tromp)          (  19 %)
- 4,8.10^44 (Wikipedia)           (1,15 %)

/

int main(int argc, char *argv[]) {

 QCoreApplication a(argc, argv);

 double    fact[64];
 double    cnp [64][64];
 int       D,d, T,t, F,f, C,c, P,p, n, i, j, cnt = 0, terrestrial;
 int       legal[10][11][11][11][9];  /* Nombre de D x T x F x C x P : [0;9] x [0;10] x [0;10] x [0;10] x [0;8] ; Cardinal : 10 x 11 x 11 x 11 x 9 = 119.790 */
 int       index[MAX][5];             /* [8.694] x [D, T, F, C, P] */
 double    element,                   /* Nombre de positions (légales ou non) lorsque les nombres de D, d, T, t, F, f, C, c, P et p sont fixés */
           total  = 0,                /* Total des éléments de cross[MAX][MAX] */
           total9 = 0,                /* Total des éléments de cross[MAX][MAX] avec 9 dames maximum, mais ni plus de 2 tours, ni plus de 2 fous, ni plus de 2 cavaliers */
           total2 = 0,                /* Total des éléments de cross[MAX][MAX] avec 2 dames maximum, mais ni plus de 2 tours, ni plus de 2 fous, ni plus de 2 cavaliers */
           total1 = 0;                /* Total des éléments de cross[MAX][MAX] avec 1 dame  maximum, mais ni plus de 2 tours, ni plus de 2 fous, ni plus de 2 cavaliers */

 for (n = 0 ; n < 64 ; ++n)
 {
   fact[n] = n ? n*fact[n-1] : 1.;
   for (p = 0 ; p <= n ; ++p)
     cnp[n][p] = fact[n]/fact[p]/fact[n-p];
 }

 for (D = 0 ; D < 10 ; ++D)
 for (T = 0 ; T < 11 ; ++T)
 for (F = 0 ; F < 11 ; ++F)
 for (C = 0 ; C < 11 ; ++C)
 for (P = 0 ; P <  9 ; ++P)
   if ((legal[D][T][F][C][P] =   (D-1 <0?0: D-1)
                               + (T-2 <0?0: T-2)
                               + (F-2 <0?0: F-2)
                               + (C-2 <0?0: C-2) <= 8-P))
   {
     index[cnt][0] = D;
     index[cnt][1] = T;
     index[cnt][2] = F;
     index[cnt][3] = C;
     index[cnt][4] = P;
     ++cnt;
   }
 printf("Pour chaque camp, il y a %d ensembles legaux sur 119.790.\n\n",cnt);  /* cnt = MAX = 8.694 et cnt^2 = 75.585.636 */

 for (i = 0 ; i < MAX ; ++i)
 for (j = 0 ; j < MAX ; ++j)
 {
   D = index[i][0]; d = index[j][0];
   T = index[i][1]; t = index[j][1];
   F = index[i][2]; f = index[j][2];
   C = index[i][3]; c = index[j][3];
   P = index[i][4]; p = index[j][4];
   total += element = 2 * cnp[48]                  [P]
                        * cnp[48-P]                [p]
                        * cnp[64-P-p]              [D]
                        * cnp[64-P-p-D]            [d]
                        * cnp[64-P-p-D-d]          [T]
                        * cnp[64-P-p-D-d-T]        [t]
                        * cnp[64-P-p-D-d-T-t]      [F]
                        * cnp[64-P-p-D-d-T-t-F]    [f]
                        * cnp[64-P-p-D-d-T-t-F-f]  [C]
                        * cnp[64-P-p-D-d-T-t-F-f-C][c];
   if ((terrestrial = T<=2 && t<=2 && F<=2 && f<=2 && C<=2 && c<=2                )) total9 += element;
   if ( terrestrial                                                && D<=2 && d<=2 ) total2 += element;
   if ( terrestrial                                                && D<=1 && d<=1 ) total1 += element;
 }
 printf("Le nombre de positions (legales ou non) de chaque element du tableau a ete calcule.\n"
        "Il y avait %d x %d = %d elements dans le tableau.\n\n",cnt, cnt, cnt*cnt);
 printf("Il y a %g positions (legales ou non).\n"
        "Il y a %g positions (legales ou non) avec au maximum, pour chaque camp, 9 dames, 2 tours, 2 fous, 2 cavaliers.\n"
        "Il y a %g positions (legales ou non) avec au maximum, pour chaque camp, 2 dames, 2 tours, 2 fous, 2 cavaliers.\n"
        "Il y a %g positions (legales ou non) avec au maximum, pour chaque camp, 1 dame , 2 tours, 2 fous, 2 cavaliers.\n",
        total,total9,total2,total1);

 return a.exec();

}

↑ Il y a même davantage de positions si on considère que deux positions diffèrent seulement par les positions qui ont été jouées auparavant dans la partie ; en clair : si des coups imprécis ont été joués, la solution qui resterait pour mater peut être telle que le camp faible peut exiger la nulle en raison de la règle des 3 positions identiques ou en raison de la règle des cinquante coups.
↑ Voir la page d'info du site Shredder Chess.

Voir aussi

Article connexe

Liens externes

(en) « Chess Endgame Database » : démonstrateur en ligne des tables de finale de Shredder (6 pièces et moins), sur shredderchess.com
« Tables de Nalimov »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}
Article sur les Tablebases de Nalimov
(en) Article sur les Tablebases de Nalimov

Portail des échecs

[1] Tristan Cazenave, Intelligence artificielle : une approche ludique, Ellipses, 2011 (ISBN 978-2-7298-6408-8), chap. 7 (« Bases de données de finales »).

[2] Ce site référence les plus longs mats calculés à partir des tablebases, par exemple un mat en 517 coups qui contrevient à règle des cinquante coups puisqu'il n'y a que cinq pièces et aucun pion sur l'échiquier.

[3] « Lomonosov tablebases », sur chessok.com (consulté le 30 juin 2023).

[4] 

code source C++ à améliorer

/* Rois oubliés */

include <QCoreApplication>

include <stdio.h>

include <math.h>

define MAX 8694

/*
1. RESULTATS
Le résultat obtenu avec le programme ci-dessous donne :

Il y a 4,152.10^46 positions (légales ou non).\n" Il y a 3,961.10^42 positions (légales ou non) avec au maximum, pour chaque camp, 9 dames, 2 tours, 2 fous, 2 cavaliers.\n" Il y a 4,941.10^39 positions (légales ou non) avec au maximum, pour chaque camp, 2 dames, 2 tours, 2 fous, 2 cavaliers.\n" Il y a 1,198.10^38 positions (légales ou non) avec au maximum, pour chaque camp, 1 dame , 2 tours, 2 fous, 2 cavaliers.\n"

Ce nombre est partiellement sous-estimé en raison d'autres positions légales :

1. d'une multiplication de certaines positions par 16 maximum si on tient compte des roques éventuels 2. d'une multiplication de certaines positions par 6 maximum si on tient compte de la prise en passant 3. de la différence entre 2 positions qui n'auraient pas le même passé si on tient compte de la règle des 3 positions identiques 4. de la différence entre 2 positions qui n'auraient pas le même passé si on tient compte de la règle des 50 coups

Ce nombre est partiellement sur-estimé en raison des positions illégales :

1. le camp ayant le trait ne peut pas capturer un roi 2. le camp ayant le trait ne doit pas avoir son roi attaqué 3 fois, ni parfois 2 fois 3. il est impossible que les pions se soient déplacées d'une certaine façon indépendamment des pièces adverses 4. il est impossible que les pions se soient déplacées d'une certaine façon compte tenu du nombre de pièces adverses restantes sur l'échiquier 5. certaines pièces ne peuvent être placée là (Fa1 avec Pb2) 6. les cavaliers ne sont pas sur la bonne couleur (exemple : la position de départ avec trait aux Noirs est illégale)

La sous-estimation est très faible si on tient compte du roque et de la prise en passant seulement. La sur-estimation est moyenne.
2. SOURCES
Les sources internet sont :

- Résultat : https://fr.wikipedia.org/wiki/Nombre_de_Shannon - Calcul : http://m3www.gonze.org/wikiPG/index.php/Nombre_de_positions_l%C3%A9gales_au_jeu_d%27%C3%A9checs

Le nombre de positions légales possibles est estimé à environ :

- 7,7.10^45 (John Tromp) - 1,8.10^46 (Shirish Chinchalkar) - 4,8.10^44 (Wikipedia : https://tromp.github.io/chess/chess.html)

Toutefois, mes chiffres correspondent avec ceux de Shirish Chinchalkar.
3. RESUME
Le nombre de positions légales possibles est estimé à environ :

- 200.10^44 (moi) ( 100 %) - 180.10^44 (Shirish Chinchalkar) ( 43 %) - 77.10^44 (John Tromp) ( 19 %) - 4,8.10^44 (Wikipedia) (1,15 %)

/

int main(int argc, char *argv[]) {

QCoreApplication a(argc, argv);

double fact[64]; double cnp [64][64]; int D,d, T,t, F,f, C,c, P,p, n, i, j, cnt = 0, terrestrial; int legal[10][11][11][11][9]; /* Nombre de D x T x F x C x P : [0;9] x [0;10] x [0;10] x [0;10] x [0;8] ; Cardinal : 10 x 11 x 11 x 11 x 9 = 119.790 */ int index[MAX][5]; /* [8.694] x [D, T, F, C, P] */ double element, /* Nombre de positions (légales ou non) lorsque les nombres de D, d, T, t, F, f, C, c, P et p sont fixés */ total = 0, /* Total des éléments de cross[MAX][MAX] */ total9 = 0, /* Total des éléments de cross[MAX][MAX] avec 9 dames maximum, mais ni plus de 2 tours, ni plus de 2 fous, ni plus de 2 cavaliers */ total2 = 0, /* Total des éléments de cross[MAX][MAX] avec 2 dames maximum, mais ni plus de 2 tours, ni plus de 2 fous, ni plus de 2 cavaliers */ total1 = 0; /* Total des éléments de cross[MAX][MAX] avec 1 dame maximum, mais ni plus de 2 tours, ni plus de 2 fous, ni plus de 2 cavaliers */

for (n = 0 ; n < 64 ; ++n) { fact[n] = n ? n*fact[n-1] : 1.; for (p = 0 ; p <= n ; ++p) cnp[n][p] = fact[n]/fact[p]/fact[n-p]; }

for (D = 0 ; D < 10 ; ++D) for (T = 0 ; T < 11 ; ++T) for (F = 0 ; F < 11 ; ++F) for (C = 0 ; C < 11 ; ++C) for (P = 0 ; P < 9 ; ++P) if ((legal[D][T][F][C][P] = (D-1 <0?0: D-1) + (T-2 <0?0: T-2) + (F-2 <0?0: F-2) + (C-2 <0?0: C-2) <= 8-P)) { index[cnt][0] = D; index[cnt][1] = T; index[cnt][2] = F; index[cnt][3] = C; index[cnt][4] = P; ++cnt; } printf("Pour chaque camp, il y a %d ensembles legaux sur 119.790.\n\n",cnt); /* cnt = MAX = 8.694 et cnt^2 = 75.585.636 */

for (i = 0 ; i < MAX ; ++i) for (j = 0 ; j < MAX ; ++j) { D = index[i][0]; d = index[j][0]; T = index[i][1]; t = index[j][1]; F = index[i][2]; f = index[j][2]; C = index[i][3]; c = index[j][3]; P = index[i][4]; p = index[j][4]; total += element = 2 * cnp[48] [P] * cnp[48-P] [p] * cnp[64-P-p] [D] * cnp[64-P-p-D] [d] * cnp[64-P-p-D-d] [T] * cnp[64-P-p-D-d-T] [t] * cnp[64-P-p-D-d-T-t] [F] * cnp[64-P-p-D-d-T-t-F] [f] * cnp[64-P-p-D-d-T-t-F-f] [C] * cnp[64-P-p-D-d-T-t-F-f-C][c]; if ((terrestrial = T<=2 && t<=2 && F<=2 && f<=2 && C<=2 && c<=2 )) total9 += element; if ( terrestrial && D<=2 && d<=2 ) total2 += element; if ( terrestrial && D<=1 && d<=1 ) total1 += element; } printf("Le nombre de positions (legales ou non) de chaque element du tableau a ete calcule.\n" "Il y avait %d x %d = %d elements dans le tableau.\n\n",cnt, cnt, cnt*cnt); printf("Il y a %g positions (legales ou non).\n" "Il y a %g positions (legales ou non) avec au maximum, pour chaque camp, 9 dames, 2 tours, 2 fous, 2 cavaliers.\n" "Il y a %g positions (legales ou non) avec au maximum, pour chaque camp, 2 dames, 2 tours, 2 fous, 2 cavaliers.\n" "Il y a %g positions (legales ou non) avec au maximum, pour chaque camp, 1 dame , 2 tours, 2 fous, 2 cavaliers.\n", total,total9,total2,total1);

return a.exec();
}

[5] ude <QCoreApplication>

[6] ude <stdio.h>

[7] ude <math.h>

[8] MAX 8694

[9] /

[5] Il y a même davantage de positions si on considère que deux positions diffèrent seulement par les positions qui ont été jouées auparavant dans la partie ; en clair : si des coups imprécis ont été joués, la solution qui resterait pour mater peut être telle que le camp faible peut exiger la nulle en raison de la règle des 3 positions identiques ou en raison de la règle des cinquante coups.

[6] Voir la page d'info du site Shredder Chess.

[12] ude <QCoreApplication>

[13] ude <stdio.h>

[14] ude <math.h>

[15] MAX 8694

[1]

[2]

[3]

[4]

[5]

[6]